Probability for high mutual coherence on all subsets of a Gaussian vector set

Question

We examine as set of independent normal vectors: $$ \forall i \in [N]\triangleq \{1,\dots,N\}:\,\mathbf{x}_{i}\sim\mathcal{N}\left(0,\mathbf{I}_{d}\right)$$

For any $\epsilon>0$ and $K\leq N$, we define the event $ \mathcal{A}_{K,\epsilon}$ that the mutual coherence is lower bounded by $\epsilon$ $$ \gamma (S) \triangleq \max_{i,j\in S:\,i\neq j}\frac{\mathbf{x}_{i}^{\top}\mathbf{x}_{j}}{\left\Vert \mathbf{x}_{i}\right\Vert \left\Vert \mathbf{x}_{j}\right\Vert }>\epsilon \,.$$ on any subset $S\subset [N]$ of size $|S|=K$.

Question: I'm looking for as tight as possible upper bound on $P(\mathcal{A}_{K,\epsilon})$, the probability for this event.

So far, the best I could think of was dividing $[N]$ into $\lfloor N/K \rfloor$ different subsets $S_i$ of size $|S_i|=K$, so we can bound $P(\mathcal{A}_{K,\epsilon})\leq \prod_i P \left( \gamma \right(S_i \left) > \epsilon \right) \, .$ Using standard mutual coherence bounds on each subset $S_i$, I get $P(\mathcal{A}_{K,\epsilon}) \leq 2K^{2N/K}\exp\left(-\frac{Nd\epsilon^{2}}{24K}\right) $. However, I was wondering if there is a way to improve the exponential part in this upper bound.

Thanks in advance!

Answer 1

It may be helpful to note that your problem is equivalent to the following question about random geometric graphs, which has been studied before. Let $\mathbf{u}_i=\mathbf{x}_i/\|\mathbf{x}_i\|$ be the normalized vectors, which are uniformly distributed on the sphere $S^{d-1}$. To these $N$ random points, associate a graph $G$ on $N$ vertices which puts an edge at $\{i,j\}$ if $\|\mathbf{u}_i - \mathbf{u}_j\|\le r = \sqrt{2(1-\varepsilon)}$. We seek an upper bound on $\mathbb{P}(\alpha(G)<K)$, where $\alpha(G)$ is the size of the largest independent set in $G$.

Some closely related questions are investigated here: http://84.89.132.1/~lugosi/corrgraphssubmitted.pdf
While they are mostly concerned with the regime where $r=r(d)$ scales so that the probability of drawing an edge $\{i,j\}$ is fixed in the large $N$ limit, you may be able to extract a quantitative bound from their methods.