Random weighted projections, random quadratic forms and random eigenvectors

Introduction

In , Tao and the first author showed that (under certain conditions) this length is strongly concentrated. In other words, the projection of $X$ onto $H$ lies essentially on a circle centered at the origin. This fact played a crucial role in the studies of the determinant of a random matrix with independent entries (see ). We say that $\xi$ is $K$-bounded if $|\xi|\leq K$ with probability 1.

The projection lemma follows from the Talagrand’s inequality ([17, Chapter 4]). The constants $10$ and $20$ are rather arbitrary. We make no attempt to optimize the constants in this paper.

2. Weighted projection lemmas

Let us fix an orthonormal basis $\{u_{1},\dots,u_{d}\}$ of $H$. We can express $\Pi_{H}X$ as

In recent studies, we came up with situations when the roles of the axes are not compatible. Formally speaking, one is required to consider a weighted version of (1) where $(\sum_{i=1}^{d}|u_{i}^{*}X|^{2})^{1/2}$ is replaced by $(\sum_{i=1}^{d}c_{i}|u_{i}^{*}X|^{2})^{1/2}$ with $c_{i}$ being non-negative numbers (weights).

We are able to prove a variant of Lemma 1.1 for this more general problem, which turns out to be useful in a number of applications, some of which will be discussed in the paper. Furthermore, we can also weaken the assumption on random vector $X$ in various ways.

where $M(Y)$ denotes the median of a random variable $Y$ (choose an arbitrary one as there are many).

Notice that the notion of $K$-concentrated is somewhat similar to the notion of threshold in random graph theory in the sense that if $X$ is $K$-concentrated then it is $cK$-concentrated for any constant $c>0$. (Similarly, if $p(n)$ is a threshold for a property ${\mathcal{P}}$ (say, containing a triangle) then $cp(n)$ is also a threshold.) One can also replace the median by the expectation (see Lemma 2.1). The dependence on $K$ on the RHS of (2) is flexible (one can replace $K^{2}$ by any function $f(K))$; however, the quality of the concentration bound will depend on $f(K)$ and we leave it as an exercise for the reader to work out this dependence.

Examples of $K$-concentrated random variables

If the coordinates of $X$ are iid standard gaussian (real or complex), then $X$ is $1$-concentrated (see ).

If $\xi_{i}$ are independent and $\xi_{i}$ are $K$-bounded for all $i$, then $X$ is $K$-concentrated (this is a corollary of Talagrand’s inequality; see [17, Chapter 4] or [27, Theorem F.5]).

If $X$ satisfies the log-Sobolev inequality with parameter $K^{2}$, then it is $K$-concentrated (see [17, Theorem 5.3]).

The coordinates $\xi_{i}$ of $X$ come from a random walk satisfying certain mixing properties (see [25, Corollary 4]; in this corollary $\|\Gamma\|$ plays the role of $K$). In this and the previous example, the coordinates of $X$ are not necessarily indepedent.

In particular, by squaring, it follows that

Another way to weaken the $K$-bounded assumption is to consider truncation. If $\xi$ is not bounded, but has light tail, then by setting $K$ appropriately, we can show that ${\mathbf{P}}(|\xi|\geq K)$ is negligible with respect to the probability bound we want to prove.

Assume that the $\xi_{i}$ are independent with mean zero and variance one. Choose a number $K>1$ and let ${\varepsilon}_{1}:=\max_{1\leq i\leq n}{\mathbf{P}}(|\xi_{i}|>K)$. Set $\xi_{i}^{\prime}:=\xi_{i}{\mathbf{I}}_{|\xi_{i}|\leq K}$ and let $\mu_{i}$ and $\sigma_{i}^{2}$ denote its mean and variance. Set ${\varepsilon}_{2}:=\max_{1\leq i\leq n}|\mu_{i}|$ and ${\varepsilon}_{3}:=\max_{1\leq i\leq n}|\sigma_{i}^{2}-1|$. Assume all ${\varepsilon}_{j}\leq 1/2$ (in practice this assumption is satisfied easily).

3. Concentration of random quadratic forms

Consider a quadratic form $Y:=X^{*}AX$ where $X=(\xi_{1},\dots,\xi_{n})$ is, as usual, a random vector and $A=(a_{ij})_{1\leq i,j\leq n}$ a deterministic matrix. As application of the new projection lemmas, we prove a large deviation result for $Y$, which can be seen as the quadratic version of the standard Chernoff bound.

Let $X$ and ${\varepsilon}_{1},{\varepsilon}_{2},{\varepsilon}_{3}$ be as in Lemma 1.3. There are constants $C,C^{\prime}>0$ such that the following holds. Assume $n^{2}K^{2}({\varepsilon}_{2}+{\varepsilon}_{3})=o(1)$, then

As an illustration, let us consider the case when $\xi_{i}$ are sub-exponential. We say that $\xi$ is sub-exponential with exponent $\alpha>0$ (with accompanying positive constants $a$ and $b$) if for any $t>0$

Assume that $\xi_{i}$ are independent and sub-exponential (with exponent $\alpha>0$) random variables with mean 0 and variance 1. Then there are constants $C,C^{\prime}>0$ such that for any $t$ satisfying

Quadratic forms of random variables appear frequently in probability and the large deviation problem has been considered by several researchers, with first and perhaps most famous result being by Hanson-Wright inequality . In many cases, our results improve earlier results significantly; see Section 3 for more details.

4. Norm of random eigenvectors

Let $M_{n}$ be a symmetric $\pm 1$ matrix (the upper diagonal and diagonal entries are iid Bernoulli random variables taking values $\pm 1$ with probability $1/2$). This is an important object in both probabilistic combinatorics and the theory of random matrices. Let $u$ be an arbitrary unit eigenvector of $M_{n}$. We investigate the following natural question,

A good bound on the infinity norm of the eigenvectors is important in spectral analysis of graphs and many other applications, such as the studies of nodal domains (see for instance and the references therein). Recently, it plays a crucial role in breakthrough works concerning local statistics of random matrices (see Section 1.5 and also for surverys).

Set $W_{n}=\frac{1}{\sqrt{n}}M_{n}$. Thanks to the classical Wigner’s semi-circle law (see Section 1.5), we know that most of the eigenvalues of $W_{n}$ belong to the interval $(-2+\epsilon,2-\epsilon)$. Using our new concentration results, we are able to obtain (what we believe to be) the optimal bound for the eigenvectors corresponding to these eigenvalues.

Let $M_{n}$ be a $n\times n$ symmetric matrix whose upper diagonal entries are iid random variables that takes values $\pm 1$ with the same probability. Let $W_{n}=\frac{1}{\sqrt{n}}M_{n}$. For any constant $C_{1}>0$, there is a constant $C_{2}>0$ such that the following holds.

(Bulk case) With probability at least $1-n^{-C_{1}}$, for any fixed $\epsilon>0$ and any $1\leq i\leq n$ with $\lambda_{i}(W_{n})\in[-2+\epsilon,2-\epsilon]$, there is a unit eigenvector $u_{i}(W_{n})$ of $\lambda_{i}(W_{n})$ satisfying

(Edge case) With probability at least $1-n^{-C_{1}}$, for any $\epsilon>0$ and any $1\leq i\leq n$ with $\lambda_{i}(W_{n})\in[-2-\epsilon,-2+\epsilon]\cup[2-\epsilon,2+\epsilon]$, there is a unit eigenvector $u_{i}(W_{n})$ of $\lambda_{i}(W_{n})$ satisfying

The best previous bound was of the form $\frac{\log^{C}n}{n^{1/2}}$ for some large (usually not explicit) constant $C$ . We conjecture that the bound $O(\sqrt{\log n/n})$ is sharp (it is easy to see that this is the case if the entries are standard gaussian) and also that it holds for all eigenvectors. Very recently, Rudelson and Vershynin also studied the norm of random eigenvectors using a geometric method, which is different from our approach discussed in Section 1.5.

5. The local semi-circle law

Denote by $\rho_{sc}$ the semi-circle density function with support on $$,

Let us recall the classical Wigner’s semi-circle law:

Let $M_{n}$ be a random Hermitian matrix whose entries on and above the diagonal are iid bounded random variables with zero mean and unit variance and $W_{n}=\frac{1}{\sqrt{n}}M_{n}$. Then for any real number $x$,

in the sense of probability, where we use $|I|$ to denote the cardinality of a finite set $I$.

The key tool for bounding the infinity norm of an eigenvector is a statement of the following type: any interval of length at least $T$ (which tends to zero with $n$) in the spectrum $$contains an eigenvalue, with high probability. The quality of the bound will depend on how small$T$is. This approach was developed by Erdős, Schlein and Yau in , leading to eigenvector norm bounds of order$n^{-2/3},n^{-3/4}$and finally$n^{-1+o(1)}$. A simpler argument, following the same approach, was developed by Tao and the first author in (see [27, Section 4] for a problem concerning random non-hermitian matrices).

One way to attack the above problem is to show that the semi-circle law holds for small intervals (or at small scale). Intuitively, we would like to have with high probability that

for any interval $I$ and fixed $\delta>0$, where $N_{I}$ denotes the number of eigenvalues of $W_{n}:=\frac{1}{\sqrt{n}}M_{n}$ in the interval $I$. Of course, the reader can easily see that $I$ cannot be arbitrarily short (since $N_{I}$ is an integer). Following , we call a statement of this kind a local semi-circle law (LSCL).

A natural question arises: how short can $I$ be ? Formally, we say that the LSCL holds at a scale $f(n)$ if with probability $1-o(1)$

for any interval $I$ in the bulk of length $\omega(f(n))$ and any fixed $\delta>0$. Furthermore, we say that $f(n)$ is a threshold scale if the LSCL holds at scale $f(n)$ but does not holds at scale $g(n)$ for any function $g(n)=o(f(n))$. (The reader may notice a similarity between this definition and the definition of threshold functions for random graphs.) We would like to raise the following problem.

Determine the threshold scale (if exists).

We do not know a sharp estimate for the threshold for any matrix ensembles, even in the basic GUE (random matrix with complex gaussian entries) and GOE (random matrix with real gaussian entries) cases. A recent result by Ben Arous and Bourgade shows that the maximum gap between two consecutive (bulk) eigenvalues of GUE is of order $\Theta(\sqrt{\log n}/n)$, with high probability. Thus, if we partition the bulk into intervals of length $\alpha\sqrt{\log n}/n$ for a sufficiently small $\alpha$, one of these intervals contains at most one eigenvalue. Therefore, we expect that in natural ensembles, the LSCL does not hold below the $\sqrt{\log n}/n$ scale. In , upper bound of the form $\log^{C}n/n$ was proved for some large value of $C$. Here we are going to show

Let $M_{n}$ be a Hermitian matrix whose upper diagonal entries are independent random variables with mean and variance $1$. Assume furthermore that for $1\leq i\leq n$, the vectors $X_{i}$, obtained by deleting the $i$-th entry of the $i$-th row vector of $M$, are $K$-concentrated. Then the threshold scale for LSCL is bounded from above by $K^{2}\log n/n$.

In the GUE case, the gap between the upper and lower bound is only $O(\sqrt{\log n})$ and it is an intriguing problem to remove this factor. We also conjecture that Ben Arous and Bourgade’s result on the largest gap holds for $\pm 1$ random matrices.

The results of Section 1.4 and Section 1.5 also hold for random sample covariance matrices. We sketch the results and proofs in the appendices.

Structure of the paper. In the next section, we prove the new projection lemmas. In Section 3, we prove the new concentration inequalities for quadratic forms and make a comparison with prior results. The next section, Section 4 can be seen as a preparation step in which we recall facts about random matrices. We prove the new threshold for the local semi-circle law in Section 5, and the bound on the infinity norm of eigenvectors in Section 6. The appendices contain proofs concerning random sample covariance matrices.

Acknowledgement. The authors would like to thank the anonymous referees for their careful reading and constructive suggestions.

Proofs of Lemmas 1.2 and 1.3

Next, we show that $f(X)$ is 1-Lipschitz. Notice that $f(X)\leq\sqrt{\sum_{j=1}^{d}|u_{j}^{*}X|^{2}}\leq\|X\|$. Since $f(X)$ is convex, one has

Thus $f(X)-f(Y)\leq f(X-Y)$ and $f(Y)-f(X)\leq f(Y-X)=f(X-Y)$, which imply

Thus, by the definition of $K$-concentrated property,

To conclude the proof, it suffices to show $|M(f(X))-\sqrt{\sum_{j=1}^{d}c_{j}}|=O(K).$ We use the following lemma. The proof of the lemma is classical and thus omitted.

Let $Y$ be a real random variable. Assume ${\mathbf{P}}(|Y-\mu|\geq t)\leq f(t)$, where $\int_{0}^{\infty}f(x)dx=O(1)$, then $|{\mathbf{E}}Y-\mu|=O(1)$. Assume furthermore that $Y$ is non-negative, $\mu\geq 0$, $\sigma=\sqrt{{\mathbf{E}}Y^{2}}$, and $\int_{0}^{\infty}xf(x)dx=O(1)$, then $|{\mathbf{E}}Y-\sigma|=O(1).$

To apply this lemma, set $c_{i}^{\prime}:=\frac{c_{i}}{\max_{1\leq i\leq d}c_{i}}$, $Y:=\frac{1}{K}\sqrt{\sum_{i=1}^{d}c^{\prime}_{i}|u_{i}^{*}X|^{2}}$ and $\mu:=M(Y)$. We have, by the $K$-concentration property

Set $f(x)=C\exp(-C^{\prime}x^{2})$. The assumptions on $f(x)$ in Lemma 2.1 are trivially satisfied. As $X$ is isotropic, $\sigma^{2}={\mathbf{E}}Y^{2}=\frac{1}{K^{2}}\sum_{i=1}^{d}c_{i}^{\prime}$. It follows from Lemma 2.1 that

As $u_{i}$ are unit vectors, $|u_{i}^{*}X_{i}^{\prime}|\leq\|X_{i}^{\prime}\|\leq\sqrt{n}K$ and $|u_{i}^{*}D_{i}|\leq\|D_{i}\|\leq 2\sqrt{n}(K\epsilon_{2}+\epsilon_{3})$ (these bounds are generous and can be improved by a polynomial factor in certain cases, but in applications such improvement rarely matters). It follows, again rather generously,

In practice, ${\varepsilon}_{j}$ are typically super-polynomially small, i.e. $n^{-\omega(1)}$, which yields $4n^{2}K^{2}({\varepsilon}_{2}+{\varepsilon}_{3})=o(1)$. This term can be ignored (by slightly changing the values of $C,C^{\prime}$ if necessary) and we end up with a more friendly inequality

In the sub-exponential case, for a sufficiently large $K$ (compared to $a$ and $b$), ${\varepsilon}_{j}\leq\exp(-\frac{b}{2}K^{1/\alpha})$ for $j=1,2,3$. For $K=\omega(\log^{\alpha}n)$, $n^{2}K^{2}\exp(-\frac{b}{2}K^{1/\alpha})=o(1)$ and (10) yield

Random Quadratic Forms

Let us first prove Theorem 1.4. Notice that if $Y=X^{*}AX$, then $Y+\bar{Y}=X^{*}(A+A^{*})X$ and $Y-\bar{Y}=X^{*}(A-A^{*})X$. Since

Moreover, as $\|A+A^{*}\|_{F},\|A-A^{*}\|_{F}=O(\|A\|_{F})$ and $\|A+A^{*}\|_{2},\|A-A^{*}\|_{2}=O(\|A\|_{2})$, it suffices to prove the theorem in the case $A$ is Hermitian.

Next, we observe that any Hermitian matrix $A$ can be written as $A:=A_{1}-A_{2}$ where $A_{i}$ are positive semi-definite and $\max_{i=1,2}\|A_{i}\|_{2}\leq\|A\|_{2},\max_{i=1,2}\|A_{i}\|_{F}\leq\|A\|_{F}$. (In fact, the positive eigenvalues of $A_{1}$ are the positive eigenvalues of $A$ and the positive eigenvalues of $A_{2}$ are the absolute values of the negative eigenvalues of $A$.) This enables us to further reduce the problem to the case when $A$ is positive semi-definite.

Finally, as the content of the theorem is invariant under scaling, we can assume that $\|A\|_{2}=1$. Let $1=c_{1}\geq c_{2},\dots,c_{n}\geq 0$ be the eigenvalues of $A$ together with corresponding orthonormal eigenvectors $\{u_{1},\ldots,u_{n}\}$. We have

This is precisely the setting of the projection lemmas. By Lemma 1.2, we know that for any numbers $0\leq d_{j}\leq 1$, $j\in J$,

However, it is somewhat wasteful to apply this directly to (12). We will perform an extra partition step. Set

and let $J_{k_{0}+1}$ be the collection of the remaining indices.

For each $0\leq k\leq k_{0}+1$, apply Lemma 1.2 to $d_{i}:=4^{k}c_{i},c_{i}\in J_{k}$, we have, for any $s\geq 0$

Set $s:=\frac{t}{\|A\|_{F}}$ and simplify by $4^{k}$, the above inequality becomes

Apparently, $\sum_{k=0}^{k_{0}+1}\frac{t^{2}}{4^{k}\|A\|_{F}^{2}}\leq 2\frac{t^{2}}{\|A\|_{F}^{2}}$. Moreover, $\sum_{i\in J_{k_{0}+1}}c_{i}\leq n\times n^{-5}=n^{-4}$ and

Putting the above estimates together and using the union bound, we obtain

We can ignore the small term $n^{-2}$ (by slightly adjusting the constant 16), the desired bound follows.

If we have more information about $A$, the $\log n$ term can be improved. For instance, if all eigenvalues of $A$ are comparable, then we do not need this term.

The proof of Theorem 1.5 uses Lemma 1.3 and is left as an exercise. To prove Corollary 1.6, notice that we can obtain an analogue of (11)

under the assumption that $K=\omega(\log^{\alpha}n)$.

To optimize the bound, we choose $K$ such that $K^{-2}\min\{\frac{t^{2}}{\|A\|_{F}^{2}\log n},\frac{t}{\|A\|_{2}}\}=K^{1/\alpha}$. This leads to setting $K:=\min\{(\frac{t}{\|A\|_{F}\sqrt{\log n}})^{\frac{2}{2+1/\alpha}},(\frac{t}{\|A\|_{2}})^{\frac{1}{2+1/\alpha}}\}$. Assume

This assumption guarantees $K=\omega(\log^{\alpha}n)$. It also implies $n\exp(-\frac{b}{2}K^{1/\alpha})\leq\exp(-\frac{b}{3}K^{1/\alpha})$, proving Corollary 1.6.

2. Comparison to earlier results

In 1971, Hanson and Wright obtained the first important inequality for sub-gaussian random variables.

Later, Wright extended Theorem 3.2 to non-symmetric random variables. Recently, Hsu, Kakade and Zhang showed that one can obtain a better upper tail (notice that $\|B\|_{2}$ is replaced by $\|A\|_{2}$)

under a considerably weaker assumption (which, in particular, does not require the $\xi_{i}$ to be independent). On the other hand, their method does not cover the lower tail. Let us pause here to point out a strong distinction from the linear case and the quadratic case: In the linear case (Chernoff type bounds), the lower tail follows from the upper tail by simply switching $\xi_{i}$ to $-\xi_{i}$, but this trick is useless in the quadratic case. Recently, Rudelson and Vershynin proved the Hanson-Wright inequality

In the previous papers, the random variables $\xi_{i}$ are required to be real. Few years ago, motivated by the delocalization problem for random matrices, Erdős, Schlein and Yau considered the complex case. By assuming either both the real and imaginary parts of $\xi_{i}$ are iid sub-gaussian or the distribution of $\xi_{i}$ is rotationally symmetric (real and imaginary parts still sub-gaussian), they proved

Later, Erdős, Yau and Yin showed that if $\xi_{i}$ are independent sub-exponential random variables with exponent $\alpha>0$, having mean 0 and variance 1, then

To simplify the comparison, let us ignore the $\log n$ terms in our theorems (which play little role in practice). If $K=O(1)$, then the main difference between Theorem 3.2 of Hanson and Wright and Theorem 1.4 is that the term $\|B\|_{2}$ in Theorem 3.2 is now replaced by $\|A\|_{2}$. It is easy to see that $\|B\|_{2}\geq\|A\|_{2}$ for any real matrix $A$. In fact, in many cases, $\|B\|_{2}$ is significantly larger than $\|A\|_{2}$. For instance, a random matrix $A$ with entries of order 1 typically has spectral norm of order $\sqrt{n}$, but in this case it is clear that $\|B\|_{2}$ has spectral norm of order $n$ (as all row sums are of this order). The same holds for several classical explicit matrices, such as the Hadamard matrix. In these cases, our bound improves Hanson-Wright’s significantly. Furthermore, our result applies in the complex case while the approach used by Hanson and Wright is restricted to the real case.

Comparing to (19), we do not need the fairly restricted assumption that either both the real and imaginary parts of $\xi_{i}$ are iid sub-gaussian or the distribution of $\xi_{i}$ is rotationally symmetric. In the case $K=O(1)$, both terms $\frac{t^{2}}{\|A\|_{F}^{2}\log n}$ and $\frac{t}{\|A\|_{2}}$ in our bound can be considerably larger than $\frac{t}{\|A\|_{F}}$. For instance, $\frac{t}{\|A\|_{2}}$ and $\frac{t}{\|A\|_{F}}$ differ by a factor $\sqrt{n}$ in both the random and Hadamard cases.

In order to make a Hanson-Wright type bound non-trivial, we need to assume $t\geq\|A\|_{F}+\|A\|_{2}$. In many applications, we want the probability bound to be polynomially or even super-polynomially small, i.e. $n^{-O(1)}$ or $n^{-\omega(1)}$. This requires a lower bound $\log^{\Omega(1)}n(\|A\|_{F}+\|A\|_{2})$ on $t$, which is consistent with the assumption (6) in Corollary 1.6.

Notice that (7) compares favorably to (20). For the term $\frac{t}{\|A\|_{F}}$, the exponent $\frac{1}{\alpha+1/2}$ is superior to $\frac{1}{2\alpha+2}$ (notice that we are talking about a double exponent, so an improvement here could improve the quality of the bound quite a lot). For the term $\frac{t}{\|A\|_{2}}$, the exponent $\frac{1}{2\alpha+1}$ is still better than $\frac{1}{2\alpha+2}$. Furthermore, $\|A\|_{2}$ can be significantly smaller than $\|A\|_{F}$, as discussed earlier.

Random matrices and the Stieltjes transform

This section serves as a preparation, in which we recall several facts about random matrices. The empirical spectral distribution (ESD) function of the $n\times n$ Hermitian matrix $W_{n}:=\frac{1}{\sqrt{n}}M_{n}=\frac{1}{\sqrt{n}}(\zeta_{ij})_{1\leq i,j\leq n}$ is a one-dimensional function

where $|\mathbf{I}|$ denotes the cardinality of a set $\mathbf{I}$. We are going to focus on the case when the entries of $M_{n}$ are $K$-bounded; it is easy to extend this assumption to $K$-concentrated.

The Stieltjes transform of a real measure $\mu(x)$ is defined for any complex number $z$ not in the support of $\mu$ as

Thus, the Stieltjes transform $s_{n}(z)$ of $W_{n}$ is

Furthermore, the Stieltjes transform $s_{sc}(z)$ of the semi-circle distribution is

where $\sqrt{z^{2}-4}$ is the branch of square root with a branch cut in $$and asymptotically equals$z$ at infinity .

The beauty (and power) of the Stieltjes transform lies in the fact that it has a clear linear algebra content; $s_{n}(z)$ of $W_{n}$ is exactly the trace of the matrix $(W_{n}-zI)^{-1}$. This allows us to compute the Stieltjes transform by looking at the diagonal entries of $(W_{n}-zI)^{-1}$. In matrix theory, Stieltjes transform plays the role Fourier transform in analysis. If the Stieltjes transforms of two spectral measures are close to each other (for all $z$), then the two measures are more or less the same. In particular, if $s_{n}(z)$ is close to $s_{sc}(z)$, then the spectral distribution of $W_{n}$ is close to the semi-circle distribution (see for instance [4, Chapter 11], ). We are going to use the following lemma.

Let $M_{n}$ be a random Hermitian matrix with independent $K$-bounded entries with mean 0 and variance 1. Let $1/n<\eta<1/10$ and $L,\varepsilon,\delta>0$. For any constant $C_{1}>0$, there exists a constant $C>0$ such that if one has the bound

with probability at least $1-n^{-C}$ uniformly for all $z$ with $|\text{Re}(z)|\leq L$ and $\text{Im}(z)\geq\eta$, then for any interval $I$ in $[-L+\varepsilon,L-\varepsilon]$ with $|I|\geq\text{max}(2\eta,\frac{\eta}{\delta}\log\frac{1}{\delta})$, one has

with probability at least $1-n^{-C_{1}}$.

This is [29, Lemma 64], which, in turn, is a variant of [10, Corollary 4.3].

An appropriate application of Lemma 4.1 will imply Theorem 1.10. (As a matter of fact, we a going to prove a little bit more.) In order to use this lemma, we set $L=4,\varepsilon=1$, and critically

where $C=C_{1}+10^{4}$. We are going to show that

In order to show that $s_{n}(z)$ is close to $s_{sc}(z)$, the key observation is that $s_{sc}(z)$ can also be defined by the equation

This equation is stable, so if we can show $s_{n}(z)\approx-\frac{1}{z+s_{n}(z)}$ then it follows that $s_{n}(z)\approx s_{sc}(z)$. This observation was due to Bai et al. , who used it to prove the $n^{-1/2}$ rate of convergence of $s_{n}(z)$ to $s_{sc}(z)$. In , Erdős et al. refined Bai’s approach to prove local semi-circle law at scales finer than $n^{-1/2}$, ultimately to $n^{-1}\log^{C}n$ . Our main contribution here is to push the scale further down to $n^{-1}\log n$, which we believe is (at most) a factor $\sqrt{\log n}$ from the truth.

Recall that $s_{n}(z)$ is the trace of $(W_{n}-zI)^{-1}$. By computing the diagonal entires, one can show (see [4, Chapter 11], or [29, Lemma 39])

and $W_{n,k}$ is the matrix $W_{n}$ with the $k$-th row and column removed, and $a_{k}$ is the $k$-th row of $W_{n}$ with the $k$-th element removed.

The entries of $a_{k}$ are independent of each other and of $W_{n,k}$, and have mean zero and variance $1/n$. By linearity of expectation we have

is the Stieltjes transform of $W_{n,k}$. From the Cauchy interlacing law, we can get

The heart of the matter now is the following concentration result.

Let $M_{n}$ be as in Lemma 4.1. For $1\leq k\leq n$, $Y_{k}=\mathbf{E}(Y_{k}|W_{n,k})+o(\delta^{2})$ holds with probability at least $1-O(n^{-C})$ for any $z$ with $|\text{Re}(z)|\leq 4$ and $\text{Im}(z)\geq{\eta}$.

To prove this lemma, we are going to make an essential use of the weighted projection lemma, as showed in the next section.

Proof of Lemma 4.2 and Threshold of the Local Law

We are going to prove Lemma 4.2 and the following more quantitative version of Theorem 1.10.

For any constants $\epsilon,\delta,C_{1}>0$, there is a constant $C_{2}>0$ such that the following holds. Let $M_{n}$ be a Hermitian matrix whose upper diagonal entries are independent random variables with mean and variance $1$. Assume furthermore that for $1\leq i\leq n$, the vectors $X_{i}$, obtained by deleting the $i$-th entry of the $i$-th row vector of $M_{n}$, are $K$-concentrated. Then with probability at least $1-n^{-C_{1}}$, we have

for all interval $I\subset(-2+\epsilon,2-\epsilon)$ of length at least $C_{2}K^{2}\log n/n$.

First, we record a lemma that provides a crude upper bound on the number of eigenvalues in short intervals.

with probability at least $1-n^{-C_{1}}$.

This lemma is Proposition 66 in , which is a variant of [11, Theorem 5.1]. Notice that

where $X_{k}=\sqrt{n}a_{k}$ is the $k$-th row of $M_{n}$ with the $k$-th element removed. Note that the entries of $X_{k}$ are independent with mean 0 and variance 1. Therefore,

where $R_{j}:=|u_{j}(W_{n,k})^{*}X_{k}|^{2}-1$. By symmetry, we can restrict the sum to those indices $j$ where $\lambda_{j}(W_{n,k})-x\geq 0$.

Let $J$ be the set of indices $j$ such that $0\leq\lambda_{j}(W_{n,k})-x\leq\eta$. Since $x={\operatorname{Re}}z,\eta={\operatorname{Im}}z$, we have

Consider the sum $S_{1}:=|\sum_{j\in J}\frac{(\lambda_{j}(W_{n,k})-x)\eta}{(\lambda_{j}(W_{n,k})-x)^{2}+\eta^{2}}R_{j}|$. As $0\leq\frac{(\lambda_{j}(W_{n,k})-x)\eta}{(\lambda_{j}(W_{n,k})-x)^{2}+\eta^{2}}\leq 1$, we are in position to apply Lemma 1.2. Taking $t=C_{4}K\sqrt{\log n}$ with a sufficiently large constant $C_{4}$, by (3) we have

with probability at least $1-C\exp(-C^{\prime}C_{4}^{2}\log n)\geq 1-n^{-C_{4}/2}$. By Lemma 5.2, $|J|\leq Bn\eta$ with probability at least $1-n^{-C_{4}}$, for some sufficiently large constant $B>0$. Recall $\eta:=\frac{K^{2}C_{3}^{2}\log n}{n\delta^{6}}$; it follows that with probability at least $1-2n^{-C_{4}/2}$ we have

Thus, for $C_{3}$ sufficiently large compared to $C_{4}$ and $B$, we have $S_{1}\leq\delta^{3}$. Similarly, we can prove the same bound for $S_{2}:=\frac{1}{n\eta}|\sum_{j\in J}\frac{\eta^{2}}{(\lambda_{j}(W_{n,k})-x)^{2}+\eta^{2}}R_{j}|$.

For the other eigenvalues, we divide the real line into small intervals. For integer $l\geq 0$, let $J_{l}$ be the set of eigenvalues $\lambda_{j}(W_{n,k})$ such that $10^{l}\eta<\lambda_{j}(W_{n,k})-x\leq 10^{l+1}\eta$. The number of such $J_{l}$ is at most $20\log n$. By Lemma 5.2 one has, $|J_{l}|\leq 9B10^{l}n\eta$ with probability at least $1-n^{-C_{4}}$, for some sufficiently large constant $B>0$. Again by Lemma 1.2 (taking $t=KC_{4}\sqrt{\log n}$),

with probability at least $1-2C\exp(-C^{\prime}C_{4}^{2}\log n)-n^{-C_{4}}\geq 1-n^{-C_{4}/2}$.

with probability at least $1-n^{-C_{4}/2+1}$, for $C_{3}$ sufficiently large. This completes the proof of Lemma 4.2.

with probability at least $1-O(n^{-C})$. The term $|\zeta_{kk}/\sqrt{n}|=o(\delta^{2})$ as $|\zeta_{kk}|\leq K$ by assumption. Comparing this equation with (22), one can use a continuity argument (see for details) to obtain $|s_{n}(z)-s(z)|\leq\delta$ with probability at least $1-O(n^{-C+100})$.

By Lemma 4.1, it follows that for random matrices $M_{n}$ with $K$-bounded entries, for any constant $C_{1}>0$, there exists a constant $C_{2}>0$ such that for $0\leq\delta\leq 1/2$ and any interval $I\subset(-3,3)$ of length at least $C_{2}K^{2}\log n/{n\delta^{8}}$,

holds with probability at least $1-n^{-C_{1}}$. In particular, Theorem 5.1 follows.

The infinity norm of eigenvectors

We prove Theorem 1.7 in the following more general form.

Let $M_{n}$ be a Hermitian matrix whose upper diagonal entries are independent random variables with mean 0 and variance 1. Further assume that for any index $1\leq i\leq n$, the vector $X_{i}$, obtained by deleting the $i$-th entry of the $i$-th row vector of $M_{n}$, is $K$-concentrated. Let $W_{n}=\frac{1}{\sqrt{n}}M_{n}$. Then for any constant $C_{1}>0$, there is a constant $C_{2}>0$ such that the following holds.

(Bulk case) With probability at least $1-n^{-C_{1}}$, for any $\epsilon>0$ and any $1\leq i\leq n$ with $\lambda_{i}(W_{n})\in[-2+\epsilon,2-\epsilon]$ there is a unit eigenvector $u_{i}(W_{n})$ of $\lambda_{i}(W_{n})$ satisfying

(Edge case) With probability at least $1-n^{-C_{1}}$, for any $\epsilon>0$ and any $1\leq i\leq n$ with $\lambda_{i}(W_{n})\in[-2-\epsilon,-2+\epsilon]\cup[2-\epsilon,2+\epsilon]$, there is a unit eigenvector $u_{i}(W_{n})$ of $\lambda_{i}(W_{n})$ satisfying

We give here the proof of the first part of Theorem 6.1. The proof of the second part is somewhat different and deferred to the appendix. With the threshold for local semi-circle law, we are able to derive the eigenvector delocalization results thanks to the next lemma.

where $u_{j}(W_{n-1})$ is a unit eigenvector corresponding to the eigenvalue $\lambda_{j}(W_{n-1}).$

The assumption that the eigenvalues of $W_{n}$ and $W_{n-1}$ do not collide was taken care of in [32, Section 3.1], so we can assume that the above formula makes sense in applications.

First, for the bulk case, for any $\lambda_{i}(W_{n})\in(-2+\varepsilon,2-\varepsilon)$, by Theorem 5.1, one can find an interval $I\subset(-2+\varepsilon,2-\varepsilon)$, centered at $\lambda_{i}(W_{n})$ and with length $|I|={K^{2}C\log n}/{n}$, such that $N_{I}\geq\delta_{1}n|I|$ ($\delta_{1}>0$ small enough) with probability at least $1-n^{-C_{1}-10}$. By Cauchy interlacing law, we can find a set $J\subset\{1,\ldots,n-1\}$ with $|J|\geq N_{I}/2$ such that $|\lambda_{j}(W_{n-1})-\lambda_{i}(W_{n})|\leq|I|$ for all $j\in J$. Let $X$ be the first column of $M_{n}$ with the first entry removed. Then $X=\sqrt{n}Y$.

for some constant $C_{2}$ with probability at least $1-n^{-C_{1}-10}$. The third inequality follows from (3) by taking $t=\delta_{1}K\sqrt{C\log n}$ (say).

Thus, by union bound and symmetry, $\|u_{i}(W_{n})\|_{\infty}\leq\frac{C_{2}K\log^{1/2}n}{\sqrt{n}}$ holds with probability at least $1-n^{-C_{1}}$.

Appendix A Proof for the Edge case of Theorem 6.1

For the edge case in Theorem 6.1, we use a different approach based on the next lemma.

Let $W_{n-1}$ be the matrix $W_{n}$ with the $n$-th row and $n$-th column removed and $Y$ is the $n$-th column of $W_{n}$ with the $n$-th element $\zeta_{nn}/\sqrt{n}$ removed. If none of the eigenvalues of $W_{n-1}$ equals $\lambda_{i}(W_{n})$, then

By symmetry, it suffices to consider the case $\lambda_{i}(W_{n})\in[2-\epsilon,2+\epsilon]$ for $\epsilon>0$ very small. Denote $X$ the $n$-th column of $M_{n}$ with the $n$-th element removed. Thus $Y=\sqrt{n}$X. By Lemma 6.2, in order to show $|x|^{2}\leq C^{4}K^{4}\log^{2}n/n$ (for constant $C>C_{1}+100$) with probability at least $1-n^{-C_{1}-10}$, it is enough to show

By the projection lemma, $|u_{j}(W_{n-1})^{*}X|\leq 10K\sqrt{C\log n}$ with probability at least $1-10n^{-C}$. It suffices to show that with probability at least $1-n^{-C_{1}-10}$,

By Cauchy-Schwardz inequality, it is enough to show for some integers $1\leq T_{-}<T_{+}\leq n-1$ that

By Lemma A.1, we are going to show for some integers $T_{+},T_{-}$ satisfying $T_{+}-T_{-}=O(\log n)$ (the choice of $T_{+},T_{-}$ will be given later) that

with probability at least $1-n^{-C_{1}-10}$.

Let $\eta=\frac{K^{2}C\log n}{n\delta^{8}}$ with constant $\delta=\epsilon/1000$. Divide the real line into disjoint intervals $I_{k}$ for $k\geq 0$ where $I_{0}=(\lambda_{i}(W_{n})-\eta,\lambda_{i}(W_{n})+\eta)$. For $1\leq k\leq k_{0}=\log^{0.9}n$ (say), $|I_{k}|$ has length $2\eta\delta^{-8k}=o(1)$ and

where we denote by $\beta_{k}=\sum_{s=0}^{k}\delta^{-8s}$. The distance from $\lambda_{i}(W_{n})$ to the interval $I_{k}$ satisfies

For each such interval, by (26), for sufficiently large constant $C>0$, the number of eigenvalues $|J_{k}|=N_{I_{k}}\leq n\alpha_{I_{k}}|I_{k}|+\delta^{k+1}n|I_{k}|$ with probability at least $1-n^{-C_{1}-100}$, where $\alpha_{I_{k}}=\int_{I_{k}}\rho_{sc}(x)dx/|I_{k}|$.

For the $k$-th interval, by (3) taking $t=K\sqrt{C\log n}$, we have that, with probability at least $1-C^{\prime\prime}\exp(-C^{\prime}C\log n)\geq 1-n^{-C_{1}-100}$ for sufficiently large $C$,

For $k\geq k_{0}+1$, let the interval $I_{k}$’s have the same length of $|I_{k_{0}}|=2\delta^{-8k_{0}}\eta$. Note that the number of such intervals is bounded crudely by $o(n)$. By (26), the number of eigenvalues $|J_{k}|\leq n\alpha_{I_{k}}|I_{k}|+\delta^{k_{0}+1}n|I_{k}|$ with probability at least $1-n^{-C_{1}-100}$. And the distance from $\lambda_{i}(W_{n})$ to the interval $I_{k}$ satisfies

The contribution of such intervals can be computed similarly

with probability at least $1-n^{-C_{1}-100}$.

Summing over all intervals for $k\geq 10$ (say), we obtain

On the other hand, it follows from Riemann integration of the principal value integral that

From the explicit formula for the Stieltjes transform and from residue calculus, one obtains

for $|\lambda_{i}(W_{n})|\leq 2$, and with the right-hand side replaced by $-\lambda_{i}(W_{n})/2+\sqrt{\lambda_{i}(W_{n})^{2}-4}/2$ for $|\lambda_{i}(W_{n})|>2$. Finally, we always have

Now for the rest of eigenvalues that satisfy $|\lambda_{i}(W_{n})-\lambda_{j}(W_{n-1})|\leq|I_{0}|+|I_{1}|+\ldots+|I_{10}|\leq 4\eta/\delta^{80}$, by Theorem 5.1 and Cauchy interlacing law, the number of eigenvalues is at most ${T_{+}-T_{-}}\leq 8n\eta/\delta^{80}=8CK^{2}\log n/\delta^{88}$ with probability at least $1-n^{-C_{1}-100}$ for sufficiently large constant $C>0$. Thus

by choosing $C$ sufficiently large compared to $\delta^{-44}$. Thus, from (29), (30), (31) and (32), we have proved that there exits a constant $C>0$ such that with probability at least $1-n^{-C_{1}-10}$,

The conclusion of the second part of Theorem 1.7 follows from symmetry and union bounds.

Appendix B Local Marchenko-Pastur law for random covariance matrix and delocalization of singular vectors

In this appendix, we extend the results obtained for random Hermitian matrices discussed in the previous sections to random covariance matrices, focusing on the changes needed for the proofs. Interested reader can refer to closely related papers and (see also ).

Let $M=M_{p,n}=(\zeta_{ij})_{1\leq i\leq p,1\leq j\leq n}$ be a $p\times n$ matrix, where $p=p(n)$ is an integer such that $p\leq n$ and $\lim_{n\rightarrow\infty}p/n=y\in(0,1]$. Assume the entries of $M_{n,p}$ are independent random variables with mean zero and variance one. For such a $p\times n$ random matrix $M$, we form the $n\times n$ (sample) covariance matrix $W=W_{p,n}=\frac{1}{n}M^{*}M$. This (non-negative definite) matrix has at most $p$ non-zero eigenvalues which are ordered as

A fundamental result concerning the asymptotic limiting behavior of ESD for large covariance matrices is the Marchenko–Pastur Law (see and ).

The hard edge of the limiting support of spectrum refers to the left edge $a$ when $y=1$ where it gives rise to a singularity of $x^{-1/2}$. The cases of left edge $a$ when $y<1$ and the right edge $b$ regardless of the value of $y$ are usually called the soft edge. Recent progress on studying the local convergence to Marchenko–Pastur Law includes for the soft edge and for the hard edge. We focus on improving the previous results for the soft edge in this appendix.

Our main results for the random covariance matrices are the following local Marchenko–Pastur law (LMPL) and the delocalization property of singular vectors.

For any constants $\epsilon,\delta,C_{1}>0$, there exists a constant $C_{2}>0$ such that the following holds. Assume $\lim_{n\rightarrow\infty}p/n=y$ for some $0<y\leq 1$. Let $M=M_{p,n}=(\zeta_{ij})_{1\leq i\leq p,1\leq j\leq n}$ be a random matrix whose entries are independent $K$-bounded random variables with mean 0 and variance 1. Consider the covariance matrix $W=\frac{1}{n}M^{*}M$. Then with probability at least $1-n^{-C_{1}}$, one has