Welcome to MathOverflow

Question

7

3

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

edited May 1 2012 at 4:04

Yemon Choi
8,437●1●19●44

asked May 1 2012 at 3:11

Kostas
159●5

1

How small are $m$ and $n$? Less than 10? Less than 100? – Yemon Choi May 1 2012 at 4:04

1

Maybe the standard $\sqrt{m}+\sqrt{n}$ bound applies here too. – S. Sra May 1 2012 at 4:36

Hi, thank you very much for your comments. $m$ and $n$ are usually less than 10. Do you have a paper in mind that talks about the $\sqrt{m}+\sqrt{n}$ bound? Thank you, best, Alex – Kostas May 1 2012 at 7:16

David Benson-Putnins · Accepted Answer · 2012-05-01 13:48:28Z UTC

5

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

answered May 1 2012 at 13:48

David Benson-Putnins
245●5

Emilio Pisanty · Answer 2 · 2012-05-02 16:20:22Z UTC

2

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.

edited May 2 2012 at 16:20

answered May 1 2012 at 12:56

Emilio Pisanty
709●2●9

Thank you very much for your time to code this! It was very helpful! – Kostas May 1 2012 at 20:53

You're welcome! Mathematica code is normally deceptively simple but this was quite straightforward. Plus, it helped me crystallize the Random[]&/@Range[] trick which had been annoyingly floating around my mind with a "there has to be a simple way" kind of taunt. – Emilio Pisanty May 2 2012 at 0:12

Any matrix with two rows which are multiples of each other will automatically have a $0$ singular value. This accounts for most of the peak you see at $0$ (each pair of rows matches for about $3900$ matrices and there's $10$ pairs of rows), but disappears as $\min\{m,n\}$ tends to infinity. – Kevin P. Costello May 2 2012 at 16:59

1

In a sense, "local" configurations (those involving only a couple rows) can only get you so close to $0$: If you look at, say, $|| \{1,-1,0,0,0,0,0,0,0,0 \} A||$, it's either going to be $0$ or at least $1$, meaning that this can't be the cause of a positive singular value smaller than $2^{-1/2}$. Intuitively, a $0$ singular value (which requires only $1$ row to go wrong) is much easier than a very small positive singular value (which requires $2$ or more rows to go wrong), though this is far from a rigorous proof. – Kevin P. Costello May 3 2012 at 18:40

1

(continued) Even if you let both $m$ and $n$ go to infinity, but at different rates (say $m/n \rightarrow c<1$), the smallest singular value will with high probability grow be within a constant of the largest (Bai and Yin, "Limit of the smallest eigenvalue of a large dimensional covariance matrix", see also Rudelson and Vershynin's "The smallest singular value of a random rectangular matrix" ) – Kevin P. Costello May 3 2012 at 18:49

show 1 more comment

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.