2

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}}$

Community
  • 1
Yaroslav Bulatov
  • 5,167
  • 2
  • 24
  • 38
  • *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. – whuber Feb 24 '17 at 01:03
  • 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 – Yaroslav Bulatov Feb 24 '17 at 01:54
  • $\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. – whuber Feb 24 '17 at 14:14
  • 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 – Yaroslav Bulatov Feb 24 '17 at 19:51
  • 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$. – whuber Feb 24 '17 at 21:16
  • Hm, if I plug n=1 into your MGF formula, I get expected value of dot product being 0, does it only work for rank>1? – Yaroslav Bulatov Feb 24 '17 at 21:51
  • I'm not sure what formula you are referring to. Please note that the cosine is not the inner product. – whuber Feb 24 '17 at 22:06
  • updated post with a promising looking inequality – Yaroslav Bulatov Feb 26 '17 at 22:59

0 Answers0