3
$\begingroup$

If I take $A^TA$, where $A$ is a full-rank random matrix (let's say with Gaussian-distributed independent entries), can I expect it to be positive-definite? It will be positive semi-definite trivially, since $x^TA^TAx = \|Ax\|^2$, so I guess it will not be positive-definite only if the random matrix $A$ is rank-deficient, which should almost never happen.

But from numerical stability point of view, things might look different, because the matrix $A^TA$ could be close to a p.s.d. non-p.d. matrix with some probability.

So: is it generally safe to apply Cholesky decomposition to such a matrix, or is there a nontrivial chance of that leading to numerical instability? (I.e. without stronger conditions which would force the matrix away from the problematic boundary of p.d. matrices with non-p.d. matrices?)

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ you're asking for the probability that $A^T A$ has an eigenvalue identical to zero; this probability is vanishingly small. $\endgroup$
    – Carlo Beenakker
    Nov 19, 2013 at 7:24
  • $\begingroup$ @CarloBeenakker Is it then typical to apply Cholesky decomposition without fearing numerical instability? I mean, given the above information alone? $\endgroup$
    – Evgeni Sergeev
    Nov 19, 2013 at 7:28
  • 1
    $\begingroup$ There is a robust Cholesky's method. math.berkeley.edu/~cinnawu/hss.pdf $\endgroup$
    – loup blanc
    Nov 19, 2013 at 10:18
  • 1
    $\begingroup$ @CarloBeenakker: The probability is not just "vanishingly small", it is zero. $\endgroup$
    – Nate Eldredge
    Nov 19, 2013 at 17:34
  • $\begingroup$ @NateEldredge what if you run an uncountably infinite number of trials in parallel, where the infinity is of high enough cardinality, isn't it possible that the expected value of trials with an exact zero eigenvalue will be some non-zero number, for example 3 or 4? $\endgroup$
    – Evgeni Sergeev
    Nov 19, 2013 at 22:02

2 Answers 2

Reset to default
3
$\begingroup$

Not sure if this is what you are really after, but anyway: The paper by Rudelson and Vershynin that Igor Rivin linked to contains lots of things which may be helpful for you. For example, for random $N\times n$ matrices ($N>n$) with iid Gaussian entries, there is Theorem 2.6 there which says that for the smallest singular value $s_\text{min}(A)$ it holds that $$\sqrt{N} - \sqrt{n}\leq \mathbb{E}s_\text{min}(A).$$ Also, there is a the quantitative bound $$\mathbb{P}(\sqrt{N}-\sqrt{n} - t \leq s_\text{min}(A)) \geq 1 - 2\exp(-t^2/2).$$ The case of square (but not necessarily symmetric) matrices is more difficult. There is also a probability for a lower bound on the smallest singular value: For square (subgaussian) matrices, Theorem 3.2 says that for some $C>0$, $0<c<1$ and any $\epsilon>0$ it holds that $$\mathbb{P}(s_\text{min}(A)\leq \epsilon n^{-1/2})\leq C\epsilon + c^n.$$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Right, in a small case we might have N=24 and n=3, so if we assume that the quantitative bound above is a good approximation to the actual probability cdf, which is probably a very bad assumption, then the probability of $|s_{min}| < 10^{-3}$ can be estimated to be around (where t0 = $\sqrt{N} - \sqrt{n}$) 2*exp(-(t0-1e-3)**2/2) - 2*exp(-(t0+1e-3)**2/2), which is 5.73e-24. Even if we're out by a factor of a trillion, that's still pretty good. $\endgroup$
    – Evgeni Sergeev
    Nov 20, 2013 at 21:39
0
$\begingroup$

Check out Rudelson-Vershynin, they answer more than you ever hoped to know...

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ This is really a comment (i.e. a pointer to an answer) rather than an answer. $\endgroup$
    – Dirk
    Nov 19, 2013 at 14:36
  • $\begingroup$ @Dirk you are free to type in the result from Rudelson-Vershynin verbatim - I am sure you have lots of spare time. $\endgroup$
    – Igor Rivin
    Nov 19, 2013 at 14:48
  • $\begingroup$ It would take me months to figure out whether these results are obvious or not. $\endgroup$
    – Evgeni Sergeev
    Nov 19, 2013 at 20:37
  • $\begingroup$ @EvgeniSergeev As evidence that they are not obvious, notice that the reference is to an ICM address. If you mean "easy to find in the paper", yes, they are. $\endgroup$
    – Igor Rivin
    Nov 20, 2013 at 0:10

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.