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$
  • 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 '16 at 22:26
  • $\begingroup$ Yep, thanks for catching this typo. $\endgroup$ – Daniel Soudry Nov 22 '16 at 8:08
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$
  • $\begingroup$ Thanks for the info and reference. Indeed seems relevant. I'll accept this answer if I find a solution there. $\endgroup$ – Daniel Soudry Nov 22 '16 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 '16 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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