1
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ Just to clarify, do you mean to write $\max_{i,j\in S:i\ne j}$ rather than $\max_{\forall i,j\in S:i\ne j}$ in the definition of $\gamma(S)$? $\endgroup$
    – Nick Cook
    Nov 21, 2016 at 22:26
  • $\begingroup$ Yep, thanks for catching this typo. $\endgroup$ Nov 22, 2016 at 8:08

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for the info and reference. Indeed seems relevant. I'll accept this answer if I find a solution there. $\endgroup$ Nov 22, 2016 at 10:57
  • 1
    $\begingroup$ Good luck! It's also possible I've missed a reference that addresses your question more directly. $\endgroup$
    – Nick Cook
    Nov 23, 2016 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.