Spectrum of Heavy-Tailed Elliptic Random Matrices

Andrew Campbell Department of Mathematics, University of Colorado at Boulder, Boulder, CO 80309 [email protected] and Sean O’Rourke Department of Mathematics, University of Colorado at Boulder, Boulder, CO 80309 [email protected]

Abstract.

An elliptic random matrix $X$ is a square matrix whose $(i,j)$ -entry $X_{ij}$ is a random variable independent of every other entry except possibly $X_{ji}$ . Elliptic random matrices generalize Wigner matrices and non-Hermitian random matrices with independent entries. When the entries of an elliptic random matrix have mean zero and unit variance, the empirical spectral distribution is known to converge to the uniform distribution on the interior of an ellipse determined by the covariance of the mirrored entries.

We consider elliptic random matrices whose entries fail to have two finite moments. Our main result shows that when the entries of an elliptic random matrix are in the domain of attraction of an $\alpha$ -stable random variable, for $0<\alpha<2$ , the empirical spectral measure converges, in probability, to a deterministic limit. This generalizes a result of Bordenave, Caputo, and Chafaï for heavy-tailed matrices with independent and identically distributed entries. The key elements of the proof are (i) a general bound on the least singular value of elliptic random matrices under no moment assumptions; and (ii) the convergence, in an appropriate sense, of the matrices to a random operator on the Poisson Weighted Infinite Tree.

A. Campbell has been supported in part by NSF grant ECCS-1610003.

S. O’Rourke has been supported in part by NSF grants DMS-1810500 and ECCS-1610003.

1. Introduction

Let $\operatorname{Mat}_{n}(\mathbb{F})$ be the set of $n\times n$ matrices over the field $\mathbb{F}$ . For a matrix $A\in\operatorname{Mat}_{n}(\mathbb{C})$ , the singular values of $A$ are the square roots of the eigenvalues of $AA^{\ast}$ , where $A^{\ast}$ is the conjugate transpose of $A$ . We let $s_{n}(A)\leq\cdots\leq s_{1}(A)$ denote the ordered singular values of $A$ , and $\lambda_{1}(A),\dots,\lambda_{n}(A)\in\mathbb{C}$ be the eigenvalues of $A$ in no particular order. For a matrix $A\in\operatorname{Mat}_{n}(\mathbb{C})$ we define the empirical spectral measure

\mu_{A}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{\lambda_{i}(A)}

and the empirical singular value measure

\nu_{A}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{s_{i}(A)}.

These measures are central objects in random matrix theory, and the goal of this paper is to study the asymptotic behavior of the empirical spectral measure for a class of heavy-tailed elliptic random matrices.

Elliptic random matrices can be thought of as interpolating between random matrices whose entries are independent and identically distributed (i.i.d.) and Wigner matrices. We now give a precise definition.

Definition 1.1 (Elliptic Random Matrix).

Let $(\xi_{1},\xi_{2})$ be a random vector with complex-valued random variable entries, $\zeta$ a complex random variable, and $X_{n}=(X_{ij})_{i,j=1}^{n}$ be an $n\times n$ random matrix. $X_{n}$ is an elliptic random matrix if

(i)

$\{X_{ii}:1\leq i\leq n\}\cup\{(X_{ij},X_{ji}):1\leq i<j\leq n\}$ is a collection of independent random elements.
(ii)

the pairs $\{(X_{ij},X_{ji})\}_{1\leq i<j\leq n}$ are independent copies of $(\xi_{1},\xi_{2})$ .
(iii)

the diagonal elements $\{X_{ii}:1\leq i\leq n\}$ are independent copies of $\zeta$ .

We refer to $(\xi_{1},\xi_{2}),\zeta$ as the atom variables of the matrix $X_{n}$ .

Elliptic random matrices were originally introduced by Girko [25, 26] in the 1980s, with the name coming from the limit of the empirical spectral measure. When the entries of the matrix have four finite moments, the limiting empirical spectral measures was investigated by Naumov [38]. The general case, when the entries are only assumed to have finite variance, was studied in [39].

Theorem 1.2 (Elliptic law for real random matrices, Theorem 1.5 in [39]).

Let $X_{n}$ be an $n\times n$ elliptic random matrix with real atom variables $(\xi_{1},\xi_{2}),\zeta$ . Assume $\xi_{1},\xi_{2}$ have mean zero and unit variance, and $\mathbb{E}[\xi_{1}\xi_{2}]=:\rho$ for $-1<\rho<1$ . Additionally assume $\zeta$ has mean zero and finite variance. Then almost surely the empirical spectral measure $\mu_{\frac{1}{\sqrt{n}}X_{n}}$ of $\frac{1}{\sqrt{n}}X_{n}$ converges weakly to the uniform probability measure on

\mathcal{E}_{\rho}:=\left\{z\in\mathbb{C}:\frac{\operatorname{Re}(z)^{2}}{(1+\rho)^{2}}+\frac{\operatorname{Im}(z)^{2}}{(1-\rho)^{2}}\leq 1\right\}

as $n\rightarrow\infty$ .

Elliptic random matrices have also been studied in [28, 29, 40, 41].

Our main result, Theorem 1.6, gives an analogous result for heavy-tailed elliptic random matrices, i.e. when $\mathbb{E}|\xi_{1}|^{2}$ and $\mathbb{E}|\xi_{2}|^{2}$ are both infinite. In 1994, Cizeau and Bouchaud [18] introduced Lévy matrices as a heavy-tailed analogue of the Gaussian Orthogonal Ensemble (GOE). Instead of Gaussian entries, these matrices have entries in the domain of attraction of an $\alpha$ -stable random variable, for $0<\alpha<2$ . They predicted a deterministic limit $\mu_{\alpha}$ , which depends only on $\alpha$ , for the empirical spectral measures of these matrices when properly scaled. Convergence to a deterministic limit was first proved by Ben Arous and Guionnet [8] and later by Bordenave, Caputo, and Chafaï [12] with an alternative characterization in their study of random Markov matrices. In [13] Bordenave, Caputo, and Chafaï proved the empirical spectral measure of random matrices with i.i.d. entries in the domain of attraction of a complex $\alpha$ -stable random variable converges almost surely to an isotropic measure on $\mathbb{C}$ with unbounded support. Notably for Lévy matrices the limiting spectral measure inherits the tail behavior of the entries, while the limiting spectral measure of heavy-tailed random matrices with i.i.d. entries has a lighter tail and finite moments of every order.

Much of the work on heavy-tailed random matrices has been on the spectrum of symmetric matrices, either Lévy or sample covariance matrices [8, 4, 5, 7, 11, 2, 49, 12, 31]. Motivated by questions of delocalization from physics there has also been considerable work done in studying the eigenvectors of symmetric heavy-tailed matrices [16, 17, 1, 37, 18, 52, 9].

As is often the case in random matrix theory most of the work on heavy-tailed random matrices has focused on ensembles where the entries are independent up to symmetry conditions on the matrix. Work on matrices with dependent entries is still limited. Heavy-tailed matrices with normalized rows have been considered for random Markov chains in [12, 14] and sample correlation matrices in [31]. In [6] extreme eigenvalue statistics of symmetric heavy-tailed random matrices with $m$ -dependent entries were studied and shown to converge to a Poisson process. This $m$ -dependence can be thought of as a short range dependence meant to model stock returns that depend on stocks from the same sector of size determined by $m$ . To the best of our knowledge there are not any results on non-Hermitian heavy-tailed matrices with long range dependence between entries from different rows outside the random reversible Markov chains studied in [12].

The key question when approaching heavy-tailed elliptic random matrices is how to measure the dependence between $\xi_{1}$ and $\xi_{2}$ . Without two finite moments the covariance between $\xi_{1}$ and $\xi_{2}$ , which was the key parameter in Theorem 1.2, cannot be defined. Similar notions, such as covariation or codifference, exist for $\alpha$ -stable random variables but they do not seem sufficient for our purposes. The difference is that the covariation does not provide as much information for $\alpha$ -stable random vectors as the covariance does for Gaussian random vectors. If $X=(X_{1},X_{2})$ is a bivariate Gaussian random vector where $X_{1}$ and $X_{2}$ are standard real Gaussian random variables, then the correlation $\rho=\mathbb{E}[X_{1}X_{2}]$ uniquely determines the distribution of $X$ . Thus one approach to measuring dependence is to find a parameter which uniquely determines the distribution of a properly normalized $\alpha$ -stable random vector. The distribution of an $\alpha$ -stable random vector $Y$ in $\mathbb{R}^{n}$ is determined uniquely through its characteristic function of the form

\mathbb{E}\exp\left(iu^{T}Y\right)=\begin{cases}\exp\left(-\int_{\mathbb{S}^{n-1}}|u^{T}s|^{\alpha}(1-i\text{sign}(u^{T}s)\tan(\frac{\pi\alpha}{2}))d\theta(s)+iu^{T}y\right),\alpha\neq 1\\ \exp\left(-\int_{\mathbb{S}^{n-1}}|u^{T}s|(1+i\text{sign}(u^{T}s)\log|u^{T}s|)d\theta(s)+iu^{T}y\right),\alpha=1\end{cases}

for a finite measure $\theta$ on the unit sphere $\mathbb{S}^{n-1}$ and a deterministic vector $y$ . $Y$ can be translated and scaled so that $y=0$ and $\theta$ is a probability measure uniquely determining the distribution of $Y$ . $\theta$ is called the spectral measure of $Y$ , and it turns out to be the appropriate explicit description of the dependence between the entries of $Y$ . The definition of $\theta$ can be extended to random variables which are not stable but rather in the domain of attraction of an $\alpha$ -stable random variable, see Definition 1.3.

If the components of $Y$ are independent, then $\theta$ is supported entirely on the intersection of the axes and the unit sphere. Intuitively, when considering the mirrored entries of a random matrix, if $\theta$ is close to a measure supported on the intersection of the axes and the unit sphere, the entries are close to independent, after scaling. If $\theta$ is close to a measure supported on the set $\{(z_{1},z_{2}):|z_{1}|^{2}+|z_{2}|^{2}=1,z_{1}=\bar{z}_{2}\}$ then the matrix is close to Hermitian. Numerical simulations seem to reflect this intuition in the spectrum of elliptic random matrices, see Figures 1, 2, and 3.

1.1. Matrix distribution

We will consider elliptic random matrices whose atom variables satisfy the following conditions.

Definition 1.3 (Condition C1).

We say the atom variables $(\xi_{1},\xi_{2}),\zeta$ satisfy Condition C1 if

(i)

there exists a positive number $0<\alpha<2$ , a sequence $a_{n}=\ell(n)n^{1/\alpha}$ for a slowly varying function $\ell$ (i.e. $\lim_{t\rightarrow\infty}\ell(tx)/t=1$ for all $x>0$ ), and a finite measure $\theta_{d}$ on the unit sphere in $\mathbb{C}^{2}$ such that for all Borel subsets $D$ of the unit sphere with $\theta_{d}(\partial D)=0$ and all $r>0$ ,

\lim\limits_{n\rightarrow\infty}n\mathbb{P}\left(\frac{(\xi_{1},\xi_{2})}{\|(\xi_{1},\xi_{2})\|}\in D,\|(\xi_{1},\xi_{2})\|\geq ra_{n}\right)=\theta_{d}(D)m_{\alpha}([r,\infty)),

where $m_{\alpha}$ is a measure on $(0,\infty)$ with density $f(r)=\alpha r^{-(1+\alpha)}$ .

(ii)

there exists a constant $C>0$ such that $\mathbb{P}(|\zeta|\geq t)\leq Ct^{-\alpha}$ for all $t>0$ .

We will reserve $\theta_{d}$ to denote the measure on a sphere associated to the atom variables of a heavy-tailed elliptic random matrix; it may be worth noting that $d$ stands for “dependence” and is not a parameter. As it turns out, Condition C1 is enough to prove convergence of the empirical singular value distribution, see Theorem 1.5. We will need more assumptions to prove convergence of the empirical spectral measure.

Definition 1.4 (Condition C2).

We say $(\xi_{1},\xi_{2}),\zeta$ satisfy Condition C2 if the atom variables satisfy Condition C1 and if

(i)

there exists no $(a,b)\in\mathbb{C}^{2}\setminus\{(0,0)\}$ such that

$\operatorname{supp}(\theta_{d})\subseteq\{(z,w)\in\mathbb{C}^{2}:az+bw=0,|z|^{2}+|w|^{2}=1\}.$
(ii)

$a_{n}/n^{1/\alpha}\rightarrow c$ , for some constant $c>0$ as $n\rightarrow\infty$ .

1.2. Main results

For simplicity, let $A_{n}:=\frac{1}{a_{n}}X_{n}$ . Our first result gives the convergence of the singular values of $A_{n}-zI_{n}$ , which we will denote as $A_{n}-z$ , for $z\in\mathbb{C}$ . Here and throughout, $I_{n}$ denotes the $n\times n$ identity matrix. While interesting on its own, this is the first step in the method of Hermitization to establish convergence of the empirical spectral measure. Throughout we will use $\Rightarrow$ to denote weak convergence of probability measures and convergence in distribution of random variables.

Theorem 1.5 (Singular values of heavy-tailed elliptic random matrices).

Let $X_{n}$ be an $n\times n$ elliptic random matrix with atom variables $(\xi_{1},\xi_{2}),\zeta$ which satisfy Condition C1. Then for each $z\in\mathbb{C}$ there exists a deterministic probability measure $\nu_{z,\alpha,\theta_{d}}$ , depending only on $z,\alpha$ and $\theta_{d}$ , such that almost surely

\nu_{A_{n}-zI_{n}}\Rightarrow\nu_{z,\alpha,\theta_{d}}

as $n\rightarrow\infty$ .

Under Condition C2 we prove the convergence of the empirical spectral measure of $A_{n}$ .

Theorem 1.6 (Eigenvalues of heavy-tailed elliptic random matrices).

Let $X_{n}$ be an $n\times n$ elliptic random matrix with atom variables $(\xi_{1},\xi_{2}),\zeta$ which satisfy Condition C2. Then there exists a deterministic probability measure $\mu_{\alpha,\theta_{d}}$ , depending only on $\alpha$ and $\theta_{d}$ , such that

\mu_{A_{n}}\Rightarrow\mu_{\alpha,\theta_{d}}

in probability as $n\rightarrow\infty$ . Moreover for any smooth $\varphi:\mathbb{C}\rightarrow\mathbb{C}$ with compact support

\int_{\mathbb{C}}\varphi\ d\mu_{\alpha,\theta_{d}}=\frac{1}{2\pi}\int_{\mathbb{C}}\Delta\varphi(z)\left[\int_{0}^{\infty}\log(t)\ d\nu_{\alpha,z,\theta_{d}}\right]dz,

(1.1)

where $\nu_{\alpha,z,\theta_{d}}$ is as in Theorem 1.5 and $dz$ is the Lebesgue measure on $\mathbb{C}$ .

A distributional equation describing the Stieltjes transform of $\nu_{\alpha,z,\theta_{d}}$ is given in Proposition 4.12, which, when combined with (1.1), gives a description of $\mu_{\alpha,\theta_{d}}$ .

Remark 1.7.

If $\theta_{d}=1/2(\theta_{1}+\theta_{2})$ where $\theta_{1}$ and $\theta_{2}$ are probability measures with $\operatorname{supp}(\theta_{i})\subseteq\{(z_{1},z_{2})\in\mathbb{S}:z_{i}=0\}$ and $\theta_{1}(A)=\theta_{2}\left(\{(z_{1},z_{2}):(z_{2},z_{1})\in A\}\right)$ , then $\nu_{\alpha,z,\theta_{d}}$ in Theorem 1.5 and $\mu_{\alpha,\theta_{d}}$ in Theorem 1.6 are the same measures as in the main results of Bordenave, Caputo, and Chafaï [13]. This can be seen by computing $\theta_{d}$ when $\xi_{1}$ and $\xi_{2}$ are independent and identically distributed. It is also worth noting that if the matrix $X_{n}$ is complex Hermitian but not real symmetric, then $(\xi_{1},\xi_{2})$ will satisfy Condition C2 (i), and thus Theorem 1.6 holds.

Numerical simulations seem to give weight to the reasoning that the support of $\theta_{d}$ determines how close $\mu_{\alpha,\theta_{d}}$ is to being isotropic or supported on the real line. In Figure 3 we see as $\operatorname{supp}(\theta_{d})$ moves further from $\{z_{1}=z_{2}\}$ the mass of the spectrum moves further from the real line. A similar phenomenon appears in Figure 2: as $\operatorname{supp}(\theta_{d})$ moves further from the intersection of the axes and the sphere the spectrum becomes further from isotropic. We also see in Figure 1 that the tail behavior of the spectrum appears to depend on $\theta_{d}$ and may vary in different directions.

Spectrum similar to Figure 1 can be found in [30] where the authors study the spectral measure of $C_{1}+iC_{2}$ where $C_{1}$ and $C_{2}$ are free random Lévy elements. The authors use tools in free probability to show the spectrum is supported inside the “hyperbolic cross”, which appears to be the case for heavy-tailed elliptic random matrices for certain $\theta_{d}$ . The limiting spectral measure in [13] is not contained in a “hyperbolic cross”, which suggests $C_{1}+iC_{2}$ is not the heavy-tailed analogue of a circular element, in contrast with the case when $C_{1}$ and $C_{2}$ are free semicircular elements and $C_{1}+iC_{2}$ is a circular element.

Refer to caption — Figure 1. The plot on the left is the spectrum of an $n\times n$ matrix $n^{-1/\alpha}X$ where $\alpha=1.25$ , $n=2000$ , and the entries of $X$ are i.i.d. random variables distributed as $\varepsilon U^{-1/\alpha}$ , where $\varepsilon$ is uniformly distributed on $\{-1,1\}$ and $U$ is uniformly distributed on $[0,1]$ . The plot on the right is the spectrum of an $n\times n$ elliptic random matrix $n^{-1/\alpha}X$ where $X$ has atom variables $(U^{-1/\alpha}\cos(w),U^{-1/\alpha}\sin(w)),1$ with $\alpha=1.25$ , $n=2000$ , $U$ uniformly distributed on $[0,1]$ , and $w$ uniformly distributed on $[0,2\pi]$ . The plot window on the right is cropped to avoid extreme values.

1.3. Further questions

Since our results capture both heavy-tailed Hermitian matrices and heavy-tailed matrices with i.i.d. entries, $\mu_{\alpha,\theta_{d}}$ does actually depend on $\theta_{d}$ . However, as can be seen from [13], $\mu_{\alpha,\theta_{d}}$ does not depend on every aspect of $\theta_{d}$ .

Question 1.8.

What properties of $\theta_{d}$ determine $\mu_{\alpha,\theta_{d}}$ ?

In the case when $X_{n}$ has i.i.d. entries the limiting empirical spectral measure has an exponential tail [13] while in the case when $X_{n}$ is Hermitian it has the same tail behavior as the entries [8, 12]. This leads us to ask how the tail of $\mu_{\alpha,\theta_{d}}$ depends on $\theta_{d}$ .

Question 1.9.

How does the tail behavior of $\mu_{\alpha,\theta_{d}}$ vary with respect to $\theta_{d}$ ?

1.4. Outline

As expected with the empirical spectral measure of non-Hermitian random matrices, we make use of Girko’s Hermitization method. However, instead of considering the logarithmic potential directly, we follow the approach of Bordenave, Caputo, and Chafaï [12, 13] by using the objective method of Aldous and Steele [3] to get convergence of the matrices to an operator on Aldous’ Poisson Weighted Infinite Tree (PWIT). This objective method approach was expanded by Jung [34] to symmetric light-tailed random matrices, adjacency matrices of sparse random graphs, and symmetric random matrices whose column entries are some combination of heavy-tailed and light-tailed random variables.

In Sections 2 and 3 we give a collection of results and background for approaching the proof of Theorem 1.5. In Section 4 we define the PWIT, establish the local weak convergence of the matrices $A_{n}$ to an operator associated with the PWIT, and give a proof of Theorem 1.5. In Section 5 we give a very general bound on the least singular value of elliptic random matrices. In Section 6 we establish the uniform integrability of $\log(\cdot)$ against $\nu_{A_{n}-zI_{n}}$ and complete the proof of Theorem 1.6. The appendix contains some auxiliary results.

We conclude this section by establishing notation, giving a brief description of Hermitization, and stating some properties of $\xi_{1}$ and $\xi_{2}$ implied by Condition C2.

1.5. Notation

We now establish notation we will use throughout.

Let $[n]:=\{1,\ldots,n\}$ denote the discrete interval. For a vector $v=(v_{i})_{i=1}^{n}\in\mathbb{C}^{n}$ and a subset $I\subset[n]$ , we let $v_{I}:=(v_{i})_{i\in I}\in\mathbb{C}^{I}$ . Similarly, for an $m\times n$ matrix $A=(A_{ij})_{i\in[m],j\in[n]}$ and $I\subset[m],J\subset[n]$ , we define $A_{I\times J}:=(A_{ij})_{i\in I,j\in J}$ . For a countable set $S$ we will let $I_{S}$ denote the identity on $\ell^{2}(S)$ . In the case when $S=[n],\ell^{2}(S)=\mathbb{C}^{n}$ we will simply write $I_{n}$ or $I$ if the dimension is clear.

For a vector $x\in\mathbb{C}^{n}$ , $\|x\|$ is the Euclidean norm of $x$ . For a matrix $A$ , $A^{\mathrm{T}}$ is the transpose of $A$ and $A^{\ast}$ is the conjugate transpose of $A$ . In addition, $\|A\|=s_{1}(A)$ is the spectral norm of $A$ and $\|A\|_{2}$ is the Hilbert–Schmidt norm of $A$ defined by the formula

\|A\|_{2}=\sqrt{\operatorname{tr}(AA^{\ast})}.

For a linear, but not necessarily bounded, operator $A$ on a Hilbert space we let $\mathcal{D}(A)$ denote the domain of $A$ . We will often use the shorthand $A+z$ to denote $A+zI$ where $I$ is the identity operator.

For two complex-valued square integrable random variables $\xi$ and $\psi$ , we define the correlation between $\xi$ and $\psi$ as

\operatorname{Corr}(\xi,\psi):=\frac{\operatorname{Cov}(\xi,\psi)}{\sqrt{\operatorname{Var}(\xi)\operatorname{Var}(\psi)}},

where $\operatorname{Cov}(\xi,\psi):=\mathbb{E}[(\xi-\mathbb{E}\xi)\overline{(\psi-\mathbb{E}\psi)}]$ is the covariance between $\xi$ and $\psi$ , and $\operatorname{Var}(\xi)=\mathbb{E}|\xi-\mathbb{E}\xi|^{2}$ is the variance of $\xi$ . For two random elements $X$ and $Y$ we say $X\overset{d}{=}Y$ if $X$ and $Y$ have the same distribution. We will also say a positive random variable $Y$ stochastically dominates a positive random variable $Z$ if for all $x>0$

\mathbb{P}(Y\geq x)\geq\mathbb{P}(Z\geq x).

For a topological space $E$ , $\mathcal{B}(E)$ will always denote the Borel $\sigma$ -algebra of $E$ . $\mathbb{R}_{+}$ will denote the positive real numbers.

Throughout this paper we will use asymptotic notation ( $O,o,\Theta$ , etc.) under the assumption that $n\rightarrow\infty$ . $X=O(Y)$ if $X\leq CY$ for an absolute constant $C>0$ and all $n\geq C$ , $X=o(Y)$ if $X\leq C_{n}Y$ for $C_{n}\rightarrow 0$ , $X=\Theta(Y)$ if $cY\leq X\leq CY$ for absolute constants $C,c>0$ and all $n\geq C$ , and $X\sim Y$ if $X/Y\rightarrow 1$ .

1.6. Hermitization

Let $\mathcal{P}(\mathbb{C})$ be the set of probability measures on $\mathbb{C}$ which integrate $\log|\cdot|$ in a neighborhood of infinity. For every $\mu\in\mathcal{P}(\mathbb{C})$ the logarithmic potential $U_{\mu}$ of $\mu$ on $\mathbb{C}$ is a function $U_{\mu}:\mathbb{C}\rightarrow[-\infty,\infty)$ defined for every $z\in\mathbb{C}$ by

U_{\mu}(z)=\int_{\mathbb{C}}\log|z-w|d\mu(w).

In $\mathcal{D^{\prime}}(\mathbb{C})$ one has $\Delta U_{\mu}=2\pi\mu$ , where $\mathcal{D^{\prime}}(\mathbb{C})$ is the set of Schwartz-Sobolev distributions on $\mathbb{C}$ endowed with its usual convergence with respect to all infinitely differentiable functions with compact support.

Lemma 1.10 (Lemma A.1 in [13]).

For every $\mu,\nu\in\mathcal{P}(\mathbb{C})$ , if $U_{\mu}=U_{\nu}$ a.e. then $\mu=\nu$ .

To see the connection between logarithmic potentials and random matrices consider an $n\times n$ random matrix $A$ . If $P(z)=\det(A-zI_{n})$ is the characteristic polynomial of $A$ , then

U_{\mu_{A}}(z)=\int_{\mathbb{C}}\log|z-w|d\mu_{A}(w)=\frac{1}{n}\log|P_{A}(z)|=\int_{0}^{\infty}\log(t)d\nu_{A-z}(t).

(1.2)

Thus, through the logarithmic potential we can move from a question about eigenvalues of $A$ to singular values of $A-z$ . We refer the reader to [15] for more on the logarithmic potential in random matrix theory. One immediate issue is that $\log(\cdot)$ is not a bounded function on $\mathbb{R}_{+}$ , and thus we need more control on the integral of $\log(\cdot)$ with respect to $\{\nu_{A_{n}-z}\}_{n\geq 1}$ .

Definition 1.11 (Uniform integrability almost surely and in probability).

Let $\{\mu_{n}\}_{n=1}^{\infty}$ be a sequence of random probability measures on a measurable space $(T,\mathcal{T})$ . We say a measurable function $f:T\rightarrow\mathbb{R}$ is uniformly integrable almost surely with respect to $\{\mu_{n}\}_{n=1}^{\infty}$ if

\lim\limits_{t\rightarrow\infty}\limsup\limits_{n\rightarrow\infty}\int_{|f|>t}|f|d\mu_{n}=0,

with probability one. We say a measurable function $f:T\rightarrow\mathbb{R}$ is uniformly integrable in probability with respect to $\{\mu_{n}\}_{n=1}^{\infty}$ if for every $\varepsilon>0$

\lim\limits_{t\rightarrow\infty}\limsup\limits_{n\rightarrow\infty}\mathbb{P}\left(\int_{|f|>t}|f|d\mu_{n}>\varepsilon\right)=0.

Lemma 1.12 (Lemma 4.3 in [15]).

Let $(A_{n})_{n\geq 1}$ be a sequence of complex random matrices where $A_{n}$ is $n\times n$ for every $n\geq 1$ . Suppose for Lebesgue almost all $z\in\mathbb{C}$ , there exists a probability measure $\nu_{z}$ on $[0,\infty)$ such that

•

a.s. $(\nu_{A_{n}-z})_{n\geq 1}$ tends weakly to $\nu_{z}$
•

a.s. (resp. in probability) $\log(\cdot)$ is uniformly integrable for $(\nu_{A_{n}-z})_{n\geq 1}$ .

Then there exists a probability measure $\mu\in\mathcal{P}(\mathbb{C})$ such that

•

a.s. (resp. in probability) $(\mu_{A_{n}})_{n\geq 1}$ converges weakly to $\mu$
•

for almost every $z\in\mathbb{C}$ ,

$U_{\mu}(z)=\int_{0}^{\infty}\log(t)d\nu_{z}(t).$

1.7. Individual entries and stable random vectors.

We now state some useful properties of $\xi_{1}$ and $\xi_{2}$ implied by Condition C2. First, if $(\xi_{1}^{(1)},\xi_{2}^{(1)}),(\xi_{1}^{(2)},\xi_{2}^{(2)})\dots$ are i.i.d copies of $(\xi_{1},\xi_{2})$ , then Condition C1 (i) guarantees, see [46], there exists a sequence $b_{n}$ such that

\frac{1}{a_{n}}\sum_{i=1}^{n}(\xi_{1}^{(i)},\xi_{2}^{(i)})-b_{n}\Rightarrow Z=(Z_{1},Z_{2}),

for some $\alpha$ -stable random vector $Z$ with spectral measure $\theta_{d}$ . Condition C2 (i) guaranties neither $Z_{1}$ nor $Z_{2}$ is identically $0$ . We need the following theorem to get results on stable random vectors.

Theorem 1.13 (Theorem 2.3.9 in [47]).

Let $(X_{1},\dots,X_{d})$ be an $\alpha$ -stable vector in $\mathbb{R}^{d}$ . Then $(X_{1},\dots,X_{k})$ is an $\alpha$ -stable random vector for any $k\leq d$ .

From this, with $k=1$ for real $\xi_{1}$ and $k=2$ for complex $\xi_{1}$ , we get that $\xi_{1}$ is in the domain of attraction of an $\alpha$ -stable random variable and satisfies

\mathbb{P}(|\xi_{1}|\geq t)=L(t)t^{-\alpha}

(1.3)

for some slowly varying function $L$ . In addition,

\lim\limits_{t\rightarrow\infty}\mathbb{P}\left(\frac{\xi_{1}}{|\xi_{1}|}\in\cdot\Bigg{|}|\xi_{1}|\geq t\right)=\theta_{1}(\cdot)

(1.4)

for some probability measure $\theta_{1}$ , again see [46]. The same holds for $\xi_{2}$ with a possibly different probability measure $\theta_{2}$ . Also note

\mathbb{E}[|\xi_{i}|^{p}]<\infty

(1.5)

for all $0\leq p<\alpha$ and $i=1,2$ .

Acknowledgment

The second author thanks Djalil Chafaï for answering his questions concerning [15, Appendix A].

2. Poisson point processes and stable distributions

In this section we give a brief review of Poisson Point Processes (p.p.p.) and their relation to the order statistics of random variables in the domain of attraction of an $\alpha$ -stable distribution. See [21, 43, 44], and the references therein for proofs.

2.1. Simple point processes

Throughout this section we will assume $E=\bar{\mathbb{R}}^{n}\setminus\{0\}$ with the relative topology, where $\bar{\mathbb{R}}^{n}$ is the one point compactification of $\mathbb{R}^{n}$ , but many of the results can be extended to other topological spaces.

Denote by $\mathcal{M}(E)$ the set of simple point Radon measures

\mu=\sum_{x\in D}\delta_{x}

where $D$ is such that $D\cap(B_{r}(0))^{c}$ is a finite set for any $r>0$ and $B_{r}(0)$ is the ball of radius $r$ around the point $0$ . Denote by $\mathcal{H}(E)$ the set of supports corresponding to measures in $\mathcal{M}(E)$ . The elements of $\mathcal{H}(E)$ are called configurations.

Let $C_{K}(E)$ denote the set of real-valued continuous functions on $E$ with compact support. The vague topology on $\mathcal{M}(E)$ is the topology where a sequence $\mu_{n}$ converges to $\mu$ if for any $f\in C_{K}(E)$

\int_{E}fd\mu_{n}\rightarrow\int_{E}fd\mu.

$\mathcal{M}(E)$ with the vague topology is a Polish space, and thus complete and metrizable.

If one considers the one-to-one function $I:\mathcal{M}(E)\rightarrow\mathcal{H}(E)$ given by $I(\mu)=\operatorname{supp}(\mu)$ , then the topology of $\mathcal{M}(E)$ can be pushed forward to $\mathcal{H}(E)$ . The vague convergence in $\mathcal{M}(E)$ can be stated in terms of a convergence of the supports. Let $\mu_{n}\xrightarrow{v}\mu$ and give some labeling $\operatorname{supp}(\mu)=\{x^{(1)},x^{(2)},\dots\}$ . Then this vague convergence implies there exists labeling $\operatorname{supp}(\mu_{n})=\{x^{(1)}_{n},x^{(2)}_{n},\dots\}$ such that for all $k$ , $x_{n}^{(k)}\rightarrow x^{(k)}$ . This description will be particularly useful for our case.

A simple point process $N$ is a measurable mapping from a probability space $(\Omega,\mathcal{F},\mathbb{P})$ to $(\mathcal{M}(E),\mathcal{B}(\mathcal{M}(E)))$ , where $\mathcal{B}(\mathcal{M}(E))$ is the Borel $\sigma$ -algebra defined by the vague topology. Weak convergence of simple point processes is defined by weak convergence of the measures in the vague topology.

2.2. Poisson point process

Definition 2.1.

Let $m$ be a Borel measure on $E$ . A point process $N$ is called a Poisson Point Process (p.p.p.) with intensity measure $m$ if for any pairwise disjoint Borel sets $A_{1},\dots,A_{n}$ , the random variables $N(A_{1}),\dots,N(A_{n})$ are independent Poisson random variables with expected values $m(A_{1}),\dots,m(A_{n})$ .

Remark 2.2.

$N$ is a.s. simple if and only if $m$ is non-atomic.

The next proposition makes clear the connection between point processes and stable random variables. See Proposition 3.21 in [43] for a proof. First, we describe an important point process. Let $\theta$ be a finite measure on the unit sphere in $\mathbb{R}^{n}$ , and $m_{\alpha}$ be a measure with density $\alpha r^{-(\alpha+1)}dr$ on $\mathbb{R}_{+}$ . We let $N_{\alpha}$ denote the p.p.p. on $\mathbb{R}^{n}$ with intensity measure $\theta\times m_{\alpha}$ .

Proposition 2.3.

Let $\{\xi_{n}\}_{n\geq 1}$ be i.i.d. $\mathbb{R}^{d}$ -valued random variables. Assume there exists a finite measure $\theta$ on the unit sphere in $\mathbb{R}^{d}$ such that

\lim\limits_{n\rightarrow\infty}n\mathbb{P}\left(\frac{\xi_{n}}{\|\xi_{n}\|}\in D,\|\xi_{n}\|\geq rb_{n}\right)=\theta(D)m_{\alpha}([r,\infty)),

for every $r>0$ and all Borel subsets $D$ of the unit sphere with $\theta(\partial D)=0$ , where $b_{n}=n^{1/\alpha}L(n)$ for $0<\alpha<2$ and a slowly varying function $L$ . Then

\beta_{n}:=\sum_{i=1}^{n}\delta_{\xi_{i}/b_{n}}\Rightarrow N_{\alpha}

as $n\to\infty$ .

Remark 2.4.

In [21], Davydov and Egorov prove this convergence in $\ell^{p}$ -type topologies, under a smoothness assumption on the $\xi_{n}$ .

2.3. Useful properties of $\mathbf{N_{\alpha}}$

The following are useful and well known properties of the p.p.p. $N_{\alpha}$ . Again, see Davydov and Egorov, [21], and the references therein for more information and proofs.

Proposition 2.5.

Let $\{\lambda_{i}\}$ and $\{w_{i}\}$ be independent i.i.d. sequences where $\lambda_{1}$ has exponential distribution with mean $1$ , and $w_{1}$ is $\frac{1}{\theta(\mathbb{S}^{d-1})}\theta$ distributed, with $\theta$ a finite nonzero measure on $\mathbb{S}^{d-1}$ . Define $\Gamma_{i}=\lambda_{1}+\cdots+\lambda_{i}$ . Then, for any $\alpha>0$ ,

N_{\alpha}\overset{d}{=}\sum_{i=1}^{\infty}\delta_{\Gamma_{i}^{-1/\alpha}(\theta(\mathbb{S}^{d-1}))^{1/\alpha}w_{i}}.

Lemma 2.6.

The p.p.p. $N_{\alpha}$ has the following properties.

(1)

Almost surely there are only a finite number of points of $\operatorname{supp}(N_{\alpha})$ outside a ball of positive radius centered at the origin.
(2)

$N_{\alpha}$ is simple.
(3)

Almost surely, we can label the points from $\operatorname{supp}(N_{\alpha})$ according to the decreasing order of their norms $\operatorname{supp}(N_{\alpha})=\{(y_{1},y_{2},\dots):\|y_{1}\|>\|y_{2}\|>\dots\}$ .
(4)

With probability one, for any $p>\alpha$ ,

$\sum_{i=1}^{\infty}|y_{i}|^{p}<\infty.$

3. Bipartized resolvent matrix

In this section we follow the notation of Bordenave, Caputo, and Chafaï in [13] to define the bipartizations of matrices and operators.

3.1. Bipartization of a matrix

For an $n\times n$ complex matrix $A$ we consider a symmetrized version of $\nu_{A-zI}$ ,

\check{\nu}_{A-z}:=\frac{1}{2n}\sum_{k=1}^{n}(\delta_{s_{k}(A-z)}+\delta_{-s_{k}(A-z)}).

Let $\mathbb{C}_{+}:=\{z\in\mathbb{C}:\operatorname{Im}(z)>0\}$ and

\mathbb{H}_{+}:=\left\{U=\begin{pmatrix}\eta&z\\ \bar{z}&\eta\end{pmatrix}:\eta\in\mathbb{C}_{+},z\in\mathbb{C}\right\}\subset\text{Mat}_{2}(\mathbb{C}).

For any $z\in\mathbb{C},\eta\in\mathbb{C}_{+}$ and $1\leq i,j\leq n$ define the following $2\times 2$ matrices

U=U(z,\eta):=\begin{pmatrix}\eta&z\\ \bar{z}&\eta\end{pmatrix}\quad\text{and}\quad B_{ij}:=\begin{pmatrix}0&A_{ij}\\ \bar{A}_{ji}&0\end{pmatrix}.

Define the matrix $B\in\text{Mat}_{n}(\text{Mat}_{2}(\mathbb{C}))\simeq\text{Mat}_{2n}(\mathbb{C})$ by $B=(B_{ij})_{1\leq i,j\leq n}$ . As an element of $\text{Mat}_{2n}(\mathbb{C})$ , $B$ is Hermitian. We call $B$ the bipartization of the matrix $A$ . We define the resolvent matrix in $\text{Mat}_{n}(\text{Mat}_{2}(\mathbb{C}))$ by

R(U)=(B-U\otimes I_{n})^{-1},

so that for all $i,j$ , $R(U)_{ij}\in\text{Mat}_{2}(\mathbb{C})$ . For $1\leq k\leq n$ we write,

R(U)_{kk}=\begin{pmatrix}a_{k}(z,\eta)&b_{k}(z,\eta)\\ b^{\prime}_{k}(z\eta)&c_{k}(z,\eta)\end{pmatrix}.

Letting $B(z)=B-U(z,0)\otimes I_{n}$ we have

R(U)=(B(z)-\eta I_{2n})^{-1}.

Let $m_{\mu}$ denote the Stieltjes transform of a probability measure $\mu$ on $\mathbb{R}$ defined by

m_{\mu}(\eta)=\int_{\mathbb{R}}\frac{1}{x-\eta}d\mu(x),\qquad\eta\in\mathbb{C}_{+}.

Theorem 3.1 (Theorem 2.1 in [13]).

Let $A\in\operatorname{Mat}_{n}(\mathbb{C})$ . Then $\mu_{B(z)}=\check{\nu}_{A-z}$ ,

m_{\check{\nu}_{A-z}}(\eta)=\frac{1}{2n}\sum_{k=1}^{n}(a_{k}(z,\eta)+c_{k}(z,\eta)),

and in $\mathcal{D^{\prime}}(\mathbb{C})$ , the set of Schwartz-Sobolev distributions on $\mathbb{C}$ endowed with its usual convergence with respect to all infinitely differentiable functions with compact support,

\mu_{A}(\cdot)=-\frac{1}{\pi n}\sum_{k=1}^{n}\partial b_{k}(\cdot,0).

3.2. Bipartization of an operator

Let $V$ be a countable set and let $\ell^{2}(V)$ denote the Hilbert space defined by the inner product

\langle\phi,\psi\rangle:=\sum_{u\in V}\bar{\phi}_{u}\psi_{u},\quad\phi_{u}=\langle\delta_{u},\phi\rangle,

where $\delta_{u}$ is the unit vector supported on $u\in V$ . Let $\mathcal{D}(V)$ denote the dense subset of $\ell^{2}(V)$ of vectors with finite support. Let $(w_{uv})_{u,v\in V}$ be a collection of complex numbers such that for all $u\in V$ ,

\sum_{v\in V}|w_{uv}|^{2}+|w_{vu}|^{2}<\infty.

We then define a linear operator $A$ with domain $\mathcal{D}(V)$ by

\langle\delta_{u},A\delta_{v}\rangle=w_{uv}.

(3.1)

Let $\hat{V}$ be a set in bijection with $V$ , and let $\hat{v}\in\hat{V}$ be the image of $v\in V$ under the bijection. Let $V^{b}=V\cup\hat{V}$ , and define the bipartization of $A$ as the symmetric operator $B$ on $\mathcal{D}(V^{b})$ by

\langle\delta_{u},B\delta_{\hat{v}}\rangle=\overline{\langle\delta_{\hat{v}},B\delta_{u}\rangle}=w_{uv},

\langle\delta_{u},B\delta_{v}\rangle=\langle\delta_{\hat{u}},B\delta_{\hat{v}}\rangle=0.

Let $\Pi_{u}:\ell^{2}(V^{b})\rightarrow\operatorname{Span}\{\delta_{u},\delta_{\hat{u}}\}$ denote the orthogonal projection onto the span of $\delta_{u},\delta_{\hat{u}}$ . $\operatorname{Span}\{\delta_{u},\delta_{\hat{u}}\}$ is isomorphic to $\mathbb{C}^{2}$ under the map $\delta_{u}\mapsto e_{1},\delta_{\hat{u}}\mapsto e_{2}$ . Under this isomorphism we may think of $\Pi_{u}B\Pi_{v}^{*}$ as a linear map from $\mathbb{C}^{2}$ to $\mathbb{C}^{2}$ with matrix representation

\Pi_{u}B\Pi_{v}^{*}=\begin{pmatrix}0&w_{uv}\\ \bar{w}_{vu}&0\end{pmatrix}.

Let $B(z)=B-U(z,0)\otimes I_{V}$ . For simplicity we will denote by $B(z)$ the closure of $B(z)$ . Recall the sum of an essentially self-adjoint operator and a bounded self-adjoint operator is essentially self-adjoint, thus if $B$ is (essentially) self-adjoint then $B(z)$ is (essentially) self-adjoint. For $\eta\in\mathbb{C}_{+}$ , $U(z,\eta)\in\mathbb{H}_{+}$ we define the resolvent operator

R(U):=(B(z)-\eta I_{V^{b}})^{-1},

and

R(U)_{vv}=\Pi_{v}R(U)\Pi_{v}^{*}=\begin{pmatrix}a_{v}(z,\eta)&b_{v}(z,\eta)\\ b_{v}^{\prime}(z,\eta)&c_{v}(z,\eta)\end{pmatrix}.

(3.2)

Lemma 3.2.

If $a_{v},b_{v},c_{v},b_{v}^{\prime}$ are defined by (3.2), then

•

for each $z\in\mathbb{C}$ , $a_{v}(z,\cdot),c_{v}(z,\cdot):\mathbb{C}_{+}\rightarrow\mathbb{C}_{+}$ ,
•

the functions $a_{v}(z,\cdot),b_{v}(z,\cdot),b_{v}^{\prime}(z,\cdot),c_{v}(z,\cdot)$ are analytic on $\mathbb{C}_{+}$ ,

•

and

|a_{v}|\leq(\operatorname{Im}(\eta))^{-1},\quad|c_{v}|\leq(\operatorname{Im}(\eta))^{-1},\quad|b_{v}|\leq(2\operatorname{Im}(\eta))^{-1},\quad\text{and}\quad|b_{v}^{\prime}|\leq(2\operatorname{Im}(\eta))^{-1}.

Moreover, if $\eta\in i\mathbb{R}_{+}$ , then $a_{v},c_{v}$ are pure imaginary and $b_{v}^{\prime}=\bar{b}_{v}$ .

See Reed and Simon [42] for a proof of the first two statements and [13] for the last.

4. Convergence to the Poisson Weighted Infinite Tree

4.1. Operators on a tree

Consider a tree $T=(V,E)$ on a vertex set $V$ with edge set $E$ . We say $u\sim v$ if $\{u,v\}\in E$ . Assume if $\{u,v\}\notin E$ then $w_{uv}=w_{vu}=0$ , in particular $w_{vv}=0$ for all $v\in V$ . We consider the operator $A$ defined by (3.1). We begin with useful sufficient conditions for a symmetric linear operator to be essentially self-adjoint, which will be very important for our use.

Lemma 4.1 (Lemma A.3 in [12]).

Let $\kappa>0$ and $T=(V,E)$ be a tree. Assume that for all $u,v\in V$ , $w_{uv}=\bar{w}_{vu}$ and if $\{u,v\}\notin E$ then $w_{uv}=w_{vu}=0$ . Assume that there exists a sequence of connected finite subsets $(S_{n})_{n\geq 1}$ of $V$ , such that $S_{n}\subset S_{n+1}$ , $\bigcup_{n}S_{n}=V$ , and for every $n$ and $v\in S_{n}$ ,

\sum_{u\notin S_{n}:u\sim v}|w_{uv}|^{2}\leq\kappa.

Then $A$ is essentially self-adjoint.

Corollary 4.2 (Corollary 2.4 in [13]).

Let $\kappa>0$ and $T=(V,E)$ be a tree. Assume that if $\{u,v\}\notin E$ then $w_{uv}=w_{vu}=0$ . Assume there exists a sequence of connected finite subsets $(S_{n})_{n\geq 1}$ of $V$ , such that $S_{n}\subset S_{n+1}$ , $\bigcup_{n}S_{n}=V$ , and for every $n$ and $v\in S_{n}$ ,

\sum_{u\notin S_{n}:u\sim v}(|w_{uv}|^{2}+|w_{vu}|^{2})\leq\kappa.

Then for all $z\in\mathbb{C}$ , $B(z)$ is self-adjoint.

The advantages of defining an operator on a tree also include the following recursive formula for the resolvents, see Lemma 2.5 in [13] for a proof.

Proposition 4.3.

Assume $B$ is sellf-adjoint and let $U=U(z,\eta)\in\mathbb{H}_{+}$ . Then

R(U)_{\varnothing\varnothing}=-\left(U+\sum_{v\sim\varnothing}\begin{pmatrix}0&w_{\varnothing v}\\ \bar{w}_{v\varnothing}&0\end{pmatrix}\tilde{R}(U)_{vv}\begin{pmatrix}0&w_{v\varnothing}\\ \bar{w}_{\varnothing v}&0\end{pmatrix}\right)^{-1},

(4.1)

where $\tilde{R}(U)_{kk}:=\Pi_{v}R_{B_{v}}\Pi_{v}^{*}$ where $B_{v}$ is the bipartization of the operator $A$ restricted to $\ell^{2}(V_{v})$ , and $V_{v}$ is the subtree of $V$ of vertices whose path to $\varnothing$ contains $v$ .

4.2. Local operator convergence.

We now define a useful type of convergence.

Definition 4.4 (Local Convergence).

Suppose $(A_{n})$ is a sequence of bounded operators on $\ell^{2}(V)$ and $A$ is a linear operator on $\ell^{2}(V)$ with domain $\mathcal{D}(A)\supset\mathcal{D}(V)$ . For any $u,v\in V$ we say that $(A_{n},u)$ converges locally to $(A,v)$ , and write

(A_{n},u)\rightarrow(A,v),

if there exists a sequence of bijections $\sigma_{n}:V\rightarrow V$ such that $\sigma_{n}(v)=u$ and, for all $\phi\in\mathcal{D}(V)$ ,

\sigma_{n}^{-1}A_{n}\sigma_{n}\phi\rightarrow A\phi,

in $\ell^{2}(V)$ , as $n\rightarrow\infty$ .

Here we use $\sigma_{n}$ for the bijection on $V$ and the corresponding linear isometry defined in the obvious way. This notion of convergence is useful to random matrices for two reasons. First, we will make a choice on how to define the action of an $n\times n$ matrix on $\ell^{2}(V)$ , and the bijections $\sigma_{n}$ help ensure the choice of location for the support of the matrix does not matter. Second, local convergence also gives convergence of the resolvent operator at the distinguished points $u,v\in V$ . This comes down to the fact that local convergence is strong operator convergence, up to the isometries. See [13] for details.

Theorem 4.5 (Theorem 2.7 in [13]).

Assume $(A_{n},u)\rightarrow(A,v)$ for some $u,v\in V$ . Let $B_{n}$ be the self-adjoint bipartized operator of $A_{n}$ . If the bipartized operator $B$ of $A$ is self-adjoint and $\mathcal{D}(V^{b})$ is a core for $B$ (i.e., the closure $B$ restricted to $\mathcal{D}(V^{b})$ is $B$ ), then for all $U\in\mathbb{H}_{+},$

R_{B_{n}}(U)_{uu}\rightarrow R_{B}(U)_{vv}.

To apply this to random operators we say that $(A_{n},u)\rightarrow(A,v)$ in distribution if there exists a sequence of random bijections $\sigma_{n}$ such that $\sigma_{n}^{-1}A_{n}\sigma_{n}\phi\rightarrow A\phi$ in distribution for every $\phi\in\mathcal{D}(V^{b})$ .

4.3. Poisson Weighted Infinite Tree (PWIT)

Let $\rho$ be a positive Radon measure on $\mathbb{C}^{n}\setminus\{0\}$ such that $\rho(\mathbb{C}^{n}\setminus\{0\})=\infty$ . $\mathbf{PWIT}(\rho)$ is the random weighted rooted tree defined as follows. The vertex set of the tree is identified with $\mathbb{N}^{f}:=\bigcup_{k\in\mathbb{N}\cup\{0\}}\mathbb{N}^{k}$ by indexing the root as $\mathbb{N}^{0}=\varnothing$ , the offspring of the root as $\mathbb{N}$ and, more generally, the offspring of some $v\in\mathbb{N}^{k}$ as $(v1),(v2),\cdots\in\mathbb{N}^{k+1}$ . Define $T$ as the tree on $\mathbb{N}^{f}$ with edges between parents and offspring. Let $\{\Xi_{v}\}_{v\in\mathbb{N}^{f}}$ be independent realizations of a Poisson point process with intensity measure $\rho$ . Let $\Xi_{\varnothing}=\{y_{1},y_{2},\dots\}$ be ordered such that $\|y_{1}\|\geq\|y_{2}\|\geq\cdots$ , and assign the weight $y_{i}$ to the edge between $\varnothing$ and $i$ , assuming such an ordering is possible. More generally assign the weight $y_{vi}$ to the edge between $v$ and $vi$ where $\Xi_{v}=\{y_{v1},y_{v2},\dots\}$ where $\|y_{v1}\|\geq\|y_{v2}\|\geq\cdots.$

Consider a realization of $\mathbf{PWIT}(\theta_{d}\times m_{\alpha})$ , with $y_{vk}=(y_{vk}^{(1)},y_{vk}^{(2)})$ . Even though the measure $\theta_{d}\times m_{\alpha}$ has a more natural representation in polar coordinates, we let $(y_{vk}^{(1)},y_{vk}^{(2)})$ be the Cartesian coordinates of $y_{vk}$ . Define an operator $A$ on $\mathcal{D}(\mathbb{N}^{f})$ by the formulas

\langle\delta_{v},A\delta_{vk}\rangle=y_{vk}^{(1)},\quad\text{ and }\quad\langle\delta_{vk},A\delta_{v}\rangle=y_{vk}^{(2)}

(4.2)

and $\langle\delta_{v},A\delta_{u}\rangle=0$ otherwise. For $0<\alpha<2$ , we know by Lemma 2.6 that the points in $\Xi_{v}$ are almost surely square summable for every $v\in\mathbb{N}^{f}$ , and thus $A$ is actually a well defined linear operator on $\mathcal{D}(\mathbb{N}^{f})$ , though is possibly unbounded on $\ell^{2}(\mathbb{N}^{f})$ . Before showing the local convergence of the random matrices $A_{n}$ to $A$ we will show the bipartization of $A$ is self-adjoint.

Proposition 4.6.

With probability one, for all $z\in\mathbb{C}$ , $B(z)$ is self-adjoint, where $B(z)$ is the bipartization of the operator $A$ defined by (4.2).

We begin with a lemma on point processes, proved in Lemma A.4 from [12], before checking our criterion for self-adjointness.

Lemma 4.7.

Let $\kappa>0,0<\alpha<2$ and let $0<x_{1}<x_{2}<\cdots$ be a Poisson process of intensity $1$ on $\mathbb{R}_{+}$ . Define $\tau=\inf\{t\in\mathbb{N}:\sum_{k=t+1}^{\infty}x_{k}^{-2/\alpha}\leq\kappa\}.$ Then $\mathbb{E}\tau$ is finite and goes to $0$ as $\kappa$ goes to infinity.

Proof of Proposition 4.6.

For $\kappa>0$ and $v\in\mathbb{N}^{f}$ define

\tau_{v}=\inf\left\{t\geq 0:\sum_{k=t+1}^{\infty}\|y_{vk}\|^{2}\leq\kappa\right\}.

Note if $N$ is a homogeneous Poisson process on $\mathbb{R}_{+}$ with intensity 1 and $f(x)=x^{-1/\alpha}$ , then $f(N)$ is Poisson process with intensity measure $\alpha r^{-1-\alpha}dr$ . Thus by Lemma 4.7, $\kappa>0$ can be chosen such that $\mathbb{E}\tau_{v}<1$ for any fixed $v$ . Since the random variables $\{\tau_{v}\}_{v\in\mathbb{N}^{f}}$ are i.i.d. this $\kappa$ works for all $v$ . Fix such a $\kappa$ . We now color the vertices red and green in an effort to build the sets $S_{n}$ in Corollary 4.2. Put a green color on all vertices $v$ such that $\tau_{v}\geq 1$ and a red color otherwise. Define the sub-forest $T^{g}$ of $T$ where an edge between $v$ and $vk$ is included if $v$ is green and $1\leq k\leq\tau_{v}$ . If the root $\varnothing$ is red let $S_{1}=\{\varnothing\}$ . Otherwise let $T^{g}_{\varnothing}=(V^{g}_{\varnothing},E^{g}_{\varnothing})$ be the subtree of $T^{g}$ containing $\varnothing$ . Let $Z_{n}$ denote the number of vertices in $T^{g}_{\varnothing}$ at a depth $n$ from the root, then $Z_{n}$ is a Galton-Watson process with offspring distribution $\tau_{\varnothing}$ . It is well known that if $\mathbb{E}\tau_{\varnothing}<1$ , then the tree is almost surely finite, see Theorem 5.3.7 in [22]. Let $L^{g}_{\varnothing}$ be the leaves of the tree $T^{g}_{\varnothing}$ . Set $S_{1}:=\bigcup_{v\in L^{g}_{\varnothing}}\{vk:1\leq k\leq\tau_{v}\}\bigcup V^{g}_{\varnothing}$ . It is clear for any $v\in S_{1}$ ,

\sum_{u\notin S_{1}:u\sim v}(|y_{uv}|^{2}+|y_{vu}|^{2})\leq\kappa.

Now define the outer boundary of $\{\varnothing\}$ as $\partial_{\tau}\{\varnothing\}=\{1,\dots,\max(\tau_{\varnothing},1)\}$ and for $v=(i_{1}\cdots i_{k})$ set $\partial_{\tau}\{v\}=\{(i_{1}\cdots i_{k-1}(i_{k}+1))\}\cup\{(i_{1}\cdots i_{k}1),\dots,(i_{1}\cdots i_{k}\max(\tau_{v},1))\}$ . For a connected set $S$ define its outer boundary as

\partial_{\tau}S=\left(\bigcup_{v\in S}\partial_{\tau}\{v\}\right)\setminus S.

Now for each $u_{1},\dots,u_{k}\in\partial_{\tau}S_{1}$ apply the above process to get subtrees $\{T^{g}_{u_{i}}=(V^{g}_{u_{i}},E^{g}_{u_{i}})\}_{i=1}^{k}$ with roots $u_{i}$ and the leaves of tree $T^{g}_{u_{i}}$ denoted by $L^{g}_{u_{i}}$ . Set

S_{2}:=S_{1}\cup\left(\bigcup_{i=1}^{k}(V^{g}_{u_{i}}\cup_{v\in L^{g}_{u_{i}}}\{vj:1\leq j\leq\tau_{v}\})\right).

Apply this procedure iteratively to get the sequence of subsets $(S_{n})_{n\geq 1}$ . Apply Corollary 4.2 to complete the proof. ∎

4.4. Local convergence

For an $n\times n$ matrix $M$ we aim to define $M$ as a bounded operator on $\ell^{2}(\mathbb{N}^{f})$ . For $1\leq i,j,\leq n,$ let $\langle\delta_{i},M\delta_{j}\rangle=M_{ij}$ . and $\langle\delta_{u},M\delta_{v}\rangle=0$ otherwise.

Theorem 4.8.

Let $(P_{n})_{n\geq 1}$ be a sequence of uniformly distributed random $n\times n$ permutation matrices, independent of $A_{n}$ . Then, in distribution, $(P_{n}A_{n}P_{n}^{T},1)\rightarrow(A,\varnothing)$ where $A$ is the operator defined by (4.2).

Remark 4.9.

This theorem holds for any sequence of permutation matrices $P_{n}$ regardless of independence or distribution, but for our use later it is important they are independent of $A_{n}$ and uniformly distributed. This is to get around the fact the entries of $A_{n}$ are not exchangeable.

The rest of this subsection is devoted to the proof of Theorem 4.8. The procedure follows along the same lines as Bordenave, Caputo, and Chafaï in [12] and [13]. We will define a network as a graph with edge weights taking values in some normed space. To begin let $G_{n}$ be the complete network on $\{1,\dots,n\}$ whose weight on edge $\{i,j\}$ equals $\xi^{n}_{ij}$ for some collection $(\xi^{n}_{ij})_{1\leq i\leq j\leq n}$ of i.i.d. random variables taking values in some normed space. Now consider the rooted network $(G_{n},1)$ with the distinguished vertex $1$ . For any realization $(\xi_{ij}^{n})$ , and for any $B,H\in\mathbb{N}$ such that $(B^{H+1}-1)/(B-1)\leq n$ , we will define a finite rooted subnetwork $(G_{n},1)^{B,H}$ of $(G_{n},1)$ whose vertex set coincides with a $B$ -ary tree of depth $H$ . To this end we partially index the vertices of $(G_{n},1)$ as elements in

J_{B,H}:=\bigcup_{l=0}^{H}\{1,\dots,B\}^{l}\subset\mathbb{N}^{f},

the indexing being given by an injective map $\sigma_{n}$ from $J_{B,H}$ to $V_{n}:=\{1,\dots,n\}$ . We set $I_{\varnothing}:=\{1\}$ and the index of the root $\sigma_{n}^{-1}(1)=\varnothing$ . The vertex $v\in V_{n}\setminus I_{\varnothing}$ is given the index $(k)=\sigma_{n}^{-1}(v),1\leq k\leq B$ , if $\xi^{n}_{1,v}$ has the $k$ -th largest norm value among $\{\xi_{1j}^{n},j\neq 1\}$ , ties being broken by lexicographic order¹¹1To help keep track of notation in this section, note that $v=(w)\in V_{n}$ if $w\in J_{B,H}$ and $\sigma_{n}(w)=v$ .. This defines the first generation, and let $I_{1}$ be the union of $I_{\varnothing}$ and this generation. If $H\geq 2$ repeat this process for the vertex labeled $(1)$ on $V_{n}\setminus I_{1}$ to order $\{\xi_{(1)j}^{n}\}_{j\in V_{n}\setminus I_{1}}$ to get $\{11,12,\dots,1B\}$ . Define $I_{2}$ to be the union of $I_{1}$ and this new collection. Repeat again for $(2),(3),\dots,(B)$ to get the second generation and so on. Call this vertex set $V_{n}^{B,H}=\sigma_{n}J_{B,H}$ .

For a realization $T$ of $\mathbf{PWIT}(\rho)$ , recall we assign the weight $y_{vk}$ to the edge $\{v,vk\}$ . Then $(T,\varnothing)$ is a rooted network. Call $(T,\varnothing)^{B,H}$ the finite rooted subnetwork obtained by restricting $(T,\varnothing)$ to the vertex set $J_{B,H}$ . If an edge is not present in $(T,\varnothing)^{B,H}$ assign the weight $0$ . We say a sequence $(G_{n},1)^{B,H}$ , for fixed $B$ and $H$ , converges in distribution, as $n\rightarrow\infty$ , to $(T,\varnothing)^{B,H}$ if the joint distribution of the weights converges weakly.

Let $\pi_{n}$ be the permutation on $\{1,\dots,n\}$ associated to the permutation matrix $P_{n}$ . We let

\xi_{ij}^{n}=\left(\xi_{ij}^{n,(1)},\xi_{ij}^{n,(2)}\right):=\left(\frac{X_{\pi_{n}(i),\pi_{n}(j)}}{a_{n}},\frac{X_{\pi_{n}(j),\pi_{n}(i)}}{a_{n}}\right).

We now consider $(G_{n},1)^{B,H}$ with weights $\xi_{ij}^{n}$ and a realization, $T$ , of $\mathbf{PWIT}(\theta_{d}\times m_{\alpha})$ . We aim to show $(G_{n},1)^{B,H}$ converges in distribution to $(T,\varnothing)^{B,H}$ , for fixed $B,H$ as $n\rightarrow\infty$ .

Order the elements of $J_{B,H}$ lexicographically, i.e. $\varnothing\prec 1\prec 2\prec\cdots\prec B\prec 11\prec 12\prec\cdots\prec B\cdots B$ . For $v\in J_{B,H}$ let $\mathcal{O}_{v}$ denote the offspring of $v$ in $(G,1)^{B,H}$ . By construction $I_{\varnothing}=\{1\}$ and $I_{v}=\sigma_{n}\left(\bigcup_{w\prec v}\mathcal{O}_{w}\right)$ , where $w\prec v$ must be strict in this union. Thus at every step of the indexing procedure we order the weights of neighboring edges not already considered at a previous step. Thus for all $v$ ,

(\xi_{\sigma_{n}(v),j}^{n})_{j\notin I_{v}}\overset{d}{=}(\xi_{1j}^{n})_{1<j\leq n-|I_{v}|}.

Note that by independence, Proposition 2.3 still holds if you take the empirical sum over $\{1,\dots,n\}\setminus I$ for any fixed finite set $I$ . Thus by Proposition 2.3 the weights from a fixed parent to its offspring in $(G_{n},1)^{B,H}$ converge weakly to those of $(T,\varnothing)^{B,H}$ . By independence we can extend this to joint convergence. Because for any fixed $n$ , $(G_{n},1)^{B,H}$ is still a complete network on $V_{n}^{B,H}$ , we must now check the weights connected to vertices not indexed above converge to zero, which is the weight given to edges not in the tree. For $v,w\in J_{B,H}$ define

x_{v,w}^{n}:=\xi_{\sigma_{n}(v),\sigma_{n}(w)}^{n}.

Also let $\{z_{v,w}^{n},v,w\in J_{B,H}\}$ denote independent variables distributed as $\|\xi_{12}^{n}\|$ . Let $E^{B,H}$ denote the set of edges $\{v,w\}\in J_{B,H}\times J_{B,H}$ that do not belong to the finite subtree $(T,\varnothing)^{B,H}$ . Because we have sorted out the largest elements, the vector $\{\|x_{v,w}^{n}\|,\{v,w\}\in E^{B,H}\}$ is stochastically dominated by the vector $Z_{n}:=\{z_{v,w}^{n},\{v,w\}\in E^{B,H}\}$ (see [12] Lemma 2.7). Since $J_{B,H}$ is finite, the vector $Z_{n}$ converges to $0$ as $n\rightarrow\infty$ . Thus $(G,1)^{B,H}\Rightarrow(T,\varnothing)^{B,H}$ .

Let $A$ be the operator associated to $\mathbf{PWIT}(\theta_{d}\times m_{\alpha})$ defined by (4.2). For fixed $B,H$ let $\sigma_{n}^{B,H}$ be the map $\sigma_{n}$ above associated to $(G,1)^{B,H}$ , and arbitrarily extend $\sigma_{n}^{B,H}$ to a bijection on $\mathbb{N}^{f}$ , where $V_{n}$ is considered in the natural way as a subset of the offspring of $\varnothing$ . From the Skorokhod Representation Theorem we may assume $(G_{n},1)^{B,H}$ converges almost surely to $(T,\varnothing)^{B,H}$ . Thus there is a sequences $B_{n},H_{n}$ tending to infinity and $\hat{\sigma}_{n}:=\sigma_{n}^{B_{n},H_{n}}$ such that for any pair $v,w\in\mathbb{N}^{f}$ , $\xi_{\hat{\sigma}_{n}(v),\hat{\sigma}_{n}(w)}^{n}$ converges almost surely to

\begin{cases}y_{vk},\quad\text{if $w=vk$ for some $k$}\\ y_{wk},\quad\text{if $v=wk$ for some $k$}\\ 0,\quad\text{otherwise.}\end{cases}

Thus almost surely

\langle\delta_{v},\hat{\sigma}_{n}^{-1}P_{n}A_{n}P_{n}^{T}\hat{\sigma}_{n}\delta_{w}\rangle=\xi_{\hat{\sigma}_{n}(v),\hat{\sigma}_{n}(w)}^{n,(i)}\rightarrow\langle\delta_{v},A\delta_{w}\rangle,

where $(i)=1,2$ depending on whether $w$ is an offspring of $v$ , vice versa, or we take the convention $i=1$ if neither in which case $\xi_{\hat{\sigma}_{n}(v),\hat{\sigma}_{n}(w)}^{n,(1)}\rightarrow 0$ . To prove the local convergence of operators it is sufficient, by linearity, to prove point wise convergence for any $\delta_{w}$ . For convenience let $\phi_{n}^{w}:=\hat{\sigma}_{n}^{-1}P_{n}A_{n}P_{n}^{T}\hat{\sigma}_{n}\delta_{w}$ . Thus all that remains to be shown to complete the proof of Theorem 4.8 is that almost surely as $n\rightarrow\infty$

\sum_{u\in\mathbb{N}^{f}}|\langle\delta_{u},\phi_{n}^{w}\rangle-\langle\delta_{u},A\delta_{w}\rangle|^{2}\rightarrow 0.

Since for every $u$ , $\langle\delta_{u},\phi_{n}^{w}\rangle\rightarrow\langle\delta_{u},A\delta_{w}\rangle$ and $\langle\delta_{u},A\delta_{w}\rangle$ is square summable in $u$ it is enough to show that if $u\in\mathbb{N}^{f}$ are given some indexing by $\mathbb{N}$ $u_{1},u_{2},\dots$ , then

\sup_{n\geq 1}\sum_{i=k}^{\infty}|\langle\delta_{u_{i}},\phi_{n}^{w}\rangle|^{2}\rightarrow 0

as $k\rightarrow\infty$ . This follows from the uniform square-integrability of order statistics, see Lemma 2.4 of [12]. This completes the proof of Theorem 4.8.

4.5. Resolvent matrix

. Let $R$ be the resolvent of the bipartized random operator of $A$ . For $U(z,\eta)\in\mathbb{H}_{+}$ , set

R(U)_{\varnothing\varnothing}=\begin{pmatrix}a(z,\eta)&b(z,\eta)\\ b^{\prime}(z,\eta)&c(z,\eta)\end{pmatrix}.

(4.3)

We have the following result.

Theorem 4.10.

Let $P_{n}$ , $A_{n}$ , and $A$ be as in the Theorem 4.8. Since $B(z)$ is almost surely self-adjoint we may almost surely define $R$ , the resolvent of $B(z)$ . Let $\hat{R}_{n}$ be the resolvent of the bipartized matrix of $P_{n}A_{n}P_{n}^{T}$ . For all $U\in\mathbb{H}_{+}$ ,

\hat{R}_{n}(U)_{11}\Rightarrow R(U)_{\varnothing\varnothing}

as $n\to\infty$ .

Proof.

This follows immediately from Theorem 4.8, Proposition 4.6, and Theorem 4.5. ∎

As functions, the entries of the resolvent matrix are continuous, and by Lemma 3.2 are bounded. Thus

\lim\limits_{n\rightarrow\infty}\mathbb{E}\hat{R}_{n}(U)_{11}=\mathbb{E}R(U)_{\varnothing\varnothing}.

(4.4)

Note that by independence of $\pi_{n}$ and $A_{n}$

\mathbb{E}\hat{R}_{n}(U)_{11}=\mathbb{E}R_{n}(U)_{\pi_{n}^{-1}(1)\pi_{n}^{-1}(1)}=\mathbb{E}\frac{1}{n}\sum_{i=1}^{n}R_{n}(U)_{ii}.

(4.5)

This is the reason for the choice of uniformly distributed $P_{n}$ independent of $A_{n}$ .

Theorem 4.11.

For all $z\in\mathbb{C}$ , almost surely the measures $\check{\nu}_{A_{n}-z}$ converge weakly to a deterministic probability measure $\check{\nu}_{\alpha,z,\theta_{d}}$ whose Stieltjes transform is given by

m_{\check{\nu}_{\alpha,z,\theta_{d}}}(\eta)=\mathbb{E}a(z,\eta),

for $\eta\in\mathbb{C}_{+}$ and $a(z,\eta)$ in (4.3).

Proof.

By Proposition 4.6 for every $z\in\mathbb{C}$ , $B(z)$ is almost surely essentially self-adjoint. Thus, using the Borel functional calculus, there exists almost surely a random probability measure $\nu_{\varnothing,z}$ on $\mathbb{R}$ such that

a(z,\eta)=\langle\delta_{\varnothing},R(U)\delta_{\varnothing}\rangle=\int_{\mathbb{R}}\frac{d\nu_{\varnothing,z}(x)}{x-\eta}=m_{\nu_{\varnothing,z}}(\eta).

See Theorem VIII.5 in [42] for more on this measure and the Borel functional calculus for unbounded self-adjoint operators. Define $R_{n}$ as the resolvent matrix of $B_{n}(z)$ , the bipartized matrix of $A_{n}$ . For $U(z,\eta)\in\mathbb{H}_{+}$ , we write

R_{n}(U)_{kk}=\begin{pmatrix}a_{k}(z,\eta)&b_{k}(z,\eta)\\ b^{\prime}_{k}(z\eta)&c_{k}(z,\eta)\end{pmatrix},\qquad\hat{R}_{n}(U)_{kk}=\begin{pmatrix}\hat{a}_{k}(z,\eta)&\hat{b}_{k}(z,\eta)\\ \hat{b}^{\prime}_{k}(z\eta)&\hat{c}_{k}(z,\eta)\end{pmatrix}.

By Theorem 3.1

m_{\mathbb{E}\check{\nu}_{A-z}}(\eta)=\mathbb{E}\frac{1}{2n}\sum_{k=1}^{n}(a_{k}(z,\eta)+c_{k}(z,\eta))=\frac{1}{2}\left(\mathbb{E}\hat{a}_{1}(z,\eta)+\mathbb{E}\hat{c}_{1}(z,\eta)\right)=\mathbb{E}\hat{a}_{1}(z,\eta).

Thus, by (4.4) and (4.5),

\lim\limits_{n\rightarrow\infty}m_{\mathbb{E}\check{\nu}_{A-z}}(\eta)=\mathbb{E}a(z,\eta).

It follows that $\mathbb{E}\check{\nu}_{A_{n}-z}$ converges to some deterministic probability measure $\check{\nu}_{z,\alpha,\theta_{d}}=\mathbb{E}\nu_{\varnothing,z}$ . By Lemma A.2 $\check{\nu}_{A_{n}-z}$ concentrates around its expected value, and thus by the Borel-Cantelli Lemma $\check{\nu}_{A_{n}-z}$ converges almost surely to $\check{\nu}_{z,\alpha,\theta_{d}}$ . ∎

Theorem 1.5 follows immediately from Theorem 4.11. We conclude this section with a recursive distributional equation describing $R(U)_{\varnothing\varnothing}$ .

Proposition 4.12.

Let $\theta_{d}$ be a probability measure. Let $(w^{(1)},w^{(2)})$ be a $\theta_{d}$ distributed random vector independent of the matrix given in (4.3). Additionally let $\rho_{z,\eta}$ be the measure on $\mathbb{C}^{4}\cong\mathbb{R}^{8}$ which is the distribution of the random vector

\begin{pmatrix}c(z,\eta)|w^{(1)}|^{2}\\ b^{\prime}(z,\eta)w^{(1)}w^{(2)}\\ b(z,\eta)\bar{w}^{(1)}\bar{w}^{(2)}\\ a(z,\eta)|w^{(2)}|^{2}\end{pmatrix},

(4.6)

where $a(z,\eta),b(z,\eta),b^{\prime}(z,\eta),$ and $c(z,\eta)$ are as in (4.3). Then the matrix given in (4.3) satisfies the following recursive distributional equation

\begin{pmatrix}a(z,\eta)&b(z,\eta)\\ b^{\prime}(z,\eta)&c(z,\eta)\end{pmatrix}\overset{d}{=}-\left(\begin{pmatrix}\eta&z\\ \bar{z}&\eta\end{pmatrix}+\begin{pmatrix}S_{1}&S_{2}\\ S_{3}&S_{4}\end{pmatrix}\right)^{-1}

(4.7)

where $S=(S_{1},S_{2},S_{3},S_{4})$ is an $\alpha/2$ -stable random vector with spectral measure is given by the image of the measure $\frac{\Gamma(2-\alpha/2)\cos(\pi\alpha/4)}{1-\alpha/2}\|v\|^{\alpha/2}d\rho_{z,\eta}(v)$ under the map $v\mapsto\frac{v}{\|v\|}$ .

The proof of Proposition 4.12 is given in Appendix A.4.

5. Least singular values of elliptic random matrices

Now that we have proven Theorem 1.5, we move on to show that $\log(\cdot)$ is uniformly integrable, in probability, with respect to $\{\nu_{A_{n}-zI_{n}}\}_{n\geq 1}$ . We begin with a bound on the least singular value of an elliptic random matrix under very general assumptions. This section is entirely self contained.

Theorem 5.1 (Least singular value bound).

Let $X=(X_{ij})$ be an $n\times n$ complex-valued random matrix such that

(i)

(off-diagonal entries) $\{(X_{ij},X_{ji}):1\leq i<j\leq n\}$ is a collection of independent random tuples,
(ii)

(diagonal entries) the diagonal entries $\{X_{ii}:1\leq i\leq n\}$ are independent of the off-diagonal entries (but can be dependent on each other),

(iii)

there exists $a>0$ such that the events

\mathcal{E}_{ij}:=\{|X_{ij}|\leq a,|X_{ji}|\leq a\}

(5.1)

defined for $i\neq j$ satisfy

b:=\min_{i<j}\mathbb{P}(\mathcal{E}_{ij})>0,\quad\sigma^{2}:=\min_{i\neq j}\operatorname{Var}(X_{ij}\mid\mathcal{E}_{ij})>0,

and

\rho:=\max_{i<j}\left|{\operatorname{Corr}(X_{ij}\mid\mathcal{E}_{ij},X_{ji}\mid\mathcal{E}_{ji})}\right|<1.

Then there exists $C=C(a,b,\sigma)>0$ such that for $n\geq C$ , any $M\in\operatorname{Mat}_{n}(\mathbb{C})$ , $s\geq 1$ , $0<t\leq 1$ ,

\mathbb{P}\left(s_{n}(X+M)\leq\frac{t}{\sqrt{n}},s_{1}(X+M)\leq s\right)\leq C\left(\frac{\log(Cns)}{\sqrt{1-\rho}}\left(\sqrt{s^{5}t}+\frac{1}{\sqrt{n}}\right)\right)^{1/4}.

Remark 5.2.

The constant $C$ from Theorem 5.1 only depends on $a,b,\sigma$ and does not depend on $\rho$ . This allows one to apply Theorem 5.1 to cases where $\rho$ depends on $n$ .

5.1. Proof of Theorem 5.1

In this section we prove Theorem 5.1. Suppose $X$ and $M$ satisfy the assumptions of the theorem and denote $A:=X+M$ . We will use $A$ throughout this section and it may be worth noting it is not the $A_{n}$ of Theorems 1.5 and 1.6. Throughout the section, we allow all constants to depend on $a,b,\sigma$ without mentioning or denoting this dependence. Constants, however, will not depend on $\rho$ ; instead we will state all dependence on $\rho$ explicitly.

For the proof of Theorem 5.1, it suffices to assume that $A$ and every principle submatrix of $A$ is invertible with probability $1$ . To see this, define $X^{\prime}:=X+\frac{t}{\sqrt{n}}\xi I$ , where $I$ is the identity matrix and $\xi$ is a real-valued random variable uniformly distributed on the interval $[-1,1]$ , independent of $X$ . It follows that $X^{\prime}$ satisfies the assumptions of Theorem 5.1. However, since $\xi$ is continuously distributed, it also follows that $A^{\prime}:=X^{\prime}+M$ and every principle submatrix of $A^{\prime}$ is invertible with probability $1$ . By Weyl’s inequality for the singular values (see, for instance, [10, Problem III.6.13]), we find

\max_{1\leq k\leq n}|s_{k}(A)-s_{k}(A^{\prime})|\leq\frac{t}{\sqrt{n}}\leq s.

Hence, we conclude that

\mathbb{P}\left(s_{n}(A)\leq\frac{t}{\sqrt{n}},s_{1}(A)\leq s\right)\leq\mathbb{P}\left(s_{n}(A^{\prime})\leq\frac{2t}{\sqrt{n}},s_{1}(A^{\prime})\leq 2s\right).

In other words, it suffices to prove Theorem 5.1 under the additional assumption that $A$ and every principle submatrix of $A$ is invertible. We work under this additional assumption for the remainder of the proof.

5.2. Nets and a decomposition of the unit sphere

Consider a compact set $K\subset\mathbb{C}^{n}$ and $\varepsilon>0$ . A subset $\mathcal{N}\subset K$ is called an $\varepsilon$ -net of $K$ if for every point $v\in K$ one has $\operatorname{dist}(v,\mathcal{N})\leq\varepsilon$ .

For some real positive parameters $\delta,\tau>0$ that will be determined later, we define the set of $\delta$ -sparse vectors as

\operatorname{Sparse}(\delta):=\{x\in\mathbb{C}^{n}:|\operatorname{supp}(x)|\leq\delta n\}.

We decompose the unit sphere $\mathbb{S}^{n-1}$ into the set of compressible vectors and the complementary set of incompressible vectors by

\operatorname{Comp}(\delta,\tau):=\{x\in\mathbb{S}^{n-1}:\operatorname{dist}(x,\operatorname{Sparse}(\delta))\leq\tau\}

and

\operatorname{Incomp}(\delta,\tau):=\mathbb{S}^{n-1}\setminus\operatorname{Comp}(\delta,\tau).

We have the following result for incompressible vectors.

Lemma 5.3 (Incompressible vectors are spread; Lemma A.3 from [15]).

Let $x\in\operatorname{Incomp}(\delta,\tau)$ . There exists a subset $\pi\subset[n]$ such that $|\pi|\geq\delta n/2$ and for all $i\in\pi$ ,

\frac{\tau}{\sqrt{n}}\leq|x_{i}|\leq\sqrt{\frac{2}{\delta n}}.

5.3. Control of compressible vectors

The case of compressible vectors roughly follows the arguments from [15]. For $i,j\in[n]$ , we let $C_{j}$ denote the $j$ -th column of $A$ and $C_{j}^{(i)}$ denote the $j$ -th column of $A$ with the $i$ -th entry removed.

Lemma 5.4 (Distance of a random vector to a deterministic subspace).

There exist constants $\varepsilon,C,c,\delta_{0}>0$ such that for all $1\leq i\leq n$ and any deterministic subspace $H$ of $\mathbb{C}^{n-1}$ with $1\leq\dim(H)\leq\delta_{0}n$ , we have

\mathbb{P}\left(\operatorname{dist}(C_{i}^{(i)},H)\leq\varepsilon\sqrt{n}\right)\leq C\exp(-cn).

Proof.

The proof follows the same arguments as those given in the proof of [15, Theorem A.2]. Fix $1\leq i\leq n$ ; the arguments and bounds below are all uniform in $i$ . Recall the definitions of the events $\mathcal{E}_{ij}$ given in (5.1). By the assumptions on $\mathcal{E}_{ij}$ , the Chernoff bound gives

\mathbb{P}\left(\sum_{j\neq i}\mathbf{1}_{{\mathcal{E}_{ji}}}\leq\frac{(n-1)b}{2}\right)\leq\exp\left(-\frac{(n-1)b}{8}\right).

In other words, with high probability, at least $m:=\left\lceil\frac{(n-1)b}{2}\right\rceil$ of the events $\mathcal{E}_{ji}$ , $j\neq i$ occur. Thus, it suffices to prove the result by conditioning on the event

E_{m}:=\bigcap_{j\in[m],j\neq i}\mathcal{E}_{ji}.

(5.2)

There are two cases to consider. Either $i\in[m]$ or $i>m$ . The arguments for these two cases are almost identical except some notations must be changed slightly to remove the $i$ -th index. For the remainder of the proof, let us only consider the case when $i>m$ ; the changes required for the other case are left to the reader.

Recall that it suffices to prove the result by conditioning on the event $E_{m}$ defined in (5.2). In fact, as $i>m$ , the definition of the event $E_{m}$ given in (5.2) can be stated as

E_{m}:=\bigcap_{j\in[m]}\mathcal{E}_{ji}.

Let $\mathbb{E}_{m}[\cdot]:=\mathbb{E}[\cdot\mid E_{m},\mathcal{F}_{m}]$ denote the conditional expectation given the event $E_{m}$ and the filtration $\mathcal{F}_{m}$ generated by $X_{ji}$ , $j>m$ , $j\neq i$ . Let $W$ be the subspace spanned by $H$ and the vectors

u:=(0,\ldots,0,X_{m+1,i},\ldots,X_{i-1,i},X_{i+1,i},\ldots,X_{n,i})

and

w:=(\mathbb{E}_{m}[X_{1,i}],\ldots,\mathbb{E}_{m}[X_{m,i}],0,\ldots,0).

By construction, $\dim(W)\leq\dim(H)+2$ and $W$ is $\mathcal{F}_{m}$ measurable. In addition,

\operatorname{dist}(C_{i}^{(i)},H)\geq\operatorname{dist}(C_{i}^{(i)},W)=\operatorname{dist}(Y,W),

where

Y:=(X_{1,i}-\mathbb{E}_{m}[X_{1,i}],\ldots,X_{m,i}-\mathbb{E}_{m}[X_{m,i}],0,\ldots,0)=C_{i}^{(i)}-u-w.

By assumption, the coordinates $Y_{1},\ldots,Y_{m}$ are independent random variables which satisfy

|Y_{k}|\leq 2a,\qquad E_{m}[Y_{k}]=0,\qquad\mathbb{E}_{m}|Y_{k}|^{2}\geq\sigma^{2}

for $1\leq k\leq m$ . Thus, since the function $x\mapsto\operatorname{dist}(x,W)$ is convex and $1$ -Lipschitz, Talagrand’s concentration inequality (see for instance [50, Theorem 2.1.13]) yields

\mathbb{P}_{m}(|\operatorname{dist}(Y,W)-\mathbb{E}_{m}[\operatorname{dist}(Y,W)]|\geq t)\leq C\exp\left(-c\frac{t^{2}}{a^{2}}\right)

(5.3)

for every $t\geq 0$ , where $C,c>0$ are absolute constants. In particular, this implies that

(\mathbb{E}_{m}\operatorname{dist}(Y,W))^{2}\geq\mathbb{E}_{m}\operatorname{dist}^{2}(Y,W)-c^{\prime}a^{2}

(5.4)

for an absolute constant $c^{\prime}>0$ . Thus, if $P$ denotes the orthogonal projection onto the orthogonal complement of $W$ , we get

	$\displaystyle\mathbb{E}_{m}\operatorname{dist}^{2}(Y,W)$	$\displaystyle=\sum_{k=1}^{m}\mathbb{E}_{m}\|Y_{k}\|^{2}P_{kk}$
		$\displaystyle\geq\sigma^{2}\left(\operatorname{tr}P-\sum_{k=m+1}^{n-1}P_{kk}\right)$
		$\displaystyle\geq\sigma^{2}((n-1)-\dim(H)-2-(n-1-m))$
		$\displaystyle\geq\sigma^{2}\left(\frac{(n-1)b}{2}-\delta_{0}n-2\right).$

The last term is lower bounded by $c^{\prime\prime}\sigma^{2}n$ for all $n$ sufficiently large by taking $\delta_{0}:=b/4$ . Combining this bound with (5.3) and (5.4) completes the proof. ∎

The next bound, which follows as a corollary of Lemma 5.4, will be useful when dealing with compressible vectors.

Corollary 5.5.

There exist $\varepsilon,C,c,\delta_{0}>0$ such that for any deterministic subset $\pi\subset[n]$ with $|\pi|\leq\delta_{0}n$ and any deterministic $u\in\mathbb{C}^{n}$ , we have

\mathbb{P}\left(\min_{i\in\pi}\operatorname{dist}(C_{i},H_{i})\leq\varepsilon\sqrt{n}\right)\leq Cn\exp(-cn),

where $H_{i}:=\operatorname{Span}\left(\{C_{j}:j\in\pi,j\neq i\}\cup\{u\}\right)$ .

Proof.

We will apply Lemma 5.4 to control $\operatorname{dist}(C_{i},H_{i})$ . To this end, define $u^{(i)}$ to be the vector $u$ with the $i$ -th entry removed, and set $H_{i}^{(i)}:=\operatorname{Span}\left(\{C_{j}^{(i)}:j\in\pi,j\neq i\}\cup\{u^{(i)}\}\right)$ . Then

\operatorname{dist}(C_{i},H_{i})\geq\operatorname{dist}(C_{i}^{(i)},H_{i}^{(i)})

for all $1\leq i\leq n$ . Note that $H_{i}^{(i)}$ is independent of $C_{i}^{(i)}$ . Hence, conditioning on $H_{i}^{(i)}$ and applying Lemma 5.4, we find the existence of $\varepsilon,C,c,\delta_{0}$ such that for any $\pi\subset[n]$ with $|\pi|\leq\delta_{0}n$ and all $i\in\pi$

\displaystyle\mathbb{P}\left(\operatorname{dist}(C_{i},H_{i})\leq{\varepsilon}\sqrt{n}\right)\leq\mathbb{P}\left(\operatorname{dist}(C_{i}^{(i)},H_{i}^{(i)})\leq{\varepsilon}\sqrt{n}\right)\leq C\exp(-cn).

Therefore, by the union bound,

\mathbb{P}\left(\min_{i\in\pi}\operatorname{dist}(C_{i},H_{i})\leq{\varepsilon}\sqrt{n}\right)\leq\sum_{i\in\pi}\mathbb{P}\left(\operatorname{dist}(C_{i},H_{i})\leq{\varepsilon}\sqrt{n}\right)\leq Cn\exp(-cn),

and the proof is complete. ∎

Let $\varepsilon,\delta_{0}$ be as in Corollary 5.5. From now on we set

\tau:=\frac{1}{4}\min\left\{1,\frac{\varepsilon}{s\sqrt{\delta}}\right\}.

(5.5)

(Recall that $s\geq 1$ is the upper bound for $s_{1}(X+M)$ specified in the statement of Theorem 5.1.) In particular, this definition implies that $\tau\leq 1/4$ . The parameter $\delta$ is still to be specified. Right now we only assume that $\delta<\delta_{0}$ .

Lemma 5.6 (Control of compressible vectors).

There exist constants $C,c,\delta>0$ such that for any deterministic vector $u\in\mathbb{C}^{n}$ and any $s\geq 1$

\mathbb{P}\left(\inf_{x\in\operatorname{Comp}(\delta,\tau)}\|Ax-u\|\leq\frac{\varepsilon}{2\sqrt{\delta}},s_{1}(A)\leq s\right)\leq C\exp(-cn).

Proof.

Let $0<\delta<\delta_{0}$ be a constant to be chosen later. We decompose $\operatorname{Comp}(\delta,\tau)$ as

\operatorname{Comp}(\delta,\tau)=\bigcup_{\pi\subset[n]:|\pi|=\lfloor\delta n\rfloor}S_{\pi},

where

S_{\pi}:=\{x\in\operatorname{Comp}(\delta,\tau):\operatorname{dist}(x,\operatorname{Sparse}_{\pi}(\delta))\leq\tau\}

and

\operatorname{Sparse}_{\pi}(\delta):=\{y\in\operatorname{Sparse}(\delta):\operatorname{supp}(y)\subset\pi\}.

So by the union bound,

	$\displaystyle\mathbb{P}$	$\displaystyle\left(\inf_{x\in\operatorname{Comp}(\delta,\tau)}\\|Ax-u\\|\leq\frac{\varepsilon}{2\sqrt{\delta}},s_{1}(A)\leq s\right)$		(5.6)
		$\displaystyle\qquad\qquad\leq\sum_{\pi\in[n]:\|\pi\|=\lfloor\delta n\rfloor}\mathbb{P}\left(\inf_{x\in S_{\pi}}\\|Ax-u\\|\leq\frac{\varepsilon}{2\sqrt{\delta}},s_{1}(A)\leq s\right).$

Fix $\pi\subset[n]$ with $|\pi|=\lfloor\delta n\rfloor$ , and suppose there exists $x\in S_{\pi}$ such that $\|Ax-u\|\leq\frac{\varepsilon}{2\sqrt{\delta}}$ and $s_{1}(A)\leq s$ . Then there exists $y\in\operatorname{Sparse}_{\pi}(\delta)$ with $\|x-y\|\leq\tau$ . In particular, this implies that $\|y\|\geq 3/4$ . In addition, we have

\displaystyle\frac{\varepsilon}{2\sqrt{\delta}}\geq\|Ax-u\|\geq\|Ay-u\|-\tau\|A\|\geq\|Ay-u\|-\frac{\varepsilon}{4\sqrt{\delta}}

by the assumption that $\|A\|\leq s$ and the definition of $\tau$ (5.5). Hence, we obtain

\|Ay-u\|\leq\frac{3\varepsilon}{4\sqrt{\delta}}.

(5.7)

We now bound $\|Ay-u\|$ from below. Indeed, we have

\displaystyle\|Ay-u\|^{2}

\displaystyle=\left\|\sum_{i\in\pi}C_{i}y_{i}-u\right\|^{2}\geq\max_{i\in\pi}|y_{i}|^{2}\operatorname{dist}^{2}(C_{i},H_{i}),

(5.8)

where $H_{i}:=\operatorname{Span}\left(\{C_{j}:j\in\pi,j\neq i\}\cup\{u\}\right)$ . In addition, we bound

\displaystyle\max_{i\in\pi}|y_{i}|^{2}\operatorname{dist}^{2}(C_{i},H_{i})\geq\min_{i\in\pi}\operatorname{dist}^{2}(C_{i},H_{i})\frac{1}{|\pi|}\sum_{i\in\pi}|y_{i}|^{2}\geq\min_{i\in\pi}\operatorname{dist}^{2}(C_{i},H_{i})\left(\frac{3}{4}\right)^{2}\frac{1}{\delta n}.

Thus, combining (5.7) and (5.8) with the bound above, we find

\min_{i\in\pi}\operatorname{dist}(C_{i},H_{i})\leq\varepsilon\sqrt{n}.

To conclude, we have shown that

\mathbb{P}\left(\inf_{x\in S_{\pi}}\|Ax-u\|\leq\frac{\varepsilon}{2\sqrt{\delta}},s_{1}(A)\leq s\right)\leq\mathbb{P}\left(\min_{i\in\pi}\operatorname{dist}(C_{i},H_{i})\leq\varepsilon\sqrt{n}\right).

In view of Corollary 5.5, there exist $C,c>0$ such that for any $\pi\in[n]$ with $|\pi|=\lfloor\delta n\rfloor$ , we have

\mathbb{P}\left(\inf_{x\in S_{\pi}}\|Ax-u\|\leq\frac{\varepsilon}{2\sqrt{\delta}},s_{1}(A)\leq s\right)\leq Cn\exp(-cn).

Returning to (5.6), we conclude that

	$\displaystyle\mathbb{P}\left(\inf_{x\in\operatorname{Comp}(\delta,\tau)}\\|Ax-u\\|\leq\frac{\varepsilon}{2\sqrt{\delta}},s_{1}(A)\leq s\right)$	$\displaystyle\leq\binom{n}{\lfloor\delta n\rfloor}Cn\exp(-cn)$
		$\displaystyle\leq\left(\frac{ne}{\lfloor\delta n\rfloor}\right)^{\lfloor\delta n\rfloor}Cn\exp(-cn)$
		$\displaystyle\leq C^{\prime}\exp(-c^{\prime}n)$

for some constants $C^{\prime},c^{\prime}>0$ by taking $\delta$ sufficiently small (in terms of $c$ ). ∎

We now fix $\delta$ to be the constant from Lemma 5.6. Thus, $\delta$ and $\tau$ are now completely determined. We will also need the following corollary of Lemma 5.6.

Corollary 5.7.

There exist constants $C,c>0$ such that for any deterministic vector $u\in\mathbb{C}^{n}$ and any $s\geq 1$

\mathbb{P}\left(\inf_{x/\|x\|\in\operatorname{Comp}(\delta,\tau)}\frac{\|Ax-u\|}{\|x\|}\leq\frac{\varepsilon}{4\sqrt{\delta}},s_{1}(A)\leq s\right)\leq Cs\exp(-cn).

(5.9)

Proof.

The proof is based on the arguments given in [53]. We first note that if $u=0$ , then the claim follows immediately from Lemma 5.6. Assume $u\neq 0$ . Let $\mathcal{E}$ denote the event on the left-hand side of (5.9) whose probability we would like to bound. Suppose that $\mathcal{E}$ holds. Then there exists $x_{0}:=x/\|x\|\in\operatorname{Comp}(\delta,\tau)$ and $u_{0}:=u/\|x\|\in\operatorname{Span}(u)$ such that $\|Ax_{0}-u_{0}\|\leq\frac{\varepsilon}{4\sqrt{\delta}}$ and $s_{1}(A)\leq s$ . In particular, this implies that

\|u_{0}\|\leq\|Ax_{0}-u_{0}\|+\|Ax_{0}\|\leq\frac{\varepsilon}{4\sqrt{\delta}}+s.

Let $\mathcal{N}$ be a $\frac{\varepsilon}{4\sqrt{\delta}}$ -net of the real interval $[-\frac{\varepsilon}{4\sqrt{\delta}}-s,\frac{\varepsilon}{4\sqrt{\delta}}+s]$ . In particular, we can choose $\mathcal{N}$ so that

|\mathcal{N}|\leq C^{\prime}s

(5.10)

for some constant $C^{\prime}>0$ . Here, we have used the assumption that $s\geq 1$ . In particular, there exists $c_{0}\in\mathcal{N}$ such that

\left\|\frac{u}{\|x\|}-c_{0}\frac{u}{\|u\|}\right\|\leq\frac{\varepsilon}{4\sqrt{\delta}}.

By the triangle inequality, this implies that

\left\|Ax_{0}-c_{0}\frac{u}{\|u\|}\right\|\leq\frac{\varepsilon}{2\sqrt{\delta}}.

To conclude, we have shown that

\mathbb{P}(\mathcal{E})\leq\mathbb{P}\left(\inf_{c_{0}\in\mathcal{N}}\inf_{x_{0}\in\operatorname{Comp}(\delta,\tau)}{\left\|Ax_{0}-c_{0}\frac{u}{\|u\|}\right\|}\leq\frac{\varepsilon}{2\sqrt{\delta}},s_{1}(A)\leq s\right),

and thus, by the union bound, we have

\mathbb{P}(\mathcal{E})\leq\sum_{c_{0}\in\mathcal{N}}\mathbb{P}\left(\inf_{x_{0}\in\operatorname{Comp}(\delta,\tau)}{\left\|Ax_{0}-c_{0}\frac{u}{\|u\|}\right\|}\leq\frac{\varepsilon}{2\sqrt{\delta}},s_{1}(A)\leq s\right).

The claim now follows by the cardinality bound for $\mathcal{N}$ in (5.10) and Lemma 5.6. ∎

When dealing with incompressible vectors we will need the following corollary.

Corollary 5.8.

There exists constants $C,c>0$ , such that, for any $u\in\mathbb{C}^{n}$ with $u\neq 0$ , and any $s\geq 1$ , we have

\mathbb{P}\left(\frac{A^{-1}u}{\|A^{-1}u\|}\in\operatorname{Comp}(\delta,\tau),s_{1}(A)\leq s\right)\leq Cs\exp(-cn).

Proof.

If $x:=A^{-1}u$ , then $(Ax-u)/\|x\|=0$ . Thus, we have

	$\displaystyle\mathbb{P}$	$\displaystyle\left(\frac{A^{-1}u}{\\|A^{-1}u\\|}\in\operatorname{Comp}(\delta,\tau),s_{1}(A)\leq s\right)$
		$\displaystyle\qquad\qquad\leq\mathbb{P}\left(\inf_{x/\\|x\\|\in\operatorname{Comp}(\delta,\tau)}\frac{\\|Ax-u\\|}{\\|x\\|}=0,s_{1}(A)\leq s\right).$

The conclusion now follows from (5.9). ∎

5.4. Anti-concentration bounds

In order to handle incompressible vectors, we will need several anti-concentration bounds. The main idea is to use the rate of convergence from the Berry–Esseen Theorem to obtain the estimates. This idea appears to have originated in [35] and has been used previously in many works including [15, 35, 45].

Lemma 5.9 (Small ball probability via Berry–Esseen; Lemma A.6 from [15]).

There exists $C>0$ such that if $Z_{1},\ldots,Z_{n}$ are independent centered complex-valued random variables, then for all $t\geq 0$ ,

\sup_{z\in\mathbb{C}}\mathbb{P}\left(\left|\sum_{i=1}^{n}Z_{i}-z\right|\leq t\right)\leq C\left(\frac{t}{\sqrt{\sum_{i=1}^{n}\mathbb{E}|Z_{i}|^{2}}}+\frac{\sum_{i=1}^{n}\mathbb{E}|Z_{i}|^{3}}{\left(\sum_{i=1}^{n}\mathbb{E}|Z_{i}|^{2}\right)^{3/2}}\right).

We begin the following anti-concentration bound for sums involving dependent random variables.

Lemma 5.10.

Let $\{(\xi_{i},\psi_{i}):1\leq i\leq n\}$ be a collection of independent complex-valued random tuples, and assume there exist $a,b,\sigma>0$ such that the events

\mathcal{E}_{i}:=\{|\xi_{i}|\leq a,|\psi_{i}|\leq a\}

for $1\leq i\leq n$ satisfy

b\leq\min_{1\leq i\leq n}\mathbb{P}(\mathcal{E}_{i}),\qquad\sigma^{2}\leq\min_{1\leq i\leq n}\operatorname{Var}(\xi_{i}\mid\mathcal{E}_{i}),\qquad\sigma^{2}\leq\min_{1\leq i\leq n}\operatorname{Var}(\psi_{i}\mid\mathcal{E}_{i}).

In addition, assume there exists $\rho<1$ such that

\max_{1\leq i\leq n}|\operatorname{Corr}(\xi_{i}\mid\mathcal{E}_{i},\psi_{i}\mid\mathcal{E}_{i})|\leq\rho.

(5.11)

Then for any $\delta,\tau\in(0,1)$ , any $w=(w_{i})_{i=1}^{n}\in\operatorname{Incomp}(\delta,\tau)$ , any $w^{\prime}=(w^{\prime}_{i})_{i=1}^{n}\in\mathbb{C}^{n}$ with $\|w^{\prime}\|\leq 1$ , any $J\subset[n]$ with $|J|\geq n(1-\delta/4)$ , and any $t\geq 0$ , we have

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}$	$\displaystyle\left(\left\|\sum_{i\in J}(\xi_{i}w_{i}+\psi_{i}w_{i}^{\prime})-z\right\|\leq t\tau\right)$
		$\displaystyle\leq\frac{C}{\sigma\sqrt{\delta b(1-\rho)}}\sqrt{\left\lceil\frac{1}{2}\log_{2}\left(\frac{2}{\tau^{2}\delta}\right)\right\rceil\left\lceil\log_{2}\left(\frac{\sqrt{n}}{\tau}\right)\right\rceil}\left(t+\frac{a}{\sqrt{n}}\right)+\exp(-\delta nb/32),$

where $C>0$ is an absolute constant.

Proof.

The proof is based on the arguments from [15]. Since $w\in\operatorname{Incomp}(\delta,\tau)$ and $|J|\geq n(1-\delta/4)$ , Lemma 5.3 implies the existence of $\pi\subset J$ such that $|\pi|\geq\delta n/4$ and

\frac{\tau}{\sqrt{n}}\leq|w_{i}|\leq\sqrt{\frac{2}{\delta n}}

for all $i\in\pi$ . By conditioning on the random variables $\xi_{i},\psi_{i}$ for $i\not\in\pi$ and absorbing their contribution into the constant $z$ , it suffices to bound

\sup_{z\in\mathbb{C}}\mathbb{P}\left(\left|\sum_{i\in\pi}(\xi_{i}w_{i}+\psi_{i}w_{i}^{\prime})-z\right|\leq t\tau\right).

We now proceed to truncate the random variables $\xi_{i},\psi_{i}$ for $i\in\pi$ . Indeed, by the Chernoff bound, it follows that

\sum_{i\in\pi}\mathbf{1}_{{\mathcal{E}_{i}}}\geq\frac{|\pi|b}{2}\geq\frac{\delta bn}{8}

with probability at least $1-\exp(-\delta bn/32)$ . Therefore, taking $m:=\lceil\delta bn/8\rceil$ , it suffices to show

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}_{m}$	$\displaystyle\left(\left\|\sum_{i=1}^{m}(\xi_{i}w_{i}+\psi_{i}w_{i}^{\prime})-z\right\|\leq t\tau\right)$
		$\displaystyle\leq\frac{C}{\sigma\sqrt{\delta b(1-\rho)}}\sqrt{\left\lceil\frac{1}{2}\log_{2}\left(\frac{2}{\tau^{2}\delta}\right)\right\rceil\left\lceil\log_{2}\left(\frac{\sqrt{n}}{\tau}\right)\right\rceil}\left(t+\frac{a}{\sqrt{n}}\right),$

E_{m}:=\left\{|\xi_{i}|\leq a,|\psi_{i}|\leq a:1\leq i\leq m\right\}\bigcap\left\{\frac{\tau}{\sqrt{n}}\leq|w_{i}|\leq\sqrt{\frac{2}{\delta n}}:1\leq i\leq m\right\}.

By centering the random variables (and absorbing the expectations into the constant $z$ ), it suffices to bound

\sup_{z\in\mathbb{C}}\mathbb{P}_{m}\left(\left|\sum_{i=1}^{m}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\psi_{i}-\mathbb{E}_{m}[\psi_{i}])w^{\prime}_{i}\right]-z\right|\leq t\tau\right).

We again reduce to the case where we only need to consider a subset of the coordinates of $w$ and $w^{\prime}$ which are roughly comparable. Indeed, as the random tuples $(\xi_{1},\psi_{1}),\ldots,(\xi_{m},\psi_{m})$ are jointly independent under the probability measure $\mathbb{P}_{m}$ , we can condition on any subset of them (and again absorb their contribution into the constant $z$ ); hence, for any subset $I\subset[m]$ , we have

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}_{m}$	$\displaystyle\left(\left\|\sum_{i=1}^{m}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\psi_{i}-\mathbb{E}_{m}[\psi_{i}])w^{\prime}_{i}\right]-z\right\|\leq t\tau\right)$		(5.12)
		$\displaystyle\leq\sup_{z\in\mathbb{C}}\mathbb{P}_{m}\left(\left\|\sum_{i\in I}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\psi_{i}-\mathbb{E}_{m}[\psi_{i}])w^{\prime}_{i}\right]-z\right\|\leq t\tau\right).$

We now choose the subset $I$ in a sequence of two steps. First, define

L:=2\left\lceil\frac{1}{2}\log_{2}\left(\frac{2}{\delta\tau^{2}}\right)\right\rceil,

and for $1\leq j\leq L$ set

I_{j}:=\left\{1\leq i\leq m:\frac{2^{j-1}\tau}{\sqrt{n}}\leq|w_{i}|<\frac{2^{j}\tau}{\sqrt{n}}\right\}.

By construction, $I_{1},\ldots,I_{L}$ partition the index set $[m]$ . Hence, by the pigeonhole principle, there exists $j$ such that $|I_{j}|\geq m/L$ . Second, we partition the set $I_{j}$ as follows. Define

K:=2\left\lceil\log_{2}\left(\frac{\sqrt{n}}{\tau}\right)\right\rceil,

and for $1\leq k\leq K$ set

I_{j,k}:=\left\{i\in I_{j}:\frac{2^{k-1}\tau}{\sqrt{n}}\leq|w_{i}^{\prime}|<\frac{2^{k}\tau}{\sqrt{n}}\right\}

and define

I_{j,0}:=\left\{i\in I_{j}:|w^{\prime}_{i}|<\frac{\tau}{\sqrt{n}}\right\}.

As $\|w^{\prime}\|\leq 1$ by assumption, the sets $I_{j,0},I_{j,1},\ldots,I_{j,K}$ form a partition of $I_{j}$ . By the pigeonhole principle, there exists $k$ such that

|I_{j,k}|\geq\frac{m}{L(K+1)}\geq\frac{m}{2LK}.

(5.13)

Applying (5.12) to the set $I_{j,k}$ , it now suffices to show

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}_{m}$	$\displaystyle\left(\left\|\sum_{i\in I_{j,k}}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\psi_{i}-\mathbb{E}_{m}[\psi_{i}])w^{\prime}_{i}\right]-z\right\|\leq t\tau\right)$		(5.14)
		$\displaystyle\qquad\qquad\qquad\leq\frac{C\sqrt{LK}}{\sigma\sqrt{\delta b(1-\rho)}}\left(t+\frac{a}{\sqrt{n}}\right)$

for some absolute constant $C>0$ .

We will apply Lemma 5.9 to obtain (5.14). For $i\in I_{j,k}$ , define

Z_{i}:=(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\psi_{i}-\mathbb{E}_{m}[\psi_{i}])w^{\prime}_{i}.

Then

	$\displaystyle q^{2}$	$\displaystyle:=\sum_{i\in I_{j,k}}\mathbb{E}_{m}\|Z_{i}\|^{2}$
		$\displaystyle\geq\sum_{i\in I_{j,k}}\left[\|w_{i}\|^{2}\operatorname{Var}_{m}(\xi_{i})+\|w^{\prime}_{i}\|^{2}\operatorname{Var}_{m}(\psi_{i})-2\rho\|w_{i}\|\|w^{\prime}_{i}\|\sqrt{\operatorname{Var}_{m}(\xi_{i})\operatorname{Var}_{m}(\psi_{i})}\right]$

by assumption (5.11). Thus, we deduce that

	$\displaystyle q^{2}$	$\displaystyle\geq(1-\rho)\sum_{i\in I_{j,k}}\left[\|w_{i}\|^{2}\operatorname{Var}_{m}(\xi_{i})+\|w_{i}^{\prime}\|^{2}\operatorname{Var}_{m}(\psi_{i})\right]$
		$\displaystyle\geq(1-\rho)\sigma^{2}\sum_{i\in I_{j,k}}\left[\|w_{i}\|^{2}+\|w_{i}^{\prime}\|^{2}\right].$		(5.15)

In addition,

\sum_{i\in I_{j,k}}\mathbb{E}_{m}|Z_{i}|^{3}\leq 2a\tau\left(\frac{2^{j}+2^{k}}{\sqrt{n}}\right)q^{2}.

Hence, Lemma 5.9 implies the existence of an absolute constant $C>0$ such that

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}_{m}$	$\displaystyle\left(\left\|\sum_{i\in I_{j,k}}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\psi_{i}-\mathbb{E}_{m}[\psi_{i}])w^{\prime}_{i}\right]-z\right\|\leq t\tau\right)$
		$\displaystyle\qquad\qquad\qquad\leq\frac{C\tau}{q}\left(t+\frac{a(2^{j}+2^{k})}{\sqrt{n}}\right).$		(5.16)

We complete the proof by considering two separate cases. First, if $k=0$ , then using (5.13) and (5.15), we obtain

q^{2}\geq\sigma^{2}(1-\rho)\sum_{i\in I_{j,k}}|w_{i}|^{2}\geq\sigma^{2}(1-\rho)|I_{j,k}|\frac{2^{2j-2}\tau^{2}}{n}\geq\sigma^{2}(1-\rho)\delta b\frac{2^{2j}\tau^{2}}{64LK}.

Hence returning to (5.16), we find that

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}_{m}$	$\displaystyle\left(\left\|\sum_{i\in I_{j,k}}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\psi_{i}-\mathbb{E}_{m}[\psi_{i}])w^{\prime}_{i}\right]-z\right\|\leq t\tau\right)$
		$\displaystyle\qquad\qquad\qquad\leq\frac{C^{\prime}\sqrt{LK}}{\sigma\sqrt{\delta b(1-\rho)}}\left(t+\frac{a}{\sqrt{n}}\right),$		(5.17)

where $C^{\prime}>0$ is an absolute constant. Similarly, if $1\leq k\leq K$ , then

q^{2}\geq\sigma^{2}(1-\rho)|I_{j,k}|\frac{\tau^{2}}{n}\left(2^{2j-2}+2^{2k-2}\right)\geq\sigma^{2}(1-\rho)\delta b\tau^{2}\frac{2^{2j}+2^{2k}}{64LK}.

In this case, we again apply (5.16) to deduce the existence of an absolute constant $C^{\prime\prime}>0$ such that

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}_{m}$	$\displaystyle\left(\left\|\sum_{i\in I_{j,k}}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\psi_{i}-\mathbb{E}_{m}[\psi_{i}])w^{\prime}_{i}\right]-z\right\|\leq t\tau\right)$
		$\displaystyle\qquad\qquad\qquad\leq\frac{C^{\prime\prime}\sqrt{LK}}{\sigma\sqrt{\delta b(1-\rho)}}\left(t+\frac{a}{\sqrt{n}}\right).$		(5.18)

Combining (5.17) and (5.18), we obtain the bound (5.14) (with the absolute constant $C:=\max\{C^{\prime},C^{\prime\prime}\}$ ), and the proof of the lemma is complete. ∎

Lastly, we will need the following technical anti-concentration bound which is similar to Lemma 5.10.

Lemma 5.11.

Let $\{(\xi_{i},\psi_{i}):1\leq i\leq n\}\cup\{(\xi_{i}^{\prime},\psi_{i}^{\prime}):1\leq i\leq n\}$ be a collection of independent complex-valued random tuples with the property that $(\xi_{i},\psi_{i})$ has the same distribution as $(\xi_{i}^{\prime},\psi_{i}^{\prime})$ for $1\leq i\leq n$ , and assume there exist $a,b,\sigma>0$ such that the events

\mathcal{E}_{i}:=\{|\xi_{i}|\leq a,|\psi_{i}|\leq a\}

for $1\leq i\leq n$ satisfy

b\leq\min_{1\leq i\leq n}\mathbb{P}(\mathcal{E}_{i}),\qquad\sigma^{2}\leq\min_{1\leq i\leq n}\operatorname{Var}(\xi_{i}\mid\mathcal{E}_{i}),\qquad\sigma^{2}\leq\min_{1\leq i\leq n}\operatorname{Var}(\psi_{i}\mid\mathcal{E}_{i}).

In addition, let $\delta_{1},\ldots,\delta_{n}$ be i.i.d. $\{0,1\}$ -valued random variables with $\mathbb{E}\delta_{i}=c_{oo}\in(0,1]$ , and assume $\delta_{1},\ldots,\delta_{n}$ are independent of the random tuples $\{(\xi_{i},\psi_{i}),(\xi_{i}^{\prime},\psi_{i}^{\prime}):1\leq i\leq n\}$ . Then for any $\delta,\tau\in(0,1)$ , any $w=(w_{i})_{i=1}^{n}\in\operatorname{Incomp}(\delta,\tau)$ , any $w^{\prime}=(w^{\prime}_{i})_{i=1}^{n}\in\mathbb{C}^{n}$ with $\|w^{\prime}\|\leq 1$ , and any $t\geq 0$ , we have

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}$	$\displaystyle\left(\left\|\sum_{i=1}^{n}(\delta_{i}\xi_{i}w_{i}+\delta_{i}\xi_{i}^{\prime}w_{i}^{\prime})-z\right\|\leq t\tau\right)$
		$\displaystyle\leq\frac{C}{\sigma\sqrt{c_{oo}\delta b^{2}}}\sqrt{\left\lceil\frac{1}{2}\log_{2}\left(\frac{2}{\tau^{2}\delta}\right)\right\rceil\left\lceil\log_{2}\left(\frac{\sqrt{n}}{\tau}\right)\right\rceil}\left(t+\frac{a}{\sqrt{n}}\right)+\exp(-\delta nc_{oo}b^{2}/16),$

where $C>0$ is an absolute constant.

Lemma 5.11 is very similar to Lemma 5.10. The statement of the lemma is somewhat unusual since the hypotheses involve the variables $\xi_{i},\psi_{i},\xi_{i}^{\prime},\psi_{i}^{\prime}$ , but the conclusion only involves the random variables $\xi_{i},\xi_{i}^{\prime}$ . This is to match the assumptions of Theorem 5.1. The proof of Lemma 5.11 presented below follows the same framework as the proof of Lemma 5.10.

Proof of Lemma 5.11.

Since $w\in\operatorname{Incomp}(\delta,\tau)$ , Lemma 5.3 implies the existence of $\pi\subset[n]$ such that $|\pi|\geq\delta n/2$ and

\frac{\tau}{\sqrt{n}}\leq|w_{i}|\leq\sqrt{\frac{2}{\delta n}}

for all $i\in\pi$ . By conditioning on the random variables $\xi_{i},\psi_{i},\xi_{i}^{\prime},\psi_{i}^{\prime},\delta_{i}$ for $i\not\in\pi$ and absorbing their contribution into the constant $z$ , it suffices to bound

\sup_{z\in\mathbb{C}}\mathbb{P}\left(\left|\sum_{i\in\pi}(\delta_{i}\xi_{i}w_{i}+\delta_{i}\xi_{i}^{\prime}w_{i}^{\prime})-z\right|\leq t\tau\right).

We now proceed to truncate the random variables $\xi_{i},\psi_{i},\xi_{i}^{\prime},\psi_{i}^{\prime}$ for $i\in\pi$ . Define the events

\mathcal{E}_{i}^{\prime}:=\{|\xi_{i}^{\prime}|\leq a,|\psi_{i}^{\prime}|\leq a\},

and observe that $\mathcal{E}_{i}^{\prime}$ is independent of $\mathcal{E}_{i}$ for $1\leq i\leq n$ . By the Chernoff bound, it follows that

\sum_{i\in\pi}\mathbf{1}_{{\mathcal{E}_{i}\cap\mathcal{E}_{i}^{\prime}\cap\{\delta_{i}=1\}}}\geq\frac{c_{oo}|\pi|b^{2}}{2}\geq\frac{c_{oo}\delta b^{2}n}{4}

with probability at least $1-\exp(-c_{oo}\delta b^{2}n/16)$ . Therefore, taking $m:=\lceil c_{oo}\delta b^{2}n/4\rceil$ , it suffices to bound

\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}_{m}

\displaystyle\left(\left|\sum_{i=1}^{m}(\delta_{i}\xi_{i}w_{i}+\delta_{i}\xi_{i}^{\prime}w_{i}^{\prime})-z\right|\leq t\tau\right)=\sup_{z\in\mathbb{C}}\mathbb{P}_{m}

\displaystyle\left(\left|\sum_{i=1}^{m}(\xi_{i}w_{i}+\xi_{i}^{\prime}w_{i}^{\prime})-z\right|\leq t\tau\right)

(5.19)

where $\mathbb{P}_{m}(\cdot):=\mathbb{P}(\cdot|E_{m},\mathcal{F}_{m})$ is the conditional probability given $\mathcal{F}_{m}$ , the $\sigma$ -algebra generated by all random variables except $\xi_{1},\ldots,\xi_{m}$ , $\psi_{1},\ldots,\psi_{m}$ , $\xi_{1}^{\prime},\ldots,\xi_{m}^{\prime}$ , $\psi_{1}^{\prime},\ldots,\psi_{m}^{\prime}$ , $\delta_{1},\ldots,\delta_{m}$ , and the event

E_{m}:=\bigcap_{i=1}^{m}\left\{|\xi_{i}|\leq a,|\psi_{i}|\leq a,|\xi_{i}^{\prime}|\leq a,|\psi_{i}^{\prime}|\leq a,\delta_{i}=1\right\}\bigcap_{i=1}^{m}\left\{\frac{\tau}{\sqrt{n}}\leq|w_{i}|\leq\sqrt{\frac{2}{\delta n}}\right\}.

Here, we have exploited the fact that on the event $E_{m}$ , $\delta_{i}=1$ for $i\in[m]$ , and so all factors of $\delta_{i}$ have been replaced by $1$ on the right-hand side of (5.19). By centering the random variables (and absorbing the expectations into the constant $z$ ), it suffices to bound

\sup_{z\in\mathbb{C}}\mathbb{P}_{m}\left(\left|\sum_{i=1}^{m}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\xi_{i}^{\prime}-\mathbb{E}_{m}[\xi_{i}^{\prime}])w^{\prime}_{i}\right]-z\right|\leq t\tau\right).

We again reduce to the case where we only need to consider a subset of the coordinates of $w$ and $w^{\prime}$ which are roughly comparable. Indeed, as the random vectors $(\xi_{1},\psi_{1},\xi_{1}^{\prime},\psi_{1}^{\prime}),\ldots,(\xi_{m},\psi_{m},\xi_{m}^{\prime},\psi_{m}^{\prime})$ are jointly independent under the probability measure $\mathbb{P}_{m}$ , we can condition on any subset of them (and again absorb their contribution into the constant $z$ ); hence, for any subset $I\subset[m]$ , we have

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}_{m}$	$\displaystyle\left(\left\|\sum_{i=1}^{m}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\xi_{i}^{\prime}-\mathbb{E}_{m}[\xi_{i}^{\prime}])w^{\prime}_{i}\right]-z\right\|\leq t\tau\right)$		(5.20)
		$\displaystyle\leq\sup_{z\in\mathbb{C}}\mathbb{P}_{m}\left(\left\|\sum_{i\in I}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\xi_{i}^{\prime}-\mathbb{E}_{m}[\xi_{i}^{\prime}])w^{\prime}_{i}\right]-z\right\|\leq t\tau\right).$

We now choose the subset $I$ in a sequence of two steps as was done in the proof of Lemma 5.10. First, define

L:=2\left\lceil\frac{1}{2}\log_{2}\left(\frac{2}{\delta\tau^{2}}\right)\right\rceil,

and for $1\leq j\leq L$ set

I_{j}:=\left\{1\leq i\leq m:\frac{2^{j-1}\tau}{\sqrt{n}}\leq|w_{i}|<\frac{2^{j}\tau}{\sqrt{n}}\right\}.

K:=2\left\lceil\log_{2}\left(\frac{\sqrt{n}}{\tau}\right)\right\rceil,

and for $1\leq k\leq K$ set

I_{j,k}:=\left\{i\in I_{j}:\frac{2^{k-1}\tau}{\sqrt{n}}\leq|w_{i}^{\prime}|<\frac{2^{k}\tau}{\sqrt{n}}\right\}

and define

I_{j,0}:=\left\{i\in I_{j}:|w^{\prime}_{i}|<\frac{\tau}{\sqrt{n}}\right\}.

As $\|w^{\prime}\|\leq 1$ by assumption, the sets $I_{j,0},I_{j,1},\ldots,I_{j,K}$ form a partition of $I_{j}$ . By the pigeonhole principle, there exists $k$ such that

|I_{j,k}|\geq\frac{m}{L(K+1)}\geq\frac{m}{2LK}.

(5.21)

Applying (5.20) to the set $I_{j,k}$ , it now suffices to show

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}_{m}$	$\displaystyle\left(\left\|\sum_{i\in I_{j,k}}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\xi_{i}^{\prime}-\mathbb{E}_{m}[\xi_{i}^{\prime}])w^{\prime}_{i}\right]-z\right\|\leq t\tau\right)$		(5.22)
		$\displaystyle\qquad\qquad\qquad\leq C\frac{\sqrt{LK}}{\sigma\sqrt{c_{oo}\delta b^{2}}}\left(t+\frac{a}{\sqrt{n}}\right)$

for some absolute constant $C>0$ .

We will apply Lemma 5.9 to obtain (5.22). For $i\in I_{j,k}$ , define

Z_{i}:=(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\xi_{i}^{\prime}-\mathbb{E}_{m}[\xi_{i}^{\prime}])w^{\prime}_{i}.

Then

$\displaystyle q^{2}$	$\displaystyle:=\sum_{i\in I_{j,k}}\mathbb{E}_{m}\|Z_{i}\|^{2}$
	$\displaystyle=\sum_{i\in I_{j,k}}\left[\|w_{i}\|^{2}\operatorname{Var}_{m}(\xi_{i})+\|w^{\prime}_{i}\|^{2}\operatorname{Var}_{m}(\xi_{i}^{\prime})\right]$	(5.23)
	$\displaystyle\geq\sigma^{2}\sum_{i\in I_{j,k}}\left[\|w_{i}\|^{2}+\|w_{i}^{\prime}\|^{2}\right]$

since $\xi_{i}$ and $\xi_{i}^{\prime}$ are independent under the measure $\mathbb{P}_{m}$ for $1\leq i\leq n$ . In addition,

\sum_{i\in I_{j,k}}\mathbb{E}_{m}|Z_{i}|^{3}\leq 2a\tau\left(\frac{2^{j}+2^{k}}{\sqrt{n}}\right)q^{2}.

Hence, Lemma 5.9 implies the existence of an absolute constant $C>0$ such that

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}_{m}$	$\displaystyle\left(\left\|\sum_{i\in I_{j,k}}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\xi_{i}^{\prime}-\mathbb{E}_{m}[\xi_{i}^{\prime}])w^{\prime}_{i}\right]-z\right\|\leq t\tau\right)$
		$\displaystyle\qquad\qquad\qquad\leq\frac{C\tau}{q}\left(t+\frac{a(2^{j}+2^{k})}{\sqrt{n}}\right).$		(5.24)

We complete the proof by considering two separate cases. First, if $k=0$ , then using (5.21) and (5.23), we obtain

q^{2}\geq\sigma^{2}\sum_{i\in I_{j,k}}|w_{i}|^{2}\geq\sigma^{2}|I_{j,k}|\frac{2^{2j-2}\tau^{2}}{n}\geq\sigma^{2}c_{oo}\delta b^{2}\frac{2^{2j}\tau^{2}}{32LK}.

Hence returning to (5.24), we find that

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}_{m}$	$\displaystyle\left(\left\|\sum_{i\in I_{j,k}}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\xi_{i}^{\prime}-\mathbb{E}_{m}[\xi_{i}^{\prime}])w^{\prime}_{i}\right]-z\right\|\leq t\tau\right)$
		$\displaystyle\qquad\qquad\qquad\leq\frac{C^{\prime}\sqrt{LK}}{\sigma\sqrt{c_{oo}\delta b^{2}}}\left(t+\frac{a}{\sqrt{n}}\right),$		(5.25)

where $C^{\prime}>0$ is an absolute constant. Similarly, if $1\leq k\leq K$ , then

q^{2}\geq\sigma^{2}|I_{j,k}|\frac{\tau^{2}}{n}\left(2^{2j-2}+2^{2k-2}\right)\geq\sigma^{2}c_{oo}\delta b^{2}\tau^{2}\frac{2^{2j}+2^{2k}}{32LK}.

In this case, we again apply (5.24) to deduce the existence of an absolute constant $C^{\prime\prime}>0$ such that

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}_{m}$	$\displaystyle\left(\left\|\sum_{i\in I_{j,k}}\left[(\xi_{i}-\mathbb{E}_{m}[\xi_{i}])w_{i}+(\xi_{i}^{\prime}-\mathbb{E}_{m}[\xi_{i}]^{\prime})w^{\prime}_{i}\right]-z\right\|\leq t\tau\right)$
		$\displaystyle\qquad\qquad\qquad\leq\frac{C^{\prime\prime}\sqrt{LK}}{\sigma\sqrt{c_{oo}\delta b^{2}}}\left(t+\frac{a}{\sqrt{n}}\right).$		(5.26)

Combining (5.25) and (5.26), we obtain the bound (5.22) (with the absolute constant $C:=\max\{C^{\prime},C^{\prime\prime}\}$ ), and the proof of the lemma is complete. ∎

5.5. Incompressible vectors

In order to control the set of incompressible vectors, we will require the following averaging estimate.

Lemma 5.12 (Invertibility via average distance; Lemma A.4 from [15]).

Let $A$ be a random matrix taking values in $\operatorname{Mat}_{n}(\mathbb{C})$ with columns $C_{1},\ldots,C_{n}$ . For any $1\leq k\leq n$ , let $H_{k}:=\operatorname{Span}\{C_{i}:i\neq k\}$ . Then, for any $t\geq 0$ ,

\mathbb{P}\left(\min_{x\in\operatorname{Incomp}(\delta,\tau)}\|Ax\|\leq\frac{t\tau}{\sqrt{n}}\right)\leq\frac{2}{\delta n}\sum_{k=1}^{n}\mathbb{P}(\operatorname{dist}(C_{k},H_{k})\leq t).

Let $A=X+M$ be the matrix from Theorem 5.1. Let $C_{1},\ldots,C_{n}$ be the columns of $A$ and $H_{k}:=\operatorname{Span}\{C_{i}:i\neq k\}$ be as in Lemma 5.12. Our main result for controlling the set of incompressible vectors is the following.

Lemma 5.13.

There exists $C,c>0$ such that for every $1\leq k\leq n$ , any $t>0$ and any $s\geq 1$ ,

\mathbb{P}(\operatorname{dist}(C_{k},H_{k})\leq t,s_{1}(A)\leq s)\leq C\left(\frac{\log(Csn)}{\sqrt{1-\rho}}\left(s^{2}\sqrt{t}+\frac{1}{\sqrt{n}}\right)\right)^{1/4}.

The rest of the subsection is devoted to the proof of Lemma 5.13. We complete the proof of Theorem 5.1 in Subsection 5.6. We will also need the following result based on [53, Proposition 5.1] and [29, Statement 2.8].

Lemma 5.14 (Distance problem via bilinear forms).

Let $A=(A_{ij})\in\operatorname{Mat}_{n}(\mathbb{C})$ , let $C_{1},\ldots,C_{n}$ denote the columns of $A$ , and fix $1\leq k\leq n$ . Let $H_{k}:=\operatorname{Span}\{C_{i}:i\neq k\}$ , $u$ be the $k$ -th row of $A$ with the $k$ -th entry removed, $v$ be $C_{k}$ with the $k$ -th entry removed, and let $B$ be the $(n-1)\times(n-1)$ submatrix of $A$ formed from removing the $k$ -th row and $k$ -th column. If $B$ is invertible, then

\operatorname{dist}(C_{k},H_{k})\geq\frac{|A_{kk}-uB^{-1}v|}{\sqrt{1+\|uB^{-1}\|^{2}}}.

(5.27)

Proof.

The proof presented below is based on the arguments given in [29, 53]. By permuting the rows and columns, it suffices to assume that $k=1$ . Let $h\in\mathbb{S}^{n-1}$ denote any normal to the hyperplane $H_{1}$ . Then

\operatorname{dist}(C_{1},H_{1})\geq|h^{\ast}C_{1}|.

We decompose

C_{1}=\begin{pmatrix}A_{11}\\ v\end{pmatrix},\quad h=\begin{pmatrix}h_{1}\\ g\end{pmatrix},

where $h_{1}\in\mathbb{C}$ and $g\in\mathbb{C}^{n-1}$ . Then

\operatorname{dist}(C_{1},H_{1})\geq|h^{\ast}C_{1}|=|\bar{h}_{1}A_{11}+g^{\ast}v|.

(5.28)

Since $h$ is orthogonal to the columns of the matrix $\begin{pmatrix}u\\ B\end{pmatrix}$ , we find

0=h^{\ast}\begin{pmatrix}u\\ B\end{pmatrix}=\bar{h}_{1}u+g^{\ast}B,

and hence

g^{\ast}=-\bar{h}_{1}uB^{-1}.

Returning to (5.28), we have

\operatorname{dist}(C_{1},H_{1})\geq|h_{1}||A_{11}-uB^{-1}v|.

(5.29)

In addition,

1=\|h\|^{2}=|h_{1}|^{2}+\|g\|^{2}=|h_{1}|^{2}(1+\|uB^{-1}\|^{2}),

and so

|h_{1}|^{2}=\frac{1}{1+\|uB^{-1}\|^{2}}.

(5.30)

The conclusion now follows from (5.29) and (5.30). ∎

Our study of the bilinear form $uB^{-1}v$ is based on the following general result, which will allow us to introduce some additional independence into the problem to deal with the fact that $u$ and $v$ are dependent. Similar decoupling techniques have also appeared in [19, 20, 27, 29, 53]. The lemma below is based on [53, Lemma 8.4] for quadratic forms.

Lemma 5.15 (Decoupling lemma).

Let $M\in\operatorname{Mat}_{n}(\mathbb{C})$ , and let $x=(x_{i})_{i=1}^{n},y=(y_{i})_{i=1}^{n}$ be random vectors in $\mathbb{C}^{n}$ such that $\{(x_{i},y_{i}):1\leq i\leq n\}$ is a collection of independent random tuples. Let $(x^{\prime},y^{\prime})$ denote an independent copy of $(x,y)$ . Then for every subset $\pi\subset[n]$ and $t\geq 0$ , we have

	$\displaystyle\sup_{z\in\mathbb{C}}\mathbb{P}$	$\displaystyle(\|x^{\mathrm{T}}My-z\|\leq t)^{2}$
		$\displaystyle\leq\mathbb{P}_{x,y,x^{\prime},y^{\prime}}\left(\|x_{\pi}^{\mathrm{T}}M_{\pi\times\pi^{c}}(y_{\pi^{c}}-y^{\prime}_{\pi^{c}})+(x_{\pi^{c}}-x^{\prime}_{\pi^{c}})^{\mathrm{T}}M_{\pi^{c}\times\pi}y_{\pi}+z_{0}\|\leq 2t\right),$

where $z_{0}$ is a random variable whose value is determined by $M_{\pi^{c}\times\pi^{c}},x_{\pi^{c}},y_{\pi^{c}},x^{\prime}_{\pi^{c}},y^{\prime}_{\pi^{c}}$ .

The proof of Lemma 5.15 is based on the following decoupling bound from [48, 53].

Lemma 5.16 (Lemma 8.5 from [53]).

Let $\xi$ and $\psi$ be independent random vectors, and let $\psi^{\prime}$ be an independent copy of $\psi$ . Let $\mathcal{E}(\xi,\psi)$ be an event which is determined by the values of $\xi$ and $\psi$ . Then

\mathbb{P}(\mathcal{E}(\xi,\psi))^{2}\leq\mathbb{P}(\mathcal{E}(\xi,\psi)\cap\mathcal{E}(\xi,\psi^{\prime})).

Proof of Lemma 5.15.

Let $\xi$ be the random vector formed by the tuples $\{(x_{i},y_{i}):i\in\pi\}$ , and let $\psi$ be the random vector formed from the tuples $\{(x_{i},y_{i}):i\not\in\pi\}$ . Then $\xi$ and $\psi$ are independent by supposition, and we can apply Lemma 5.16. To this end, let $\tilde{x},\tilde{y}$ be random vectors in $\mathbb{C}^{n}$ defined by

\tilde{x}_{\pi}:=x_{\pi},\quad\tilde{x}_{\pi^{c}}:=x^{\prime}_{\pi^{c}},\quad\tilde{y}_{\pi}:=y_{\pi},\quad\tilde{y}_{\pi^{c}}:=y^{\prime}_{\pi^{c}}.

An application of Lemma 5.16 yields

	$\displaystyle\mathbb{P}(\|x^{\mathrm{T}}My-z\|\leq t)^{2}$	$\displaystyle\leq\mathbb{P}_{x,y,\tilde{x},\tilde{y}}(\|{x}^{\mathrm{T}}My-z\|\leq t,\|\tilde{x}^{\mathrm{T}}M\tilde{y}-z\|\leq t)$
		$\displaystyle\leq\mathbb{P}_{x,y,\tilde{x},\tilde{y}}(\|x^{\mathrm{T}}My-\tilde{x}^{\mathrm{T}}M\tilde{y}\|\leq 2t),$

where the last inequality follows from the triangle inequality. We now note that

\displaystyle x^{\mathrm{T}}My-\tilde{x}^{\mathrm{T}}M\tilde{y}=x_{\pi}^{\mathrm{T}}M_{\pi\times\pi^{c}}(y_{\pi^{c}}-\tilde{y}_{\pi^{c}})+(x_{\pi^{c}}-\tilde{x}_{\pi^{c}})^{\mathrm{T}}M_{\pi^{c}\times\pi}y_{\pi}+z_{0},

where $z_{0}$ depends only on $M_{\pi^{c}\times\pi^{c}},x_{\pi^{c}},y_{\pi^{c}},\tilde{x}_{\pi^{c}},\tilde{y}_{\pi^{c}}$ . Since $\tilde{x}_{\pi^{c}}=x^{\prime}_{\pi^{c}}$ and $\tilde{y}_{\pi^{c}}=y^{\prime}_{\pi^{c}}$ , the claim follows. ∎

We now turn to the proof of Lemma 5.13. The arguments presented here follow the general framework of [53, Section 8.3]. Fix $1\leq k\leq n$ ; the arguments and bounds below will all be uniform in $k$ . Let $u$ be the $k$ -th row of $A$ with the $k$ -th entry removed. Let $v$ be the $k$ -th column of $A$ with the $k$ -th entry removed, and let $B$ be the $(n-1)\times(n-1)$ matrix formed by removing the $k$ -th row and $k$ -th column from $A$ . In view of Lemma 5.14, it suffices to prove that

\mathbb{P}\left(\frac{|A_{kk}-uB^{-1}v|}{\sqrt{1+\|uB^{-1}\|^{2}}}\leq t,s_{1}(A)\leq s\right)\leq C\left(\frac{\log(Csn)}{\sqrt{1-\rho}}\left(s^{2}\sqrt{t}+\frac{1}{\sqrt{n}}\right)\right)^{1/4}

(5.31)

for some constants $C,c>0$ . Our argument is based on applying Lemma 5.15 to decouple the bilinear form $uB^{-1}v$ and then applying our anti-concentration bounds from Subsection 5.4 to bound the resulting expressions. We divide the proof of (5.31) into a number of sub-steps.

5.5.1. Step 1: Constructing a random subset $\pi$

Following [53], we decompose $[n-1]$ into two random subsets $\pi$ and $\pi^{c}$ . Let $\delta_{1},\ldots,\delta_{n-1}$ be i.i.d. $\{0,1\}$ -valued random variables, independent of $X$ , with $\mathbb{E}\delta_{i}=c_{oo}/2$ , where $c_{oo}$ is a constant defined by

c_{oo}:=\delta/8

and $\delta\in(0,1)$ was previously fixed. We then define $\pi:=\{i\in[n-1]:\delta_{i}=0\}$ . By the Chernoff bound, it follows that

|\pi^{c}|\leq c_{oo}n

(5.32)

with probability at least $1-C_{oo}^{\prime}\exp(-c_{oo}^{\prime}n)$ for some constants $C_{oo}^{\prime},c_{oo}^{\prime}>0$ .

5.5.2. Step 2: Estimating $\|B^{-1}\|_{2}$

Lemma 5.17 below will allow us to estimate the denominator appearing on the right-hand side of (5.27). To this end, let $(u^{\prime},v^{\prime})$ be an independent copy of $(u,v)$ , also independent of $X$ .

Lemma 5.17.

There exist constants $C,c>0$ such that, for any $s\geq 1$ , the random matrix $B$ has the following properties with probability at least $1-Cs\exp(-cn)$ . If $s_{1}(B)\leq s$ , one has:

(i)

for any $t_{0}\geq 0$ , with probability at least $1-C{\log(Cns)}\left(st_{0}+n^{-1/2}\right)$ in $u,u^{\prime},\pi$ ,

$\|(u-u^{\prime})_{\pi^{c}}B^{-1}_{\pi^{c}\times[n-1]}\|\geq t_{0}\|B^{-1}\|_{2}.$
(ii)

for any $t_{0}\geq 0$ , with probability at least $1-C{\log(Cns)}\left(st_{0}+n^{-1/2}\right)$ in $v,v^{\prime},\pi$ ,

$\|B^{-1}_{[n-1]\times\pi^{c}}(v-v^{\prime})_{\pi^{c}}\|\geq t_{0}\|B^{-1}\|_{2}.$

In order to prove the lemma, we will need the following elementary result.

Lemma 5.18 (Sums of dependent random variables; Lemma 8.3 from [53]).

Let $Z_{1},\ldots,Z_{n}$ be arbitrary non-negative random variables (not necessarily independent), and $p_{1},\ldots,p_{n}$ be non-negative numbers such that

\sum_{j=1}^{n}p_{j}=1.

Then, for every $t\geq 0$ , we have

\mathbb{P}\left(\sum_{j=1}^{n}p_{j}Z_{j}\leq t\right)\leq 2\sum_{j=1}^{n}p_{j}\mathbb{P}(Z_{j}\leq 2t).

Proof of Lemma 5.17.

By Corollary 5.8 and the union bound, under the assumption $s_{1}(B)\leq s$ , we have

x_{j}:=\frac{B^{-1}e_{j}}{\|B^{-1}e_{j}\|}\in\operatorname{Incomp}(\delta,\tau),\qquad y_{j}:=\frac{e_{j}^{\ast}B^{-1}}{\|e_{j}^{\ast}B^{-1}\|}\in\operatorname{Incomp}(\delta,\tau)

for $1\leq j\leq n-1$ with probability at least $1-Cs\exp(-cn)$ . Here, $e_{1},\ldots,e_{n-1}$ are the standard basis elements of $\mathbb{C}^{n-1}$ . Fix a realization of $B$ for which this property holds. We will prove that both properties hold with the desired probability for this fixed realization of $B$ .

For (i), we note that

	$\displaystyle\\|(u-u^{\prime})_{\pi^{c}}B^{-1}_{\pi^{c}\times[n-1]}\\|^{2}$	$\displaystyle=\sum_{j=1}^{n-1}\|(u-u^{\prime})_{\pi^{c}}B^{-1}_{\pi^{c}\times[n-1]}e_{j}\|^{2}$
		$\displaystyle=\sum_{j=1}^{n-1}\|(u-u^{\prime})_{\pi^{c}}(x_{j})_{\pi^{c}}\|^{2}\\|B^{-1}e_{j}\\|^{2}.$

Taking $p_{j}:=\|B^{-1}e_{j}\|^{2}/\|B^{-1}\|_{2}^{2}$ , we see that $\sum_{j=1}^{n-1}p_{j}=1$ , and hence

	$\displaystyle\mathbb{P}_{u,u^{\prime},\pi}$	$\displaystyle\left(\\|(u-u^{\prime})_{\pi^{c}}B^{-1}_{\pi^{c}\times[n-1]}\\|\leq t_{0}\\|B^{-1}\\|_{2}\right)$
		$\displaystyle\qquad\qquad\leq\mathbb{P}_{u,u^{\prime},\pi}\left(\sum_{j=1}^{n-1}\|(u-u^{\prime})_{\pi^{c}}(x_{j})_{\pi^{c}}\|^{2}p_{j}\leq t_{0}^{2}\right)$
		$\displaystyle\qquad\qquad\leq 2\sum_{j=1}^{n-1}p_{j}\mathbb{P}_{u,u^{\prime},\pi}(\|(u-u^{\prime})_{\pi^{c}}(x_{j})_{\pi^{c}}\|^{2}\leq 2t_{0}^{2})$
		$\displaystyle\qquad\qquad\leq 2\sup_{w\in\operatorname{Incomp}(\delta,\tau)}\mathbb{P}_{u,u^{\prime},\pi}(\|(u-u^{\prime})_{\pi^{c}}w_{\pi^{c}}\|\leq\sqrt{2}t_{0})$

by Lemma 5.18. Recalling our choice of $\delta$ , $\tau$ (5.5), and $c_{oo}$ , the claim now follows from the anti-concentration bound given in Lemma 5.11.

The proof of (ii) is similar. Indeed, we have

\|B^{-1}_{[n-1]\times\pi^{c}}(v-v^{\prime})_{\pi^{c}}\|^{2}=\sum_{j=1}^{n-1}|(y_{j})_{\pi^{c}}(v-v^{\prime})_{\pi^{c}}|^{2}\|e_{j}^{\ast}B^{-1}\|^{2}.

Applying Lemma 5.18 with $p_{j}:=\|e_{j}^{\ast}B^{-1}\|^{2}/\|B^{-1}\|_{2}^{2}$ , we conclude that

	$\displaystyle\mathbb{P}_{v,v^{\prime},\pi}$	$\displaystyle\left(\\|B^{-1}_{[n-1]\times\pi^{c}}(v-v^{\prime})_{\pi^{c}}\\|\leq t_{0}\\|B^{-1}\\|_{2}\right)$
		$\displaystyle\qquad\qquad\leq 2\sum_{j=1}^{n-1}p_{j}\mathbb{P}_{v,v^{\prime},\pi}\left(\|(y_{j})_{\pi^{c}}(v-v^{\prime})_{\pi^{c}}\|\leq\sqrt{2}t_{0}\right)$
		$\displaystyle\qquad\qquad\leq 2\sup_{w\in\operatorname{Incomp}(\delta,\tau)}\mathbb{P}_{v,v^{\prime},\pi}\left(\|w_{\pi^{c}}^{\mathrm{T}}(v-v^{\prime})_{\pi^{c}}\|\leq\sqrt{2}t_{0}\right).$

As before, the conclusion now follows from the anti-concentration bound given in Lemma 5.11. ∎

5.5.3. Step 3: Working on the appropriate events

We have one last preparatory step before we can apply the decoupling lemma, Lemma 5.15. In this step, we define the events we will need to work on for the remainder of the proof. To this end, define the events

\mathcal{B}_{A}:=\{s_{1}(A)\leq s\},\qquad\mathcal{B}_{B}:=\{s_{1}(B)\leq s\},\qquad\mathcal{B}_{u}:=\{\|u\|\leq s\}.

We note that $\mathcal{B}_{A}\subset\mathcal{B}_{B}$ and $\mathcal{B}_{A}\subset\mathcal{B}_{u}$ since $u$ and $B$ are sub-matrices of $A$ . Consider the random vectors

w:=(u-u^{\prime})_{\pi^{c}}B^{-1}_{\pi^{c}\times[n-1]},\qquad w^{\prime}:=B^{-1}_{[n-1]\times\pi^{c}}(v-v^{\prime})_{\pi^{c}}.

(5.33)

It is possible that $w=0$ or $w^{\prime}=0$ , although we will show that these events happen with small probability momentarily.

Let $t_{0}>0$ . Consider the event

\|B^{-1}\|_{2}\leq\frac{1}{t_{0}}\min\{\|w\|,\|w^{\prime}\|\}.

(5.34)

By Lemma 5.17, we find

\mathbb{P}_{B,u,u^{\prime},v,v^{\prime},\pi}(\eqref{eq:condB2}\text{ holds }\lor\mathcal{B}_{B}^{c})\geq 1-C\log(csn)(st_{0}+n^{-1/2})-Cs\exp(-cn)

for some constants $C,c>0$ . In particular, since $\|B^{-1}\|_{2}>0$ , it follows that when the event in (5.34) occurs, it must be the case that $w$ and $w^{\prime}$ are both nonzero. In order to avoid several different cases later in the proof, let us define $\omega$ and $\omega^{\prime}$ as follows. If $w$ is nonzero, we take $\omega:=w$ , and if $w$ is zero, we define $\omega$ to be a fixed vector in $\operatorname{Incomp}(\delta,\tau)$ . We define $\omega^{\prime}$ analogously in terms of $w^{\prime}$ . It follows that on the event (5.34), we have

\omega=w,\qquad\omega^{\prime}=w^{\prime}.

(5.35)

Next, consider the event

\displaystyle\frac{\omega}{\|\omega\|}\in\operatorname{Incomp}(\delta,\tau),\qquad\frac{\omega^{\prime}}{\|\omega^{\prime}\|}\in\operatorname{Incomp}(\delta,\tau).

(5.36)

Let us fix an arbitrary realization of $u,v,u^{\prime},v^{\prime}$ and a realization of $\pi$ which satisfies (5.32). We will apply Corollary 5.8 to control the event in (5.36). Indeed, we only need to consider the cases when $w\neq 0$ or $w^{\prime}\neq 0$ . In these cases, it follows that $\omega=w$ or $\omega^{\prime}=w^{\prime}$ . Let us suppose this is the case. Then $\omega=(u-u^{\prime})P_{\pi^{c}}B^{-1}$ or $\omega^{\prime}=B^{-1}P_{\pi^{c}}(v-v^{\prime})$ , where $P_{\pi^{c}}$ is an orthogonal projection onto those coordinates specified by $\pi^{c}$ . Thus, from Corollary 5.8, we deduce that

\mathbb{P}_{B}(\eqref{eq:condIncomp}\text{ holds }\lor\mathcal{B}_{B}^{c}\mid u,v,u^{\prime},v^{\prime},\pi\text{ satisfies }\eqref{eq:condpic})\geq 1-C^{\prime}s\exp(-c^{\prime}n)

for some constants $C^{\prime},c^{\prime}>0$ . Combining the probabilities above, we conclude that

	$\displaystyle\mathbb{P}_{B,u,v,u^{\prime},v^{\prime},\pi}$	$\displaystyle\left((\eqref{eq:condpic},\eqref{eq:condB2},\eqref{eq:condIncomp}\text{ hold})\lor\mathcal{B}_{B}^{c}\right)$
		$\displaystyle\qquad\qquad\geq 1-C^{\prime\prime}\log(C^{\prime\prime}sn)(st_{0}+n^{-1/2})-C^{\prime\prime}s\exp(-c^{\prime\prime}n)$
		$\displaystyle\qquad\qquad=:1-p_{0}$

for some constants $C^{\prime\prime},c^{\prime\prime}>0$ .

It follows that there exists a realization of $\pi$ that satisfies (5.32) and such that

\mathbb{P}_{B,u,v,u^{\prime},v^{\prime}}\left((\eqref{eq:condB2},\eqref{eq:condIncomp}\text{ hold})\lor\mathcal{B}_{B}^{c}\right)\geq 1-p_{0}.

We fix such a realization of $\pi$ for the remainder of the proof. Using Fubini’s theorem, we deduce that the random matrix $B$ has the following property with probability at least $1-\sqrt{p_{0}}$ :

\mathbb{P}_{u,v,u^{\prime},v^{\prime}}\left((\eqref{eq:condB2},\eqref{eq:condIncomp}\text{ hold})\lor\mathcal{B}_{B}^{c}\mid B\right)\geq 1-\sqrt{p_{0}}.

Since the event $\mathcal{B}_{B}$ depends only on $B$ and not on $u,v,u^{\prime},v^{\prime}$ , it follows that the random matrix $B$ has the following property with probability at least $1-\sqrt{p_{0}}$ : either $\mathcal{B}_{B}^{c}$ holds, or

\mathcal{B}_{B}\text{ holds and }\mathbb{P}_{u,v,u^{\prime},v^{\prime}}\left(\eqref{eq:condB2},\eqref{eq:condIncomp}\text{ hold}\mid B\right)\geq 1-\sqrt{p_{0}}.

(5.37)

5.5.4. Step 4: Decoupling

Recall that we are interested in bounding $\mathbb{P}_{B,u,v,A_{kk}}(\mathcal{E}\land\mathcal{B}_{A})$ , where

\mathcal{E}:=\left\{\frac{|A_{kk}-uB^{-1}v|}{\sqrt{1+\|uB^{-1}\|^{2}}}\leq t\right\}.

We first observe that

\mathbb{P}_{B,u,v,A_{kk}}(\mathcal{E}\land\mathcal{B}_{A})\leq\mathbb{P}_{B,u,v,A_{kk}}(\mathcal{E}\land\mathcal{B}_{B}\land\mathcal{B}_{u}).

On the event $\mathcal{B}_{u}$ , we have

\|uB^{-1}\|\leq\|u\|\|B^{-1}\|\leq s\|B^{-1}\|_{2}.

In addition, if $s_{1}(B)\leq s$ , then $\|B^{-1}\|_{2}\geq 1/s$ . Hence, on the event $\mathcal{B}_{B}\land\mathcal{B}_{u}$ ,

1+\|uB^{-1}\|^{2}\leq 1+s^{2}\|B^{-1}\|_{2}^{2}\leq 2s^{2}\|B^{-1}\|_{2}^{2}.

Thus, we obtain

\mathbb{P}_{B,u,v,A_{kk}}(\mathcal{E}\land\mathcal{B}_{A})\leq\mathbb{P}_{B,u,v,A_{kk}}(\mathcal{E}^{\prime}\land\mathcal{B}_{B}),

where

\mathcal{E}^{\prime}:=\left\{|A_{kk}-uB^{-1}v|\leq\sqrt{2}ts\|B^{-1}\|_{2}\right\}.

Thus, we find

\displaystyle\mathbb{P}_{B,u,v,A_{kk}}(\mathcal{E}\land\mathcal{B}_{A})\leq\mathbb{P}_{B,u,v,A_{kk}}(\mathcal{E}^{\prime}\land\eqref{eq:conddagger}\text{ holds})+\mathbb{P}_{B,u,v,A_{kk}}(\mathcal{B}_{B}\land\eqref{eq:conddagger}\text{ fails}).

The last probability is bounded above by $\sqrt{p_{0}}$ by the previous step. We conclude that

\mathbb{P}_{B,u,v,A_{kk}}(\mathcal{E}\land\mathcal{B}_{A})\leq\sup_{\begin{subarray}{c}B\text{ satisfies }\eqref{eq:conddagger}\\ A_{kk}\in\mathbb{C}\end{subarray}}\mathbb{P}_{u,v}(\mathcal{E}^{\prime}\mid B,A_{kk})+\sqrt{p_{0}}.

We now begin to work with the random vectors $u^{\prime},v^{\prime}$ (recall that $(u^{\prime},v^{\prime})$ are independent of $X$ ). To do so, we will work on a larger probability space which also includes the random vectors $u^{\prime},v^{\prime}$ . Indeed, computing the probability above on the larger space which includes $u^{\prime},v^{\prime}$ , we conclude that

\mathbb{P}_{B,u,v,A_{kk}}(\mathcal{E}\land\mathcal{B}_{A})\leq\sup_{\begin{subarray}{c}B\text{ satisfies }\eqref{eq:conddagger}\\ A_{kk}\in\mathbb{C}\end{subarray}}\mathbb{P}_{u,v,u^{\prime},v^{\prime}}(\mathcal{E}^{\prime}\mid B,A_{kk})+\sqrt{p_{0}}.

For the remainder of the proof, we fix a realization of $B$ which satisfies (5.37) and fix an arbitrary realization of $A_{kk}$ . By supposition, both $B$ and $A_{kk}$ are independent of $u,v,u^{\prime},v^{\prime}$ . It remains to bound the probability

p_{1}:=\sup_{z\in\mathbb{C}}\mathbb{P}_{u,v,u^{\prime},v^{\prime}}(\mathcal{E}_{z}^{\prime}),

where

\mathcal{E}_{z}^{\prime}:=\left\{|z-uB^{-1}v|\leq\sqrt{2}ts\|B^{-1}\|_{2}\right\}.

To bound $p_{1}$ , we apply the decoupling lemma, Lemma 5.15. Indeed, by Lemma 5.15,

p_{1}^{2}\leq\mathbb{P}_{u,v,u^{\prime},v^{\prime}}(\mathcal{E}^{\prime\prime}),

where

\mathcal{E}^{\prime\prime}:=\left\{|u_{\pi}B^{-1}_{\pi\times\pi^{c}}(v-v^{\prime})_{\pi^{c}}+(u-u^{\prime})_{\pi^{c}}B^{-1}_{\pi^{c}\times\pi}v_{\pi}+z_{0}|\leq 2\sqrt{2}st\|B^{-1}\|_{2}\right\}

and $z_{0}$ is a complex number depending only on $B_{\{}\pi^{c}\times\pi^{c}\}$ , $u_{\pi^{c}},v_{\pi^{c}},u_{\pi^{c}}^{\prime},v_{\pi^{c}}^{\prime}$ . Using (5.37) (where the conditioning on $B$ is no longer required since $B$ is now fixed), we find

p_{1}^{2}\leq\mathbb{P}_{u,v,u^{\prime},v^{\prime}}(\mathcal{E}^{\prime\prime}\land\eqref{eq:condB2},\eqref{eq:condIncomp}\text{ hold})+\sqrt{p_{0}},

and hence

p_{1}^{2}\leq\mathbb{P}_{u,v,u^{\prime},v^{\prime}}(\mathcal{E}^{\prime\prime\prime}\land\eqref{eq:condomega},\eqref{eq:condIncomp}\text{ hold})+\sqrt{p_{0}},

where

\displaystyle\mathcal{E}^{\prime\prime\prime}

\displaystyle:=\left\{\left|u_{\pi}w_{\pi}^{\prime}+w_{\pi}v_{\pi}+z_{0}\right|\leq 2\sqrt{2}\frac{st}{t_{0}}\max\{\|w\|,\|w^{\prime}\|\}\right\};

here, we used the fact that on the event (5.34), the event (5.35) holds.

5.5.5. Step 5: Applying the anti-concentration bounds

Recall that $w,w^{\prime}$ depend only on $u_{\pi^{c}},v_{\pi^{c}},u_{\pi^{c}}^{\prime},v_{\pi^{c}}^{\prime}$ . In addition, $u_{\pi}$ and $v_{\pi}$ are independent of these random vectors. Let us fix a realization of the random vectors $u_{\pi^{c}},v_{\pi^{c}},u_{\pi^{c}}^{\prime},v_{\pi^{c}}^{\prime}$ which satisfy (5.35) and (5.36). This completely determines $w$ and $w^{\prime}$ ; moreover, $z_{0}$ is also completely determined. Therefore, we conclude that

p_{1}^{2}\leq\sup_{\begin{subarray}{c}w,w^{\prime}\text{ satisfy }\eqref{eq:condomega},\eqref{eq:condIncomp}\\ z_{0}\in\mathbb{C}\end{subarray}}\mathbb{P}_{u_{\pi},v_{\pi}}\left(\left|u_{\pi}w_{\pi}^{\prime}+w_{\pi}v_{\pi}+z_{0}\right|\leq 2\sqrt{2}\frac{st}{t_{0}}\max\{\|w\|,\|w^{\prime}\|\}\right)+\sqrt{p_{0}}.

In order to bound this first term on the right-hand side, we will apply the anti-concentration bound given in Lemma 5.10. Without loss of generality, let us assume that $\max\{\|w\|,\|w^{\prime}\|\}=\|w\|$ . Then dividing through by $\|w\|$ , we find that

p_{1}^{2}\leq\sup_{\begin{subarray}{c}w,w^{\prime}\text{ satisfy }\eqref{eq:condomega},\eqref{eq:condIncomp}\\ z_{0}\in\mathbb{C}\end{subarray}}\mathbb{P}_{u_{\pi},v_{\pi}}\left(\left|u_{\pi}\frac{w_{\pi}^{\prime}}{\|w\|}+\frac{w_{\pi}}{\|w\|}v_{\pi}+z_{0}\right|\leq 2\sqrt{2}\frac{st}{t_{0}}\right)+\sqrt{p_{0}},

and

\frac{\left\|{w^{\prime}}\right\|}{\|w\|}\leq 1.

In view of Lemma 5.10 (where we recall that $|\pi|\geq n(1-\delta/8)$ due to (5.32)), we conclude that

p_{1}^{2}\leq C^{\prime\prime\prime}\frac{1}{\sqrt{1-\rho}}\log(C^{\prime\prime\prime}ns)\left(\frac{s^{2}t}{t_{0}}+\frac{1}{\sqrt{n}}\right)+\sqrt{p_{0}}

for some constant $C^{\prime\prime\prime}>0$ .

5.5.6. Step 6: Completing the proof

Combining the bounds from the previous steps, we obtain

\mathbb{P}_{B,u,v,A_{kk}}(\mathcal{E}\land\mathcal{B}_{A})\leq p_{1}+\sqrt{p_{0}}.

We now proceed to simplify the expression to obtain (5.31). We still have the freedom to chose $t_{0}>0$ ; let us take $t_{0}:=\sqrt{t}$ . In addition, we may assume that the expression

C^{\prime\prime\prime}\log(C^{\prime\prime\prime}ns)\left({s^{2}\sqrt{t}}+\frac{1}{\sqrt{n}}\right)

(5.38)

is less than one as the bound is trivial otherwise. In particular, this implies that $s\leq\exp(\sqrt{n})$ . Among others, this means that the error term $C^{\prime\prime}s\exp(-c^{\prime\prime}n)$ can be absorbed into terms of the form (5.38) (by increasing the constant $C^{\prime\prime\prime}$ if necessary). After some simplification, the bound for $p_{1}$ obtained in the previous step (with the substitution $t_{0}:=\sqrt{t}$ ) yields

\mathbb{P}_{B,u,v,A_{kk}}(\mathcal{E}\land\mathcal{B}_{A})\leq C\left(\frac{\log(Csn)}{\sqrt{1-\rho}}\left(s^{2}\sqrt{t}+\frac{1}{\sqrt{n}}\right)\right)^{1/4}

for some constant $C>0$ . This completes the proof of (5.31), and hence the proof of Lemma 5.13 is complete.

5.6. Proof of Theorem 5.1

In this subsection, we complete the the proof of Theorem 5.1. Indeed, for any $s\geq 1$ and any $0<t\leq 1$ , we have

$\displaystyle\mathbb{P}\left(s_{n}(A)\leq\frac{t}{\sqrt{n}},s_{1}(A)\leq s\right)$	$\displaystyle\leq\mathbb{P}\left(\min_{x\in\mathbb{S}^{n-1}}\\|Ax\\|\leq\frac{t}{\sqrt{n}},s_{1}(A)\leq s\right)$
	$\displaystyle\leq\mathbb{P}\left(\min_{x\in\operatorname{Incomp}(\delta,\tau)}\\|Ax\\|\leq\frac{t}{\sqrt{n}},s_{1}(A)\leq s\right)$	(5.39)
	$\displaystyle\qquad+\mathbb{P}\left(\min_{x\in\operatorname{Comp}(\delta,\tau)}\\|Ax\\|\leq\frac{1}{\sqrt{n}},s_{1}(A)\leq s\right)$

due to our decomposition of the unit sphere into compressible and incompressible vectors. It remains to bound each of the terms on the right-hand side.

For the incompressible vectors, we combine Lemmas 5.12 and 5.13 to find that, for any $t>0$ ,

	$\displaystyle\mathbb{P}\left(\min_{x\in\operatorname{Incomp}(\delta,\tau)}\\|Ax\\|\leq\frac{t\tau}{\sqrt{n}},s_{1}(A)\leq s\right)$	$\displaystyle\leq\frac{2}{\delta n}\sum_{k=1}^{n}\mathbb{P}(\operatorname{dist}(C_{k},H_{k})\leq t,s_{1}(A)\leq s)$
		$\displaystyle\leq\frac{2C}{\delta}\left(\frac{\log(Csn)}{\sqrt{1-\rho}}\left(s^{2}\sqrt{t}+\frac{1}{\sqrt{n}}\right)\right)^{1/4}$

for some constant $C>0$ . Recalling the definitions of $\delta$ and $\tau$ (5.5), we conclude that

\mathbb{P}\left(\min_{x\in\operatorname{Incomp}(\delta,\tau)}\|Ax\|\leq\frac{t}{\sqrt{n}},s_{1}(A)\leq s\right)\leq C^{\prime}\left(\frac{\log(C^{\prime}sn)}{\sqrt{1-\rho}}\left(\sqrt{s^{5}t}+\frac{1}{\sqrt{n}}\right)\right)^{1/4}

(5.40)

for some constant $C^{\prime}>0$ . For compressible vectors, Lemma 5.6 implies the existence of constants $C^{\prime\prime},c^{\prime\prime}>0$ such that

\mathbb{P}\left(\min_{x\in\operatorname{Comp}(\delta,\tau)}\|Ax\|\leq\frac{1}{\sqrt{n}},s_{1}(A)\leq s\right)\leq C^{\prime\prime}\exp(-c^{\prime\prime}n).

(5.41)

Combining (5.40) and (5.41) with (5.39), we conclude that, for any $s\geq 1$ and any $0<t\leq 1$ ,

	$\displaystyle\mathbb{P}\left(s_{n}(A)\leq\frac{t}{\sqrt{n}},s_{1}(A)\leq s\right)$	$\displaystyle\leq C^{\prime}\left(\frac{\log(C^{\prime}sn)}{\sqrt{1-\rho}}\left(\sqrt{s^{5}t}+\frac{1}{\sqrt{n}}\right)\right)^{1/4}+C^{\prime\prime}\exp(-c^{\prime\prime}n)$
		$\displaystyle\leq C^{\prime\prime\prime}\left(\frac{\log(C^{\prime\prime\prime}sn)}{\sqrt{1-\rho}}\left(\sqrt{s^{5}t}+\frac{1}{\sqrt{n}}\right)\right)^{1/4}$

for some constant $C^{\prime\prime\prime}>0$ , where the second inequality follows from the fact that the first error term dominates the second for all $n$ sufficiently large. The proof of Theorem 5.1 is complete.

6. Singular values of $A_{n}$ and uniform integrability

6.1. Tightness

We begin with a bound on the largest singular values of $A_{n}-z$ .

Lemma 6.1.

If Condition C1 holds, there exists $r>0,C>0$ such that the following hold.

•

For all $z\in\mathbb{C}$ , there exists $C_{z}>0$ such that almost surely

\limsup_{n\rightarrow\infty}\int_{0}^{\infty}t^{r}d\nu_{A_{n}-z}(t)<C_{z}\text{ and thus }(\nu_{A_{n}-z})_{n\geq 1}\text{ is tight.}

•

Almost surely

\limsup_{n\rightarrow\infty}\int_{\mathbb{C}}|w|^{r}d\mu_{A_{n}}(w)<C\text{ and thus }(\mu_{A_{n}})_{n\geq 1}\text{ is tight.}.

Proof.

We follow the approach of Lemma 3.1 in [13]. The tightness follows from the moment bound and Markov’s inequality. The moment bound on $\mu_{A_{n}}$ follows from the bound on $\nu_{A_{n}}$ and Weyl’s inequality, Lemma A.7. One has from Lemma A.3, $s_{k}(A_{n}-z)\leq s_{k}(A_{n})+|z|$ for every $1\leq k\leq n$ and thus using the fact for any $x,y\geq 0,(x+y)^{r}\leq 2^{r}(x^{r}+y^{r})$ we can assume $z=0$ . We aim to work with matrices with independent entries, and thus decompose $A_{n}=U_{n}+L_{n}$ where $L_{n}$ is strictly lower triangular, and $U_{n}$ is upper triangular. Note for all $0\leq k\leq n-1$ , we have by Lemma A.3

s_{1+k}(A_{n})\leq s_{1+\lfloor k/2\rfloor}(U_{n})+s_{1+\lceil k/2\rceil}(L_{n}).

We now restrict $r$ such that $0<r\leq 2$ . Thus

\int_{0}^{\infty}t^{r}d\nu_{A_{n}}(t)\leq 8\left[\int_{0}^{\infty}t^{r}d\nu_{U_{n}}(t)+\int_{0}^{\infty}t^{r}d\nu_{L_{n}}(t)\right].

We show only

\limsup_{n\rightarrow\infty}\int_{0}^{\infty}t^{r}d\nu_{U_{n}}(t)<\infty\qquad\qquad\text{a.s.}

as the proof that

\limsup_{n\rightarrow\infty}\int_{0}^{\infty}t^{r}d\nu_{L_{n}}(t)<\infty\qquad\qquad\text{a.s.}

follows in the exact same way.

By the Schatten bound, Lemma A.8,

\int_{0}^{\infty}t^{r}d\nu_{U_{n}}(t)\leq Z_{n}:=\frac{1}{n}\sum_{i=1}^{n}Y_{n,i}

where

Y_{n,i}=\left(\sum_{j=i}^{n}a_{n}^{-2}|X_{ij}|^{2}\right)^{r/2}.

For every $1\leq i<j\leq n$ we let $X_{ji}^{\prime}$ be a copy of $\xi_{1}$ , independent of all $X_{ij}$ and all other $X_{ji}^{\prime}$ . In addition let

Y_{n,i}^{\prime}:=\left(\sum_{j=i}^{n}a_{n}^{-2}|X_{ij}|^{2}+\sum_{j=1}^{i-1}a_{n}^{-2}|X_{ij}^{\prime}|^{2}\right)^{r/2}

then

Z_{n}\leq\frac{1}{n}\sum_{i=1}^{n}Y_{n,i}^{\prime},

since $Y_{n,i}\leq Y_{n,i}^{\prime}$ . The proof then follows exactly as in Lemma 3.1 of [13]. ∎

6.2. Distance from a row and a vector space.

Throughout the rest of this section we assume the atom variables of $X_{n}$ satisfy Condition C2. The proof of Proposition 3.3 from [13] can be adapted in a straight forward way to get Proposition 6.2 below. We give a brief explanation of the changes to the proof needed for entries that are independent but not necessarily identically distributed.

Proposition 6.2.

Let $0<\gamma<1/2$ , and $R$ be the $i$ -th row of $a_{n}(A_{n}-z)$ with the $i$ -th entry set to zero. There exists $\delta>0$ depending on $\alpha,\gamma$ such that for all $d$ -dimensional subspaces $W$ of $\mathbb{C}^{n}$ with $n-d\geq n^{1-\gamma}$ , one has

\mathbb{P}\left(\operatorname{dist}(R,W)\leq n^{(1-2\gamma)/\alpha}\right)\leq e^{-n^{\delta}}.

Proof.

Assume $R$ is the $i$ -th row of $a_{n}(A_{n}-z)$ with the $i$ -th entry set to zero. If $X^{(i)}$ is the $i$ -th row of $X_{n}$ with the $i$ -th entry set to zero, we have

\operatorname{dist}(R,W)\geq\operatorname{dist}(X^{(i)},W_{1})

where $W_{1}=\operatorname{Span}(W,e_{i})$ . Note the entries of $X^{(i)}$ are independent, but have two potentially different distributions, in contrast with [13] where the entries are independent and identically distributed. However, Lemma A.9 can be applied to either distribution. Under Condition C2 the slowly varying function, $L(t)$ , in (1.3) is bounded and $L(t)\rightarrow c>0$ as $t\rightarrow\infty$ for both entries. To adapt the proof of Proposition 3.3 in [13] apply Lemma A.9 to the entries of $X^{(i)}$ to get uniform bounds on the truncated moments without assuming the entries are identically distributed. ∎

We now give some results for stable random variables which will be helpful. For $0<\beta<1$ , let $Z=Z^{(\beta)}$ denote the one-sided positive $\beta$ -stable distribution such that for all $s\geq 0$ ,

\mathbb{E}\exp(-sZ)=\exp(-s^{\beta}).

(6.1)

Recall for $y,m>0$ ,

y^{-m}=\Gamma(m)^{-1}\int_{0}^{\infty}x^{m-1}e^{-xy}dx.

Thus for all $m>0$ ,

\mathbb{E}[Z^{-m}]=\Gamma(m)^{-1}\int_{0}^{\infty}x^{m-1}e^{-x^{\beta}}dx,

(6.2)

and if $Z_{1},\dots,Z_{n}$ are i.i.d. copies of $Z$ and $w_{1},w_{2},\dots,w_{n}$ are non-negative real numbers then

\sum_{i=1}^{n}w_{i}Z_{i}\overset{d}{=}\left(\sum_{i=1}^{n}w_{i}^{\beta}\right)^{1/\beta}Z_{1}.

(6.3)

Lemma 6.3 (Lemma 3.5 in [13]).

Let $0<\alpha<2$ and $Y$ be a random variable such that $t^{\alpha}\mathbb{P}(|Y|\geq t)\rightarrow c$ as $t\rightarrow\infty$ for some $c>0$ . Then there exists $\varepsilon>0$ and $p\in(0,1)$ such that the random variable $|Y|^{2}$ dominates stochastically the random variable $\varepsilon DZ$ , where $\mathbb{P}(D=1)=1-\mathbb{P}(D=0)=p$ is a Bernoulli random variable, $Z=Z^{(\alpha/2)}$ and $D$ and $Z$ are independent.

Lemma 6.4.

Let $X^{(i)}$ be the $i$ -th row of the matrix $X_{n}$ , with the $i$ -th entry set to zero. Let $w_{j}\in[0,1]$ be numbers such that $w(n):=\sum_{j=1}^{n}w_{j}\geq n^{1/2+\varepsilon}$ for some $\varepsilon>0$ . Let $Z=Z^{(\beta)}$ with $\beta=\alpha/2$ . Then there exists $\delta>0$ and a coupling of $X^{(i)}$ and $Z$ such that

\mathbb{P}\left(\sum_{j=1}^{n}w_{j}|X_{ij}|^{2}\leq\delta w(n)^{1/\beta}Z\right)\leq Ce^{-cn^{\delta}}

for constants $C,c>0$ .

Proof.

Let $D=(D_{j})_{j=1}^{i}$ and $D^{\prime}=(D_{j})_{j=i+1}^{n}$ be two independent vectors of i.i.d. Bernoulli random variables given by Lemma 6.3 for $Y=X_{21}$ with parameter $p$ and $Y=X_{12}$ with parameter $p^{\prime}$ respectively. We know from Lemma 6.3 there exists $\varepsilon^{\prime}>0$ , such that for independent random variables $Z_{j}$ satisfying (6.1) such that for every $j$ , $w_{j}|X_{ij}|^{2}$ stochastically dominates $\varepsilon^{\prime}w_{j}D_{j}Z_{j}$ . Then there exists a coupling (see Lemma 2.12 in [32]) such that

\mathbb{P}\left(\sum_{j=1}^{n}w_{j}|X_{ij}|^{2}\geq\varepsilon^{\prime}\sum_{j=1}^{n}w_{j}D_{j}Z_{j}\right)=1.

Let $\mathbf{a}=(a_{1},\dots,a_{n})\in\{0,1\}^{n}$ , and $A_{\mathbf{a}}$ be the event $D_{j}=a_{j}$ for all $j$ . Then define the random variable $Z$ pointwise on $A_{\mathbf{a}}$ , $\mathbf{a}\neq\mathbf{0}$

Z(\omega):=\frac{\sum_{j=i}^{n}w_{j}a_{j}Z_{j}(\omega)}{\left(\sum_{j=1}^{n}w_{j}^{\beta}a_{j}\right)^{1/\beta}},

for $\omega\in A_{\mathbf{a}}$ and $Z(\omega)=Z_{1}(\omega)$ on $A_{\mathbf{0}}$ . From (6.3), we see $Z$ satisfies (6.1) and the distribution of $Z$ does not depend on $D_{1},\dots,D_{n}$ . Thus it is sufficient to show there exists $\varepsilon^{\prime\prime}>0$ such that

\mathbb{P}\left(\sum_{j=1}^{n}w_{j}^{\beta}D_{j}\leq\varepsilon^{\prime\prime}w(n)\right)\leq Ce^{-cn^{\varepsilon^{\prime\prime}}}.

Note $w_{j}^{\beta}\geq w_{j}$ , and thus $\mathbb{E}\sum_{j=1}^{n}w_{j}^{\beta}D_{j}\geq\min(p,p^{\prime})w(n)$ . Therefore for $0<\varepsilon^{\prime\prime}<\min(p,p^{\prime})$ ,

	$\displaystyle\mathbb{P}\left(\sum_{j=1}^{n}w_{j}^{\beta}D_{j}\leq\varepsilon^{\prime\prime}w(n)\right)$
	$\displaystyle\qquad\qquad\leq\mathbb{P}\left(\big{\|}\sum_{j=1}^{n}(w_{j}^{\beta}D_{j}-\mathbb{E}w_{j}^{\beta}D_{j})\big{\|}\geq(\min(p,p^{\prime})-\varepsilon^{\prime\prime})w(n)\right)$
	$\displaystyle\qquad\qquad\leq 2e^{-\frac{1}{2}(\min(p,p^{\prime})-\varepsilon^{\prime\prime})^{2}w(n)^{2}/n},$

where the last bound follows from Hoeffding’s inequality. ∎

We now give another bound on the distance between a row of $A_{n}$ and a deterministic subspace.

Proposition 6.5.

Take $0<\gamma<\alpha/4$ . Let $R$ be the $i$ -th row of $a_{n}(A_{n}-z)$ with the $i$ -th entry set to zero. There exists an event $E$ such that for any $d$ -dimensional subspace $W$ of $\mathbb{C}^{n}$ with $n-d\geq n^{1-\gamma}$ , we have for sufficiently large $n$

\mathbb{E}[\operatorname{dist}^{-2}(R,W);E]\leq c(n-d)^{-2/\alpha}\quad\text{and}\quad\mathbb{P}(E^{c})\leq cn^{-\frac{1}{2}+\gamma(\frac{2}{\alpha}-\frac{1}{2})},

where $c>0$ is an absolute constant which does not depend on the choice of row.

Proof.

We follow the approach of the proof of Proposition 3.7 in [13]. The only difference with Proposition 3.7 in [13] is the entries here are independent but not necessarily identically distributed. Assume that $R$ is the $i$ -th row of $a_{n}(A_{n}-z)$ with the $i$ -th entry set to zero. Note

\operatorname{dist}(R,W)\geq\operatorname{dist}(X^{(i)},W_{1}),

(6.4)

where $W_{1}=\operatorname{Span}(W,e_{i})$ , $e_{i}$ is the $i$ -th basis vector, and $X^{(i)}=(X_{ij})_{1\leq j\leq n}$ . Though the $i$ -th entry of $X^{(i)}$ is not necessarily zero, inequality (6.4) still holds since the subspace spanned by $e_{i}$ is contained in $W_{1}$ . Let $\mathcal{J}$ denote the set of indices $j$ such that $|X_{ij}|\leq a_{n}$ . It is a straight forward application of the Chernoff bound to show there exists $\delta>0$ such that

\mathbb{P}(|\mathcal{J}|<n-\sqrt{n})\leq e^{-n^{\delta}}.

We begin by showing for any set $J\subset\{1,\dots,n\}$ such that $|J|\geq n-\sqrt{n}$ ,

\mathbb{E}[\operatorname{dist}^{-2}(R,W);E_{J}|\mathcal{J}=J]\leq c(n-d)^{-2/\alpha},

for some event $E_{J}$ satisfying $\mathbb{P}(E_{J}^{c}|\mathcal{J}=J)\leq cn^{-\frac{1}{2}+\gamma(\frac{2}{\alpha}-\frac{1}{2})}$ . Without loss of generality assume $J:=\{1,\dots,n^{\prime}\}$ with $n^{\prime}\geq n-\sqrt{n}$ . Let $\pi_{J}$ be the orthogonal projection onto the first $n^{\prime}$ canonical basis vectors. Let $W_{2}=\pi_{J}(W_{1})$ , set

W^{\prime}=\operatorname{Span}\left(W_{2},\mathbb{E}(\pi_{J}(X^{(i)})|\mathcal{J}=J)\right).

Note $d-\sqrt{n}\leq\dim(W^{\prime})\leq\dim(W_{1})+1\leq d+2$ . Define

Y=\pi_{J}(X^{(i)})-\mathbb{E}(\pi_{J}(X^{(i)})|\mathcal{J}=J).

One has

\operatorname{dist}(R,W)\geq\operatorname{dist}(Y,W^{\prime}).

$Y$ is a mean zero vector under $\mathbb{P}(\cdot|\mathcal{J}=J)$ . Note $W^{\prime}\subseteq\pi_{J}(\mathbb{C}^{n})$ and $Y\in\pi_{J}(\mathbb{C}^{n})$ , so we will work with both as objects in only $\pi_{J}(\mathbb{C}^{n})\simeq\mathbb{C}^{n^{\prime}}$ and not the larger vector space $\mathbb{C}^{n}$ . Let $P$ be the orthogonal projection matrix onto $(W^{\prime})^{\perp}$ in $\mathbb{C}^{n^{\prime}}$ . Note $\operatorname{tr}P=n^{\prime}-\dim(W^{\prime})$ satisfies for sufficiently large $n$

2(n-d)\geq\operatorname{tr}P\geq\frac{1}{2}(n-d).

(6.5)

By construction

\mathbb{E}(\operatorname{dist}^{2}(Y,W^{\prime})|\mathcal{J}=J)=\mathbb{E}\left[\sum_{j,k=1}^{n^{\prime}}Y_{j}P_{jk}\bar{Y}_{k}|\mathcal{J}=J\right]=\sum_{j=1}^{n^{\prime}}P_{jj}\mathbb{E}[|Y_{j}|^{2}|\mathcal{J}=J].

(6.6)

Let $S:=\sum_{j=1}^{n^{\prime}}P_{jj}|Y_{j}|^{2}$ . Before beginning note by Lemma A.9 there exists $C>0$ such that $\mathbb{E}[|Y_{j}|^{2}|\mathcal{J}=J]\leq Ca_{n}^{2}/n$ for $1\leq j\leq n^{\prime}$ . Thus³³3We believe there is a small typo in the bound of $\mathbb{E}(|\operatorname{dist}^{2}(Y,W^{\prime})-S|^{2}\big{|}\mathcal{J}=J)$ in the proof of Proposition 3.7 in [13]

	$\displaystyle\mathbb{E}(\|\operatorname{dist}^{2}(Y,W^{\prime})-S\|^{2}\big{\|}\mathcal{J}=J)$	$\displaystyle=\mathbb{E}\left(\left\|\sum_{k\neq j}Y_{j}P_{jk}\bar{Y}_{k}\right\|^{2}\big{\|}\mathcal{J}=J\right)$
		$\displaystyle\leq\frac{2Ca_{n}^{4}}{n^{2}}\sum_{j,k}\|P_{jk}\|^{2}$
		$\displaystyle=\frac{2Ca_{n}^{4}}{n^{2}}\\|P\\|_{2}^{2}$
		$\displaystyle=\frac{2Ca_{n}^{4}}{n^{2}}\operatorname{tr}(P^{*}P)$
		$\displaystyle=\frac{2Ca_{n}^{4}}{n^{2}}\operatorname{tr}(P).$

Thus

\mathbb{E}(|\operatorname{dist}^{2}(Y,W^{\prime})-S|^{2}\big{|}\mathcal{J}=J)=O\left(a_{n}^{4}\frac{n-d}{n^{2}}\right).

(6.7)

Let $Z$ be as in Lemma 6.4. Set $w_{j}=P_{jj}$ and for $\varepsilon>0$ , consider the event

\Gamma_{J}:=\left\{\sum_{j=1}^{n^{\prime}}w_{j}|X_{ij}|^{2}\geq\varepsilon(n-d)^{1/\beta}Z\right\},

where $\beta=\alpha/2$ . From Lemma 6.4 there exists a coupling of $X_{i1},\dots,X_{i,n^{\prime}}$ and $Z$ such that

\mathbb{P}(\Gamma_{J}^{c})\leq Ce^{-cn^{\delta}},

(6.8)

for some $\delta>0$ and some choice of $\varepsilon>0$ . Since $(a-b)^{2}\geq a^{2}/2-b^{2}$ for $a,b\in\mathbb{R}$ we have $S\geq\frac{1}{2}S_{a}-S_{b}$ where

S_{a}:=\sum_{j=1}^{n^{\prime}}w_{j}|X_{ij}|^{2},

and

S_{b}:=\sum_{j=1}^{n^{\prime}}w_{j}\mathbb{E}[|X_{ij}|\big{|}X_{ij}\leq a_{n}]^{2}.

From Lemma A.9 and (6.5) one has

S_{b}\leq h^{(\alpha)}(n,d)

where $h^{(\alpha)}(n,d)=\Theta((n-d)a_{n}^{2}/n^{2})$ if $\alpha\in(0,1]$ and $h^{(\alpha)}(n,d)=\Theta((n-d))$ if $\alpha\in(1,2)$ . Let $G_{J}^{1}$ be the event that $S_{a}\geq 3S_{b}$ . There exists some $c_{0}$ such that

\mathbb{P}((G_{J}^{1})^{c}\cap\Gamma_{J}|\mathcal{J}=J)\leq\mathbb{P}(Z\leq c_{0}(n-d)^{-1/\beta}h^{(\alpha)}(n,d)|\mathcal{J}=J).

From the assumption $n-d\geq n^{1-\gamma}$ with $0<\gamma<\alpha/4$ we have $(n-d)^{-1/\beta}h^{(\alpha)}(n,d)\leq Cn^{-\varepsilon_{0}}$ for some $C,\varepsilon_{0}>0$ . From here, using the bound (6.2) on the negative second moment of $Z$ , it is straightforward to show that for every $p>0$ there exists a constant $\kappa_{p}$ such that

\mathbb{P}((G_{J}^{1})^{c}\cap\Gamma_{J}|\mathcal{J}=J)\leq\kappa_{p}n^{-p}.

(6.9)

Set $\tilde{\Gamma}_{J}=G_{J}^{1}\cap\Gamma_{J}$ . On $\tilde{\Gamma}_{J}$ , $S\geq\frac{1}{6}S_{a}\geq\frac{\varepsilon}{6}(n-d)^{2/\alpha}Z$ , and therefore

\mathbb{E}[S^{-2};\tilde{\Gamma}_{J}|\mathcal{J}=J]\leq c_{1}(n-d)^{-4/\alpha}\mathbb{E}[Z^{-2}].

and thus using again the negative second moment bound on $Z$ ,

\mathbb{E}[S^{-2};\tilde{\Gamma}_{J}|\mathcal{J}=J]=O\left((n-d)^{-4/\alpha}\right).

(6.10)

Let $G_{J}^{2}$ be the event $\{\operatorname{dist}^{2}(Y,W^{\prime})\geq S/2\}$ . Note using Markov’s inequality and the Cauchy-Schwarz inequality leads to

$\displaystyle\mathbb{P}\left(\operatorname{dist}^{2}(Y,W^{\prime})\leq S/2;\tilde{\Gamma}_{J}\|\mathcal{J}=J\right)$	$\displaystyle\leq\mathbb{P}\left(\frac{\|\operatorname{dist}^{2}(Y,W^{\prime})-S\|}{S}\geq 1/2;\tilde{\Gamma}_{J}\|\mathcal{J}=J\right)$
	$\displaystyle\leq 2\mathbb{E}\left[\frac{\|\operatorname{dist}^{2}(Y,W^{\prime})-S\|}{S};\tilde{\Gamma}_{J}\|\mathcal{J}=J\right]$	(6.11)
	$\displaystyle\leq 2\sqrt{\mathbb{E}\left[\|\operatorname{dist}^{2}(Y,W^{\prime})-S\|^{2}\|\mathcal{J}=J\right]\mathbb{E}[S^{-2};\tilde{\Gamma}_{J}\|\mathcal{J}=J]}.$

Then by (6.7), (6.10), and (6.2)

\mathbb{P}\left((G_{J}^{2})^{c}\cap\tilde{\Gamma}_{J}|\mathcal{J}=J\right)=O\left(a_{n}^{2}n^{-1}(n-d)^{\frac{1}{2}-\frac{2}{\alpha}}\right).

(6.12)

By the Cauchy-Schwarz inequality

\mathbb{E}\left[\operatorname{dist}^{-2}(X,W);G_{J}^{2}\cap\tilde{\Gamma}_{J}|\mathcal{J}=J\right]\leq 2\mathbb{E}\left[S^{-1};\tilde{\Gamma}_{J}|\mathcal{J}=J\right]=O\left((n-d)^{-2/\alpha}\right).

To conclude take $E_{J}=G_{J}^{2}\cap\tilde{\Gamma}_{J}$ . Then

\mathbb{P}(E_{J}^{c}|\mathcal{J}=J)\leq\mathbb{P}(\Gamma_{J}^{c}|\mathcal{J}=J)+\mathbb{P}((G_{J}^{1})^{c}\cap\Gamma_{J}|\mathcal{J}=J)+\mathbb{P}\left((G_{J}^{2})^{c}\cap\tilde{\Gamma}_{J}|\mathcal{J}=J\right).

It is then straightforward to show using (6.8), (6.9), and (6.12)

\mathbb{P}(E_{J}^{c}|\mathcal{J}=J)=O\left(n^{-\frac{1}{2}+\gamma(\frac{2}{\alpha}-\frac{1}{2})}\right).

Take $E=\bigcup_{J\in\mathbf{J}}E_{J}\cap\{\mathcal{J}=J\}$ where $\mathbf{J}=\{J\subseteq[n]:|J|\geq n-\sqrt{n}\}$ to complete the proof. ∎

6.3. Application of Theorem 5.1

We now show that Theorem 5.1 can be applied to $A_{n}$ to bound $s_{n}(A_{n}-z)$ from below with high probability. The difficulty is connecting the hypothesis on the spectral measure in Condition C2 to the correlation of truncated random variables in the statement of Theorem 5.1.

Theorem 6.6.

For all $z\in\mathbb{C}$ , there exists $C,r>0$ such that

\mathbb{P}\left(s_{n}(A_{n}-z)\leq Cn^{-r}\right)=o(1).

It is worth noting $o(1)$ can be improved to $n^{-\varepsilon}$ for some sufficiently small $\varepsilon>0$ . The proof of Theorem 6.6 will be an application of Theorem 5.1. First we need a bound on the operator norm, and hence the largest singular value, of $A_{n}-z$ .

Lemma 6.7.

For every $z\in\mathbb{C}$ , there exists $C>0$ depending on the distribution of the entries and $z$ such that for any $k>1/\alpha$ and $n$ sufficiently large,

\mathbb{P}(\|X_{n}-a_{n}z\|\geq n^{k})\leq\frac{C}{n^{((k-1)\alpha/2)-2}}.

Proof.

Since

\|X_{n}-a_{n}z\|\leq\|X_{n}\|+a_{n}|z|\leq\|X_{n}\|+C_{z}n^{1/\alpha},

it is sufficient to bound $\mathbb{P}\left(\|X_{n}\|\geq cn^{k}\right)$ , for some $0<c<1$ and $n$ sufficiently large. Note

\|X_{n}\|^{2}\leq n^{2}\max_{1\leq i,j\leq n}\{|X_{ij}|^{2}\}.

Thus, by the union bound,

	$\displaystyle\mathbb{P}\left(\\|X_{n}\\|\geq cn^{k}\right)$	$\displaystyle=\mathbb{P}\left(\\|X_{n}\\|^{2}\geq c^{2}n^{2k}\right)$
		$\displaystyle\leq\mathbb{P}\left(\max_{1\leq i,j\leq n}\{\|X_{ij}\|^{2}\}\geq c^{2}n^{2(k-1)}\right)$
		$\displaystyle\leq\mathbb{P}\left(\bigcup_{1\leq i,j\leq n}\{\|X_{ij}\|^{2}\geq c^{2}n^{2(k-1)}\}\right)$
		$\displaystyle\leq n^{2}\max_{i,j=1,2}\left\{\mathbb{P}\left(\|X_{ij}\|^{2}\geq c^{2}n^{2(k-1)}\right)\right\}$
		$\displaystyle\leq n^{2}\frac{C^{\prime}\mathbb{E}\|X_{12}\|^{\alpha/2}}{n^{2(k-1)\alpha/4}},$

where the last inequality follows from Markov’s inequality and (1.5). ∎

Proof of Theorem 6.6.

Clearly $X_{n}$ satisfies conditions (i) and (ii) of Theorem 5.1, so it only remains to check condition (iii) before we can apply Theorem 5.1. Let $\mathcal{E}_{ij}^{n}:=\{|X_{ij}|<\log(n)a_{n},|X_{ji}|<\log(n)a_{n}\}$ . Since $\{(X_{ij},X_{ji}):1\leq i<j\leq n\}$ is a collection i.i.d. random tuples we focus on showing for some $n$ , $\mathcal{E}_{12}^{n}$ satisfies the desired conditions. From the tail bounds on $X_{12},$ and $X_{21}$ ,

\mathbb{P}(\mathcal{E}^{n}_{12})\geq 1-\frac{C}{\log(n)^{\alpha}n}.

$\operatorname{Var}(X_{12}|\mathcal{E}^{n}_{12})=0$ if and only if $X_{12}$ is constant on $\mathcal{E}^{n}_{12}$ , and hence on any subset of $\mathcal{E}^{n}_{12}$ . Thus if $\operatorname{Var}(X_{12}|\mathcal{E}^{n_{0}}_{12})>0$ for some $n_{0}$ , then $\operatorname{Var}(X_{12}|\mathcal{E}^{n}_{12})>0$ for all $n\geq n_{0}$ . Since $X_{12}$ is non-constant, there must be some $n$ sufficiently large such that $X_{12}$ is non-constant on $\mathcal{E}_{12}^{n}$ . Thus $\operatorname{Var}(X_{12}|\mathcal{E}^{n}_{12})>0$ for all $n$ sufficiently large. The same argument follows for $\operatorname{Var}(X_{21}|\mathcal{E}^{n}_{12})$ .

Now assume for all $n$ sufficiently large,

|\text{Corr}\left(X_{12}|\mathcal{E}_{12}^{n},X_{21}|\mathcal{E}_{12}^{n}\right)|=1.

Then there exists $\theta_{n}\in[0,2\pi)$ such that on $\mathcal{E}_{12}^{n}$ ,

X_{12}-\mathbb{E}[X_{12}|\mathcal{E}^{n}_{12}]=e^{i\theta_{n}}\sqrt{\frac{\operatorname{Var}(X_{12}|\mathcal{E}^{n}_{12})}{\operatorname{Var}(X_{21}|\mathcal{E}^{n}_{12})}}\left[X_{21}-\mathbb{E}[X_{21}|\mathcal{E}^{n}_{12}]\right].

For $\alpha<1$ , by Lemma A.9

\frac{\mathbb{E}[|X_{12}|\mathbf{1}_{\{{|X_{12}|\leq t}\}}]}{\left(\frac{\alpha}{1-\alpha}L(t)t^{1-\alpha}\right)}\rightarrow 1,

as $t\rightarrow\infty$ , for some slowly varying function $L$ . We assumed the atom variables satisfy Condition C2 (ii), specifically $a_{n}\sim cn^{1/\alpha}$ and thus $L(t)\rightarrow c^{\prime}$ for some constant $c^{\prime}>0$ as $t\rightarrow\infty$ . For $\alpha\geq 1$ , $\mathbb{E}[|X_{12}|\mathbf{1}_{\{{|X_{12}|\leq t}\}}]$ is dominated by $t^{r}$ for any $r>0$ . Thus on $\mathcal{E}_{12}^{n}$

X_{12}=R_{n}X_{21}+C_{n}

where $R_{n}$ is a sequence of complex numbers and

\lim\limits_{n\rightarrow\infty}\frac{C_{n}}{a_{n}}=0,

(6.13)

since $\sqrt{\frac{\operatorname{Var}(X_{12}|\mathcal{E}^{n}_{12})}{\operatorname{Var}(X_{21}|\mathcal{E}^{n}_{12})}}$ is slowly varying by Lemma A.9. If $R_{n}$ has a bounded subsequence $R_{n_{k}}$ , we shall take the corresponding sequences $a_{n_{k}}$ , and $n_{k}$ and for simplicity denote all three by $R_{n},a_{n},$ and $n$ . If not, then we note on $\mathcal{E}_{12}^{n}$

X_{21}=(R_{n})^{-1}X_{12}+C_{n}^{\prime}

where $(R_{n})^{-1}$ is bounded, and (6.13) still holds for $C_{n}^{\prime}$ . Thus we will assume $R_{n}$ is bounded and we take a subsequence which converges to $R$ . Let $r>0$ and $B$ be a Borel subset of the unit sphere in $\mathbb{C}^{2}$ such that $\theta_{d}(\partial B)=0$ . Note

$\displaystyle\theta_{d}(B)m_{\alpha}([r,\infty)=$	$\displaystyle\lim\limits_{n\rightarrow\infty}n\mathbb{P}\left(\frac{(X_{12},X_{21})}{\\|(X_{12},X_{21})\\|}\in B,\\|(X_{12},X_{21})\\|\geq ra_{n}\right)=$
	$\displaystyle\lim\limits_{n\rightarrow\infty}n\mathbb{P}\left(\frac{(X_{12},X_{21})}{\\|(X_{12},X_{21})\\|}\in B,\\|(X_{12},X_{21})\\|\geq ra_{n},\mathcal{E}^{n}_{12}\right)$	(6.14)
	$\displaystyle\quad\quad+\lim\limits_{n\rightarrow\infty}n\mathbb{P}\left(\frac{(X_{12},X_{21})}{\\|(X_{12},X_{21})\\|}\in B,\\|(X_{12},X_{21})\\|\geq ra_{n},(\mathcal{E}^{n}_{12})^{c}\right),$

and

		$\displaystyle\lim\limits_{n\rightarrow\infty}n\mathbb{P}\left(\frac{(X_{12},X_{21})}{\\|(X_{12},X_{21})\\|}\in B,\\|(X_{12},X_{21})\\|\geq ra_{n},(\mathcal{E}^{n}_{12})^{c}\right)$
		$\displaystyle\quad\leq\lim\limits_{n\rightarrow\infty}n\mathbb{P}((\mathcal{E}^{n}_{12})^{c})$
		$\displaystyle\quad=\lim\limits_{n\rightarrow\infty}n\mathbb{P}(\|X_{12}\|\geq\log(n)a_{n},\text{or}\|X_{21}\|\geq\log(n)a_{n})$		(6.15)
		$\displaystyle\quad\leq\lim\limits_{n\rightarrow\infty}Cn(\log(n)a_{n})^{-\alpha}$
		$\displaystyle\quad=\lim\limits_{n\rightarrow\infty}C^{\prime}n(\log(n)n^{1/\alpha})^{-\alpha}$
		$\displaystyle\quad=0.$

Thus we will consider only

\lim\limits_{n\rightarrow\infty}n\mathbb{P}\left(\frac{(X_{12},X_{21})}{\|(X_{12},X_{21})\|}\in B,\|(X_{12},X_{21})\|\geq ra_{n},\mathcal{E}^{n}_{12}\right).

(6.16)

Define the set $A$ as

A=\{(z,w)\in\mathbb{C}^{2}:z=Rw,|z|^{2}+|w|^{2}=1\},

where $R$ is the limit of $R_{n}$ . Let $(z_{1},z_{2})\in\mathbb{C}^{2}$ be such that $(z_{1},z_{2})\notin A$ and $|z_{1}|^{2}+|z_{2}|^{2}=1$ . Let $O$ be a small open neighborhood of $(z_{1},z_{2})$ in $\mathbb{C}^{2}$ such that $A\cap\bar{O}=\emptyset$ . We will consider the limit

\lim\limits_{n\rightarrow\infty}n\mathbb{P}\left(\frac{(X_{12},X_{21})}{\|(X_{12},X_{21})\|}\in O,\|(X_{12},X_{21})\|\geq ra_{n},\mathcal{E}^{n}_{12}\right).

(6.17)

Before we deal with this limit note that on $\mathcal{E}^{n}_{12}$

\frac{(X_{12},X_{21})}{\|(X_{12},X_{21})\|}=\frac{(RX_{21},X_{21})}{\|(X_{12},X_{21})\|}+\frac{((R_{n}-R)X_{21},0)}{\|(X_{12},X_{21})\|}+\frac{(C_{n},0)}{\|(X_{12},X_{21})\|},

(6.18)

\left|\|(RX_{21},X_{21})\|-\|((R_{n}-R)X_{21},0)\|-\|(C_{n},0)\|\right|\leq\|(X_{12},X_{21})\|,

(6.19)

and

\|(X_{12},X_{21})\|\leq\|(RX_{21},X_{21})\|+\|((R_{n}-R)X_{21},0)\|+\|(C_{n},0)\|.

(6.20)

We aim to show the unit vector in (6.17) is approaching the bad set $A$ , which will lead to a contradiction of Condition C2. To this end note by factoring out $\|(RX_{21},X_{21})\|$ from (6.19) and (6.20), we get

\|(X_{12},X_{21})\|\geq\|(RX_{21},X_{21})\|\left|1-\frac{\|((R_{n}-R)X_{21},0)\|+|C_{n}|}{\|(RX_{21},X_{21})\|}\right|,

and

\|(X_{12},X_{21})\|\leq\|(RX_{21},X_{21})\|\left[1+\frac{\|((R_{n}-R)X_{21},0)\|+|C_{n}|}{\|(RX_{21},X_{21})\|}\right].

Since $|C_{n}|=o(a_{n})$ , it follows from (6.20) that if $\|(X_{12},X_{21})\|\geq ra_{n}$ , then $\|(RX_{21},X_{21})\|\geq ca_{n}$ for some $c>0$ . It then follows that on $\{\|(X_{12},X_{21})\|\geq ra_{n},\mathcal{E}^{n}_{12}\}$

\|(X_{12},X_{21})\|\geq\|(RX_{21},X_{21})\|\left[1-o(1)\right],

and

\|(X_{12},X_{21})\|\leq\|(RX_{21},X_{21})\|\left[1+o(1)\right].

Thus

		$\displaystyle\lim\limits_{n\rightarrow\infty}n\mathbb{P}\left(\frac{(X_{12},X_{21})}{\\|(X_{12},X_{21})\\|}\in O,\\|(X_{12},X_{21})\\|\geq ra_{n},\mathcal{E}^{n}_{12}\right)$
		$\displaystyle\quad=\lim\limits_{n\rightarrow\infty}n\mathbb{P}\left(\frac{(RX_{21},X_{21})}{\\|(RX_{21},X_{21})\\|}+o(1)\in O,\\|(X_{12},X_{21})\\|\geq ra_{n},\mathcal{E}^{n}_{12}\right)$		(6.21)
		$\displaystyle\quad=0,$

since $\frac{(RX_{21},X_{21})}{\|(RX_{21},X_{21})\|}+o(1)$ is a small perturbation of a vector in $A$ which is disjoint from $O$ . From (6.3), (6.3), and (6.3) we see

\lim\limits_{n\rightarrow\infty}n\mathbb{P}\left(\frac{(X_{12},X_{21})}{\|(X_{12},X_{21})\|}\in O,\|(X_{12},X_{21})\|\geq ra_{n}\right)=0.

Thus for arbitrary $(z_{1},z_{2})\in\mathbb{C}^{2}$ , $(z_{1},z_{2})\notin\operatorname{supp}(\theta_{d})$ and $\operatorname{supp}(\theta_{d})\subseteq A$ , a contradiction of Condition C2 (i). Therefore there exists arbitrarily large $n$ such that

|\text{Corr}\left(X_{12}|\mathcal{E}_{12}^{n},X_{21}|\mathcal{E}_{12}^{n}\right)|<1.

From the above we see Theorem 5.1 may be applied to $A_{n}-z$ , which combining with Lemma 6.7 completes the proof of Theorem 6.6. ∎

6.4. Uniform integrability

For $0<\delta<1$ we define $K_{\delta}=[\delta,\delta^{-1}]$ . We aim to show that $\log(\cdot)$ is uniformly integrable in probability with respect to $\{\nu_{A-z}\}_{n\geq 1}$ , i.e. for all $\varepsilon>0$

\lim\limits_{\delta\rightarrow 0}\lim\limits_{n\rightarrow\infty}\mathbb{P}\left(\int_{K_{\delta}^{c}}|\log(x)|d\nu_{A_{n}-z}(x)>\varepsilon\right)=0.

(6.22)

From Lemma 6.1 there exists a constant $c_{0}>0$ such that with probability 1

\limsup_{n\rightarrow\infty}\int_{1}^{\infty}|\log(x)|d\nu_{A_{n}-z}(x)<c_{0}.

From this, the part of the integral in (6.22) over $[\delta^{-1},\infty)$ is not a concern. Thus it suffices to prove that for every sequence $\delta_{n}$ converging to $0$ ,

\frac{1}{n}\sum_{i=0}^{n-1}\mathbf{1}_{\{s_{n-i}\leq\delta_{n}\}}\log s_{n-i}^{-2}

converges to $0$ in probability. By Theorem 6.6 we may, with probability $1-o(1)$ , lower bound $s_{n-i}$ by $cn^{-r}$ for all $i$ . Take $0<\gamma<\alpha/4$ to be fixed later. Using the polynomial lower bound for $0\leq i\leq n^{1-\gamma}$ , it follows that it is sufficient to prove that

\frac{1}{n}\sum_{i=\lfloor n^{1-\gamma}\rfloor}^{n-1}\mathbf{1}_{\{s_{n-i}\leq\delta_{n}\}}\log s_{n-i}^{-2}

converges in probability to $0$ .

We next aim to show there exists an event $F_{n}$ such that for some $\delta>0$ and $c>0$

\mathbb{P}(F_{n}^{c})\leq c\exp(-n^{\delta}),

and

\mathbb{E}[s_{n-i}^{-2}|F_{n}]\leq c(\frac{n}{i})^{\frac{2}{\alpha}+1},

for $\lfloor n^{1-\gamma}\rfloor\leq i\leq n-1$ . First to see why this implies convergence in probability to zero, note

\mathbb{P}(s_{n-i}\leq\delta_{n})\leq\mathbb{P}(F_{n}^{c})+c\delta_{n}^{2}(\frac{n}{i})^{1+2/\alpha}.

It follows there exists a sequence $\varepsilon_{n}=\delta_{n}^{1/(\frac{2}{\alpha}+1)}$ tending to zero such that $\mathbb{P}(s_{n-\lfloor n\varepsilon_{n}\rfloor}\leq\delta_{n})$ converges to $0$ . Hence it is sufficient to prove, given $F_{n}$ ,

\frac{1}{n}\sum_{i=\lfloor n^{1-\gamma}\rfloor}^{\lfloor\varepsilon_{n}n\rfloor}\log s_{n-i}^{-2}

(6.23)

converges to zero in probability. Using the negative second moment bound on $F_{n}$ and the concavity of $\log$ we have

	$\displaystyle\mathbb{E}\left[\frac{1}{n}\sum_{i=\lfloor n^{1-\gamma}\rfloor}^{\lfloor\varepsilon_{n}n\rfloor}\mathbf{1}_{\{s_{n-i}\leq\delta_{n}\}}\log s_{n-i}^{-2}\big{\|}F_{n}\right]$	$\displaystyle\leq\frac{1}{n}\sum_{i=\lfloor n^{1-\gamma}\rfloor}^{\lfloor\varepsilon_{n}n\rfloor}\log\mathbb{E}[s_{n-i}^{-2}\|F_{n}]$
		$\displaystyle\leq\frac{c_{1}}{n}\sum_{i=1}^{\lfloor\varepsilon_{n}n\rfloor}\log(\frac{n}{i})$
		$\displaystyle\rightarrow 0$

where the last sum converges to zero by a Riemann Sum approximation. Thus, by Markov’s inequality we obtain convergence (given $F_{n}$ ) of (6.23) in probability to zero.

Now we finish with the construction of such an event $F_{n}$ . Let $B_{n}$ be the matrix formed by the first $n-\lfloor i/2\rfloor$ rows of $a_{n}(A_{n}-z)$ . If $s_{1}^{\prime}\geq s_{2}^{\prime}\geq\cdots\geq s_{n-\lfloor i/2\rfloor}^{\prime}$ are the singular values of $B_{n}$ , then by Cauchy interlacing

s_{n-i}\geq\frac{s_{n-i}^{\prime}}{a_{n}}.

(6.24)

By the Tao-Vu negative second moment lemma, Lemma A.4, we have

s_{1}^{\prime-2}+\cdots s_{n-\lfloor i/2\rfloor}^{\prime-2}=\operatorname{dist}_{1}^{-2}+\cdots\operatorname{dist}_{n-\lfloor i/2\rfloor}^{-2}

(6.25)

where $\operatorname{dist}_{j}$ is the distance from the $j$ -th row of $B_{n}$ to the subspace spanned by the other rows. Using (6.24) and (6.25) we get

\frac{i}{2}s_{n-i}^{-2}\leq a_{n}^{2}\sum_{j=i}^{n-\lfloor i/2\rfloor}\operatorname{dist}_{j}^{-2}.

Now let $\operatorname{dist}_{j}^{\prime}$ be the distance from the $j$ -th row of $B_{n}$ with its $j$ -th entry removed and the subspace spanned by the other rows minus their $j$ -th entry. Since $\operatorname{dist}_{j}\geq\operatorname{dist}_{j}^{\prime}$ we have

\frac{i}{2}s_{n-i}^{-2}\leq a_{n}^{2}\sum_{j=i}^{n-\lfloor i/2\rfloor}\operatorname{dist}_{j}^{\prime-2}

(6.26)

Let $F_{n,i}$ be the event that for all $1\leq j\leq n-\lfloor i/2\rfloor$ , $\operatorname{dist}_{j}^{\prime}\geq(n-1)^{(1-2\gamma)/\alpha}$ . Since the span of all but 1 row of $B_{n}$ is at most $n-i/2$ , we can use Proposition 6.2 to obtain, for sufficiently large $n$ ,

\mathbb{P}(F_{n,i}^{c})\leq\exp(-(n-1)^{\delta^{\prime}}),

for some $\delta^{\prime}>0$ (after a union bound). Let $F_{n}=\bigcap_{i=0}^{n^{1-\gamma}}F_{n,i}$ , then

\mathbb{P}(F_{n}^{c})\leq\exp(-(n-1)^{\delta}),

for some $\delta>0$ .

We now aim to show the desired negative second moment bound on $F_{n}$ . Recall from Proposition 6.5 there exists an event $E_{j}$ independent from the rows $i\neq j$ of $B_{n}$ without their $i$ -th entry such that $\mathbb{P}(E_{j}^{c})\leq n^{-\frac{1}{2}+\gamma(\frac{2}{\alpha}-\frac{1}{2})}$ and for any subspace $W$ with dimension $d<n-n^{1-\gamma}$ one has

\mathbb{E}[\operatorname{dist}(R,W)^{-2};E_{j}]\leq c(n-d)^{-2/\alpha}

where $R$ is the $j$ -th row of $B_{n}$ with the $j$ -th entry removed. Thus

\mathbb{E}[\operatorname{dist}_{j}^{\prime-2};E_{j}]=O(i^{-2/\alpha}),

for $i\leq j\leq n-\lfloor i/2\rfloor$ .

By taking the lower bound of $\operatorname{dist}_{j}^{\prime}\geq(n-1)^{(1-2\gamma)/\alpha}$ on $E^{c}_{j}\cap F_{n}$ , we get

\mathbb{E}[\operatorname{dist}_{j}^{\prime-2};F_{n}]\leq c_{2}\left(i^{-2/\alpha}+n^{-\frac{1}{2}+\gamma(\frac{2}{\alpha}-\frac{1}{2})-2(1-2\gamma)/\alpha}\right).

So for $\gamma$ , not dependent on $i$ , sufficiently small one has

\mathbb{E}[\operatorname{dist}_{j}^{\prime-2};F_{n}]\leq c_{3}i^{-2/\alpha}.

Thus by (6.26)

\mathbb{E}[s_{n-i}^{-2};F_{n}]\leq c_{3}a_{n}^{2}ni^{-(1+2/\alpha)}.

The result then follows from the assumption $a_{n}\sim cn^{1/\alpha}$ .

6.5. Proof of Theorem 1.6

We have shown that almost surely $\nu_{A_{n}-zI_{n}}$ converges weakly to $\nu_{z,\alpha,\theta_{d}}$ and that $\log(\cdot)$ is uniformly integrable in probability with respect to $(\nu_{A_{n}-zI_{n}})_{n\geq 1}$ . Thus by Lemma 1.12, $\mu_{A_{n}}$ converges weakly to some deterministic probability measure $\mu_{\alpha,\theta_{d}}$ in probability.

Appendix A Additional lemmas

A.1. Concentration

Lemma A.1 (McDiarmid’s inequality, Theorem 3.1 in [36]).

Let $X_{1},X_{2},\dots,X_{n}$ be independent random variables taking values in $R_{1},R_{2},\dots,R_{n}$ respectively. Let $F:R_{1}\times\cdots\times R_{n}\rightarrow\mathbb{C}$ be a function with the property that for every $1\leq i\leq n$ there exists a $c_{i}>0$ such that

|F(x_{1},x_{2},\dots,x_{i},\dots,x_{n})-F(x_{1},x_{2},\dots,x_{i}^{\prime},\dots,x_{n})|\leq c_{i}

for all $x_{j}\in R_{j}$ , $x_{i}^{\prime}\in R_{i}$ for $1\leq j\leq n$ . Then for any $t>0$ ,

\mathbb{P}(|F(X)-\mathbb{E}F(X)|\geq\sigma t)\leq C\exp(-ct^{2})

for absolute constants $C,c>0$ and $\sigma^{2}:=\sum_{i=1}^{n}c_{i}^{2}$ .

For the following lemma we need a way of breaking up an elliptic random matrix $X$ into independent pieces. For a matrix $M=(m_{ij})_{i,j=1}^{n}$ we let the $k$ -wedge of $M$ be the $n\times n$ matrix $C_{k}$ with entries $c_{ij}=m_{ij}$ if either $i=k$ and $j\geq i$ or $j=k$ and $i\geq j$ , with $c_{ij}=0$ otherwise. Note

M_{n}=\sum_{k=1}^{n}C_{k},

and $\operatorname{rank}(C_{k})\leq 2$ for all $1\leq k\leq n$ . Recall the total variation norm of a function $f:\mathbb{R}\rightarrow\mathbb{R}$ is given by

\|f\|_{TV}=\sup\sum_{k\in\mathbb{Z}}|f(x_{k+1})-f(x_{k})|,

where the supremum runs over all sequences $(x_{k})_{k\in\mathbb{Z}}$ with $x_{k+1}\geq x_{k}$ .

Lemma A.2.

Let $M$ be a $n\times n$ random matrix with independent wedges. Then for any $f:\mathbb{R}\rightarrow\mathbb{R}$ going to $0$ at $\pm\infty$ with $\|f\|_{TV}\leq 1$ and every $t\geq 0$ ,

\mathbb{P}\left(\left|\int fd\nu_{M}-\mathbb{E}\int fd\nu_{M}\right|\geq t\right)\leq C\exp(-cnt^{2}),

for absolute constants $C,c>0$ .

Proof.

If $A,B\in\operatorname{Mat}_{n}(\mathbb{C})$ let $F_{A}$ and $F_{B}$ be the cumulative distribution functions of $\nu_{A}$ and $\nu_{B}$ . By the Lidskii inequality (see Theorem 3.3.16 in [33]) for singular values

\|F_{A}-F_{B}\|_{\infty}\leq\frac{\operatorname{rank}(A-B)}{n}.

Assume $f$ is smooth. Integrating by parts we get

\left|\int fd\nu_{A}-\int fd\nu_{B}\right|=\left|\int_{\mathbb{R}}f^{\prime}(t)(F_{A}(t)-F_{B}(t))dt\right|\leq\frac{\operatorname{rank}(A-B)}{n}\|f\|_{TV}.

(A.1)

Since $\left|\int fd\nu_{A}-\int fd\nu_{B}\right|$ depends on only finitely many points for any $f$ , we can extend the previous inequality to any function of finite total variation.

Now fix $f:\mathbb{R}\rightarrow\mathbb{R}$ going to $0$ at $\pm\infty$ with $\|f\|_{TV}\leq 1$ . Let $\mathcal{C}_{k}$ be the space of all $k$ -wedges and $F_{f}:\mathcal{C}_{1}\times\mathcal{C}_{2}\times\dots\times\mathcal{C}_{n}$ be the function defined by

F_{f}(C_{1},C_{2},\dots,C_{n})=\int fd\nu_{A}

where $A$ is the matrix with $k$ -wedge $C_{k}$ . By (A.1)

|F_{f}(C_{1},C_{2},\dots,C_{i},\dots,C_{n})-F_{f}(C_{1},C_{2},\dots,C_{i}^{\prime},\dots,C_{n})|\leq\frac{2}{n},

and thus by McDiarmid’s inequality, Lemma A.1, and the definition of $F_{f}$ ,

\mathbb{P}\left(\left|\int fd\nu_{M}-\mathbb{E}\int fd\nu_{M}\right|\geq t\right)\leq C\exp(-cnt^{2}).

∎

A.2. Singular value estimates

Lemma A.3 (See [33], Chapter 3).

If $A$ and $B$ are $n\times n$ complex matrices then

s_{1}(AB)\leq s_{1}(A)s_{1}(B)\text{ and }s_{1}(A+B)\leq s_{1}(A)+s_{1}(B),

\max_{1\leq k\leq n}|s_{k}(A+B)-s_{k}(A)|\leq\|B\|,

s_{i+j-1}(A+B)\leq s_{i}(A)+s_{j}(B)

for $1\leq i,j\leq n$ and $i+j\leq n+1$ . In addition,

\max_{1\leq i\leq n}|s_{i}(A)-s_{i}(B)|\leq s_{1}(A-B).

Lemma A.4 (Tao-Vu Negative Second Moment, [51] Lemma A.4).

If $A$ is a full rank $n^{\prime}\times n$ complex matrix with rows $R_{1},\dots,R_{n^{\prime}}$ and $R_{-i}:=\operatorname{Span}\{R_{j}:j\neq i\}$ , then

\sum_{i=1}^{n^{\prime}}s_{i}(A)^{-2}=\sum_{i=1}^{n^{\prime}}\operatorname{dist}(R_{i},R_{-i})^{-2}.

Lemma A.5 (Cauchy interlacing, see [33]).

Let $A$ be an $n\times n$ complex matrix. If $B$ is an $n^{\prime}\times n$ matrix obtained by deleting $n-n^{\prime}$ rows from $A$ , then for every $1\leq i\leq n^{\prime}$ ,

s_{i}(A)\geq s_{i}(B)\geq s_{i+n-n^{\prime}}(A).

Lemma A.6 (See Remark 1 in [23]).

Let $A$ be an $n\times n$ matrix and let $\operatorname{Re}(A)=(A+A^{*})/2$ denote the real part of $A$ . If $s_{1}\geq s_{2}\geq\dots\geq s_{n}$ and $\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n}$ denote the singular values of $A$ and eigenvalues of $\operatorname{Re}(A)$ respectively, then

\lambda_{j}\leq s_{j}

(A.2)

for every $1\leq j\leq n$ .

Lemma A.7 (Weyl’s inequality, [54], see also Lemma B.5 in [13]).

For every $n\times n$ complex matrix $A$ with eigenvalues ordered as $|\lambda_{1}(A)|\geq|\lambda_{2}(A)|\geq\dots\geq|\lambda_{n}(A)|$ one has

\prod_{i=1}^{k}|\lambda_{i}(A)|\leq\prod_{i=1}^{k}s_{i}(A)\text{ and }\prod_{i=k}^{n}s_{i}(A)\leq\prod_{i=k}^{n}|\lambda_{i}(A)|

for all $1\leq k\leq n$ . Moreover for $r>0$

\sum_{k=1}^{n}|\lambda_{k}(A)|^{r}\leq\sum_{k=1}^{n}s_{k}(A)^{r}.

Lemma A.8 (Schatten Bound, see proof of Theorem 3.32 in [55]).

Let $A$ be an $n\times n$ complex matrix with rows $R_{1},\dots,R_{n}$ . Then for every $0<r\leq 2$ ,

\sum_{i=1}^{n}s_{k}(A)^{r}\leq\sum_{i=1}^{r}\|R_{k}\|^{r}.

A.3. Moments of stable distributions

Lemma A.9 (See [13] and [24] Theorem VIII.9.2).

Let $Z$ be a positive random variable such that for every $t>0$ ,

\mathbb{P}(Z\geq t)=L(t)t^{-\alpha}

for some slowly varying function $L$ and some $\alpha\in(0,2)$ . Then for every $p>\alpha$ ,

\lim\limits_{t\rightarrow\infty}\frac{\mathbb{E}[Z^{p}\mathbf{1}_{\{Z\leq t\}}]}{c(p)L(t)t^{p-\alpha}}\rightarrow 1,

where $c(p):=\alpha/(p-\alpha)$ .

A.4. Proof of Proposition 4.12

From Proposition 4.3 one has

\begin{pmatrix}a(z,\eta)&b(z,\eta)\\ b^{\prime}(z,\eta)&c(z,\eta)\end{pmatrix}=-\left(\begin{pmatrix}\eta&z\\ \bar{z}&\eta\end{pmatrix}+\sum_{k=1}^{\infty}\begin{pmatrix}0&y_{k}^{(1)}\\ \bar{y}_{k}^{(2)}&0\\ \end{pmatrix}\tilde{R}(U)_{kk}\begin{pmatrix}0&y_{k}^{(2)}\\ \bar{y}_{k}^{(1)}&0\\ \end{pmatrix}\right)^{-1}.

We will consider the point process $\{(y_{k}^{(1)},y_{k}^{(2)})\}_{k\geq 1}$ in the polar form $\{(r_{k},w_{k})\}_{k\geq 1}$ where $\{r_{k}\}_{k\geq 1}$ is a Poisson point process with intensity measure $m_{\alpha}$ and $w_{1},w_{2},\dots$ is a collection of independent identically $\theta_{d}$ distributed random variables independent of $\{r_{k}\}_{k\geq 1}$ . We will denote the coordinates of $w_{k}$ by $(w_{k}^{(1)},w_{k}^{(2)})$ . In polar coordinates the recursive equation becomes

\begin{pmatrix}a(z,\eta)&b(z,\eta)\\ b^{\prime}(z,\eta)&c(z,\eta)\end{pmatrix}=-\left(\begin{pmatrix}\eta&z\\ \bar{z}&\eta\end{pmatrix}+\sum_{k=1}^{\infty}r_{k}^{2}\begin{pmatrix}c_{k}(z,\eta)|w^{(1)}_{k}|^{2}&b^{\prime}_{k}(z,\eta)w^{(1)}_{k}w^{(2)}_{k}\\ b_{k}(z,\eta)\bar{w}^{(1)}_{k}\bar{w}^{(2)}_{k}&a_{k}(z,\eta)|w^{(2)}_{k}|^{2}\end{pmatrix}\right)^{-1},

(A.3)

where

\begin{pmatrix}a_{k}(z,\eta)&b_{k}(z,\eta)\\ b^{\prime}_{k}(z,\eta)&c_{k}(z,\eta)\end{pmatrix}:=\tilde{R}(U)_{kk}.

To complete the proof that the matrix in (4.3) satisfies the distributional equation we need the following lemma, which is essentially Theorem 10.3 in [8].

Lemma A.10.

Let $\{r_{k}\}_{k\geq 1}$ be a Poisson point process with intensity measure $m_{\alpha}$ for $\alpha\in(0,2)$ and $v_{1},v_{2},\dots$ be a collection of bounded independent and identically $\nu$ distributed random vectors for some probability measure $\nu$ . Then

\sum_{k=1}^{\infty}r_{k}^{2}v_{k}\overset{d}{=}S,

(A.4)

where $S$ is an $\frac{\alpha}{2}$ -stable random vector with spectral measure $\Gamma_{\nu}$ , where $\Gamma_{\nu}$ is the measure on the unit sphere obtained by the image of the measure $\frac{\Gamma(2-\alpha/2)\cos(\pi\alpha/4)}{1-\alpha/2}\|v\|^{\alpha/2}d\nu(v)$ under the map $v\mapsto\frac{v}{\|v\|}$ .

Proof.

Let $(X_{k})_{k\geq 1}$ be a sequence of i.i.d. non-negative random variables such that

\mathbb{P}(X_{1}\geq u)=\frac{L(u)}{u^{\alpha/2}},

(A.5)

for some slowly varying function $L$ , and define the normalizing constants

b_{n}:=\inf\left\{b:\mathbb{P}(X\geq b)\leq\frac{1}{n}\right\}.

(A.6)

From Theorem 10.3 in [8], $\frac{1}{b_{n}}\sum_{k=1}^{n}X_{k}v_{k}$ converges in distribution to $S$ . It also follows from Proposition 2.3 that

\sum_{k=1}^{n}\delta_{X_{k}v_{k}/b_{n}}\Rightarrow\sum_{k=1}^{\infty}\delta_{r_{k}^{2}v_{k}},

(A.7)

as $n\rightarrow\infty$ . It then follows from the almost sure uniform summability of the sequence $(X_{k})_{k\geq 1}$ that

\frac{1}{b_{n}}\sum_{k=1}^{n}X_{k}v_{k}\Rightarrow\sum_{k=1}^{\infty}r_{k}^{2}v_{k},

(A.8)

as $n\rightarrow\infty$ . ∎

An application of Lemma A.10 to the series in (A.3) gives (4.7).

References

[1] A. Aggarwal, P. Lopatto, and J. Marcinek. Eigenvector statistics of Lévy matrices. The Annals of Probability, 49(4):1778 – 1846, 2021.
[2] A. Aggarwal, P. Lopatto, and H.-T. Yau. GOE statistics for Lévy matrices. Journal of the European Mathematical Society, 23(11):3707–3800, 2021.
[3] D. Aldous and J. M. Steele. The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures, volume 110 of Encyclopaedia of Mathematical Sciences, page 1–72. Springer-Verlag, New York, 2004.
[4] A. Auffinger, G. Ben Arous, and S. Péché. Poisson convergence for the largest eigenvalues of heavy tailed random matrices. Ann. Inst. Henri Poincaré, Probab. Stat., 45(3):589–610, 2009.
[5] A. Auffinger and S. Tang. Extreme eigenvalues of sparse, heavy tailed random matrices. Stochastic Processes and their Applications, 126(11):3310–3330, Nov 2016.
[6] B. Basrak, Y. Cho, J. Heiny, and P. Jung. Extreme eigenvalue statistics of m-dependent heavy-tailed matrices. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 57(4):2100 – 2127, 2021.
[7] S. Belinschi, A. Dembo, and A. Guionnet. Spectral measure of heavy tailed band and covariance random matrices. Communications in Mathematical Physics, 289(3):1023–1055, May 2009.
[8] G. Ben Arous and A. Guionnet. The spectrum of heavy tailed random matrices. Communications in Mathematical Physics, 278(3):715–751, Dec 2007.
[9] F. Benaych-Georges and A. Guionnet. Central limit theorem for eigenvectors of heavy tailed matrices. Electron. J. Probab., 19:27 pp., 2014.
[10] R. Bhatia. Matrix analysis, volume 169 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1997.
[11] G. Biroli, J.-P. Bouchaud, and M. Potters. On the top eigenvalue of heavy-tailed random matrices. Europhysics Letters (EPL), 78(1):10001, Mar 2007.
[12] C. Bordenave, P. Caputo, and D. Chafaï. Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph. The Annals of Probability, 39(4):1544–1590, 2011.
[13] C. Bordenave, P. Caputo, and D. Chafaï. Spectrum of non-Hermitian heavy tailed random matrices. Communications in Mathematical Physics, 307(2):513–560, Oct. 2011.
[14] C. Bordenave, P. Caputo, D. Chafaï, and D. Piras. Spectrum of large random markov chains: Heavy-tailed weights on the oriented complete graph. Random Matrices: Theory and Applications, 06(02):1750006, 2017.
[15] C. Bordenave and D. Chafaï. Around the circular law. Probab. Surveys, 9:1–89, 2012.
[16] C. Bordenave and A. Guionnet. Localization and delocalization of eigenvectors for heavy-tailed random matrices. Probability Theory and Related Fields, 157(3-4):885–953, Jan 2013.
[17] C. Bordenave and A. Guionnet. Delocalization at small energy for heavy-tailed random matrices. Communications in Mathematical Physics, 354(1):115–159, May 2017.
[18] P. Cizeau and J. P. Bouchaud. Theory of Lévy matrices. Phys. Rev. E, 50:1810–1822, Sep 1994.
[19] K. P. Costello. Bilinear and quadratic variants on the Littlewood-Offord problem. Israel Journal of Mathematics, 194(1):359–394, Mar 2013.
[20] K. P. Costello, T. Tao, and V. Vu. Random symmetric matrices are almost surely nonsingular. Duke Math. J., 135(2):395–413, Nov 2006.
[21] Y. Davydov and V. Egorov. On convergence of empirical point processes. Statistics & Probability Letters, 76(17):1836–1844, Nov. 2006.
[22] R. Durrett. Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 4 edition, 2010.
[23] K. Fan and A. J. Hoffman. Some metric inequalities in the space of matrices. Proceedings of the American Mathematical Society, 6(1):111–116, 1955.
[24] W. Feller. An introduction to probability theory and its applications. Vol. II. Second edition. John Wiley & Sons Inc., New York, 1971.
[25] V. Girko. Elliptic law. Theory of Probability & Its Applications, 30(4):677–690, 1986.
[26] V. Girko. The elliptic law: ten years later I. Random Operators and Stochastic Equations, 3(3):257–302, 1995.
[27] F. Götze. Asymptotic expansions for bivariate von Mises functionals. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 50(3):333–355, Jan 1979.
[28] F. Götze, A. Naumov, and A. Tikhomirov. On a generalization of the elliptic law for random matrices. Acta Physica Polonica B, 46(9):1737–1745, 2015.
[29] F. Götze, A. Naumov, and A. Tikhomirov. On minimal singular values of random matrices with correlated entries. Random Matrices: Theory and Applications, 04(02):1550006, 2015.
[30] E. Gudowska-Nowak, A. Jarosz, M. Nowak, and G. Papp. Towards non-hermitian random Lévy matrices. Acta Physica Polonica B, 38, 01 2007.
[31] J. Heiny and J. Yao. Limiting distributions for eigenvalues of sample correlation matrices from heavy-tailed populations. Available at arXiv:2003.03857, 2020.
[32] R. v. d. Hofstad. Random Graphs and Complex Networks, volume 1 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2016.
[33] R. Horn and C. R. Johnson. Topics in matrix analysis. Cambridge University Press.
[34] P. Jung. Lévy-Khintchine random matrices and the poisson weighted infinite skeleton tree. Transactions of the American Mathematical Society, 370, 02 2014.
[35] A. E. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegermann. Smallest singular value of random matrices and geometry of random polytopes. Adv. Math., 195(2):491–523, 2005.
[36] C. McDiarmid. Concentration. In M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, editors, Probabilistic Methods for Algorithmic Discrete Mathematics, Algorithms and Combinatorics. Springer-Verlag, New York, 1998.
[37] C. Monthus. Localization transition in random Lévy matrices: multifractality of eigenvectors in the localized phase and at criticality. Journal of Statistical Mechanics: Theory and Experiment, 2016(9):093304, Sep 2016.
[38] A. Naumov. Elliptic law for real random matrices. Available at arXiv:1201.1639, 2012.
[39] H. H. Nguyen and S. O’Rourke. The elliptic law. International Mathematics Research Notices, 2015(17):7620–7689, Oct 2014.
[40] S. O’Rourke and D. Renfrew. Central limit theorem for linear eigenvalue statistics of elliptic random matrices. Journal of Theoretical Probability, 29(3):1121–1191, Mar 2015.
[41] S. O’Rourke, D. Renfrew, A. Soshnikov, and V. Vu. Products of independent elliptic random matrices. Journal of Statistical Physics, 160(1):89–119, Apr 2015.
[42] M. Reed and B. Simon. Methods of modern mathematical physics, volume 1. Academic Press, 1972.
[43] S. I. Resnick. Extreme Values, Regular Variation and Point Processes. Springer Series in Operations Research and Financial Engineering. Springer-Verlag, New York, 1 edition, 1987.
[44] S. I. Resnick. Heavy-Tailed Phenomemena. Springer Series in Operations Research and Financial Engineering. Springer-Verlag, New York, 1 edition, 2007.
[45] M. Rudelson and R. Vershynin. The Littlewood-Offord problem and invertibility of random matrices. Adv. Math., 218(2):600–633, 2008.
[46] G. Sakovich. A single form for the conditions for attraction to stable laws. Theory of Probability & Its Applications, 1(3):322–325, 1956.
[47] G. Samorodnitsky and M. S. Taqqu. Stable non-gaussian random processes. Stochastic Modeling. Chapman & Hall, New York, NY, 1994.
[48] A. Sidorenko. A correlation inequality for bipartite graphs. Graphs and Combinatorics, 9(2):201–204, Jun 1993.
[49] A. Soshnikov. Poisson statistics for the largest eigenvalues of Wigner random matrices with heavy tails. Electronic Communications in Probability, 9:82–91, 2004.
[50] T. Tao. Topics in random matrix theory, volume 132 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2012.
[51] T. Tao, V. Vu, and M. Krishnapur. Random matrices: Universality of ESDs and the circular law. Ann. Probab., 38(5):2023–2065, 09 2010.
[52] E. Tarquini, G. Biroli, and M. Tarzia. Level statistics and localization transitions of Lévy matrices. Physical Review Letters, 116(1), Jan 2016.
[53] R. Vershynin. Invertibility of symmetric random matrices. Random Structures & Algorithms, 44(2):135–182, 2014.
[54] H. Weyl. Inequalities between the two kinds of eigenvalues of a linear transformation. Proceedings of the National Academy of Sciences, 35(7):408–411, 1949.
[55] X. Zhan. Matrix inequalities, volume 1790 of Lecture Notes in Mathematics. Springer-Verlag, New York, 2002.

$\displaystyle q^{2}$	$\displaystyle:=\sum_{i\in I_{j,k}}\mathbb{E}_{m}\|Z_{i}\|^{2}$
	$\displaystyle=\sum_{i\in I_{j,k}}\left[\|w_{i}\|^{2}\operatorname{Var}_{m}(\xi_{i})+\|w^{\prime}_{i}\|^{2}\operatorname{Var}_{m}(\xi_{i}^{\prime})\right]$	(5.23)
	$\displaystyle\geq\sigma^{2}\sum_{i\in I_{j,k}}\left[\|w_{i}\|^{2}+\|w_{i}^{\prime}\|^{2}\right]$

	$\displaystyle\mathbb{P}_{u,u^{\prime},\pi}$	$\displaystyle\left(\\|(u-u^{\prime})_{\pi^{c}}B^{-1}_{\pi^{c}\times[n-1]}\\|\leq t_{0}\\|B^{-1}\\|_{2}\right)$
		$\displaystyle\qquad\qquad\leq\mathbb{P}_{u,u^{\prime},\pi}\left(\sum_{j=1}^{n-1}\|(u-u^{\prime})_{\pi^{c}}(x_{j})_{\pi^{c}}\|^{2}p_{j}\leq t_{0}^{2}\right)$
		$\displaystyle\qquad\qquad\leq 2\sum_{j=1}^{n-1}p_{j}\mathbb{P}_{u,u^{\prime},\pi}(\|(u-u^{\prime})_{\pi^{c}}(x_{j})_{\pi^{c}}\|^{2}\leq 2t_{0}^{2})$
		$\displaystyle\qquad\qquad\leq 2\sup_{w\in\operatorname{Incomp}(\delta,\tau)}\mathbb{P}_{u,u^{\prime},\pi}(\|(u-u^{\prime})_{\pi^{c}}w_{\pi^{c}}\|\leq\sqrt{2}t_{0})$

	$\displaystyle\mathbb{P}_{v,v^{\prime},\pi}$	$\displaystyle\left(\\|B^{-1}_{[n-1]\times\pi^{c}}(v-v^{\prime})_{\pi^{c}}\\|\leq t_{0}\\|B^{-1}\\|_{2}\right)$
		$\displaystyle\qquad\qquad\leq 2\sum_{j=1}^{n-1}p_{j}\mathbb{P}_{v,v^{\prime},\pi}\left(\|(y_{j})_{\pi^{c}}(v-v^{\prime})_{\pi^{c}}\|\leq\sqrt{2}t_{0}\right)$
		$\displaystyle\qquad\qquad\leq 2\sup_{w\in\operatorname{Incomp}(\delta,\tau)}\mathbb{P}_{v,v^{\prime},\pi}\left(\|w_{\pi^{c}}^{\mathrm{T}}(v-v^{\prime})_{\pi^{c}}\|\leq\sqrt{2}t_{0}\right).$

$\displaystyle\mathbb{P}\left(s_{n}(A)\leq\frac{t}{\sqrt{n}},s_{1}(A)\leq s\right)$	$\displaystyle\leq\mathbb{P}\left(\min_{x\in\mathbb{S}^{n-1}}\\|Ax\\|\leq\frac{t}{\sqrt{n}},s_{1}(A)\leq s\right)$
	$\displaystyle\leq\mathbb{P}\left(\min_{x\in\operatorname{Incomp}(\delta,\tau)}\\|Ax\\|\leq\frac{t}{\sqrt{n}},s_{1}(A)\leq s\right)$	(5.39)
	$\displaystyle\qquad+\mathbb{P}\left(\min_{x\in\operatorname{Comp}(\delta,\tau)}\\|Ax\\|\leq\frac{1}{\sqrt{n}},s_{1}(A)\leq s\right)$

	$\displaystyle\mathbb{E}(\|\operatorname{dist}^{2}(Y,W^{\prime})-S\|^{2}\big{\|}\mathcal{J}=J)$	$\displaystyle=\mathbb{E}\left(\left\|\sum_{k\neq j}Y_{j}P_{jk}\bar{Y}_{k}\right\|^{2}\big{\|}\mathcal{J}=J\right)$
		$\displaystyle\leq\frac{2Ca_{n}^{4}}{n^{2}}\sum_{j,k}\|P_{jk}\|^{2}$
		$\displaystyle=\frac{2Ca_{n}^{4}}{n^{2}}\\|P\\|_{2}^{2}$
		$\displaystyle=\frac{2Ca_{n}^{4}}{n^{2}}\operatorname{tr}(P^{*}P)$
		$\displaystyle=\frac{2Ca_{n}^{4}}{n^{2}}\operatorname{tr}(P).$

Spectrum of Heavy-Tailed Elliptic Random Matrices

Abstract.

1. Introduction

Definition 1.1 (Elliptic Random Matrix).

Theorem 1.2 (Elliptic law for real random matrices, Theorem 1.5 in [39]).

1.1. Matrix distribution

Definition 1.3 (Condition C1).

Definition 1.4 (Condition C2).

1.2. Main results

Theorem 1.5 (Singular values of heavy-tailed elliptic random matrices).

Theorem 1.6 (Eigenvalues of heavy-tailed elliptic random matrices).

Remark 1.7.

1.3. Further questions

Question 1.8.

Question 1.9.

1.4. Outline

1.5. Notation

1.6. Hermitization

Lemma 1.10 (Lemma A.1 in [13]).

Definition 1.11 (Uniform integrability almost surely and in probability).

Lemma 1.12 (Lemma 4.3 in [15]).

1.7. Individual entries and stable random vectors.

Theorem 1.13 (Theorem 2.3.9 in [47]).

Acknowledgment

2. Poisson point processes and stable distributions

2.1. Simple point processes

2.2. Poisson point process

Definition 2.1.

Remark 2.2.

Proposition 2.3.

Remark 2.4.

2.3. Useful properties of 𝐍α\mathbf{N_{\alpha}}

Proposition 2.5.

Lemma 2.6.

3. Bipartized resolvent matrix

3.1. Bipartization of a matrix

Theorem 3.1 (Theorem 2.1 in [13]).

3.2. Bipartization of an operator

Lemma 3.2.

4. Convergence to the Poisson Weighted Infinite Tree

4.1. Operators on a tree

Lemma 4.1 (Lemma A.3 in [12]).

Corollary 4.2 (Corollary 2.4 in [13]).

Proposition 4.3.

4.2. Local operator convergence.

Definition 4.4 (Local Convergence).

Theorem 4.5 (Theorem 2.7 in [13]).

4.3. Poisson Weighted Infinite Tree (PWIT)

Proposition 4.6.

Lemma 4.7.

Proof of Proposition 4.6.

4.4. Local convergence

Theorem 4.8.

Remark 4.9.

4.5. Resolvent matrix

Theorem 4.10.

Proof.

Theorem 4.11.

Proof.

Proposition 4.12.

5. Least singular values of elliptic random matrices

Theorem 5.1 (Least singular value bound).

Remark 5.2.

5.1. Proof of Theorem 5.1

5.2. Nets and a decomposition of the unit sphere

Lemma 5.3 (Incompressible vectors are spread; Lemma A.3 from [15]).

5.3. Control of compressible vectors

Lemma 5.4 (Distance of a random vector to a deterministic subspace).

Proof.

Corollary 5.5.

Proof.

Lemma 5.6 (Control of compressible vectors).

Proof.

Corollary 5.7.

Proof.

Corollary 5.8.

Proof.

5.4. Anti-concentration bounds

Lemma 5.9 (Small ball probability via Berry–Esseen; Lemma A.6 from [15]).

Lemma 5.10.

2.3. Useful properties of $\mathbf{N_{\alpha}}$

5.5.1. Step 1: Constructing a random subset $\pi$

5.5.2. Step 2: Estimating $\|B^{-1}\|_{2}$

6. Singular values of $A_{n}$ and uniform integrability