Random covariance matrices: Universality of local statistics of eigenvalues

Introduction

The main purpose of this paper is to study the asymptotic local eigenvalue statistics of covariance matrices of large random matrices. Let us first fix the matrix ensembles that we will be studying.

Let $n$ be a large integer parameter going off to infinity, and let $p=p(n)$ be another integer parameter such that $p\leq n$ and $\lim_{n\to\infty}p/n=y$ for some $0<y\leq 1$. We let $M=M_{n,p}=(\zeta_{ij})_{1\leq i\leq p,1\leq j\leq n}$ be a random $p\times n$ matrix, whose distribution is allowed to depend on $n$. We say that the matrix ensemble $M$ obeys condition C1 with some exponent $C_{0}\geq 2$ if the random variables $\zeta_{ij}$ are jointly independent, have mean zero and variance $1$, and obey the moment condition $\sup_{i,j}{\mathbf{E}}|\zeta_{ij}|^{C_{0}}\leq C$ for some constant $C$ independent of $n,p$. We say that the matrix $M$ is i.i.d. if the $\zeta_{ij}$ are identically and independently distributed with law independent of $n,p$.

Given such a matrix, we form the $n\times n$ covariance matrix $W=W_{n,p}:=\frac{1}{n}M^{\ast}M$. This matrix has rank $p$ and so the first $n-p$ eigenvalues are trivial; we order the (necessarily positive) remaining eigenvalues of these matrices (counting multiplicity) as

We often abbreviate $\lambda_{i}(W)$ as $\lambda_{i}$.

Note that the only distributional hypothesis we require on the entries $\zeta_{ij}$, besides the crucial joint independence hypothesis, are moment conditions. In particular, we make no distinction between continuous and discrete distributions here.

In this paper, we will focus primarily on the case $y=1$, but several of our results extend to other values of $y$ as well. The case $p>n$ can be easily deduced from the $p<n$ case after some minor notational changes by transposing the matrix $M$, which does not affect the nontrivial eigenvalues of the covariance matrix. One can also easily normalise the variance of the entries to be some other quantity $\sigma^{2}$ than $1$ if one wishes. Observe that the quantities $\sigma_{i}:=\sqrt{n}\lambda_{i}^{1/2}$ can be interpreted as the nontrivial singular values of the original matrix $M$, and $\lambda_{1},\ldots,\lambda_{p}$ can also be interpreted as the eigenvalues of the $p\times p$ matrix $\frac{1}{n}MM^{\ast}$. It will be convenient to exploit all three of these spectral interpretations of $\lambda_{1},\ldots,\lambda_{p}$ in this paper. condition C1 is analogous to condition C0 for Wigner-type matrices in TVlocal1 , but with the exponential decay hypothesis relaxed to polynomial decay only.

The well-known Marchenko–Pastur law governs the bulk distribution of the eigenvalues $\lambda_{1},\ldots,\lambda_{p}$ of $W$:

Assume condition C1 with $C_{0}>2$, and suppose that $p/n\to y$ for some $0<y\leq 1$. Then for any $x>0$, the random variables

When furthermore $M$ is i.i.d., one can also obtain the case $C_{0}=2$.

For the case $C_{0}\geq 4$, see marchenko , pastur ; for the case $C_{0}>2$, see wachter ; for the $C_{0}=2$ i.i.d. case, see yin . Further results are known on the rate of convergence: see gotze .

In this paper, we are concerned instead with the local eigenvalue statistics. A model case is the (complex) Wishart ensemble, in which the $\zeta_{ij}$ are i.i.d. variables which are complex Gaussians with mean zero and variance $1$. In this case, the distribution of the eigenvalues $(\lambda_{1},\ldots,\lambda_{n})$ of $W$ can be explicitly computed (as a special case of the Laguerre unitary ensemble). For instance, when $p=n$, the joint distribution is given by the density function

for some explicit normalization constant $c(n)$ whose exact value is not important for this discussion.

Very similarly to the GUE case, one can use this explicit formula to directly compute several local statistics, including the distribution of the largest and smallest eigenvalues edelman , the correlation functions nw etc. Also in similarity to the GUE case, it is widely conjectured that these statistics hold for a much larger class of random matrices. For some earlier results in this direction, we refer to soshnikov , TVhard , BenP , FS and the references therein.

The goal of this paper is to establish a Four Moment theorem for random covariance matrices, as an analogue of a recent result in TVlocal1 . Roughly speaking, this theorem asserts that the asymptotic behaviour of local statistics of the eigenvalues of $W_{n}$ are determined by the first four moments of the entries.

2 The Four Moment theorem

To state the Four Moment theorem, we first need a definition.

We say that two complex random variables $\zeta$, $\zeta^{\prime}$ match to order $k$ for some integer $k\geq 1$ if one has ${\mathbf{E}}{\operatorname{Re}}(\zeta)^{m}{\operatorname{Im}}(\zeta)^{l}={\mathbf{E}}{\operatorname{Re}}(\zeta^{\prime})^{m}{\operatorname{Im}}(\zeta^{\prime})^{l}$ for all $m,l\geq 0$ with $m+l\leq k$.

For sufficiently small $c_{0}>0$ and sufficiently large $C_{0}>0$ ($C_{0}=10^{4}$ would suffice) the following holds for every $0<{\varepsilon}<1$ and $k\geq 1$. Let $M=(\zeta_{ij})_{1\leq i\leq p,1\leq j\leq n}$ and $M^{\prime}=(\zeta^{\prime}_{ij})_{1\leq i\leq p,1\leq j\leq n}$ be matrix ensembles obeying condition C1 with the the indicated constant $C_{0}$, and assume that for each $i,j$ that $\zeta_{ij}$ and $\zeta^{\prime}_{ij}$ match to order $4$. Let $W,W^{\prime}$ be the associated covariance matrices. Assume also that $p/n\to y$ for some $0<y\leq 1$.

Then for any ${\varepsilon}p\leq i_{1}<i_{2}<\cdots<i_{k}\leq(1-{\varepsilon})p$, and for $n$ sufficiently large depending on ${\varepsilon},k,c_{0}$ we have

If $\zeta_{ij}$ and $\zeta^{\prime}_{ij}$ only match to order $3$ rather than $4$, the conclusion (5) still holds provided that one strengthens (4) to

This is an analogue of TVlocal1 , Theorem 15, for covariance matrices, with the main difference being that the exponential decay condition from TVlocal1 , Theorem 15, has been weakened to the high moment condition in C1. This is achieved by an “exponential decay removing trick” that relies on using a truncated version of the four moment theorem to extend the range of validity of a key “gap condition” that is used in the proof of the above theorem. The same trick also allows one to obtain a similar strengthening of the main results of TVlocal1 , TVlocal2 , thus relaxing the exponential decay hypotheses in those results to high moment conditions. The value $C_{0}=10^{4}$ is ad hoc, and we make no attempt to optimize this constant.

As observed in ERSTVY , the requirement that the moments of $\zeta_{ij}$ and $\zeta^{\prime}_{ij}$ match exactly can be relaxed slightly. Indeed, to obtain the desired conclusions, it suffices to require that for $k=1,2,3,4$, the $k$th moments of $\zeta_{ij}$ and $\zeta^{\prime}_{ij}$ differ by $O(n^{-(4-k)/2-\delta})$ for some $\delta>0$ independent of $n$. Indeed, if one inspects the proof of the four moment theorem, and specifically the step in which one performs a Taylor expansion argument to understand the effect of exchanging a single entry $\zeta_{ij}$ with $\zeta^{\prime}_{ij}$ on the expectations in (5) (see TVlocal1 , Section 3.2), the above near-matching property is sufficient to ensure that this effect has magnitude $O(n^{-2-c})$ for some $c>0$, and so the net effect on (5) after performing $O(n^{2})$ such exchange operations is acceptable. We omit the details. This relaxed version of the four moment theorem is particularly useful for dealing with Bernoulli distributions, which are completely determined by their first four moments; see ERSTVY for further discussion.

3 Applications

One can apply Theorem 5 in a similar way as its counterpart TVlocal1 , Theorem 15, in order to obtain universality results for large classes of random matrices. In many cases, one can combine this theorem with existing partial results for special ensembles to remove some of the moment assumptions. Let us demonstrate this through an example concerning the universality of the sine kernel.

Using the explicit formula (3), Nagao and Wadati nw established the following result for the complex Wishart ensemble, which roughly speaking asserts that the spectrum of such an ensemble enjoys sine kernel statistics in the neighborhood of any bulk energy level $0<u<4$.

where $K(x,y):=\frac{\sin(\pi(x-y))}{\pi(x-y)}$ is the sine kernel.

The results in nw allowed $f$ to be bounded measurable rather than continuous, but when we consider discrete ensembles later, it will be important to keep $f$ continuous.

Returning to the bulk, the following extension was established by Ben Arous and Peché BenP , as a variant of Johansson’s result Joh1 for random hermitian matrices. We say that a complex random variable $\zeta$ of mean zero and variance one is Gauss divisible if $\zeta$ has the same distribution as $\zeta=(1-t)^{1/2}\zeta^{\prime}+t^{1/2}\zeta^{\prime\prime}$ for some $0<t<1$ and some independent random variables $\zeta^{\prime}$, $\zeta^{\prime\prime}$ of mean zero and variance $1$, with $\zeta^{\prime\prime}$ distributed according to the complex Gaussian.

BenP Theorem 8 [which is for the Wishart ensemble and for $p=n+O(1)$] can be extended to the case when $p=n+O(n^{43/48})$ (so $y$ is still $1$), and when $M$ is an i.i.d. matrix obeying condition C1 with $C_{0}=2$, and with the $\zeta_{ij}$ gauss divisible.

Using Theorem 5 and Theorem 10 (in exactly the same way we used TVlocal1 , Theorem 15, and Johansson’s theorem Joh1 to establish TVlocal1 , Theorem 11), we can extend Theorem 10 from the gauss divisible case to a more general situation.

Theorem 8 can be extended to the case when $p=n+O(n^{43/48})$ (so $y$ is still $1$), and when $M$ is an i.i.d. matrix obeying condition C1 with $C_{0}$ sufficiently large ($C_{0}=10^{4}$ would suffice), and where the real and imaginary parts of $\zeta_{ij}$ are i.i.d. and are supported on at least three points.

(Sketch) It was shown in TVlocal1 , Corollary 30, that if the real and imaginary parts of a complex random variable $\zeta$ were independent with mean zero and variance one, and both were supported on at least three points, then $\zeta$ matched to order $4$ with a gauss divisible random variable $\zeta^{\prime}$ with finite $C_{0}$ moment (indeed, if one inspects the convexity argument used to solve the moment problem in TVlocal1 , Lemma 28, the Gauss divisible random variable could be taken to be the sum of a Gaussian variable and a discrete variable, and in particular is thus exponentially decaying). If one lets $M^{\prime}$ be the i.i.d. matrix whose coefficients have entries $\zeta^{\prime}$, then Theorem 10 asserts that the conclusions of Theorem 8 hold for $M^{\prime}$. Using Theorem 5 exactly as in the proof of TVlocal1 , Theorem 11, (and approximating $f$ uniformly by smooth functions), we conclude that the conclusions of Theorem 8 hold for $M$ also.

One can also extend the above argument to cover cases in which the real and imaginary parts of $\zeta_{ij}$ are not i.i.d. by an analysis of the moment matching problem for complex random variables (and in particular, by extending the three-moment analysis in Lemma 34 below to four moments), but we will not do so here.

The arguments in this paper will be a nonsymmetric version of those in TVlocal1 . The arguments in TVlocal1 started with analyzing the stability of the eigenvalue equation $Mv_{i}=\lambda_{i}v_{i}$ where $M$ is a random Hermitian matrix and $\lambda_{i}$ is the $i$th eigenvalue with eigenvector $v$. For the situation considered in this paper, it is tempting to similarly analyze the eigenvalue equation $Wv_{i}=\lambda_{i}v_{i}$ for the covariance matrix $W$. However, this does not work, since the covariance matrix $W$, while random, does not have independent entries. The new idea here is to work with a system of two equations

where $u_{i}$ and $v_{i}$ are the left and right singular vectors of $M$. This leads to a number of technical issues that need to be addressed through the paper.

One can combine the singular value equations (7), (8) into a single eigenvalue equation

where ${\mathbf{M}}$ is the augmented matrix

4 Extensions

In a very recent work, Erdős et al. ESYY extendedEven more recently, a similar result was also established by Péché peche . Theorem 10 to a large class of matrices, assuming that the distribution of the entries $\zeta_{ij}$ is sufficiently smooth and obeys a log-Sobolev inequality. While their results do not apply for entries with discrete distributions, it allows one to extend Theorem 10 to the case when $t$ is a negative power of $n$. Given this, one can use the argument in ERSTVY to remove the requirement that the real and imaginary parts of $\zeta_{ij}$ be supported on at least three points.

We can also have the following analogue of ERSTVY , Theorem 2.

for all symmetric test functions $f$. (If $W$ is a discrete ensemble, one has to interpret $p_{n}^{(k)}$ as a distribution or a probability measure rather than as a function.)

The detailed proof of Theorem 12 are essentially the same as the proof of ERSTVY , Theorem 2, and is omitted.

The four moment theorem controls the distribution of individual eigenvalues (or singular values) $\lambda_{i}$ , but as indicated above, this control can then be used to obtain control of correlation expressions such as (12). The local relaxation flow methods developed in ESY1 , ESY2 , ESY3 , ERSY , ERSY2 , ESYY , by contrast, are focused on individual energy levels $u$ rather than individual eigenvalues. As such, they provide an alternate approach to controlling correlation expressions such as (12), but we do not know how to convert such information back to control on individual eigenvalues or singular values in general, because the standard deviation of each eigenvalue can exceed (by a logarithmic factor, see Gus ) the scale of the mean eigenvalue spacing, which is the scale at which the correlation estimates operate at.

5 Notation

We write $\sqrt{-1}$ for the complex imaginary unit, in order to free up the letter $i$ to denote an integer (usually between $1$ and $n$).

We write $\|X\|$ for the length of a vector $X$, $\|A\|=\|A\|_{op}$ for the operator norm of a matrix $A$, and $\|A\|_{F}=\operatorname{tr}(AA^{*})^{1/2}$ for the Frobenius (or Hilbert–Schmidt) norm.

We will need to quantify the intuitive assertion that a given event $E$ occurs “frequently,” as follows.

TVlocal1 Let $E$ be an event depending on $n$.

$E$ holds with high probability if ${\mathbf{P}}(E)\geq 1-O(n^{-c})$ for some constant $c>0$ (independent of $n$).

$E$ holds with overwhelming probability if ${\mathbf{P}}(E)\geq 1-O_{C}(n^{-C})$ for every constant $C>0$.

$E$ holds almost surely if ${\mathbf{P}}(E)=1$.

The gap property and the exponential decay removing trick

The following property, which roughly speaking asserts that unexpectedly small eigenvalue spacings are rare, plays an important role in proving the main results of TVlocal1 .

Let $M$ be a matrix ensemble obeying condition C1. We say that $M$ obeys the gap property if for every ${\varepsilon},c>0$ (independent of $n$), and for every ${\varepsilon}p\leq i\leq(1-{\varepsilon})p$, one has $|\lambda_{i+1}(W)-\lambda_{i}(W)|\geq n^{-1-c}$ with high probability. (The implied constants in this statement are allowed to depend on ${\varepsilon}$ and $c$.)

In the Wigner case, it was shown that exponential decay of the atom distribution implied the gap property, and the gap property was then used to establish deduce the four moment theorem from a “truncated four moment theorem.” As it turns out, the proof of this latter theorem does not require exponential decay of the atom distribution, relying instead on the weaker hypothesis that a sufficiently high moment of the atom distribution is finite. A new technical observation of this paper is that one can use the truncated four moment theorem to extend the gap property from exponentially decaying atom distributions to distributions with sufficiently high moments finite, and as a consequence we can extend the full Four Moment theorem to this case also.

We turn to the details. First, as an analogue of TVlocal1 , Theorem 19, we prove the following theorem, using a slight modification of the method in TVlocal1 .

Let $M=(\zeta_{ij})_{1\leq i\leq p,1\leq j\leq n}$ obey condition C1 for some $C_{0}$, and suppose that the coefficients $\zeta_{ij}$ are exponentially decaying in the sense that ${\mathbf{P}}(|\zeta_{ij}|\geq t^{C})\leq\exp(-t)$ for all $t\geq C^{\prime}$ for all $i,j$ and some constants $C$, $C^{\prime}>0$. Then $M$ obeys the gap property.

Next, we have the following analogue of TVlocal1 , Theorem 15.

For sufficiently small $c_{0}>0$ and sufficiently large $C_{0}>0$ ($C_{0}=10^{4}$ would suffice) the following holds for every $0<{\varepsilon}<1$ and $k\geq 1$. Let $M=(\zeta_{ij})_{1\leq i\leq p,1\leq j\leq n}$ and $M^{\prime}=(\zeta^{\prime}_{ij})_{1\leq i\leq p,1\leq j\leq n}$ be matrix ensembles obeying condition C1 with the indicated constant $C_{0}$, and assume that for each $i,j$ that $\zeta_{ij}$ and $\zeta^{\prime}_{ij}$ match to order $4$. Let $W,W^{\prime}$ be the associated covariance matrices. Assume also that $M$ and $M^{\prime}$ obeys the gap property, and that $p/n\to y$ for some $0<y\leq 1$.

Then for any ${\varepsilon}p\leq i_{1}<i_{2}<\cdots<i_{k}\leq(1-{\varepsilon})p$, and for $n$ sufficiently large depending on ${\varepsilon},k,c_{0}$ we have

If $\zeta_{ij}$ and $\zeta^{\prime}_{ij}$ only match to order $3$ rather than $4$, the conclusion (13) still holds provided that one strengthens (12) to

This theorem is weaker than Theorem 5, as we assume the gap property. Besides the fact that we consider singular values here instead of eigenvalues, the main difference between this result and TVlocal1 , Theorem 15, is that in the latter we assume exponential decay rather than the gap property. However, this difference is only a formality, since in the proof of TVlocal1 , Theorem 15, the only place we used exponential decay is to prove the gap property (via TVlocal1 , Theorem 19).

The core of the proof of Theorem 17 is a truncated four moment theorem (Theorem 32), which allows us to insert information such as the gap property into the test function $G$.

By combining Theorem 17 with Theorem 16, we obtain Theorem 5 in the case when the coefficients $\zeta_{ij}$ are exponentially decaying. To remove the exponential decay hypothesis, we will apply the truncated four moment theorem (Theorem 32) a second time, together with a moment matching argument (Lemma 34) to eliminate this hypothesis from Theorem 16.

Assume that $M=(\zeta_{ij})_{1\leq i\leq p,1\leq j\leq n}$ satisfies condition C1 with $C_{0}$ sufficiently large. Then $M$ obeys the gap property.

Theorem 5 follows directly from Theorems 17 and 18.

The rest of the paper is organized as follows. The next three sections are devoted to technical lemmas. The proofs of Theorems 17 and 18 are presented in Section 6, assuming Theorems 32 and 16. The proofs of these latter two theorems are presented in Sections 7 and 8, respectively.

The main technical lemmas

Important note. The arguments in this paper are very similar to, and draw heavily from, the previous paper TVlocal1 of the authors. We recommend therefore that the reader be familiar with that paper first, before reading the current one.

Furthermore, in the generic case the unit singular vectors $u_{i},v_{i}$ are determined up to multiplication by a complex phase $e^{i\theta}$.

We will establish the following Erdös–Schlein–Yau type delocalization theorem (analogous to TVlocal1 , Proposition 62), which is an essential ingredient to Theorems 17, 16 and is also of some independent interest.

Suppose that $p/n\to y$ for some $0<y\leq 1$, and let $M$ obey condition C1 for some $C_{0}\geq 2$. Suppose further that that $|\zeta_{ij}|\leq K$ almost surely for some $K>1$ (which can depend on $n$) and all $i,j$, and that the probability distribution of $M$ is continuous. Let ${\varepsilon}>0$ be independent of $n$. Then with overwhelming probability, all the unit left and right singular vectors of $M$ with eigenvalue $\lambda_{i}$ in the interval $[a+{\varepsilon},b-{\varepsilon}]$ [with $a,b$ defined in (2)] have all coefficients uniformly of size $O(Kn^{-1/2}\log^{10}n)$.

The factors $K\log^{10}n$ can probably be improved slightly, but anything which is polynomial in $K$ and $\log n$ will suffice for our purposes. Observe that if $M$ obeys condition C1, then each event $|\zeta_{ij}|\leq K$ with $K:=n^{10/C_{0}}$ (say) occurs with probability $1-O(n^{-10})$. Thus, in practice, we will be able to apply the above theorem with $K=n^{10/C_{0}}$ without difficulty. The continuity hypothesis is a technical one, imposed so that the singular values are almost surely simple, but in practice we will be able to eliminate this hypothesis by a limiting argument (as none of the bounds will depend on any quantitative measure of this continuity).

As with other proofs of delocalization theorems in the literature, Theorem 19 is in turn deduced from the following eigenvalue concentration bound (analogous to TVlocal1 , Proposition 60).

Let the hypotheses be as in Theorem 19, and let $\delta>0$ be independent of $n$. Then for any interval $I\subset[a+{\varepsilon},b-{\varepsilon}]$ of length $|I|\geq K^{2}\log^{20}n/n$, one has with overwhelming probability (uniformly in $I$) that

We remark that a very similar result (with slightly different hypotheses on the parameters and on the underlying random variable distributions) was recently established in ESYY , Corollary 7.2.

We isolate one particular consequence of Theorem 20 (also established in GZ ):

Let the hypotheses be as in Theorem 19. Then there exists ${\varepsilon}^{\prime}>0$ independent of $n$ such that with overwhelming probability, one has $a+{\varepsilon}^{\prime}\leq\lambda_{i}(W)\leq b-{\varepsilon}^{\prime}$ for all ${\varepsilon}p\leq i\leq(1-{\varepsilon})p$.

From Theorem 20, we see with overwhelming probability that the number of eigenvalues in $[a+{\varepsilon}^{\prime},b-{\varepsilon}^{\prime}]$ is at least $(1-{\varepsilon})p$, if ${\varepsilon}^{\prime}$ is sufficiently small depending on ${\varepsilon}$. The claim follows.

Basic tools

In this section, we recall some basic identities and inequalities from linear algebra which will be used in this paper.

We begin with the Cauchy interlacing law and the Weyl inequalities.

If $A_{n}$ is an $n\times n$ Hermitian matrix, and $A_{n-1}$ is an $n-1\times n-1$ minor, then $\lambda_{i}(A_{n})\leq\lambda_{i}(A_{n-1})\leq\lambda_{i+1}(A_{n})$ for all $1\leq i<n$.

If $M_{n,p}$ is a $p\times n$ matrix, and $M_{n,p-1}$ is an $p-1\times n$ minor, then $\sigma_{i}(M_{n,p})\leq\sigma_{i}(M_{n,p-1})\leq\sigma_{i+1}(M_{n,p})$ for all $1\leq i<p$.

If $p<n$, if $M_{n,p}$ is a $p\times n$ matrix, and $M_{n-1,p}$ is a $p\times n-1$ minor, then $\sigma_{i-1}(M_{n,p})\leq\sigma_{i}(M_{n-1,p})\leq\sigma_{i}(M_{n,p})$ for all $1\leq i\leq p$, with the understanding that $\sigma_{0}(M_{n,p})=0$. [For $p=n$, one can also use the transpose of (ii) instead.]

Claim (i) follows from the minimax formula

If $A,B$ are $n\times n$ Hermitian matrices, then $\|\lambda_{i}(A)-\lambda_{i}(B)|\leq\|A-B\|_{op}$ for all $1\leq i\leq n$.

If $M,N$ are $p\times n$ matrices, then $\|\sigma_{i}(M)-\sigma_{i}(N)|\leq\|M-N\|_{op}$ for all $1\leq i\leq p$.

This follows from the same minimax formulae used to establish Lemma 22.

One can also deduce the singular value versions of Lemmas 22, 23 from their Hermitian counterparts by using the augmented matrices (9). We omit the details.

We have the following elementary formula for a component of an eigenvector of a Hermitian matrix, in terms of the eigenvalues and eigenvectors of a minor.

This implies an analogous formula for singular vectors.

We just prove the first claim, as the second is proven analogously (or by taking adjoints). Observe that ${u\choose x}$ is a unit eigenvector of the matrix

with eigenvalue $\sigma_{i}(M_{p,n})^{2}$. Applying Lemma 25, we obtain

But $u_{j}(M_{p,n-1}^{\ast}M_{p,n-1})^{\ast}M_{p,n-1}^{\ast}=\sigma_{j}(M_{p,n-1})v_{j}(M_{p,n-1})^{\ast}$ for the $\min(p,n-1)$ nontrivial singular values (possibly after relabeling the $j$), and vanishes for trivial ones, and $\lambda_{j}(M_{p,n-1}^{\ast}M_{p,n-1})=\sigma_{j}(M_{p,n-1})^{2}$, so the claim follows.

The Stieltjes transform $s(z)$ of a Hermitian matrix $W$ is defined for complex $z$ by the formula

It has the following alternate representation (see, e.g., BS , Chapter 11).

Let $W=(\zeta_{ij})_{1\leq i,j\leq n}$ be a Hermitian matrix, and let $z$ be a complex number not in the spectrum of $W$. Then we have

By Schur’s complement, $\frac{1}{\zeta_{kk}-z-a_{k}^{\ast}(W_{k}-zI)^{-1}a_{k}}$ is the $k$th diagonal entry of $(W-zI)^{-1}$. Taking traces, one obtains the claim.

2 Tools from probability theory

We will rely frequently on the following concentration of measure result for projections of random vectors.

See TVlocal1 , Lemma 43; the proof is a short application of Talagrand’s inequality Le .

Delocalization

The purpose of this section is to establish Theorem 19 and Theorem 20. The material here is closely analogous to TVlocal1 , Sections 5.2, 5.3, as well as that of the original results in ESY1 , ESY2 , ESY3 and can be read independently of the other sections of the paper. The recent paper ESYY also contains arguments and results closely related to those in this section.

We begin by showing how Theorem 19 follows from Theorem 20. We shall just establish the claim for the right singular vectors $u_{i}$, as the claim for the left singular vectors is similar. We fix ${\varepsilon}$ and allow all implied constants to depend on ${\varepsilon}$ and $y$. We can also assume that $K^{2}\log^{20}n=o(n)$ as the claim is trivial otherwise.

As $M$ is continuous, we see that the nontrivial singular values are almost surely simple and positive, so that the singular vectors $u_{i}$ are well defined up to unit phases. Fix $1\leq i\leq p$; it suffices by the union bound and symmetry to show that the event that $\lambda_{i}$ falls outside $[a+{\varepsilon},b-{\varepsilon}]$ or that the $n$th coordinate $x$ of $u_{i}$ is $O(Kn^{-1/2}\log^{10}n)$ holds with (uniformly) overwhelming probability.

Applying Corollary 26, it suffices to show that with uniformly overwhelming probability, either $\lambda_{i}\notin[a+{\varepsilon},b-{\varepsilon}]$, or

where $M=\left({M_{p,n-1}\enskip X}\right)$. But if $\lambda_{i}\in[a+{\varepsilon},b-{\varepsilon}]$, then byIn the case $p=n$, one would have to replace $M_{p,n-1}$ by its transpose to return to the regime $p\leq n$. Theorem 20, one can find (with uniformly overwhelming probability) a set $J\subset\{1,\ldots,\min(p,\allowbreak n-1)\}$ with $|J|\gg K^{2}\log^{20}n$ such that $\lambda_{j}(M_{p,n-1})=\lambda_{i}(M_{p,n})+\break O(K^{2}\log^{20}n/n)$ for all $j\in J$; since $\lambda_{i}=\frac{1}{n}\sigma_{i}^{2}$, we conclude that $\sigma_{j}(M_{p,n-1})^{2}=\sigma_{i}(M_{p,n})^{2}+O(K^{2}\log^{20}n)$. In particular, $\sigma_{j}(M_{p,n-1})=\Theta(\sqrt{n})$. By Pythagoras’ theorem, the left-hand side of (15) is then bounded from below by

with uniformly overwhelming probability, and the claim follows.

2 A crude upper bound

Let the hypotheses be as in Theorem 20. We first establish a crude upper bound, which illustrates the techniques used to prove Theorem 20, and also plays an important direct role in that proof.

Let the hypotheses be as in Theorem 19. Then for any interval $I\subset[a+{\varepsilon},b-{\varepsilon}]$ of length $|I|\geq K\log^{2}n/n$, one has with overwhelming probability (uniformly in $I$) that

where $|I|$ denotes the length of $I$, and $N_{I}$ was defined in (14).

To prove this proposition, we suppose for contradiction that

for some large constant $C$ to be chosen later. We will show that for $C$ large enough, this leads to a contradiction with overwhelming probability.

We follow the standard approach (see, e.g., BS ) of controlling the eigenvalue counting function $N_{I}$ via the Stieltjes transform

Fix $I$. If $x$ is the midpoint of $I$, $\eta:=|I|/2$, and $z:=x+\sqrt{-1}\eta$, we see that

[recall that $p=\Theta(n)$] so from (16) one has

Using the crude bound $|{\operatorname{Im}}\frac{1}{z}|\leq\frac{1}{|{\operatorname{Im}}(z)|}$ and (17), one concludes

By the pigeonhole principle, there exists $1\leq k\leq p$ such that

The fact that $k$ varies will cost us a factor of $p$ in our failure probability estimates, but this will not be of concern since all of our claims will hold with overwhelming probability.

The expression $a_{k}^{\ast}v_{j}(M_{k})$ can be rewritten much more favorably using (20) as

The advantage of this latter formulation is that the random variables $X_{k}$ and $u_{j}(M_{k})$ are independent (for fixed $k$).

Next, note that from (16) and the Cauchy interlacing law (Lemma 22) one can find an interval $J\subset\{1,\ldots,p-1\}$ of length

such that $\lambda_{j}(W_{k})\in I$. We conclude that

Since $\lambda_{j}(W_{k})\in I$, one has $\sigma_{j}(M_{k})=\Theta(\sqrt{n})$, and thus

The left-hand side can be rewritten using Pythagoras’ theorem as $\|\pi_{H}X_{k}\|^{2}$, where $H$ is the span of the eigenvectors $u_{j}(M_{k})$ for $j\in J$. But from Lemma 28 and (23), we see that this quantity is $\gg\eta n$ with overwhelming probability, giving the desired contradiction with overwhelming probability (even after taking the union bound in $k$). This concludes the proof of Proposition 29.

3 Reduction to a Stieltjes transform bound

We now begin the proof of Theorem 20 in earnest. We continue to allow all implied constants to depend on ${\varepsilon}$ and $y$.

It suffices by a limiting argument (using Lemma 23) to establish the claim under the assumption that the distribution of $M$ is continuous; our arguments will not use any quantitative estimates on this continuity.

The strategy is to compare $s$ with the Marchenko–Pastur Stieltjes transform

A routine application of (1) and the Cauchy integral formula yields the explicit formula

We have the following standard relation between convergence of Stieltjes transform and convergence of the counting function.

Let $1/10\geq\eta\geq 1/n$, and $L,{\varepsilon},\delta>0$. Suppose that one has the bound

with overwhelming probability for each $z$ with $|{\operatorname{Re}}(z)|\leq L$ and ${\operatorname{Im}}(z)\geq\eta$, with the implied constants in the definition of overwhelming probability uniform in $z$. Then for any interval $I$ in $[a+{\varepsilon},b-{\varepsilon}]$ with $|I|\geq\max(2\eta,\frac{\eta}{\delta}\log\frac{1}{\delta})$, one has

This follows from TVlocal1 , Lemma 64; strictly speaking, that lemma was phrased for the semi-circular distribution rather than the Marchenko–Pastur distribution, but an inspection of the proof shows the proof can be modified without difficulty. See also GT00 and ESY1 , Corollary 4.2, for closely related lemmas.

In view of this lemma, we see that to show Theorem 20, it suffices to show that for each complex number $z$ in the region

with (uniformly) overwhelming probability.

For this, we return to the formula (18). Inserting the identities (21), (22) into this formula, one obtains

Suppose we condition $M_{k}$ (and thus $W_{k}$) to be fixed; the entries of $X_{k}$ remain independent with mean zero and variance $1$, and thus (since the $u_{j}$ are unit vectors)

From the Cauchy interlacing law (Lemma 22), we see that the difference

is bounded in magnitude by $O(\frac{1}{p})$ times the total variation of the function $\lambda\mapsto\frac{1}{\lambda-z}$ on $[0,+\infty)$, which is $O(\frac{1}{\eta})$. Thus,

We will shortly show a similar bound for $Y_{k}$ itself.

Let $z\in\Omega$. For each $1\leq k\leq p$, one has $Y_{k}=y+o(1)+(y+o(1))zs(z)$ with overwhelming probability (uniformly in $k$ and $I$).

and hence by Lemma 28, $\xi_{kk}=1+o(1)$ with overwhelming probability (again uniformly in $k$ and $I$). Inserting these bounds into (28), one obtains

(with the convention that $\frac{y+z-1}{yz}=1$ when $y=1$). By using a $n^{-100}$-net of possible $z$’s in $\Omega$ and using the union bound [and the fact that $s(z)$ has a Lipschitz constant of at most $O(n^{10})$ in $\Omega$] we may assume (with overwhelming probability) that the above trichotomy holds for all $z\in\Omega$. In other words, if $\delta>0$ is a small number (which may depend on $a,b,{\varepsilon}$) and $n$ is sufficiently large depending on $\delta$, we may cover

since $(y+z-1)^{2}-4yz$ has zeroes only when $z=a,b$, and $z$ is bounded away from these singularities, we see also that $\Omega_{1}$ and $\Omega_{3}$ are also disjoint.

The sets $\Omega_{1}$, $\Omega_{2}\cup\Omega_{3}$ are thus disjoint closed subsets of $\Omega$. As $\Omega$ is connected and $\Omega_{1}$ is nonempty, we conclude that $\Omega_{1}=\Omega$ (whenever $n$ is sufficiently large depending on $\delta$). Letting $\delta\to 0$, we conclude that (30) holds unniformly for $z\in\Omega$ with overwhelming probability, which gives (27) and thus Theorem 20.

Proof of Theorem 17 and Theorem 18

We first prove Theorem 17. The arguments follow those in TVlocal1 .

We begin by observing from Markov’s inequality and the union bound that one has $|\zeta_{ij}|,|\zeta^{\prime}_{ij}|\leq n^{10/C_{0}}$ (say) for all $i,j$ with probability $O(n^{-8})$. Thus, by truncation (and adjusting the moments appropriately, using Lemma 23 to absorb the error), one may assume without loss of generality that

almost surely for all $i,j$. Next, by a further approximation argument we may assume that the distribution of $M,M^{\prime}$ is continuous. This is a purely qualitative assumption, to ensure that the singular values are almost surely simple; our bounds will not depend on any quantitative measure on the continuity, and so the general case then follows by a limiting argument using Lemma 23.

The key technical step is the following theorem, whose proof is delayed to the next section.

For sufficiently small $c_{0}>0$ and sufficiently large $C_{0}>0$, the following holds for every $0<{\varepsilon}<1$ and $k\geq 1$. Let $M=(\zeta_{ij})_{1\leq i\leq p,1\leq j\leq n}$ and $M^{\prime}=(\zeta^{\prime}_{ij})_{1\leq i\leq p,1\leq j\leq n}$ be matrix ensembles obeying condition C1 for some $C_{0}$, as well as (33). Assume that $p/n\to y$ for some $0<y\leq 1$, and that $\zeta_{ij}$ and $\zeta^{\prime}_{ij}$ match to order $4$.

Then for any ${\varepsilon}p\leq i_{1}<i_{2}<\cdots<i_{k}\leq(1-{\varepsilon})p$, and for $n$ sufficiently large depending on ${\varepsilon},k,c_{0}$ we have

If $\zeta_{ij},\zeta^{\prime}_{ij}$ match to order $3$, then the conclusion still holds as long as one strengthens (34) to

for some $c_{1}>0$, if $c_{0}$ is sufficiently small depending on $c_{1}$.

Informally, Theorem 32 is a truncated version of Theorem 17 in which one has smoothly restricted attention to the event where eigenvalue gaps are not unexpectedly small.

Given a $p\times n$ matrix $M$ we form the augmented matrix ${\mathbf{M}}$ defined in (9), whose eigenvalues are $\pm\sigma_{1}(M),\ldots,\pm\sigma_{p}(M)$, together with the eigenvalue with multiplicity $n-p$ (if $p<n$). For each $1\leq i\leq p$, we introduce (in analogy with the arguments in TVlocal1 ) the quantities

(The factor of $\frac{1}{n}$ in $Q_{i}({\mathbf{M}})$ is present to align the notation here with that in TVlocal1 , in which one dilated the matrix by $\sqrt{n}$.) We set $Q_{i}({\mathbf{M}})=\infty$ if the singular value $\sigma_{i}$ is repeated, but this event occurs with probability zero since we are assuming $M$ to be continuously distributed. One should view $Q_{i}({\mathbf{M}})$ as measuring the extent to which eigenvalue (or singular value) gaps near $\sigma_{i}(M)$ are unexpectedly small.

The gap property on $M$ ensures an upper bound on $Q_{i}({\mathbf{M}})$.

If $M$ satisfies the gap property, then for any $c_{0}>0$ (independent of $n$), and any ${\varepsilon}p\leq i\leq(1-{\varepsilon})p$, one has $Q_{i}({\mathbf{M}})\leq n^{c_{0}}$ with high probability.

From Corollary 21, we see that with overwhelming probability, $\sigma_{i}(M)^{2}/n$ is bounded away from zero, and so $\frac{n-p+1}{n\sigma_{i}(M)^{2}}=O(1/n)$. To bound the other term in (37), one repeats the proof of TVlocal1 , Lemma 49.

By applying a truncation argument exactly as in TVlocal1 , Section 3.3, one can now remove the hypothesis in Theorem 32 that $G$ is supported in the region $q_{1},\ldots,q_{k}\leq n^{c_{0}}$. In particular, one can now handle the case when $G$ is independent of $q_{1},\ldots,q_{k}$; and Theorem 17 follows after making the change of variables $\lambda=\frac{1}{n}\sigma^{2}$ and using the chain rule (and Corollary 21).

Next, we prove Theorem 18, assuming both Theorems 32 and 16. The main observation here is the following lemma.

Now consider a random matrix $M$ as in Theorem 18 with atom variables $\zeta_{ij}$. By the above lemma, for each $i,j$, we can find $\zeta^{\prime}_{ij}$ which satisfies the exponential decay hypothesis and match $\zeta_{ij}$ to third order. Let $\eta(q)$ be a smooth cutoff to the region $q\leq n^{c_{0}}$ for some $c_{0}>0$ independent of $n$, and let ${\varepsilon}p\leq i\leq(1-{\varepsilon})p$. By Theorem 16, the matrix $M^{\prime}$ formed by the $\zeta^{\prime}_{ij}$ satisfies the gap property. By Lemma 33,

for some $c_{1}>0$ independent of $n$, so by Theorem 32 one has

for some $c_{2}>0$ independent of $n$. We conclude that $M$ also obeys the gap property.

The next two sections are devoted to the proofs of Theorem 32 and Theorem 16, respectively.

The above trick to remove the exponential decay hypothesis for Theorem 16 also works to remove the same hypothesis in TVlocal1 , Theorem 19. The point is that in the analogue of Theorem 32 in that paper (implicit in TVlocal1 , Section 3.3), the exponential decay hypothesis is not used anywhere in the argument; only a uniformly bounded $C_{0}$ moment for $C_{0}$ large enough is required, as is the case here. Because of this, one can replace all the exponential decay hypotheses in the results of TVlocal1 , TVlocal2 by a hypothesis of bounded $C_{0}$ moment; we omit the details.

The proof of Theorem 32

It remains to prove Theorem 32. By telescoping series, it suffices to establish a bound

under the assumption that the coefficients $\zeta_{ij}$, $\zeta^{\prime}_{ij}$ of $M$ and $M^{\prime}$ are identical except in one entry, say the $qr$ entry for some $1\leq q\leq p$ and $1\leq r\leq n$, since the claim then follows by interchanging each of the $pn=O(n^{2})$ entries of $M$ into $M^{\prime}$ separately.

Write $M(z)$ for the matrix $M$ (or $M^{\prime}$) with the $qr$ entry replaced by $z$. We apply the following proposition, which follows from a lengthy argument in TVlocal1 :

Let the notation and assumptions be as in Theorem 32. There exists a positive constant $C_{1}$ (independent of $k$) such that the following holds. Let ${\varepsilon}_{1}>0$. We condition (i.e., freeze) all the entries of $M(z)$ to be constant, except for the $qr$ entry, which is $z$. We assume that for every $1\leq j\leq k$ and every $|z|\leq n^{1/2+{\varepsilon}_{1}}$ whose real and imaginary parts are multiples of $n^{-C_{1}}$, we have

(Singular value separation) For any $1\leq i\leq n$ with $|i-i_{j}|\geq n^{{\varepsilon}_{1}}$, we have

whenever $P_{i_{j},\alpha}$ (resp., $P^{\prime}_{i_{j},\alpha}$) is the orthogonal projection to the span of right singular vectors $u_{i}(M(z))$ [resp., left singular vectors $v_{i}(M(z))$] corresponding to singular values $\sigma_{i}(A(z))$ with $2^{\alpha}\leq|i-i_{j}|<2^{\alpha+1}$.

We say that $M(0),e_{q},e_{r}$ are a good configuration for $i_{1},\ldots,i_{k}$ if the above properties hold. Assuming this good configuration, then we have (7) if $\zeta_{ij}$ and $\zeta^{\prime}_{ij}$ match to order $4$, or if they match to order $3$ and (36) holds.

This follows by applying TVlocal1 , Proposition 46, to the $p+n\times p+n$ Hermitian matrix $A(z):=\sqrt{n}{\mathbf{M}}(z)$, where ${\mathbf{M}}(z)$ is the augmented matrix of $M(z)$, defined in (9). Note that the eigenvalues of $A(z)$ are $\pm\sqrt{n}\sigma_{1}(M(z)),\break\ldots,\pm\sqrt{n}\sigma_{p}(M(z))$ and , and that the eigenvalues are given (up to unit phases) by ${v_{j}(M(z))\choose\pm u_{j}(M(z))}$. Note also that the analogue of (42) in TVlocal1 , Proposition 46, is trivially true if $2^{\alpha}$ is comparable to $n$, so one can restrict attention to the regime $2^{\alpha}=o(n)$.

In view of the above proposition, we see that to conclude the proof of Theorem 32 (and thus Theorem 17) it suffices to show that for any ${\varepsilon}_{1}>0$, that $M(0)$, $e_{q}$, $e_{r}$ are a good configuration for $i_{1},\ldots,i_{k}$ with overwhelming probability, if $C_{0}$ is sufficiently large depending on ${\varepsilon}_{1}$ (cf. TVlocal1 , Proposition 48).

Our main tools for this are Theorem 19 and Theorem 20. Actually, we need a slight variant.

The conclusions of Theorem 19 and Theorem 20 continue to hold if one replaces the $qr$ entry of $M$ by a deterministic number $z=O(n^{1/2+O(1/C_{0})})$.

This is proven exactly as in TVlocal1 , Corollary 63, and is omitted.

We return to the task of establishing a good configuration with overwhelming probability. By the union bound, we may fix $1\leq j\leq k$, and also fix the $|z|\leq n^{1/2+{\varepsilon}_{1}}$ whose real and imaginary parts are multiples of $n^{-C_{1}}$. By the union bound again and Proposition 37, the eigenvalue separation condition (39) holds with overwhelming probability for every $1\leq i\leq n$ with $|i-j|\geq n^{{\varepsilon}_{1}}$ (if $C_{0}$ is sufficiently large), as does (41). A similar argument using Pythagoras’ theorem and Corollary 21 gives (42) with overwhelming probability [noting as before that we may restrict attention to the regime $2^{\alpha}=o(n)$]. Corollary 21 also gives (40) with overwhelming probability. This gives the claim, and Theorem 17 follows.

Proof of Theorem 16

We now prove Theorem 16, closely following the analogous arguments in TVlocal1 . Using the exponential decay condition, we may truncate the $\zeta_{ij}$ (and renormalise moments, using Lemma 23) to assume that

almost surely. By a limiting argument, we may assume that $M$ has a continuous distribution, so that the singular values are almost surely simple.

We write $i_{0}$ instead of $i$, $p_{0}$ instead of $p$, and write $N_{0}:=p_{0}+n$. As in TVlocal1 , the strategy is to propagate a narrow gap for $M=M_{p_{0},n}$ backwards in the $p$ variable, until one can use Theorem 20 to show that the gap occurs with small probability.

More precisely, for any $1\leq i-l<i\leq p\leq p_{0}$, we let $M_{p,n}$ be the $p\times n$ matrix formed using the first $p$ rows of $M_{p_{0},n}$, and we define (following TVlocal1 ) the regularized gap

where $C_{1}>1$ is a large constant to be chosen later. It will suffice to show that

The main tool for this is the following lemma.

Suppose that $p_{0}/2\leq p<p_{0}$ and $l\leq{\varepsilon}p/10$ is such that

for some $0<\delta\leq 1$ (which can depend on $n$), and that

Let $X_{p+1}$ be the ($p+1$)th row of $M_{p_{0},n}$, and let $u_{1}(M_{p,n}),\ldots,u_{p}(M_{p,n})$ be an orthonormal system of right singular vectors of $M_{p,n}$ associated to $\sigma_{1}(M_{p,n}),\ldots,\sigma_{p}(M_{p,n})$. Then one of the following statements hold: {longlist}[(iii)]

(Macroscopic spectral concentration) There exists $1\leq i_{-}<i_{+}\leq p+1$ with $i_{+}-i_{-}\geq\log^{C_{1}/2}n$ such that $|\sqrt{n}\sigma_{i_{+}}(M_{p+1,n})-\sqrt{n}\sigma_{i_{-}}(M_{p+1,n})|\leq\break\delta^{1/4}\exp(\log^{0.95}n)(i_{+}-i_{-})$.

(Small inner products) There exists ${\varepsilon}p/2\leq i_{-}\leq i_{0}-l<i_{0}\leq i_{+}\leq(1-{\varepsilon}/2)p$ with $i_{+}-i_{-}\leq\log^{C_{1}/2}n$ such that

(Large singular value) For some $1\leq i\leq p+1$, one has

(Large inner product in bulk) There exists ${\varepsilon}p/10\leq i\leq(1-{\varepsilon}/10)p$ such that

(Large inner product near $i_{0}$) There exists ${\varepsilon}p/10\leq i\leq(1-{\varepsilon}/10)p$ with $|i-i_{0}|\leq\log^{C_{1}}n$ such that

This follows by applyingStrictly speaking, there are some harmless adjustments by constant factors that need to be made to this lemma, ultimately coming from the fact that $n,p,n+p$ are only comparable up to constants, rather than equal, but these adjustments make only a negligible change to the proof of that lemma. TVlocal1 , Lemma 51, to the $p+n+1\times p+n+1$ Hermitian matrix

which after removing the bottom row and rightmost column (which is $X_{p+1}$, plus $p+1$ zeroes) yields the $p+n\times p+n$ Hermitian matrix

which has eigenvalues $\pm\sqrt{n}\sigma_{1}(M_{p,n}),\ldots,\pm\sqrt{n}\sigma_{p}(M_{p,n})$ and , and an orthonormal eigenbasis that includes the vectors ${u_{j}(M_{p,n})\choose v_{j}(M_{p,n})}$ for $1\leq j\leq p$. (The “large coefficient” event in TVlocal1 , Lemma 51(iii), cannot occur here, as $A_{p+n+1}$ has zero diagonal.)

By repeating the arguments in TVlocal1 , Section 3.5, almost verbatim, it then suffices to show the following proposition.

Suppose that $p_{0}/2\leq p<p_{0}$ and $l\leq{\varepsilon}p/10$, and set $\delta:=n_{0}^{-\kappa}$ for some sufficiently small fixed $\kappa>0$. Then: {longlist}[(b)]

The events (i), (iii), (iv), (v) in Lemma 38 all fail with high probability.

There is a constant $C^{\prime}$ such that all the coefficients of the right singular vectors $u_{j}(M_{p,n})$ for ${\varepsilon}p/2\leq j\leq(1-{\varepsilon}/2)p$ are of magnitude at most $n^{-1/2}\log^{C^{\prime}}n$ with overwhelming probability. Conditioning $M_{p,n}$ to be a matrix with this property, the events (ii) and (vi) occur with a conditional probability of at most $2^{-\kappa m}+n^{-\kappa}$.

Furthermore, there is a constant $C_{2}$ (depending on $C^{\prime},\kappa,C_{1}$) such that if $l\geq C_{2}$ and $M_{p,n}$ is conditioned as in (b), then (ii) and (vi) in fact occur with a conditional probability of at most $2^{-\kappa m}\log^{-2C_{1}}n+n^{-\kappa}$.