0
$\begingroup$

Let $A$ be an $n\times n$ gaussian matrix whose entries are i.i.d. copies of a gaussian variable, and $\left\{ a_{j}\right\} _{j=1}^{n}$ be the column vectors of $A$. How to show that the probability $\mathbb{P}\left(d\geq t\right)\leq Ce^{-ct}$ for some $c,C>0$ and every $t>0$, where $d$ is the distance between $a_{1}$ and the $n-1$-dimensional subspace spanned by $a_{2},\cdots,a_{n}$.

Thanks a lot!

$\endgroup$
2
  • $\begingroup$ Is this Gaussian variable assumed to have mean 0? $\endgroup$ Mar 13, 2010 at 13:23
  • $\begingroup$ Yes, we assume it is in stardard normal distribution. $\endgroup$
    – user4606
    Mar 14, 2010 at 3:46

1 Answer 1

4
$\begingroup$

symmetry shows that you can suppose that $$\text{span}(a_2, \ldots, a_n) = ( x \in \mathbb{R}^n: x_1=0 ) = H.$$ Hence you just want to show that $d(a_1, H) = |A_{1,1}|$ is exponentially small - there is a closed-form expression for that: $$ P(d>t) = P(|\mathcal{N}(0,1)|>t) = \sqrt{\frac{2}{\pi}} \int_t^{\infty} e^{-\frac{x^2}{2}} dx.$$

$\endgroup$
3
  • $\begingroup$ I don't see how to use symmetry to get $$\text{span}(a_2, \ldots, a_n) = ( x \in \mathbb{R}^n: x_1=0 ) = H$$. Could you please explain a little more on that? $\endgroup$
    – user4606
    Mar 14, 2010 at 3:25
  • 1
    $\begingroup$ You can see it using the concepts of conditional probability. For each possible $H$ (using Alekk's notation) there is a probability distribution of $d$ conditional on that $H$, and the total (unconditional) distribution of $d$ is obtained from that by integrating over $H$. Now the conditional distribution of $d$ given $H$ is independent of $H$, because the joint probability distribution of all the $a$'s is invariant under rotation. So integrating over $H$ is unnecessary – just use one fixed $H$. $\endgroup$ Mar 14, 2010 at 4:40
  • 1
    $\begingroup$ If you want $\ell_1$ distance, I think the formula (if one can be found) will be rather complex, and its derivation horrendously so. You might experiment with a computer algebra system and see how it works out for small values of $n$. $\endgroup$ Mar 14, 2010 at 21:53

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.