2
$\begingroup$

I'm looking for large-deviations style results for cosine of two independent samples drawn from $\mathcal N(0,\Sigma)$ .

IE, $$q = \frac{\langle X,Y\rangle}{\|X\|\|Y\|}$$

More specifically, are there any interesting bounds on the probability of this value being large in terms of properties of $\mathcal \Sigma$ ? Intuitively it seems this value should be small when $\Sigma$ has small condition number.

The closest thing I found was this question Moment generating function of the inner product of two gaussian random vectors which derives the moment generating function, but would take some work to turn that into a bound.

Also there's Concentration results for inner products of two independent random gaussian vectors, but the answer looks at special case of diagonal $\Sigma$

Any suggestions or references appreciated!

Update Feb 26

I found the following inequality in Sanjeev Arora's CS 521 lecture notes (page 3)

$$P\left[|\cos(\theta_{a,b})| > \sqrt{\frac{\log c}{n}}\right] < \frac{1}{c}$$ where $a,b$ are sampled uniformly from $\{-1,1\}^n$

So from this perhaps one could argue that if $\Sigma$ is extremely badly conditioned, some eigenvalues are close to 0, and we are essentially sampling from lower dimensional space. Improving condition number of $\Sigma$ would increase effective dimensionality $n$, and the cosine shrinks as $\frac{1}{\sqrt{n}}$

Improve this question
$\endgroup$
8
  • $\begingroup$ All such $\Sigma$ are diagonal: you just have to choose a suitable basis in which to represent the vectors. Therefore you already have your answer. $\endgroup$
    – whuber ♦
    Commented Feb 24, 2017 at 1:03
  • $\begingroup$ I guess the question is how property of \sigma affects the bound, and MO bound is independent of sigma. I'm looking to confirm or contradict that picking a a basis in which \Sigma is identity makes it more likely that pairs of drawn vectors are orthogonal $\endgroup$
    – Yaroslav Bulatov
    Commented Feb 24, 2017 at 1:54
  • $\begingroup$ $\Sigma$ will rarely be the identity, but it always can be considered diagonal. Of course pairs of vectors will not be orthogonal with probability $1$, so that version of the question comes down to how close to orthogonal you wish to be. $\endgroup$
    – whuber ♦
    Commented Feb 24, 2017 at 14:14
  • $\begingroup$ So the question I'm trying to figure out is if better conditioned Sigma makes the cosine smaller. For practical reasons (for distributing computation) we need these vectors to be near orthogonal. One thing I tried -- use your MGF derivation to get variance of inner product when k eigenvalues are 1 and rest are 0. So the variance of inner product grows as O(k), but so does norm squared, so it's inconclusive $\endgroup$
    – Yaroslav Bulatov
    Commented Feb 24, 2017 at 19:51
  • $\begingroup$ You're correct. This can be seen by considering an extreme case of ill-conditioned $\Sigma$: those of rank $1$. The cosines will then be $1$ in absolute value with probability $1$. $\endgroup$
    – whuber ♦
    Commented Feb 24, 2017 at 21:16

0

Reset to default

Your Answer

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