Random matrices: The distribution of the smallest singular values

Introduction

Let $\xi$ be a real or complex-valued random variable and $M_{n}(\xi)$ denote the random $n\times n$ matrix whose entries are i.i.d. copies of $\xi$. In this paper, we always impose one of the following two normalizations on $\xi$:

A basic problem in random matrix theory is to understand the distribution of singular values in the asymptotic limit $n\to\infty$. Given an $m\times n$ matrix $M$, let

denote the non-trivial singular values of $M$. Our paper will be focused on the “hard edge” of this spectrum, and in particular on the least singular value $\sigma_{n}(M)$, in the case of square matrices $m=n$, but let us begin with a brief review of some known results for the rest of the spectrum.

There is a general belief that (under reasonable hypotheses) the limiting distributions concerning the spectrum of a large random matrix should be “universal”, in the sense that they should not depend too strongly on the distributions of the entries of the matrix. In particular, one usually expects that the asymptotic statistical properties that are known for matrices with (independent) gaussian entries should also hold for matrices with more general entries (such as Bernoulli). A well-known conjecture (now a theorem) of this type is the Circular Law conjecture (see [5, Chapter 10] and ). Another example is that of Dixon’s conjectures (see [26, Conjectures 1.2.1 and 1.2.2]).

as $n\to\infty$, both in the sense of probability and in the almost sure sense. For more details, we refer to . (In literature, very frequently one views $\sigma_{i}(M_{n}(\xi))^{2}$ as the eigenvalues of the sample covariance matrix $M_{n}(\xi)M_{n}(\xi)^{\ast}$ and so it is more traditional to write down the limiting distributions in term of $\sigma^{2}$.)

The next objects to consider are the extremal singular values. The distribution of the largest singular value $\sigma_{1}$ (and more generally, the joint distribution of the top $k$ singular values) was computed for the gaussian case by Johansson and Johnstone . This distribution is governed by the Tracy-Widom law (and more generally, the Airy kernel). In particular, one has

where $TW$ denotes the Tracy-Widom distribution. More recently, Soshnikov showed that the same result holds for all random matrices with normalized subgaussian entries.

Both integrals can be computed explicitly. By change of variables, one can show

The error term $o(1)$ in (1) is not explicitly stated in (it relies on an asymptotic for the Tricomi function), but our Theorem 1.3 below will imply that it is of the form $O(n^{-c})$ for some absolute constant $c>0$.

In the general setting (and in particular in discrete cases such as Bernoulli), it is already not trivial to show that the probability that $\sigma_{n}(M_{n}(\xi))$ is positive tends to one with $n$ (this statement is, of course, obvious in the continuous case, such as gaussian, by a dimension argument). This was first done by Komlós . For more recent developments along this line we refer to . These papers give better and better bounds on the rate of convergence (to one) of the probability in question, but do not give any quantitative estimate on $\sigma_{n}$.

In the last few years,we have seen considerable progresses in the problem of estimating $\sigma_{n}$ and its tail distribution. In , the present authors proved an (almost sure) lower bound for the absolute value of the determinant of a random Bernoulli matrix. As the absolute value of the determinant is the product of the singular values, this result implies an (almost sure) lower bound of the form $\exp(-n^{1/2+o(1)})$ for the least singular value. A significant breakthrough was achieved by Rudelson , who established a polynomial lower bound for $\sigma_{n}(M_{n}(\xi))$ and also tail estimates for a certain range. Rudelson’s results were then extended by several authors , , , , , , , using the machinery of Inverse Littlewood-Offord theorems, introduced in . For instance, under the assumption of bounded fourth moment ${\mathbf{E}}|\xi|^{4}<\infty$, it was shown in that

for all fixed $t>0$, where $f(t)$ goes to zero as $t\to 0$; similarly, in it was shown that

for all fixed $t>0$, where $g(t)$ goes to zero as $t\to\infty$. Under the stronger assumption that $\xi$ is subgaussian, the lower tail estimate was improved in to

for some constants $C>0$ and $0<c<1$ depending only on the subgaussian moments of $\xi$. At the other extreme, with no moment assumptions on $\xi$, the bound

A common feature of the above mentioned results is that they give good upper and lower tail bounds on $n\sigma_{n}(M_{n}(\xi))^{2}$, but not the distributional law. In fact, many papers are partially motivated by the following conjecture of Spielman and Teng [40, Conjecture 2].

Let $\xi$ be the Bernoulli random variable. Then there is a constant $0<c<1$ such that for all $t\geq 0$

In this paper, we introduce a new method to study small singular values. This method is analytic in nature and enables us to prove the universality of the limiting distribution of $n\sigma_{n}(M_{n}(\xi))^{2}$.

Figure 1 shows an empirical demonstration of the theorem above for Bernoulli and for gaussian distributions.

Our arguments are completely effective, and give an explicit value for $C_{0}$; for instance, $C_{0}:=10^{4}$ certainly suffices. Clearly, one should be able to lower $C_{0}$ significantly (we have made no attempt to optimize in $C_{0}$, in order to simplify the exposition), but we will not explore this issue here.

Theorem 1.3 can be extended in several directions, with simple modifications of the proof. For example, we can prove a similar universality result involving the joint distribution of the bottom $k$ singular values of $M_{n}(\xi)$, for bounded $k$ (and even some results when $k$ is a small power of $n$). Next, we can also consider rectangular matrixes where the difference between the two dimensions is not too large. Finally, all results hold if we drop the condition that the entries have identical distribution. (It is important that they are all normalized, independent and their $C_{0}$-moments are uniformly bounded.) For precise statements, see Section 6.

It is clear that one can use Theorem 1.3 to address Conjecture 1.2. By Theorem 1.3 and (2), the left hand side of (7) is

Since $1-e^{-t^{2}/2-t}<t$ for any $t>0$, we conclude that Conjecture 1.2 holds for any $t>n^{-c_{0}}$, for some positive constant $c_{0}$. More importantly, it shows that the main term $t$ on the right hand side of (7) is only a (first order) approximation of the truth and could certainly be improved. For example, for sufficiently small $t$, Taylor expansion gives

Figure 2 provides empirical evidence that ${\mathbf{P}}(\sqrt{n}\sigma_{n}(M_{n}(\xi))\leq t)<t$ for the Bernoulli and gaussian cases.

Notation. We consider $n$ as an asymptotic parameter tending to infinity. We use $X\ll Y$, $Y\gg X$, $Y=\Omega(X)$, or $X=O(Y)$ to denote the bound $X\leq CY$ for all sufficiently large $n$ and for some $C$ which can depend on fixed parameters (such as $C_{0}$ or ${\mathbf{E}}|\xi|^{C_{0}}$) but is independent of $n$.

The Frobenius norm $\|A\|_{F}$ of a matrix is defined as $\|A\|_{F}=\operatorname{trace}(AA^{*})^{1/2}$. Note that this bounds the operator norm $\|A\|_{op}:=\sup\{|Ax|:|x|=1\}$ of the same matrix.

For a random variable $X$, ${\mathbf{E}}(X)$ is the expectation of $X$. If $X$ is real, we denote by $M(X)$ its median, namely a number $x$ such that both ${\mathbf{P}}(X\geq x)$ and ${\mathbf{P}}(X\leq x)$ are at least $1/2$. (If $x$ is not unique, choose one arbitrarily.)

For an event ${\mathcal{E}}$, ${\mathbf{I}}_{{\mathcal{E}}}$ is its indicator function, taking value 1 if ${\mathcal{E}}$ holds and 0 otherwise. Clearly ${\mathbf{E}}({\mathbf{I}}_{{\mathcal{E}}})={\mathbf{P}}({\mathcal{E}})$.

The main idea and the proof strategy

We now discuss our main idea and the strategy behind Theorem 1.3. A formal version of this argument is given in Section 3, though for various minor technical reasons, the presentation there will be rearranged slightly from the one given here.

Let us first reveal our main idea. To start, we are going to view $\sigma_{n}(M_{n}(\xi))$ as the (reciprocal of the) largest singular value of $M_{n}^{-1}(\xi)$. One of the most popular methods to study the largest singular value is the moment method, which enables one to control on $\sigma_{1}(M)$ (of a random matrix $M$) if one can have good estimates on $\operatorname{trace}(MM^{\ast})^{k/2}$ for very large $k$. The moment method was used successfully by Sosnhikov to study $\sigma_{1}(M_{n}(\xi))$. However, it is important in the applications of this method that the entries of $M$ are independent and their distributions well-understood. Unfortunately, the entries of $M_{n}^{-1}$ are highly correlated and not much is known about their distributions.

We have found a new approach, motivated by the general idea of “property testing”, a topics popular in theoretical computer science and combinatorics. The general setting of a property testing problem is as follows. Given a large, complex, structure $S$, we would like to study some parameter $P$ of $S$. It has been observed that quite often one can obtain good estimates about $P$ by just looking at the small substructure of $S$, sampled randomly. In our situation, the large structure is the matrix $S:=M_{n}^{-1}$, and the parameter in question is its largest singular value. It has turned out that this largest singular value can be estimated quite precisely (with high probability) by sampling a few rows (say $s$) from $S$ and considering the submatrix $S^{\prime}$ formed by these rows. The heart of the proof then consists of two observations: (1) The singular values of $S^{\prime}$ can be computed from a matrix obtained by projecting the rows of $S^{-1}=M_{n}$ onto a subspace of dimension $s$ and (2) Such a projection has a central limit theorem effect. All these together allow us to compare the least singular value of $M_{n}(\xi)$ with the least singular value of $M_{s}({\mathbf{g}})$ (properly normalized), proving the universality.

(From existing results, e.g. , it is known that $M_{n}(\xi)$ is invertible with very high probability.) We now wish to show that

thus reducing our task to that of showing that

The relation (12) looks very similar to our original relation (9) (indeed, when $s=n$, (12) collapses back to (9)). However, the critical gain here is that (12) becomes much easier to prove than (9) when $s$ is only a small power of $n$, because the projection $\pi$ will act to average out the random variable $\xi$ into (approximately) a gaussian variable (essentially thanks to the central limit theorem). Indeed, by using a variant of the Berry-Esséen central limit theorem (Proposition 3.4), together with some non-degeneracy (or “delocalization”) properties of $V_{s,n}(\xi)$ (Proposition 3.5), we will be able to establish a relation of the form

The rigorous proof

We now implement the strategy sketched out in Section 2 to give a rigorous proof of Theorem 1.3. This proof will rely on several key propositions which are proven in later sections or in the appendices.

We first make a simple reduction. By hypothesis, ${\mathbf{E}}|\xi|^{C_{0}}=O(1)$. Hence by Markov’s inequality, we see that ${\mathbf{P}}(|\xi|\leq n^{10/C_{0}})=O(n^{-10})$. Thus, by the union bound, we see that with probability at least $1-O(n^{-8})$, all coefficients of $M_{n}(\xi)$ are $O(n^{10/C_{0}})$. If we remove the tail event $|\xi|\geq n^{10/C_{0}}$ from $\xi$, and readjust $\xi$ slightly to restore the $F$-normalization conditions (using (36) to absorb the error, and using the continuity of $f$), we may thus reduce to the case when

with probability one. This is a standard truncation and re-normalization process, used frequently in random matrix literature (see, for instance, ). We omit the (routine, but somewhat tedious) details.

For minor technical reasons, it is also convenient to assume $\xi$ to be a continuous random variable (in particular, this implies that $M_{n}(\xi)$ is invertible with probability one). However, we emphasise that the bounds in our arguments do not explicitly depend on the continuity properties of $\xi$, and instead depend only on the $C_{0}$ moment of $\xi$ for any fixed $n$. Since one can express any discrete random variable with finite $C_{0}$ moment (and obeying (14)) as the limit of a sequence of continuous random variables with uniformly bounded $C_{0}$ moment (and also obeying (14)), we see that the discrete case of the theorem can be recovered from the continuous one by a standard limiting argument (keeping $n$ fixed during this process, and using (36) as necessary).

Let $R_{1}(\xi),\ldots,R_{n}(\xi)$ denote the rows of $M_{n}(\xi)^{-1}$. Since the columns $X_{1}(\xi),\ldots,X_{n}(\xi)$ of $M_{n}(\xi)$ are exchangeable (i.e. exchanging any two columns of $M_{n}(\xi)$ does not affect the distribution), we see that $M_{n}(\xi)^{-1}$ is row-exchangeable.

Our first step is motivated by the observation that in certain cases the largest singular values of a matrix can be well approximated by sampling. This fact is well-known in theoretical computer science and numerical analysis. In particular, the lemma below is a special case of more general results from .

Let $1\leq s\leq n$ be integers. $A$ be an $n\times n$ real or complex matrix with rows $R_{1},\ldots,R_{n}$. Let $k_{1},\ldots,k_{s}\in\{1,\ldots,n\}$ be selected independently and uniformly at random, and let $B$ be the $s\times n$ matrix with rows $R_{k_{1}},\ldots,R_{k_{s}}$. Then

The proof of Lemma 3.1 is presented in Appendix A.

In order to apply Lemma 3.1, we need to bound the right hand side. This is done in the following proposition.

Let $R_{1},\dots,R_{n}$ be the rows of $M_{n}(\xi)^{-1}$. Then

We will prove this important proposition in Section 5.

To continue, let ${\mathcal{E}}_{1}$ denote the event

Sample a matrix $A$ from the distribution $M_{n}(\xi)$. Let $B$ be the submatrix formed by $s$ random rows of $A^{-1}$. If the rows of $A^{-1}$ satisfies ${\mathcal{E}}_{1}$, then by Lemma 3.1 and the definition of $s$, we have

(The expectation and probability in the last two estimates are with respect to the random choice of the rows; the matrix $A$ is fixed and satisfies ${\mathcal{E}}_{1}$.)

Let ${\mathcal{E}}_{2}$ be the event that

Finally, let ${\mathcal{E}}_{3}$ be the event that

We are going to view both ${\mathcal{E}}_{2},{\mathcal{E}}_{3}$ as events in the product space generated by $M_{n}(\xi)$ and the random choice of the rows. A simple calculation shows that if ${\mathcal{E}}_{1},{\mathcal{E}}_{2},{\mathcal{E}}_{3}$ hold, then

Our next tool is a linear algebraic lemma that connects the submatrices of $A^{-1}$ to matrices obtained by projecting the row vectors of $A$ onto a subspace.

Let $1\leq s\leq n$ be integers, let $F$ be the real or complex field, let $A$ be an $n\times n$ $F$-valued invertible matrix with columns $X_{1},\ldots,X_{n}$, and let $R_{1},\ldots,R_{n}$ denote the rows of $A^{-1}$. Let $B$ be the $s\times n$ matrix with rows $R_{1},\ldots,R_{s}$. Let $V$ be the $s$-dimensional subspace of $F^{n}$ formed as the orthogonal complement of the span of $X_{s+1},\ldots,X_{n}$, which we identify with $F^{s}$ via an orthonormal basis, and let $\pi:F^{n}\to F^{s}$ be the orthogonal projection to $V\equiv F^{s}$. Let $M$ be the $s\times s$ matrix with columns $\pi(X_{1}),\ldots,\pi(X_{s})$. Then $M$ is invertible, and we have

For any fixed value of the rows $X_{s+1},\ldots,X_{n}$, we choose a projection $\pi:F^{n}\to F^{s}$ as above. The exact choice of $\pi$ is not terribly important so long as it is made independently of the rows $X_{1},\ldots,X_{s}$; for instance, one could pick $\pi$ uniformly at random with respect to the Haar measure on all such available projections, independently of $X_{1},\ldots,X_{s}$.

Applying Lemma 3.3 twice, and noticing that since the rows of $M_{n}(\xi)$ have identical distribution, we can rewrite the inequalities in question as

(with the convention that $t_{+}=\infty$ if $t>n^{40/C_{0}}$) and

and $M_{s,n}(\xi)$ is the $s\times s$ matrix with rows $\pi(X_{1}(\xi)),\ldots,\pi(X_{s}(\xi))$, and $\pi:F^{n}\to F^{s}$ is the orthogonal projection to the $s$-dimensional space $V=V_{s,n}(\xi)$ orthogonal to the columns $X_{s+1}(\xi),\ldots,X_{n}(\xi)$ of $M_{n}(\xi)$, where we identify $V$ with $F^{s}$ via some orthonormal basis of $V$, chosen in some fashion independent of first $s$ columns $X_{1}(\xi),\ldots,X_{s}(\xi)$.

The final, and key, point in the proof is to show that the distribution of $M_{s,n}(\xi)$ is very close to that of $M_{s,n}({\mathbf{g}})$. We are going to need the following high-dimensional generalization of the classical Berry-Esseen central limit theorem, which we will prove in Appendix D.

Let $1\leq N\leq n$, let $F$ be the real or complex field, and let $\xi$ be $F$-normalized and have finite third moment ${\mathbf{E}}|\xi|^{3}<\infty$. Let $v_{1},\ldots,v_{n}\in F^{N}$ be a normalized tight frame for $F^{N}$, or in other words

where $I_{N}$ is the identity matrix on $F^{N}$. Let $S\in F^{N}$ denote the random variable

where $\xi_{1},\ldots,\xi_{n}$ are iid copies of $\xi$. Similarly, let $G:=({\mathbf{g}}_{F,1},\ldots,{\mathbf{g}}_{F,N})\in F^{N}$ be formed from $N$ iid copies of ${\mathbf{g}}_{F}$. Then for any measurable set $\Omega\subset F^{N}$ and any ${\varepsilon}>0$, one has

$\partial\Omega$ is the topological boundary of $\Omega$, and and $\operatorname{dist}_{\infty}$ is the distance using the $l^{\infty}$ metric on $F^{N}$. The implied constant depends on the third moment ${\mathbf{E}}|\xi|^{3}$ of $\xi$.

In order to apply this result, we need to ensure non-degeneracy of the subspace $V=V_{s,n}(\xi)$. This is done in the following proposition, which we will proved in Section 4.

Let $E_{c}(\xi)$ denote the event that there does not exist a unit vector $v=(v_{1},\ldots,v_{n})$ in $V_{s,n}(\xi)$ such that $\max_{1\leq i\leq n}|v_{i}|\geq n^{-c}$. If $c$ is a sufficiently small absolute constant, then

An important point here is that $c$ does not depend on $C_{0}$. For instance, we will be able to take $c:=1/20$.

The idea that normal vectors are non-degenerate was considered in and has since then become an important part in several papers on the least singular value problem, e.g. , , , , , , , . The notion of non-degeneracy here is, however, somewhat different from those considered before. In the above mentioned papers, it was typically required that no small set of coordinates (say $n^{.99}$ coordinates) contains most of the mass of the vector (in other words, one cannot compress the vector into a much shorter one). In contrast, we require here that no individual coordinate can contain a significant (but not overwhelming) portion of the mass.

Let us take this proposition for granted for now, and condition on

so that $E_{c}(\xi)$ holds; note that $X_{1}(\xi),\ldots,X_{s}(\xi)$ remain iid under this conditioning. We can then write

where the $\xi_{ij}$ are iid copies of $\xi$, and $V_{ij}$ is the $s\times s$ matrix with all rows vanishing except the $i^{th}$ row, which is equal to $\pi(e_{j})$, where $e_{j}$ is the $j^{th}$ basis vector of $F^{n}$. Since $\pi$ is a partial isometry, $\pi\pi^{*}=I_{s}$, which implies that

where we view identify the space of $s\times s$ matrices with the vector space $F^{s^{2}}$ in the standard manner.

Now let $\Omega\subset F^{s^{2}}$ be the set of all $s\times s$ matrices $A$ such that $s\sigma_{s}(A)^{2}\leq t_{+}$, thus

Applying Proposition 3.4 (with $N:=s^{2}$) and the definition of the event $E_{c}$, we thus have

where ${\varepsilon}$ is a parameter to be chosen later. But by (36) and the crude bound

for any $s\times s$ matrix $A=(a_{ij})_{1\leq i,j\leq s}$, we see that if $A$ is an $s\times s$ matrix in $\Omega\cup\partial_{\varepsilon}\Omega$, then

Setting ${\varepsilon}:=n^{-c/4}$ (say), we see from construction of $s$ that $s^{5}{\varepsilon}^{-3}n^{-c}=O(n^{-1/C_{0}})$, if $C_{0}$ is large enough depending on $c$. Also, we can absorb the $O(s{\varepsilon})$ error into the main term $\sqrt{\frac{t_{+}}{s}}$ by replacing $t_{+}$ by a slightly larger quantity, e.g.

Integrating over all $X_{s+1}(\xi),\ldots,X_{n}(\xi)$ obeying $E_{c}$, and then using Proposition 3.5 and the above argument, we conclude that

At this point we could use Theorem 1.1 and obtain a qualitative version of Theorem 1.3. This would result in error terms $o(1)$ rather than $O(n^{-c})$. However, one only needs a little more effort to obtain the full result. The estimates (19), (20) hold with $n$ replaced by $2n$; adjusting $t$ appropriately (as well as the implied constants defining $t_{--},t_{++}$), one obtains the bounds

This bound is established under the hypothesis (14), but as discussed at the beginning of the section, we may easily remove this hypothesis. In particular, the above bounds now hold for the gaussian distribution $\xi={\mathbf{g}}_{F}$. Meanwhile, from Theorem 1.1 we have

IteratingOne way to interpret this iteration is to view (21), (22) as asserting that the random variables $n\sigma_{n}(M_{n}(\xi))^{2}$ form a Cauchy sequence in the Lévy metric. (21), (22) and using (23) to pass to the limit (and adjusting the implied constants in the definition of $t_{--}$, $t_{++}$ again), we conclude that

since $f$ is absolutely integrable and decays exponentially at infinity, we thus have

Inserting this bound (with $n$ replaced by $s$) into (19), (20) and using the continuity of $f$ again, we obtain (13), and Theorem 1.3.

The above argument used the explicit limiting statistics for the hard edge of the gaussian random matrix spectrum in Theorem 1.1. If one refused to use this theorem, the best one could say using the above argument is that there exists a random variable $X_{F}$ taking values in the positive real line and independent of $n$ and $\xi$ such that

for any $t>0$. (We can replace $O(n^{-c})$ by $n^{-c}$ by slightly changing the value of $c$.) In other words, the random variables $n\sigma_{n}(M_{n}(\xi))^{2}$ converge at some polynomial rate with respect to the Lévy metric to a universal limit $X_{F}$ depending only on the field $F$. Theorem 1.1 can then be viewed as a computation as to what this universal limit is.

Non-degeneracy of normal vectors

In this section we prove Proposition 3.5. Let $c>0$ be a sufficiently small constant. By the union bound and symmetry, it suffices to show that

Let $v=(v_{1},\ldots,v_{n})$ be such that the event in (24) occurs. Since $v\in V_{s,n}$, we have

where $B$ is the $(n-s)\times n$ matrix with rows $X_{s+1},\ldots,X_{n}$. We write $B=(Y_{1},B^{\prime})$, where $Y_{1}\in F^{n-s}$ is a column vector whose entries are iid copies of $\xi$, and $B^{\prime}$ is a $n-s\times n-1$ matrix whose entries are also iid copies of $\xi$. We similarly write $v=(v_{1},v^{\prime})$ where $v^{\prime}:=(v_{2},\ldots,v_{n})\in F^{n-1}$. Then we have

Our first tool here is the following lemma, which asserts that with overwhelming probability, a random matrix has many small singular values. We will prove this lemma in Appendix F.

The next tool has a geometric flavor. It asserts that the orthogonal projection of a random vector onto a large subspace is strongly concentrated.

Let $n\geq d\geq 1$ be integers, let $K\geq 1$, let $F$ be the real or complex field, let $\xi$ be $F$-normalised with $|\xi|\leq K$ almost surely, and let $V$ be a subspace of $F^{n}$ of dimension $d$. Let $X:=(\xi_{1},\ldots,\xi_{n})$, where $\xi_{1},\ldots,\xi_{n}$ are iid copies of $\xi$. Suppose that $d>CK^{2}$ for some sufficiently large absolute constant $C$. Then

This lemma is an extension of the special case considered in , in which $\xi$ is Bernoulli. We are going to prove this lemma in Appendix E.

Applying Lemma 4.1 to an $(n-s)\times(n-s)$ block of $B$ and using the interlacing law (Lemma B.2), we conclude (given that $C_{0}$ is sufficiently large) that with probability $1-\exp(-n^{\Omega(1)})$, $B^{\prime}$ has at least $n^{1-c_{0}}$ singular values of size $O(n^{\frac{1}{2}-c_{0}})$, for some absolute constant $c_{0}>0$. This implies the existence of a subspace $V\subset F^{n-s}$ of dimension $d:=\lfloor n^{1-c_{0}}\rfloor$ such that $\|\pi_{V}B^{\prime}\|_{op}\ll n^{\frac{1}{2}-c_{0}}$, where $\pi_{V}$ is the orthogonal projection to $V$. Let us condition on the event that this is the case (note that this event does not depend on $v$). Then we have

Combining this with (25) and the hypothesis $|v_{1}|\geq n^{-c}$, we conclude that

On the other hand, from Lemma 4.2 we see that with probability $1-\exp(-n^{\Omega(1)})$, we have

If we choose $c$ sufficiently small depending on $c_{0}$, we obtain a contradiction with probability $1-\exp(-n^{\Omega(1)})$. The claim (24) follows.

A lower bound for the distance between a random vector and a random hyperplane

In this section we prove Proposition 3.2. This type of result is somewhat related to the lower tail bounds on the lowest singular value in the literature (e.g. , , , , , , ). There are two basic means to obtain such bounds, namely via Littlewood-Offord theorems and via Berry-Esséen-type central limit theorems. We will rely solely on the second route (cf. , [36, Section 2.3]).

Let $n\geq 1$, let $F$ be the real or complex field, let $A$ be an $n\times n$ $F$-valued invertible matrix with columns $X_{1},\ldots,X_{n}$, and let $R_{1},\ldots,R_{n}$ denote the rows of $A^{-1}$. Then for any $1\leq i\leq n$, we have

where $V_{i}$ is the hyperplane spanned by $X_{1},\ldots,X_{i-1},X_{i+1},\ldots,X_{n}$.

One can directly verify this lemma using the identity $AA^{-1}=I$. It is also the special case $s=1$ of Lemma 3.3.

By Lemma 5.1, the desired proposition is equivalent to the lower tail estimate

where $d_{i}:=\operatorname{dist}(X_{i},V_{i})$, $X_{i}:=X_{i}(\xi)$, $V_{i}:=\operatorname{Span}(X_{1},\ldots,X_{i-1},X_{i+1},\ldots,X_{n})$.

To start, we first study the distribution of $d_{1}$. Let us temporarily condition on (i.e. freeze) the vectors $X_{2},\ldots,X_{n}$, leaving $X_{1}$ random, and let $(v_{1},\ldots,v_{n})$ be a unit normal vector to the hyperplane spanned by $X_{2},\ldots,X_{n}$. Applying Proposition 3.5, we see that with probability $1-\exp(-n^{\Omega(1)})$, we have $\max_{1\leq i\leq n}|v_{i}|\leq n^{-c}$ for some absolute constant $c>0$. Suppose that this event occurs. If we write $X_{1}=(\xi_{1},\ldots,\xi_{n})$, where $\xi_{1},\ldots,\xi_{n}$ are iid copies of $\xi$, then we have

setting ${\varepsilon}:=n^{-c/4}$ we conclude

Notice that a slight modification of the above argument also yields the following corollary:

Let $X_{1},\dots,X_{n}$ be random vectors whose entries are iid copies of $\xi$. Then the distribution of the distance $d_{1}$ from $X_{1}$ to $\operatorname{Span}(X_{2},\dots,X_{n})$ is approximately gaussian, in the sense that

A naive application of the union bound to (27) is clearly insufficient to establish (26), since we have $d$ distances to deal with. However, we can at least use that bound to show that

The key fact that enables us to overcome the ineffectiveness of the union bound is that the distances $d_{i}$ are correlated. They tend to be large or small at the same time. Quantitatively, we have

Let $n\geq 1$, let $F$ be the real or complex field, let $A$ be an $n\times n$ $F$-valued invertible matrix with columns $X_{1},\ldots,X_{n}$, and let $d_{i}:=\operatorname{dist}(X_{i},V_{i})$ denote the distance from $X_{i}$ to the hyperplane $V_{i}$ spanned by $X_{1},\ldots,X_{i-1},X_{i+1},\ldots,X_{n}$. Let $1\leq L<j\leq n$, let $V_{L,j}$ denote the orthogonal complement of the span of $X_{L+1},\ldots,X_{j-1},X_{j+1},\ldots,X_{n}$, and let $\pi_{L,j}:F^{n}\to V_{L,j}$ denote the orthogonal projection onto $V_{L,j}$. Then

We are going to prove this lemma in Appendix C.

Fix $L=\lfloor n^{20/C_{0}}\rfloor$ and $t:=n^{-21/C_{0}}$; then (if $C_{0}$ is sufficiently large compared with $c$) we have

To control the other distances $d_{j}$ for $L<j\leq n$, we use Lemma 5.3, which gives the lower bound

where $\pi_{L,j}$ is the orthogonal projection to the $L+1$-dimensional space $V_{L,j}$ orthogonal to $X_{L+1},\ldots,X_{j-1},X_{j+1},\ldots,X_{n}$.

(say) for all $1\leq i\leq L<j\leq n$. By the union bound, we thus have

(say). If the events in (28), (30) both occur, then we conclude from (29) that

for all $L<j\leq n$, and (26) follows. The proof of Proposition 3.2 is complete.

Extensions of Theorem 1.3

In this section, we describe several extension of Theorem 1.3, mentioned briefly at the end of the introduction. As an application, we show that our results determine the distribution of the condition number of $M_{n}(\xi)$, extending results of Edelman from .

Then a routine modification of the proof of Theorem 1.3 gives

Let $F$ be the real or complex field, let $\xi$ be $F$-normalized, and suppose ${\mathbf{E}}|\xi|^{C_{0}}<\infty$ for some sufficiently large absolute constant $C_{0}$. If $c>0$ is a sufficiently small absolute constant, then we have

for all $1\leq k\leq n^{c}$ and all measurable $\Omega\in F^{k}$, where $\partial_{n^{-c}}\Omega$ is the set of all points in $F^{k}$ which lie within $n^{-c}$ (in $l^{\infty}$ norm) of the topological boundary of $\Omega$.

Indeed, one simply repeats the arguments for Theorem 1.3 (which is basically the $k=1$ case) but acquires losses of $k^{O(1)}$ throughout the argument, which will be acceptable if we force $k$ to be a sufficiently small power of $n$, and if one shrinks $c$ as necessary; we omit the details.

Figure 3 shows the joint distribution of the smallest two singular values for Bernoulli and gaussian distributions.

Figure 4 plots the functions ${\mathbf{P}}(\sqrt{n}\sigma_{n-k}(M_{n}(\xi))\leq x)$, where $k=0,1,2$, for Bernoulli and gaussian distributions.

4. Rectangular matrices

We can use our method to consider the least singular value of a rectangular matrix of the dimension $(n-l)\times n$, where $l$ is a constant. In fact, we can reduce this problem to the square case by adding a (dummy) set of $l$ rows vectors which form an orthonormal complement of the $n-l$ row vectors of the matrix. We consider these dummy vectors as the first $l$ vectors of the (now square) matrix and repeat the proof. The additional vectors remain the same after the projection and by removing them we obtain an $(s-l)\times s$ matrix which is asymptotically gaussian. Thus, we will be able to compare the least singular value of the original matrix with this one.

The limiting distribution of the least singular value of $(n-l)\times n$ random matrices with gaussian entries (for $l$ constant) can be computed, at least in principle. However, we cannot find a reference for this. Thus, we are going to phrase the result here in the spirit of Remark 3.6. To this end, $M_{n-l,n}(\xi)$ denotes the $(n-l)\times n$ random matrix whose entries are iid copies of $\xi$.

Figure 5 plots the functions ${\mathbf{P}}(\sqrt{n}\sigma_{n-k}(M_{n}(\xi))\leq x)$, where $k=0,1,2$, for Bernoulli and gaussian distributions.

To conclude this section, let us mention two important recent results. In , Rudelson and Vershynin obtained strong tail estimates for the smallest singular value of random rectangular matrices of all possible sizes. In Feldheim and Sodin considered the case when $l$ is large, $l=\Theta(n)$ and proved universality for the distribution of the least singular value of random matrices with entries having sub-gaussian tails. (In this case the least singular value is large, of order $\Theta(\sqrt{n})$, with high probability.)

6. Random matrices with not necessarily identical entries

All results hold if we drop the condition that the entries of $M_{n}$ have the same distribution. In the proofs, it is only important that the these entries are all normalized, independent, and their $C_{0}$-moment is uniformly bounded. The fact that they are iid copies of $\xi$ has not played any important role. The only place where this information was used is in the paragraph following Lemma 3.3 (this allows one to fix the random rows of $B$ to be the first $s$). But we can easily avoid this by conditioning on the choice of the rows of $B$. Thus we have the following extension of Theorem 1.3.

The reader is invited to formalize the extensions of the results in the previous two subsections regarding joint distribution of the least $k$-singular values and rectangular matrices.

Figure 6 shows an empirical demonstration of this theorem.

8. Distribution of the condition number

Let $M$ be an $n\times n$ matrix, its condition number $\kappa(M)$ is defined as

Motivated by an earlier study of von Neuman and Goldstein , Edelman studied the distribution of $\kappa(M_{n}(\xi))$ when $\xi$ is gaussian. His results can be extended for the general setting in this paper, thanks to Theorem 1.3 and the well known fact that the largest singular value $\sigma_{1}(M_{n}(\xi))$ is concentrated strongly around $2\sqrt{n}$.

Under the setting of Theorem 1.3, we have, with probability $1-\exp(-n^{\Omega(1)})$, $\sigma_{1}(M_{n}(\xi))=(2+o(1))\sqrt{n}$.

One can prove this lemma by combining [5, Theorem 5.8] with the tools in Appendix F or by following the arguments in . See also for references.

Appendix A Estimating singular values via random sampling

Let $1\leq s\leq n$ be integers. $A$ be an $n\times n$ real or complex matrix with rows $R_{1},\ldots,R_{n}$. Let $k_{1},\ldots,k_{s}\in\{1,\ldots,n\}$ be selected independently and uniformly at random, and let $B$ be the $s\times n$ matrix with rows $R_{k_{1}},\ldots,R_{k_{s}}$. Then

Let $a_{ij}$ denote the coefficients of $A$, thus $R_{i}=(a_{i1},\ldots,a_{in})$. For $1\leq i\leq j$, the $ij$ entry of $A^{*}A-\frac{n}{s}B^{*}B$ is given by

For $l=1,\ldots,s$, the random variables $\overline{a_{k_{l}i}}a_{k_{l}j}$ are iid with mean $\frac{1}{n}\sum_{k=1}^{n}\overline{a_{ki}}a_{kj}$ and variance

and so the random variable (33) has mean zero and variance $\frac{n^{2}}{s}V_{ij}$. Summing over $i,j$, we conclude that

Discarding the second term in (34) we conclude

Performing the $i,j$ summations, we obtain the claim. ∎

Combining this lemma with the Hoefmann-Wielandt theorem (Lemma B.1) we conclude that

Now observe that if $s\leq\sqrt{n}$, then by the standard birthday paradox computationOne could remove this condition $s\leq\sqrt{n}$ by reworking the second moment computation in Lemma A.1 when $k_{1},\ldots,k_{s}$ are sampled with replacement (and thus have some slight correlation with each other), but we will not do so here since in our applications $s$ will be a small power of $n$., the rows $k_{1},\ldots,k_{s}$ are distinct with probability $\Omega(1)$. Conditioning on this event, we thus see that if $k_{1},\ldots,k_{s}$ are sampled from $\{1,\ldots,n\}$ without replacement, that

The inequality (35) is valid for deterministic matrices $A$. If $A$ is a random matrix (with the $k_{1},\ldots,k_{s}$ being sampled independently of $A$), then we may take expectations of (35) for each instance of $A$ and conclude that

Now assume that the random matrix $A$ is row-exchangeable, i.e. the distribution of $A$ is stationary with respect to row permutations $R_{i}\leftrightarrow R_{j}$. For fixed and distinct $k_{1},\ldots,k_{s}\in\{1,\ldots,n\}$, the distribution of $\sum_{i=1}^{n}(\sigma_{i}(A)^{2}-\frac{n}{s}\sigma_{i}(B)^{2})^{2}$ is independent of the choice of $k_{1},\ldots,k_{s}$. Crudely bounding $|R_{k}|$ by $\max_{1\leq k\leq n}|R_{k}|$, we conclude

Let $s,n$ be integers with $1\leq s\leq\sqrt{n}$, let $A$ be a row-exchangeable random $n\times n$ matrix with rows $R_{1},\ldots,R_{n}$, and let $B$ be the $s\times n$ matrix with rows $R_{1},\ldots,R_{s}$. Then

One could use row-exchangeability here to instead simplify ${\mathbf{E}}\sum_{k=1}^{n}|R_{k}|^{4}$ as $n{\mathbf{E}}|R_{1}|^{4}$, but it will turn out that this will not be useful for us, as we will need to truncate $\max_{1\leq k\leq n}|R_{k}|$ in any event in order to assure that ${\mathbf{E}}|R_{1}|^{4}$ is bounded.

In our applications, $A$ is going to be the inverse of $M_{n}(\xi)$ (after conditioning away some bad but rare events in which $M_{n}(\xi)$ is close to degenerate), and the summand of most interest on the left-hand side is the $i=1$ summand. We expect $\sigma_{1}(A)$ to be of size about $\sqrt{n}$, and we also expect the $|R_{k}|$ to have size about $O(1)$ (thanks to Lemma 5.1 and basic heuristics about the distance between a random vector and a random hyperplane). So, as soon as $s$ is a non-trivial power of $n$, we expect Corollary A.2 to yield an approximation of the form (11).

Appendix B Linear algebra

In this appendix we collect various basic facts from linear algebra which we will rely upon in this paper. We begin with the Hoeffman-Wielandt theorem, which controls the variation of singular values of a matrix using the Frobenius norm.

For any two $n\times n$ self-adjoint matrices $M,M^{\prime}$, we have

As a corollary, for any two $n\times n$ matrices $A,B$, we have

It suffices to prove the first inequality, which we rewrite as

for self-adjoint $M,N$. By the fundamental theorem of calculus (or a compactness argument) and the triangle inequality in $l^{2}$, it suffices to show the infinitesimal version

of this inequality for fixed $M,N$ and sufficiently small ${\varepsilon}>0$. But if we diagonalise $M$, the left-hand side can be computed (up to errors of $o({\varepsilon})$) as ${\varepsilon}$ times the $l^{2}$ norm of the diagonal of $N$, and the claim follows. ∎

for any $m\times n$ matrices $A,B$. Another easy corollary of the minimax characterization is

Let $A$ be an $m\times n$ matrix, and let $A^{\prime}$ be a $r\times n$ matrix formed by taking $r$ of the $m$ rows of $A$. Then

for all $1\leq j\leq\min(r,n)$, with the convention that $\sigma_{j}(A)=0$ for $j>\min(m,n)$.

Next, we prove the elementary but crucial projection lemma (Lemma 3.3) that relates a random sample of an inverse matrix, to a randomly projected version of the original matrix. For the reader’s convenience, we restate this lemma.

Let $1\leq s\leq n$ be integers, let $F$ be the real or complex field, let $A$ be an $n\times n$ $F$-valued invertible matrix with columns $X_{1},\ldots,X_{n}$, and let $R_{1},\ldots,R_{n}$ denote the rows of $A^{-1}$. Let $B$ be the $s\times n$ matrix with rows $R_{1},\ldots,R_{s}$. Let $V$ be the $s$-dimensional subspace of $F^{n}$ formed as the orthogonal complement of the span of $X_{s+1},\ldots,X_{n}$, which we identify with $F^{s}$ via an orthonormal basis, and let $\pi:F^{n}\to F^{s}$ be the orthogonal projection to $V\equiv F^{s}$. Let $M$ be the $s\times s$ matrix with columns $\pi(X_{1}),\ldots,\pi(X_{s})$. Then $M$ is invertible, and we have

By construction, we have $R_{i}\cdot X_{j}=\delta_{ij}$ for all $1\leq i,j\leq n$. In particular, $R_{1},\ldots,R_{s}$ lie in $V$, and

for $1\leq i,j\leq s$. Thus $M$ is invertible, and the rows of $M^{-1}$ are given by $\pi(R_{1}),\ldots,\pi(R_{s})$. Thus the $ij$ entry of $(M^{-1})(M^{-1})^{*}$ is given by $\pi(R_{i})\cdot\pi(R_{j})$, while the $ij$ entry of $BB^{*}$ is given by $R_{i}\cdot R_{j}$. Since $R_{1},\ldots,R_{s}$ lie in $V$, and $\pi$ is an isometry on $V$, the claim follows. ∎

Appendix C Correlation between distances

Let $n\geq 1$, let $F$ be the real or complex field, let $A$ be an $n\times n$ $F$-valued invertible matrix with columns $X_{1},\ldots,X_{n}$, and let $d_{i}:=\operatorname{dist}(X_{i},V_{i})$ denote the distance from $X_{i}$ to the hyperplane $V_{i}$ spanned by $X_{1},\ldots,X_{i-1},X_{i+1},\ldots,X_{n}$. Let $1\leq L<j\leq n$, let $V_{L,j}$ denote the orthogonal complement of the span of $X_{L+1},\ldots,X_{j-1},X_{j+1},\ldots,X_{n}$, and let $\pi_{L,j}:F^{n}\to V_{L,j}$ denote the orthogonal projection onto $V_{L,j}$. Then

In practice, we will be able to get good upper and lower bounds on $|\pi_{L,j}(X_{i})|$. The above lemma asserts that as long as the $d_{1},\ldots,d_{L}$ are bounded away from zero, all the other $d_{j}$ will also be bounded away from zero.

By relabeling we may take $j=L+1$. For $1\leq i\leq L+1$, write $Y_{i}:=\pi_{L,L+1}(X_{i})\in V_{L,j}$. By applying $\pi_{L,L+1}$ to both $X_{i}$ and $V_{i}$, we see that $d_{i}$ is the distance from $Y_{i}$ to $Y_{1},\ldots,Y_{i-1},Y_{i+1},\ldots,Y_{L+1}$ for any $1\leq i\leq L+1$. Since $V_{L,j}$ is isomorphic to $F^{L+1}$, we see (on replacing $n$ with $L+1$, and $X_{i}$ with $Y_{i}\in V_{L,j}\equiv F^{L+1}$) that we may assume that $L+1=n$, thus $\pi_{L,j}$ is trivial and our task is now to show that

Let $R_{1},\ldots,R_{n}$ be the rows of $A^{-1}$. By Corollary 5.1, $d_{i}=1/|R_{i}|$, so our task is now to show that

On the other hand, observe (since $R_{1},\ldots,R_{n}$ is a dual basis to $X_{1},\ldots,X_{n}$) that the vector

is orthogonal to $X_{1},\ldots,X_{n-1}$ and has an inner product of $1$ with $X_{n}$, and thus must equal $R_{n}$. By the triangle inequality and Cauchy-Schwarz we thus obtain the claim. ∎

Appendix D Berry-Esseen type results

Let us first state the classical Berry-Esséen central limit theorem (see e.g. ):

where the implied constant depends on the third moment ${\mathbf{E}}|\xi|^{3}$ of $\xi$. In particular, by (37) we have

Next, we prove the key Proposition 3.4, which can be seen as a high-dimensional extension of Proposition D.1. Let us restate this proposition for the reader’s convenience.

Let $1\leq N\leq n$, let $F$ be the real or complex field, and let $\xi$ be $F$-normalized and have finite third moment ${\mathbf{E}}|\xi|^{3}<\infty$. Let $v_{1},\ldots,v_{n}\in F^{N}$ be a normalized tight frame for $F^{N}$, or in other words

where $I_{N}$ is the identity matrix on $F^{N}$. Let $S\in F^{N}$ denote the random variable

where $\xi_{1},\ldots,\xi_{n}$ are iid copies of $\xi$. Similarly, let $G:=({\mathbf{g}}_{F,1},\ldots,{\mathbf{g}}_{F,N})\in F^{N}$ be formed from $N$ iid copies of ${\mathbf{g}}_{F}$. Then for any measurable set $\Omega\subset F^{N}$ and any ${\varepsilon}>0$, one has