Sunday, July 15, 2007

Smallest singular value of a random matrix.

Say A is an n X n random matrix, eg iid +/- 1. Its smallest singular value s_n(A)= inf_{x; x_2=1} Ax_2. A conjecture, derived from von Neumann, Smale and others, has been that s_n(A) \tilde n^{-1/2} whp. In an improvement to a recent result of Tao and Vu that proved n^{-B}, B not quite a 1/2, Rudelson and Vershynin finally nail it and prove the conjecture. Check out the paper and the talks. Roman Vershynin's talk was totally inspiring and the papers seem they must be studied, full frontal. The proof involves nice intuition from sparse representations and embeding into arithmetic progressions.


Post a Comment

<< Home