Maximum Singular Value of a random +1/-1 matrix - MathOverflow

Maximum Singular Value of a random +1/-1 matrix

2012-05-01T03:11:16Z

Hi,

Define a matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ such that each element is independently and randomly chosen with probability 0.5 to be either +1, or -1. Do you know any result in the literature that talks about properties of this kind of matrices?

I have seen that there are some results for other kind of random matrices (for example matrices whose entries are i.i.d gaussian.) but not for this simple matrix of +1/-1.

I would be interested for example on the distribution of the $\sigma_{max}(A)$, (not in an asymptotic regime. $m$, $n$ are finite numbers and usually small in my case.)

Thank you very much for any pointer or any thoughts.

Best,

Alex

Answer by Emilio Pisanty for Maximum Singular Value of a random +1/-1 matrix

2012-05-01T12:56:01Z

For what it's worth, here's some numerical data in Mathematica CDF format.

Edit: I've been playing around some more and this is a histogram for 1,000,000 tries with $m=9$, $n=5$ for the five different singular values (each in a different colour). I'm intrigued by the peaks - @Alex, were you expecting that? There is also a significant portion of matrices with one zero singular value, but I am unsure whether it is due to numerical artifacts.

Answer by David Benson-Putnins for Maximum Singular Value of a random +1/-1 matrix

2012-05-01T13:48:28Z

http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf Theorem 5.39 (page 23) gives a non-asymptotic upper bound on the largest singular value