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?)

$\endgroup$
  • 2
    $\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 '13 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 '13 at 7:28
  • 1
    $\begingroup$ There is a robust Cholesky's method. math.berkeley.edu/~cinnawu/hss.pdf $\endgroup$ – loup blanc Nov 19 '13 at 10:18
  • 1
    $\begingroup$ @CarloBeenakker: The probability is not just "vanishingly small", it is zero. $\endgroup$ – Nate Eldredge Nov 19 '13 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 '13 at 22:02
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.$$

$\endgroup$
  • $\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 '13 at 21:39
0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ This is really a comment (i.e. a pointer to an answer) rather than an answer. $\endgroup$ – Dirk Nov 19 '13 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 '13 at 14:48
  • $\begingroup$ It would take me months to figure out whether these results are obvious or not. $\endgroup$ – Evgeni Sergeev Nov 19 '13 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 '13 at 0:10

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.