










– Proof strategy –

As with our earlier paper on the universality of the circular law, we do not attempt to prove (1) for general ensembles such as the Bernoulli ensemble (say) directly.  Instead, we use a Lindeberg-style approach to separate the analytic difficulties from the algebraic ones by first comparing the least singular value \sigma_n(M_n) of a Bernoulli matrix M_n with the corresponding least singular value \sigma_n(G_n) of a gaussian matrix G_n.  If we can show a universality property

\sigma_n(M_n) \approx \sigma_n(G_n) (2)

where we use X \approx Y to denote the informal statement that two random variables X, Y have asymptotically the same distribution (after appropriate renormalisation, and in some appropriate metric), then the claim (1) for the Bernoulli matrix M_n will then follow from the existing work of Edelman establishing (1) for the gaussian matrix G_n.

To establish the approximation (2) for the least singular value, the first thing we do is flip it around, so that we now seek an approximation for the largest singular value for the inverse matrices:

\sigma_1(M_n^{-1}) \approx \sigma_1( G_n^{-1} ). (3)

Experience has shown that largest singular values are easier to compute than least singular values (for instance, they are the same thing as the operator norm and can be computed by, say, the power method).  But there is a huge price to pay: whereas the matrices M_n, G_n had iid entries and were thus tractable to manipulate, the inverse matrices M_n^{-1}, G_n^{-1} have highly coupled entries and are quite difficult to manipulate; in particular, it is not easy at all to control high moments of M_n^{-1}.  So the moment method does not work terribly well (although the second moment of M_n^{-1} is computable, and already useful – we used this “negative second moment identity” to good effect in our earlier paper).

So we do something else.  It turns out that the singular values of M_n tend to be spaced apart with spacing about 1/\sqrt{n}; in particular, \sigma_{n-k+1}(M) is heuristically about k / \sqrt{n}.  (This intuition is supported by the Marchenko-Pastur law, and is also backed up by the tail estimates of Rudelson and Vershynin mentioned earlier.)  Inverting this, we see that the k^{th} largest singular value of M_n^{-1} should be about \sqrt{n} / k.  Thus we see that (after dividing out the normalising factor \sqrt{n}) the matrix M_n^{-1} should behave like a compact operator; its singular values decay to zero at a noticeable rate.  In particular, M_n^{-1} should behave approximately like a finite rank matrix.  (More accurately, “finite” should be “bounded uniformly in n”.)

At this point, we use the philosophy from the property testing literature for finite rank matrices, which tells us that statistics of large finite rank matrix (and in particular, its largest eigenvalue) often can be computed accurately from a small random sample of that matrix.  Indeed, if we pick a small integer s (in practice s \sim n^\varepsilon for some small \varepsilon > 0, and let B(M_n) be the s \times n matrix formed by taking s rows of M_n^{-1} at random (actually, given the iid nature of M_n, we can just take the first s rows), then we expect (from the approximate finite rank nature of M_n^{-1})

\sigma_1(M_n^{-1}) \approx \sqrt{\frac{n}{s}} \sigma_1( B(M_n) ).

It turns out that one can justify this by an application of the moment method, coupled with some estimates on the size of the rows of M_n^{-1} which can be obtained variants of the machinery used in previous papers (in particular, we need some new estimates on distances between random vectors and random hyperplanes).

Of course, everything we say about the Bernoulli ensemble has counterparts for the gaussian ensemble, and so we are reduced to showing that

\sigma_1(B(M_n)) \approx \sigma_1(B(G_n)).

To show this, we invert again, viewing the largest singular value of B(M_n) as the least non-trivial singular value of the (pseudo-)inverse of B(M_n).  Indeed, some elementary linear algebra tells us that

\sigma_1(B(M_n)) = \sigma_s(M_{n,s})^{-1}

where the s \times s matrix M_{n,s} is formed by projecting the first s columns X_1,\ldots,X_s of M onto the s-dimensional space V defined as the orthocomplement of the span of the remaining columns X_{s+1},\ldots,X_n, and then expressing those vectors using some arbitrarily chosen orthonormal basis for V.  [This fact is perhaps most familiar in the simple case s=1, when it is saying that the size of a row of M_n^{-1} is the reciprocal of the distance between the corresponding column of M_n to the hyperplane spanned by the other columns of M_n.]

Of course, we have similar computations for the gaussian ensemble; so we are now reduced to showing that

\sigma_s(M_{n,s}) \approx \sigma_s( G_{n,s} ).

It looks like we are more or less back to where we started (cf. (2)), but with s \times s matrices instead of n \times n matrices.  Indeed, the projected gaussian matrix G_{n,s} can easily be checked to have exactly the same distribution as the s \times s gaussian matrix G_s, basically because the projection of an n-dimensional gaussian random vector to an s-dimensional subspace is an s-dimensional gaussian vector.

But now for the punchline: the projected Bernoulli matrix M_{n,s} also has distribution very close to the gaussian matrix G_s, because the projection of a n-dimensional Bernoulli random vector to a (sufficiently non-degenerate) s-dimensional subspace also behaves like an s-dimensional gaussian vector.  This is basically a consequence of the central limit theorem; for technical reasons we need a modification of the Berry-Esseén version of this theorem.  One has to show that the space V is sufficiently non-degenerate, but this can be done by a modification of techniques already in the literature (specifically, we rely on Talagrand’s inequality and a quantitative form of the Marchenko-Pastur law).  Once this is done, the claim follows from the stability properties of \sigma_s (specifically, we use the Hoffman-Weilandt inequality).