# Spiked Singular Values and Vectors
under Extreme Aspect Ratios

Michael J<EMAIL_ADDRESS>[ Department of Statistics,
Stanford University,

###### Abstract

The behavior of the leading singular values and vectors of noisy low-rank
matrices is fundamental to many statistical and scientific problems.
Theoretical understanding currently derives from asymptotic analysis under one
of two regimes: classical, with a fixed number of rows, large number of
columns or vice versa; and proportional, with large numbers of rows and
columns, proportional to one another. This paper is concerned with the
disproportional regime, where the matrix is either ‘tall and narrow’ or ‘short
and wide’: we study sequences of matrices of size $n\times m_{n}$ with aspect
ratio $n/m_{n}\rightarrow 0$ or $n/m_{n}\rightarrow\infty$ as
$n\rightarrow\infty$. This regime has important ‘big data’ applications.

Theory derived here shows that the displacement of the empirical singular
values and vectors from their noise-free counterparts and the associated phase
transitions—well-known under proportional growth asymptotics—still occur in
the disproportionate setting. They must be quantified, however, on a novel
scale of measurement that adjusts with the changing aspect ratio as the matrix
size increases. In this setting, the top singular vectors corresponding to the
longer of the two matrix dimensions are asymptotically uncorrelated with the
noise-free signal.

60B20,

random matrix,

singular value,

singular vector,

low-rank,

spiked model,

spiked covariance,

Stieltjes transform,

###### keywords:

[class=MSC2020]

###### keywords:

##  1 Introduction

The low-rank signal-plus-noise model is a simple statistical model of data
with latent low-dimensional structure. Data $\widetilde{X}_{n}$ is the sum of
a low-rank matrix and white noise: where $\theta_{i}\in\mathbb{R}$ are signal
strengths, $u_{i}\in\mathbb{R}^{n}$ and $v_{i}\in\mathbb{R}^{m_{n}}$ are the
left and right signal vectors, and the noise matrix
$X_{n}\in\mathbb{R}^{n\times m_{n}}$ contains independent and identically
distributed (i.i.d.) entries with mean zero and variance one. The noise matrix
is normalized so that rows are asymptotically unit norm.

###  1.1 Proportionate growth asymptotic

Recent work studies this model in the high-dimensional setting where $n$ and
$m_{n}$ are large, in particular, where $n$ and $m_{n}$ are of comparable
magnitude. Such analyses derive limiting behavior of sequences
$\widetilde{X}_{n}$ as

$\phantom{\,,}n\rightarrow\infty,\,\,\,\,\frac{n}{m_{n}}\rightarrow\beta>0\,.$

Here, the parameter $\beta>0$ is the limiting aspect ratio of the data; thus
for $\beta=1$, the matrices are effectively square for all large $n$. Baik and
Silverstein [7] and Paul [21] find the limits of leading eigenvalues in the
spiked covariance model, which is closely related to model (LABEL:model).
Benaych-Georges and Rao Nadakuditi [11] derive asymptotic properties of the
empirical singular value decomposition of $\widetilde{X}_{n}$ (details of
model (LABEL:model) are provided in Section 1.3). Two phenomena arise not
present in classical fixed-$n$ asymptotics:

Leading singular value displacement. The leading singular values of
$\frac{1}{\sqrt{m_{n}}}\widetilde{X}_{n}$ are inconsistent estimators of the
signal strengths. Let
$\tilde{\lambda}_{1}\geq\tilde{\lambda}_{2}\geq\cdots\geq\tilde{\lambda}_{n}$
denote the eigenvalues of
$\widetilde{S}_{n}=\frac{1}{m_{n}}\widetilde{X}_{n}\widetilde{X}_{n}^{\prime}$,
the sample covariance matrix. For fixed $i\geq 1$, the eigenvalues satisfy

$\displaystyle\hskip 56.9055pt\phantom{\,,}\tilde{\lambda}_{i}$
$\displaystyle\xrightarrow{a.s.}\frac{(1+\theta_{i}^{2})(\beta+\theta_{i}^{2})}{\theta_{i}^{2}}\,,$
$\displaystyle i\leq r,\,\theta_{i}>\beta^{1/4}\,,$

and $\tilde{\lambda}_{i}\xrightarrow{a.s.}(1+\sqrt{\beta})^{2}$ otherwise. The
singular values of $\frac{1}{\sqrt{m_{n}}}\widetilde{X}_{n}$ are of course
determined by the eigenvalues of $\widetilde{S}_{n}$, and vice versa. We will
occasionally switch between the two without comment.

Leading singular vector rotation. Let $\tilde{u}_{1},\ldots,\tilde{u}_{n}$ and
$\tilde{v}_{1},\ldots,\tilde{v}_{n}$ denote the left and right singular
vectors of $\widetilde{X}_{n}$. The leading singular vectors
$\tilde{u}_{1},\ldots,\tilde{u}_{r}$ and $\tilde{v}_{1},\ldots,\tilde{v}_{r}$
are inconsistent estimators of the left and right signal vectors. For $1\leq
i\leq r$ and $1\leq j\leq n$,

$\phantom{\,,}\begin{aligned} \hskip 59.75095pt&|\langle
u_{i},\tilde{u}_{j}\rangle|^{2}\xrightarrow{a.s.}1-\frac{\beta(1+\theta_{i}^{2})}{\theta_{i}^{2}(\theta_{i}^{2}+\beta)}\,,\\\
\hskip 28.45274pt&|\langle
v_{i},\tilde{v}_{j}\rangle|^{2}\xrightarrow{a.s.}1-\frac{\beta+\theta_{i}^{2}}{\theta_{i}^{2}(\theta_{i}^{2}+1)}\,,\end{aligned}\qquad\hskip
28.45274pti=j,\,\theta_{i}>\beta^{1/4}\,,$

and $|\langle u_{i},\tilde{u}_{j}\rangle|,|\langle
v_{i},\tilde{v}_{j}\rangle|\xrightarrow{a.s.}0$ otherwise.

###  1.2 Disproportionate growth asymptotic

Contrary to the proportionate growth asymptotic, the dimensions of many large
data matrices are not comparable. For example, [20] demonstrates a genetic
dataset with 3,000 rows (people) and 250,000 columns (genetic measurements)
has low-rank structure. Here the aspect ratio is $\beta\approx 3/250$.

This paper considers asymptotic analysis of the low-rank signal-plus-noise
model as ${\beta_{n}=n/m_{n}\rightarrow 0}$. Transposing $\widetilde{X}_{n}$
if necessary, our results also apply to $\beta_{n}\rightarrow\infty$. A
particular calibration ${\theta_{n}=\tau\cdot\beta_{n}^{1/4}}$ is identified
between signal strength $\theta_{n}$ and $\beta_{n}$ depending on a new
(constant) formal parameter $\tau$. Under this calibration, we rigorously
establish a new set of formulas for the limiting displacement of singular
values and rotation of singular vectors, in explicit terms of the parameter
$\tau$. These new formulas may be heuristically derived by substituting our
expression for $\theta_{n}$ into the Benaych-Georges and Rao Nadakuditi
formulas and taking limits; this means that certain previously unjustified
uses in the disproportionate growth asymptotic are rigorously justifiable.
Many important applications previously made using the Benaych-Georges and Rao
Nadakuditi formulas in the $\beta_{n}\rightarrow\beta>0$ limit may in parallel
fashion now be rigorously made in the $\beta_{n}\rightarrow 0$ setting.
Furthermore, there are new potential uses.

###  1.3 Assumptions and notation

We make the following assumptions:

  * [A1. Noise] The entries of $X_{n}=(X_{i,j}:1\leq i\leq n,1\leq j\leq m)$ are i.i.d. with $\mathbf{E}X_{11}=0$, $\mathbf{E}X_{11}^{2}=1$, and $\mathbf{E}X_{11}^{4}<\infty$.

  * [A2. Signal vectors] The signal rank $r$ is fixed. $G_{u}^{n},G_{v}^{n}$ are matrices of size $n\times r$ and $m_{n}\times r$ respectively, containing i.i.d. entries with mean zero, variance one, and finite eighth moment. $G_{u}^{n}$ and $G_{v}^{n}$ are independent of one another and $X_{n}$. The signal vectors $u_{i}$ and $v_{i}$ denote the $i$-th column of $U_{n}=\frac{1}{\sqrt{n}}G_{u}^{n}$ and $V_{m}=\frac{1}{\sqrt{m_{n}}}G_{v}^{n}$, respectively.

  * [A3. Signal Strength] The signal strengths $\theta_{i}=\theta_{i,n}$ obey

$\theta_{i}=\tau_{i}\beta_{n}^{1/4}(1+\varepsilon_{i,n})$

for distinct constants $\tau_{1}>\ldots>\tau_{r}\geq 0$ and (nonrandom)
sequences $\varepsilon_{i,n}\rightarrow 0$.

Alternatively, A1 and A2 may be replaced with

  * [B1. Noise] The entries of $X_{n}=(X_{i,j}:1\leq i\leq n,1\leq j\leq m)$ are independent standard Gaussians.

  * [B2. Signal vectors] The signal rank $r$ is fixed. $U_{n}$ and $V_{m}$ are orthogonal matrices independent of $X_{n}$ with respective sizes $n\times r$ and $m_{n}\times r$.

In this paper, “almost surely eventually” means with probability one, a
sequence of events indexed by $n$ occurs for all sufficiently large $n$. The
notation $a_{n}\lesssim b_{n}$ means eventually $a_{n}\leq Cb_{n}$ for some
universal constant $C$; $a_{n}\asymp b_{n}$ means $b_{n}\lesssim a_{n}\lesssim
b_{n}$; and $a_{n}=O(b_{n})$ means $|a_{n}|\lesssim b_{n}$. For a parameter
$\ell$, $a_{n}\lesssim_{\ell}b_{n}$ means $a_{n}\leq C(\ell)b_{n}$.

###  1.4 Results

The formal parameter $\tau$ introduced above describes the signal strength on
a more refined scale of analysis. On this new scale, a phase transition occurs
at $\tau=1$. While for $\tau<1$, both left and right singular vectors are
asymptotically uncorrelated with the underlying signal vectors, it will be
shown that for $\tau>1$, the empirical left singular vectors correlate with
left signal vectors. Let $i_{0}=\max_{1\leq i\leq r}\\{\tau_{i}>1\\}$.

######  Theorem 1.1.

Consider a sequence of matrices $\widetilde{X}_{n}$ following model
(LABEL:model) with $\beta_{n}\rightarrow 0$. Then,

$\displaystyle\hskip
56.9055pt\frac{\tilde{\lambda}_{i}-1}{\sqrt{\beta_{n}}}\xrightarrow{a.s.}\tau_{i}^{2}+\frac{1}{\tau_{i}^{2}}\,,$
$\displaystyle i\leq i_{0}\,.$ (1.1) For any fixed $i>i_{0}$,
$\displaystyle\hskip
56.9055pt\frac{\tilde{\lambda}_{i}-1}{2\sqrt{\beta_{n}}}\xrightarrow{a.s.}1\,.$
(1.2)

Specifically, for $i\leq i_{0}$, define

$\displaystyle\phantom{\,.}\bar{\lambda}_{i}=\frac{(1+\theta_{i}^{2})(\beta_{n}+\theta_{i}^{2})}{\theta_{i}^{2}}=1+(\tau_{i}^{2}+\tau_{i}^{-2})\sqrt{\beta_{n}}+\beta_{n}\,.$
(1.3)

For any $\ell<1/4$, almost surely,

$\displaystyle\phantom{\,.}|\tilde{\lambda}_{i}-\bar{\lambda}_{i}|\lesssim(n^{-\ell}+|\varepsilon_{i,n}|)\sqrt{\beta_{n}}\,.$
(1.4)

######  Theorem 1.2.

For $1\leq i,j\leq i_{0}$,

$\phantom{\,,}\begin{aligned} \hskip
28.45274pt&|\langle\tilde{u}_{i},u_{j}\rangle|\xrightarrow{a.s.}\delta_{ij}\cdot
c(\tau_{i})\,,\\\ \hskip
28.45274pt&|\langle\tilde{v}_{i},v_{j}\rangle|\xrightarrow{a.s.}0\,,\end{aligned}$
(1.5)

where the cosine function is given by

$\displaystyle\phantom{\,.}c(\tau)=\begin{cases}\sqrt{1-\tau^{-4}}&\tau>1\\\
0&\tau\leq 1\end{cases}\,.$ (1.6)

Specifically, for $j\neq i$ and any $\ell<1/8$, almost surely,

$\displaystyle|\langle\tilde{u}_{i},u_{i}\rangle|=c(\tau_{i})+O(n^{-\ell}+|\varepsilon_{i,n}|+\sqrt{\beta_{n}})\,,$
$\displaystyle|\langle\tilde{u}_{i},u_{j}\rangle|\lesssim n^{-2\ell}\,,$ (1.7)
$\displaystyle|\langle\tilde{v}_{i},v_{i}\rangle|\lesssim\beta_{n}^{1/4}\,,$
$\displaystyle|\langle\tilde{v}_{i},v_{j}\rangle|\lesssim
n^{-2\ell}\beta_{n}^{1/4}\,.$ (1.8)

Let $S_{n}=\frac{1}{m_{n}}X_{n}X_{n}^{\prime}$ be the sample covariance matrix
of noise. Let $F_{n}$ denote the empirical spectral distribution (ESD) of
$S_{n}$ and $\mkern 1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{n}$
the Marchenko-Pasteur law with parameter $\beta_{n}$. $s_{n}(z)$ and
$\bar{s}_{n}(z)$ will denote the corresponding Stieltjes transforms. The proof
of Theorems 1.1 and 1.2 requires results on the convergence rates of
$s_{n}(z)$ to $\bar{s}_{n}(z)$ and the corresponding derivatives, stated
below. Proof of these bounds and a discussion of their novel aspects appears
in Section 5.

######  Theorem 1.3.

Let $\eta>0$ and $u_{n}\geq 1+(2+\eta)\sqrt{\beta_{n}}$ be a bounded sequence.
For any $\ell<1/4$, almost surely,

$\displaystyle\phantom{\,.}\sup_{|z-u_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\,|s_{n}(z)-\bar{s}_{n}(z)|\lesssim
n^{-\ell}\beta_{n}^{-1/2}\,.$ (1.9)

######  Corollary 1.3.1.

Let $\eta>0$ and $u_{n}\geq 1+(2+\eta)\sqrt{\beta_{n}}$ be a bounded sequence.
For any $\ell<1/8$, almost surely,

$\displaystyle\phantom{\,.}\sup_{|z-u_{n}|\leq
n^{-1/8}\sqrt{\beta_{n}}}\,\Big{|}\frac{d}{dz}\big{(}s_{n}(z)-\bar{s}_{n}(z)\big{)}\Big{|}\lesssim
n^{-\ell}\beta_{n}^{-1}\,.$ (1.10)

###  1.5 Acknowledgements

The author is grateful to David Donoho for continuous encouragement, helpful
conversations, and very detailed comments on drafts of this paper. This work
was partially supported by NSF DMS grants 1407813, 1418362, and 1811614.

##  2 Preliminaries

###  2.1 Overview

This section reviews the framework developed in Benaych-Georges and Rao
Nadakuditi’s work [10, 11] addressing the $\beta_{n}\rightarrow\beta>0$
setting, followed by a discussion of adaptations required to study the
$\beta_{n}\rightarrow 0$ setting. We assume $\varepsilon_{i,n}=0$, meaning
$\theta_{i}=\tau_{i}\beta_{n}^{1/4}$. The Stieltjes transforms of the ESD of
$S_{n}$ and the Marchenko-Pasteur law with parameter $\beta_{n}$, introduced
in Section 1.4, are defined as follows:

$\displaystyle\phantom{\,,}s_{n}(z)$
$\displaystyle=\int\frac{1}{\lambda-z}dF_{n}(\lambda)=\frac{1}{n}\mathrm{tr}(S_{n}-zI_{n})^{-1}\,,$
$\displaystyle\phantom{\,.}\bar{s}_{n}(z)$
$\displaystyle=\int\frac{1}{\lambda-z}d\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern
1.5mu_{n}(\lambda)=\frac{1-\beta_{n}-z+\sqrt{(1-\beta_{n}-z)^{2}-4\beta_{n}}}{2\beta_{n}z}\,,$
(2.1)

defined for $z$ outside the support of $F_{n},\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{n}$.

Let $\Theta_{n}=\text{diag}(\theta_{1},\ldots,\theta_{r})$. Recall that
$U_{n}$ and $V_{m}$, defined in Section 1.3, contain as columns the left and
right signal vectors. The following $2r\times 2r$ matrices will be the central
objects of study, providing insight into the spectral decomposition of
$\widetilde{S}_{n}$:

$\displaystyle\widetilde{M}_{n}(z)$
$\displaystyle=\begin{bmatrix}\sqrt{z}U_{n}^{\prime}(S_{n}-zI_{n})^{-1}U_{n}&\frac{1}{\sqrt{m}}U_{n}^{\prime}(S_{n}-zI_{n})^{-1}X_{n}V_{m}+\Theta_{n}^{-1}\\\
\frac{1}{\sqrt{m}}V_{m}^{\prime}X_{n}^{\prime}(S_{n}-zI_{n})^{-1}U_{n}+\Theta_{n}^{-1}&\sqrt{z}V_{m}^{\prime}(\frac{1}{m}X_{n}^{\prime}X_{n}-zI_{m})^{-1}V_{m}\end{bmatrix}\,,$
(2.2) $\displaystyle M_{n}(z)$
$\displaystyle=\begin{bmatrix}\sqrt{z}s_{n}(z)I_{r}&\Theta_{n}^{-1}\\\
\Theta_{n}^{-1}&\big{(}\beta_{n}\sqrt{z}s_{n}(z)-\frac{1-\beta_{n}}{\sqrt{z}}\big{)}I_{r}\end{bmatrix}\,,$
(2.3) $\displaystyle\mkern 1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu_{n}(z)$
$\displaystyle=\begin{bmatrix}\sqrt{z}\bar{s}_{n}(z)I_{r}&\Theta_{n}^{-1}\\\
\Theta_{n}^{-1}&\big{(}\beta_{n}\sqrt{z}\bar{s}_{n}(z)-\frac{1-\beta_{n}}{\sqrt{z}}\big{)}I_{r}\end{bmatrix}\,.$
(2.4)

Pivotal to their utility is this essential observation from [11]:

######  Lemma 2.1.

(Lemma 4.1 of [11]) The eigenvalues of $\widetilde{S}_{n}$ that are not
eigenvalues of $S_{n}$ are the real values $z$ such $\widetilde{M}_{n}(z)$ is
non-invertible.

Lemma 2.1 focuses the study of the leading eigenvalues of
$\widetilde{S}_{n}$—those resulting from the signal component of
$\widetilde{X}_{n}$—away from the increasing-dimensional sequence
$\widetilde{S}_{n}$ to the fixed-dimensional sequence $\widetilde{M}_{n}$ and
its associates, $M_{n}$ and $\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}$. The roots of
$\det\widetilde{M}_{n}(z)$ will be shown to localize near the roots of
$\det\mkern 1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)$.
Using the closed form (2.1) of the Stieltjes transform $\bar{s}_{n}$,
$\det\mkern 1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}$ has
explicitly known roots. As [11] shows, these roots are precisely
$\bar{\lambda}_{1},\ldots,\bar{\lambda}_{i_{0}}$, introduced in Section 1.4:

######  Lemma 2.2.

(Section 3.1 of [11]) Define

$\displaystyle\phantom{\,.}\mkern
1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern 1.5mu_{n}(z)$
$\displaystyle=\sqrt{z}\bar{s}_{n}(z)\Big{(}\beta_{n}\sqrt{z}\bar{s}_{n}(z)-\frac{1-\beta_{n}}{\sqrt{z}}\Big{)}$
$\displaystyle=-\frac{1+\beta_{n}-z+\sqrt{(1+\beta_{n}-z)^{2}-4\beta_{n}}}{2\beta_{n}}\,.$
(2.5)

As the blocks of $\mkern 1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu_{n}(z)$ commute,

$\displaystyle\phantom{\,.}\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)=\det(\mkern
1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu_{n}(z)I_{r}-\Theta_{n}^{-2})=\prod_{i=1}^{r}(\mkern
1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu_{n}(z)-\theta_{i}^{-2})\,.$ (2.6)

On the real axis, $\mkern 1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu_{n}(z)$ maps $\big{(}(1+\sqrt{\beta_{n}})^{2},\infty)$ in a one-to-one
fashion onto $(0,\beta_{n}^{-1/2})$. The compositional inverse
$D_{n}^{(-1)}(t)$ exists on the real interval $(0,\beta_{n}^{-1/2})$ and is
given in closed form by

$\displaystyle D_{n}^{(-1)}(t)=\frac{(t+1)(\beta_{n}t+1)}{t}\,,$
$\displaystyle 0<t<\beta_{n}^{-1/2}\,.$ (2.7)

Thus, $\bar{\lambda}_{i}=\mkern
1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu_{n}^{(-1)}(\theta_{i}^{-2})$ is a root of $\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)$ provided that
$\theta_{i}^{-2}<\beta_{n}^{-1/2}$, or $i\leq i_{0}$.

The singular vectors of $\widetilde{X}_{n}$ are related to $U_{n}$ and $V_{m}$
via the next lemma.

######  Lemma 2.3.

(Lemma 5.1 of [11]) Let $\tilde{\sigma}=\sqrt{\tilde{\lambda}}$ be a singular
value of $\frac{1}{\sqrt{m}}\widetilde{X}_{n}$ that is not a singular value of
$\frac{1}{\sqrt{m}}X_{n}$ and let $\tilde{u},\tilde{v}$ be a corresponding
pair of singular unit vectors. Then the column vector

$\displaystyle\begin{bmatrix}\Theta V_{m}^{\prime}\tilde{v}\\\ \Theta
U_{n}^{\prime}\tilde{u}\end{bmatrix}\hskip 199.16928pt$

belongs to the kernel of $\widetilde{M}_{n}(\tilde{\lambda})$. Moreover, for
$P_{n}=\sum_{i=1}^{r}\theta_{i}u_{i}v_{i}^{\prime}$,

$\displaystyle\phantom{\,.}1$
$\displaystyle=\tilde{\lambda}\tilde{v}^{\prime}P_{n}^{\prime}(S_{n}-\tilde{\lambda}I_{n})^{-2}P_{n}\tilde{v}+\frac{1}{m}\tilde{u}^{\prime}P_{n}X_{n}^{\prime}(S_{n}-\tilde{\lambda}I_{n})^{-2}X_{n}P_{n}^{\prime}\tilde{u}$
$\displaystyle+\frac{\tilde{\sigma}}{\sqrt{m}}\tilde{u}^{\prime}P_{n}X_{n}^{\prime}(S_{n}-\tilde{\lambda}I_{n})^{-2}P_{n}\tilde{v}+\frac{\tilde{\sigma}}{\sqrt{m}}\tilde{v}^{\prime}P_{n}^{\prime}(S_{n}-\tilde{\lambda}I_{n})^{-2}X_{n}P_{n}^{\prime}\tilde{u}\,.$
(2.8)

The results quoted above lie at the heart of the strategy for the
proportionate growth asymptotic carried out by Benaych-Georges and Rao
Nadakuditi [10, 11]. That strategy is able to employ convenient convergence
arguments. Indeed, as $\beta_{n}\rightarrow\beta>0$, almost surely, the ESD of
noise eigenvalues $F_{n}$ converges weakly to $\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{\beta}$, the Marchenko-
Pastur law with parameter $\beta$. Moreover, the top noise eigenvalue
$\lambda_{1}\xrightarrow{a.s.}(1+\sqrt{\beta})^{2}$, the upper bulk edge, i.e.
the upper endpoint of the support of $\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{\beta}$. Let $[a,b]$ be
a compact interval outside the bulk, having $(1+\sqrt{\beta})^{2}<a$. By the
Arzela-Ascoli theorem, the empirical Stieltjes transform of the noise
eigenvalues $s_{n}(z)$ converges uniformly on $[a,b]$ to $\bar{s}_{\beta}(z)$,
the Stieltjes transform of $\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{\beta}$. The
implications of this key observation include the uniform convergence of
$M_{n}(z)$ to a non-random matrix $\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{\beta}(z)$ (the
fixed-$\beta$ analog of $\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)$). From the
uniform convergence of $M_{n}(z)$, the convergence of the roots of $\det
M_{n}(z)$ to those of $\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{\beta}(z)$ may be
established.

Now, consider the disproportionate growth asymptotic. The convergences which
were previously so helpful as $\beta_{n}\rightarrow\beta>0$ are not useful as
$\beta_{n}\rightarrow 0$. The limits of $F_{n}$ and $\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)$ are degenerate,
as all noise eigenvalues converge to one. The upper edge of the support of
$F_{n}$ lies approximately at $(1+\sqrt{\beta_{n}})^{2}$. Theorem 1.1 tells us
the leading eigenvalues of $\widetilde{S}_{n}$ may still emerge from the bulk,
but only by a multiple of $\sqrt{\beta_{n}}$. The phenomena of interest are no
longer made visible by taking limits, but must be captured by detailed
finite-$n$ analysis. This will require bounds on the convergence rate of
$s_{n}(z)$ to $\bar{s}_{n}(z)$, developed in Section 5, as well as careful
tracking of the precise size of remainders, where previously it sufficed to
know that such remainders tended to zero. The proof of Theorem 1.1 is a
refinement of the proofs of Theorem 2.9 of [11] and Lemma 6.1 of [10]. The
proof of Theorem 1.2 is a refinement of Theorem 2.10 of [11].

###  2.2 Preliminary lemmas

This section contains lemmas used in the proof of both Theorem 1.1 and 1.2.
Let $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$ denote the
eigenvalues of $S_{n}=\frac{1}{m}X_{n}X_{n}^{\prime}$. In light of the
preceding discussion, particularly, Lemma 2.1, we require
$\bar{\lambda}_{1},\ldots,\bar{\lambda}_{i_{0}}$ to emerge from the bulk
spectrum of $S_{n}$. Indeed, by Lemma 6.1, for any $\eta>0$, almost surely
eventually,

$\displaystyle\phantom{\,.}\lambda_{1}\leq 1+(2+\eta/2)\sqrt{\beta_{n}}\,.$
(2.9)

Furthermore, we will argue using Lemma 6.2 that (2.9) occurs with high
probability. Without loss of generality, we may assume the entries of $X_{n}$
truncated and normalized in accordance with Lemma 6.2. By Lemma 6.3,
truncation and normalization perturbs the eigenvalues of $\widetilde{S}_{n}$
by at most $C\sqrt{\beta_{n}}/n$, a negligible amount compared to the rate
claimed in Theorem 1.1. An immediate consequence of Theorem 1.1 is separation
of the leading eigenvalues of $\widetilde{S}_{n}$:
$\tilde{\lambda}_{i}-\tilde{\lambda}_{i+1}\asymp\sqrt{\beta_{n}}$, $i\leq
i_{0}$. Hence, by Lemma 6.4, truncation and normalization of the entries of
$X_{n}$ perturbs $|\langle u_{i},\tilde{u}_{j}\rangle|$ and $|\langle
v_{i},\tilde{v}_{j}\rangle|$ by at most $C/n$. This is insignificant compared
to the convergence rate in Theorem 1.2.

The following lemma bounds $s_{n}(z)$ and $\bar{s}_{n}(z)$ on a region
containing $\bar{\lambda}_{1},\ldots,\bar{\lambda}_{i_{0}}$. The first point
is a standard result. See, for example, Lemma $8.17$ of [5]. The second point
relies on the location of $\lambda_{1}$.

######  Lemma 2.4.

Let $\eta>0$ and $\mathcal{Z}_{\eta,n}=\\{z:\Re(z)\geq
1+(2+\eta)\sqrt{\beta_{n}}\\}$. Almost surely,

$\displaystyle\sup_{z\in\mathcal{Z}_{\eta,n}}\,|\bar{s}_{n}(z)|\lesssim\beta_{n}^{-1/2}\,,$
$\displaystyle\sup_{z\in\mathcal{Z}_{\eta,n}}\,\Big{|}\frac{d}{dz}\bar{s}_{n}(z)\Big{|}\lesssim\beta_{n}^{-1}\,.$

Furthermore, almost surely,

$\displaystyle\sup_{z\in\mathcal{Z}_{\eta,n}}\,|s_{n}(z)|\lesssim\beta_{n}^{-1/2}\,,$
$\displaystyle\sup_{z\in\mathcal{Z}_{\eta,n}}\,\Big{|}\frac{d}{dz}s_{n}(z)\Big{|}\lesssim\beta_{n}^{-1}\,.$

The implied coefficients depend on $\eta$ only.

###### Proof.

As the upper edge of the support of the Marchenko-Pasteur law lies at
$(1+\sqrt{\beta_{n}})^{2}$,

$\displaystyle\phantom{\,.}\inf_{z\in\mathcal{Z}_{\eta,n}}\inf_{\lambda\in\text{supp}\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern
1.5mu_{n}}|\lambda-z|\gtrsim\sqrt{\beta_{n}}\,,$
$\displaystyle\inf_{z\in\mathcal{Z}_{\eta,n}}\inf_{\lambda\in\text{supp}\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern
1.5mu_{n}}|\lambda-z|^{2}\gtrsim\beta_{n}\,.$ (2.10)

The first claims of the lemma now follow from the integral representations

$\displaystyle\phantom{\,.}\bar{s}_{n}(z)=\int\frac{1}{\lambda-z}d\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{n}(\lambda)\,,$
$\displaystyle\frac{d}{dz}\bar{s}_{n}(z)=-\int\frac{1}{(\lambda-z)^{2}}d\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{n}(\lambda)\,.$

By (2.9), almost surely eventually,

$\displaystyle\phantom{\,.}\inf_{z\in\mathcal{Z}_{\eta,n}}\min_{1\leq\alpha\leq
n}|\lambda_{\alpha}-z|\geq\frac{\eta\sqrt{\beta_{n}}}{2}\,,$
$\displaystyle\inf_{z\in\mathcal{Z}_{\eta,n}}\min_{1\leq\alpha\leq
n}|\lambda_{\alpha}-z|^{2}\geq\frac{\eta^{2}\beta_{n}}{4}\,.$ (2.11)

Together with

$\displaystyle
s_{n}(z)=\frac{1}{n}\sum_{\alpha=1}^{n}\frac{1}{\lambda_{\alpha}-z}\,,$
$\displaystyle\frac{d}{dz}s_{n}(z)=-\frac{1}{n}\sum_{\alpha=1}^{n}\frac{1}{(\lambda_{\alpha}-z)^{2}}\,,$

we obtain the second group of claims. ∎

$M_{n}(z)$ and $\frac{d}{dz}M_{n}(z)$ are the matrices of the entrywise
conditional expectations of $\widetilde{M}_{n}(z)$ and
$\frac{d}{dz}\widetilde{M}_{n}(z)$ given $X_{n}$ (under assumptions A1, A2).
The following lemmas bound the deviation of $\widetilde{M}_{n}(z)$ and
$\frac{d}{dz}\widetilde{M}_{n}(z)$ from their conditional means.

######  Lemma 2.5.

Let $a_{n}\geq 1+(2+\eta)\sqrt{\beta_{n}}$ be a bounded sequence. For any
$\ell<1/4$ and $1\leq i,j\leq r$, almost surely,

$\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\,\big{|}(\widetilde{M}_{n}(z)-M_{n}(z))_{i,j}\big{|}\lesssim
n^{-\ell}\beta_{n}^{-1/2}\,,$ (2.12) $\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\,\big{|}(\widetilde{M}_{n}(z)-M_{n}(z))_{i,j+r}\big{|}\lesssim
n^{-\ell}\,,$ (2.13) $\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\,\big{|}(\widetilde{M}_{n}(z)-M_{n}(z))_{i+r,j+r}\big{|}\lesssim
n^{-\ell}\sqrt{\beta_{n}}\,.$ (2.14)

###### Proof.

The argument is presented under assumptions A1, A2 for the diagonal of
$\widetilde{M}_{n}(z)-M_{n}(z)$ only; the off-diagonal argument or argument
assuming B1, B2 is similar and omitted. Consider $z$ satisfying $|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}$ and $z^{\prime}=a_{n}+in^{-1/4}\sqrt{\beta_{n}}$. We
will decompose $\widetilde{M}_{n}(z)-M_{n}(z)$ as

$\displaystyle\widetilde{M}_{n}(z)-M_{n}(z)$
$\displaystyle=\big{(}\widetilde{M}_{n}(z)-\widetilde{M}_{n}(z^{\prime})\big{)}+\big{(}\widetilde{M}_{n}(z^{\prime})-M_{n}(z^{\prime})\big{)}+\big{(}M_{n}(z^{\prime})-M_{n}(z)\big{)}$

and bound (the diagonal entries of) each term.

Relation (2.12): the upper left block. For $1\leq\alpha\leq n$, by the almost-
sure eventual spacing bound (2.11) and $|z-z^{\prime}|\leq
2n^{-1/4}\sqrt{\beta_{n}}$,

$\displaystyle\phantom{\,.}\bigg{|}\frac{1}{\lambda_{\alpha}-z}-\frac{1}{\lambda_{\alpha}-z^{\prime}}\bigg{|}=\frac{|z-z^{\prime}|}{|\lambda_{\alpha}-z||\lambda_{\alpha}-z^{\prime}|}\leq\frac{8}{\eta^{2}n^{1/4}\sqrt{\beta_{n}}}\,.$
(2.15)

Hence, almost surely,

$\displaystyle\big{|}\mfrac{1}{\sqrt{z}}\big{(}\widetilde{M}_{n}(z)-\widetilde{M}_{n}(z^{\prime})\big{)}_{i,i}\big{|}$
$\displaystyle=\big{|}u_{i}^{\prime}(S_{n}-zI_{n})^{-1}u_{i}-u_{i}(S_{n}-z^{\prime}I_{n})^{-1}u_{i}\big{|}$
$\displaystyle\leq\|u_{i}\|_{2}^{2}\,\lambda_{max}\big{(}(S_{n}-zI_{n})^{-1}-(S_{n}-z^{\prime}I_{n})^{-1}\big{)}$
$\displaystyle=\|u_{i}\|_{2}^{2}\bigg{|}\frac{1}{\lambda_{1}-z}-\frac{1}{\lambda_{1}-z^{\prime}}\bigg{|}$
$\displaystyle\lesssim\frac{1}{n^{1/4}\sqrt{\beta_{n}}}\,,$ (2.16)
$\displaystyle\big{|}\mfrac{1}{\sqrt{z}}\big{(}M_{n}(z)-M_{n}(z^{\prime})\big{)}_{i,i}\big{|}$
$\displaystyle=|s_{n}(z)-s_{n}(z^{\prime})|$
$\displaystyle\leq\frac{1}{n}\sum_{\alpha=1}^{n}\bigg{|}\frac{1}{\lambda_{\alpha}-z}-\frac{1}{\lambda_{\alpha}-z^{\prime}}\bigg{|}$
$\displaystyle\lesssim\frac{1}{n^{1/4}\sqrt{\beta_{n}}}\,.$ (2.17)

Next, consider $\widetilde{M}_{n}(z^{\prime})-M_{n}(z^{\prime})$. Applying
Lemma 6.6 conditional on $X_{n}$,

$\displaystyle\phantom{\,,}\mathbf{E}|u_{i}^{\prime}(S_{n}-z^{\prime}I_{n})^{-1}u_{i}-s_{n}(z^{\prime})|^{4}\lesssim$
$\displaystyle\,\frac{1}{n^{4}}\mathbf{E}|\mathrm{tr}(S_{n}-z^{\prime}I_{n})^{-1}(S_{n}-\bar{z}^{\prime}I_{n})^{-1}|^{2}$
$\displaystyle+$
$\displaystyle\,\frac{1}{n^{4}}\mathbf{E}\mathrm{tr}\big{(}(S_{n}-z^{\prime}I_{n})^{-1}(S_{n}-\bar{z}^{\prime}I_{n})^{-1}\big{)}^{2}$
$\displaystyle\leq$
$\displaystyle\,\frac{2}{n^{4}}\mathbf{E}\bigg{(}\sum_{\alpha=1}^{n}\frac{1}{|\lambda_{\alpha}-z^{\prime}|^{2}}\bigg{)}^{2}\,.$

By Lemma 6.2,

$\displaystyle\phantom{\,.}\mathbf{P}(\lambda_{1}\geq
1+(2+\eta/2)\sqrt{\beta_{n}})\lesssim\frac{1}{n}\,.$ (2.18)

On this event, $|\lambda_{\alpha}-z^{\prime}|^{2}\geq\beta_{n}$, while with
probability one, $|\lambda_{\alpha}-z^{\prime}|^{2}\geq\Im(z^{\prime})$:

$\displaystyle\phantom{\,,}\mathbf{E}|u_{i}^{\prime}(S_{n}-z^{\prime}I_{n})^{-1}u_{i}-s_{n}(z^{\prime})|^{4}\lesssim$
$\displaystyle\,\frac{1}{n^{4}}\Big{(}\frac{n^{2}}{\beta_{n}^{2}}+\frac{n}{\Im(z^{\prime})^{2}}\Big{)}\,.$

This yields the tail probability bound

$\displaystyle\mathbf{P}\big{(}|u_{i}^{\prime}(S_{n}-z^{\prime}I_{n})^{-1}u_{i}-s_{n}(z^{\prime})|\geq
n^{-\ell}\beta_{n}^{-1/2}\big{)}$ $\displaystyle\leq
n^{4\ell}\beta_{n}^{2}\mathbf{E}|u_{i}^{\prime}(S_{n}-z^{\prime}I_{n})^{-1}u_{i}-s_{n}(z^{\prime})|^{4}$
$\displaystyle\lesssim\frac{1}{n^{2-4\ell}}\,,$

which is summable. Thus,

$\displaystyle\phantom{\,,}\big{|}\mfrac{1}{\sqrt{z^{\prime}}}\big{(}\widetilde{M}_{n}(z^{\prime})-M_{n}(z^{\prime})\big{)}_{i,i}\big{|}$
$\displaystyle\lesssim\frac{1}{n^{\ell}\sqrt{\beta_{n}}}\,,$ (2.19)

almost surely. (2.12) follows from (2.16) - (2.19) and
$|\sqrt{z^{\prime}/z}|\leq 2$.

Relation (2.14): the lower right block. Let
$\breve{S}_{n}=\frac{1}{m}X_{n}^{\prime}X_{n}$ denote the “companion” matrix
to $S_{n}$, so-called because the eigenvalues of $\breve{S}_{n}$ are the $n$
(possibly repeated) eigenvalues of $S_{n}$ joined by a zero eigenvalue with
multiplicity $m-n$. Let $W$ be an orthogonal matrix such that
$W^{\prime}\breve{S}_{n}W$ is diagonal. By Lemma 6.10, we have an almost-sure
bound on the magnitude of the component of $v_{i}$ orthogonal to the nullspace
of $\breve{S}_{n}$:

$\displaystyle\phantom{\,.}\|(W^{\prime}v_{i})_{1:n}\|_{2}^{2}\lesssim\beta_{n}\log(n)\,.$
(2.20)

Consider first $\widetilde{M}_{n}(z)-\widetilde{M}_{n}(z^{\prime})$.

$\displaystyle\big{|}\mfrac{1}{\sqrt{z}}\big{(}\widetilde{M}_{n}(z)-\widetilde{M}_{n}(z^{\prime})\big{)}_{i+r,i+r}\big{|}$
$\displaystyle=\big{|}v_{i}^{\prime}\big{(}(\breve{S}_{n}-zI_{m})^{-1}-(\breve{S}_{n}-z^{\prime}I_{m})^{-1}\big{)}v_{i}\big{|}$
$\displaystyle\leq\sum_{\alpha=1}^{n}(W^{\prime}v_{i})_{\alpha}^{2}\bigg{|}\frac{1}{\lambda_{\alpha}-z}-\frac{1}{\lambda_{\alpha}-z^{\prime}}\bigg{|}+\sum_{\alpha=n+1}^{m}(W^{\prime}v_{i})^{2}_{\alpha}\bigg{|}\frac{1}{z}-\frac{1}{z^{\prime}}\bigg{|}$
$\displaystyle\leq\|(W^{\prime}v_{i})_{1:n}\|_{2}^{2}\bigg{|}\frac{1}{\lambda_{1}-z}-\frac{1}{\lambda_{1}-z^{\prime}}\bigg{|}+\|(W^{\prime}v_{i})_{n+1:m}\|_{2}^{2}\bigg{|}\frac{1}{z}-\frac{1}{z^{\prime}}\bigg{|}\,.$

We bound the first term above using (2.15) and (2.20). For the second term,
$|z-z^{\prime}|\leq 2n^{-1/4}\beta_{n}$ and $|z|,|z^{\prime}|\geq 1$: almost
surely,

$\displaystyle\big{|}\mfrac{1}{\sqrt{z}}\big{(}\widetilde{M}_{n}(z)-\widetilde{M}_{n}(z^{\prime})\big{)}_{i+r,i+r}\big{|}\lesssim\frac{\sqrt{\beta_{n}}}{n^{\ell}}\,.$
(2.21)

Next, consider $M_{n}(z)-M_{n}(z^{\prime})$. By $(\ref{002})$,

$\displaystyle\big{|}\mfrac{1}{\sqrt{z}}\big{(}M_{n}(z)-M_{n}(z^{\prime})\big{)}_{i+r,i+r}\big{|}$
$\displaystyle=\bigg{|}\beta_{n}s_{n}(z)-\frac{1-\beta_{n}}{z}-\beta_{n}s_{n}(z^{\prime})+\frac{1-\beta_{n}}{z^{\prime}}\bigg{|}$
$\displaystyle\leq\beta_{n}|s_{n}(z)-s_{n}(z^{\prime})|+(1-\beta_{n})\bigg{|}\frac{1}{z}-\frac{1}{z^{\prime}}\bigg{|}$
$\displaystyle\lesssim\frac{\sqrt{\beta_{n}}}{n^{1/4}}\,.$ (2.22)

$\widetilde{M}_{n}(z^{\prime})-M_{n}(z^{\prime})$ is bounded similarly to
(2.19). Applying Lemma 6.6 conditional on $X_{n}$ and (2.18),

$\displaystyle\mathbf{E}\Big{|}v_{i}^{\prime}(\breve{S}_{n}-z^{\prime}I_{m})^{-1}v_{i}-\beta_{n}s_{n}(z^{\prime})+\frac{1-\beta_{n}}{z^{\prime}}\Big{|}^{4}$
$\displaystyle\lesssim\frac{1}{m^{4}}\mathbf{E}\big{|}\mathrm{tr}(\breve{S}_{n}-z^{\prime}I_{m})^{-1}(\breve{S}_{n}-\bar{z}^{\prime}I_{m})^{-1}\big{|}^{2}$
$\displaystyle=\frac{1}{m^{4}}\mathbf{E}\bigg{(}\sum_{\alpha=1}^{n}\frac{1}{|\lambda_{\alpha}-z^{\prime}|^{2}}+\frac{m-n}{|z^{\prime}|^{2}}\bigg{)}^{2}$
$\displaystyle\leq\frac{1}{m^{4}}\Big{(}\frac{n}{\beta_{n}}+m\Big{)}^{2}\,,$

Thus,

$\displaystyle\mathbf{P}\big{(}\big{|}\mfrac{1}{\sqrt{z^{\prime}}}(\widetilde{M}_{n}(z^{\prime})-M_{n}(z^{\prime}))_{i+r,i+r}\big{|}\geq
n^{-\ell}\sqrt{\beta_{n}}\big{)}\lesssim\frac{n^{4\ell}}{m^{2}\beta_{n}^{2}}\leq\frac{1}{n^{2-4\ell}}\,.$
(2.23)

Summability of the right-hand side together with (2.21), (2.22) yields (2.14).
The analysis of the off-diagonal entries of $\widetilde{M}_{n}(z)-M_{n}(z)$
uses Lemma 6.7 rather than 6.6. Under assumptions B1, B2, the proof uses that
the eigenvectors of $S_{n}$ are Haar-distributed. ∎

######  Lemma 2.6.

Let $a_{n}\geq 1+(2+\eta)\sqrt{\beta_{n}}$ be a bounded sequence. For any
$\ell<1/4$ and $1\leq i,j\leq r$, almost surely,

$\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\,\Big{|}\frac{d}{dz}(\widetilde{M}_{n}(z)-M_{n}(z))_{i,j}\Big{|}\lesssim
n^{-\ell}\beta_{n}^{-1}\,,$ (2.24) $\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\,\Big{|}\frac{d}{dz}(\widetilde{M}_{n}(z)-M_{n}(z))_{i,j+r}\Big{|}\lesssim
n^{-\ell}\beta_{n}^{-1/2}\,,$ (2.25) $\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\,\Big{|}\frac{d}{dz}(\widetilde{M}_{n}(z)-M_{n}(z))_{i+r,j+r}\Big{|}\lesssim
n^{-\ell}\,.$ (2.26)

Furthermore, for $i\neq j$, almost surely,

$\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\,\frac{1}{m}\Big{|}v_{i}^{\prime}X_{n}^{\prime}(S_{n}-zI_{n})^{-2}X_{n}v_{i}-\mathrm{tr}(S_{n}-zI_{n})^{-2}S_{n}\Big{|}\lesssim
n^{-\ell}\,,$ (2.27) $\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\,\frac{1}{m}|v_{i}^{\prime}X_{n}^{\prime}(S_{n}-zI_{n})^{-2}X_{n}v_{j}|\lesssim
n^{-\ell}\,.$ (2.28)

###### Proof.

The proof is similar to that of Lemma 2.5 and is omitted. ∎

##  3 Proof of Theorem 1.1

The following lemmas, which we shall use to bound
$|\det\widetilde{M}_{n}(z)-\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)|$ and
$\big{|}\frac{d}{dz}(\det\widetilde{M}_{n}(z)-\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z))\big{|}$ in the
vicinities of $\bar{\lambda}_{1},\ldots,\bar{\lambda}_{i_{0}}$, are critical
to the proof of the theorem.

######  Lemma 3.1.

Let $a_{n}\geq 1+(2+\eta)\sqrt{\beta_{n}}$ be a bounded sequence. For any
$\ell<1/4$, almost surely,

$\displaystyle\phantom{\,.}\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}|\det\widetilde{M}_{n}(z)-\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)|$
$\displaystyle\lesssim n^{-\ell}\beta_{n}^{-r/2}\,.$ (3.1)

###### Proof.

Partition $\widetilde{M}_{n}(z)$ into four blocks of size $r\times r$:

$\displaystyle\phantom{\,.}\widetilde{M}_{n}(z)=\begin{bmatrix}\widetilde{M}_{11}&\widetilde{M}_{12}\\\
\widetilde{M}_{21}&\widetilde{M}_{22}\end{bmatrix}\,.$

Let $\underline{\widetilde{M}}_{n}(z)$ denote the matrix containing the above
four submatrices individually rescaled:

$\displaystyle\phantom{\,.}\underline{\widetilde{M}}_{n}(z)=\begin{bmatrix}\sqrt{\beta_{n}}\widetilde{M}_{11}&\beta_{n}^{1/4}\widetilde{M}_{12}\\\
\beta_{n}^{1/4}\widetilde{M}_{21}&\widetilde{M}_{22}\end{bmatrix}\,.$ (3.2)

Let $\underline{M}_{n}(z)$ and $\underline{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu}_{n}(z)$ denote
$M_{n}(z)$ and $\mkern 1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu_{n}(z)$ similarly partitioned and rescaled. This rescaling simplifies
comparison of determinants as all blocks are of similar size. Indeed, as
consequences of Lemma 2.4, Lemma 2.5, and Theorem 1.3, we have the following
almost-sure results:

$\displaystyle\sup_{|z-a_{n}|\leq n^{-1/4}\sqrt{\beta_{n}}}\|\underline{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu}_{n}(z)\|_{\infty}\lesssim 1\,,$ $\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\|\underline{\widetilde{M}}_{n}(z)-\underline{M}_{n}(z)\|_{\infty}\lesssim
n^{-\ell}\,,$ $\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\|\underline{M}_{n}(z)-\underline{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu}_{n}(z)\|_{\infty}\lesssim n^{-\ell}\,.$ (3.3)

Applying Lemma 6.8, we obtain

$\phantom{\,.}\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}|\det\underline{\widetilde{M}}_{n}(z)-\det\underline{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu}_{n}(z)|\lesssim
n^{-\ell}\,,$

which is equivalent to (3.1) as
$\det\widetilde{M}_{n}(z)=\beta_{n}^{-r/2}\det\underline{\widetilde{M}}_{n}(z)$.
∎

######  Lemma 3.2.

Let $a_{n}\geq 1+(2+\eta)\sqrt{\beta_{n}}$ be a bounded sequence. For any
$\ell<1/8$, almost surely,

$\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\Big{|}\frac{d}{dz}(\det\widetilde{M}_{n}(z)-\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z))\Big{|}\lesssim
n^{-\ell}\beta_{n}^{-(r+1)/2}\,,$ $\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\Big{|}\frac{d}{dz}\det\widetilde{M}_{n}(z)\Big{|}\lesssim\beta_{n}^{-(r+1)/2}\,.$

###### Proof.

The proof is similar to that of Lemma 3.1. By Lemma 2.4, Lemma 2.6, and
Corollary 1.3.1,

$\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\Big{\|}\frac{d}{dz}\underline{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu}_{n}(z)\Big{\|}_{\infty}\lesssim\beta_{n}^{-1/2}\,,$
$\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\Big{\|}\frac{d}{dz}(\underline{\widetilde{M}}_{n}(z)-\underline{M}_{n}(z))\Big{\|}_{\infty}\lesssim
n^{-\ell}\beta_{n}^{-1/2}\,,$ $\displaystyle\sup_{|z-a_{n}|\leq
n^{-1/4}\sqrt{\beta_{n}}}\Big{\|}\frac{d}{dz}(\underline{M}_{n}(z)-\underline{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu}_{n}(z))\Big{\|}_{\infty}\lesssim n^{-\ell}\beta_{n}^{-1/2}\,.$ (3.4)

The claim follows from Lemma 6.9, (3.3), and (3.4):

$\displaystyle\Big{|}\frac{d}{dz}(\det\underline{\widetilde{M}}_{n}(z)-\det\underline{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu}_{n}(z))\Big{|}$
$\displaystyle\lesssim\Big{\|}\frac{d}{dz}(\underline{\widetilde{M}}_{n}(z)-\underline{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu}_{n}(z))\Big{\|}_{\infty}+\Big{\|}\frac{d}{dz}\underline{\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu}_{n}(z)\Big{\|}_{\infty}\|\underline{\widetilde{M}}_{n}(z)-\underline{M}_{n}(z)\|_{\infty}$
$\displaystyle\lesssim n^{-\ell}\beta_{n}^{-1/2}\,.$

∎

###### Proof of Theorem 1.1.

We initially assume $\varepsilon_{i,n}=0$, $1\leq i\leq r$. Fix $\ell<1/4$ and
let $\gamma_{i,n}$ denote a circular contour with center $\bar{\lambda}_{i}$
and radius $n^{-\ell}\sqrt{\beta_{n}}$. We divide the proof into four claims:

  1. (1)

$\gamma_{i,n}$ eventually encircles a single real root of $\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)$.

  2. (2)

Almost surely eventually, there exists a unique root $\tilde{\lambda}_{(i)}$
of $\det\widetilde{M}_{n}(z)$ encircled by $\gamma_{i,n}$.

  3. (3)

$\tilde{\lambda}_{(1)},\ldots,\tilde{\lambda}_{(i_{0})}$ are real and
therefore eigenvalues of $\widetilde{S}_{n}$ by Lemma 2.1

  4. (4)

Almost surely eventually, $\widetilde{S}_{n}$ has no unidentified eigenvalues
larger than $\tilde{\lambda}_{(i_{0})}$.

Notice that $\gamma_{i,n}$ eventually encircles a single real root of
$\det\mkern 1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)$: as
$\tau_{1},\ldots,\tau_{i_{0}}$ are distinct,
$|\bar{\lambda}_{i}-\bar{\lambda}_{j}|\gtrsim\sqrt{\beta_{n}}$, $j\neq i$. We
now argue $\gamma_{i,n}$ eventually encircles no complex roots of $\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)$. For
$\xi\in\mathbb{C}$ such that $|\xi|\leq n^{-\ell}\sqrt{\beta_{n}}$,

$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu_{n}(\bar{\lambda}_{i}+\xi)-\theta_{i}^{-2}=\frac{\xi+\sqrt{(\mkern
1.5mu\overline{\mkern-1.5mu\lambda\mkern-1.5mu}\mkern
1.5mu_{i}-\beta_{n}-1)^{2}-4\beta_{n}}(1-\sqrt{1+y})}{2\beta_{n}}\,,$
$\displaystyle
y=\frac{2(\bar{\lambda}_{i}-\beta_{n}-1)\xi+\xi^{2}}{(\bar{\lambda}_{i}-\beta_{n}-1)^{2}-4\beta_{n}}=\frac{2(\tau_{i}^{2}+\tau_{i}^{-2})\beta_{n}^{-1/2}\xi+\beta_{n}^{-1}\xi^{2}}{(\tau_{i}^{2}+\tau_{i}^{-2})^{2}-4}\,.$

Using $|1-\sqrt{1+z}+z/2|\leq|z|^{2}/8$ for $z\in\\{\Re(z)\geq 0,|z|\leq
1\\}$, $|\xi|\leq n^{-\ell}\sqrt{\beta_{n}}$, and $|y|\lesssim n^{-\ell}$,

$\displaystyle\phantom{\,,}|\mkern
1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu_{n}(\bar{\lambda}_{i}+\xi)-\theta_{i}^{-2}|$
$\displaystyle\asymp|\xi|\beta_{n}^{-1}\,.$ (3.5)

For $j\neq i$, almost surely,

$\displaystyle|\mkern 1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu_{n}(\bar{\lambda}_{i}+\xi)-\theta_{j}^{-2}|$ $\displaystyle=|\mkern
1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu_{n}(\bar{\lambda}_{i}+\xi)-\theta_{i}^{-2}+(\theta_{i}^{-2}-\theta_{j}^{-2})|\asymp\beta_{n}^{-1/2}\,.$
(3.6)

Recalling the formula $\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu_{n}(z)=\prod_{j=1}^{r}(\mkern
1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu_{n}(z)-\theta_{j}^{-2})$, (3.5) and (3.6) imply

$\displaystyle\phantom{\,.}|\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu_{n}(\bar{\lambda}_{i}+\xi)|\asymp|\xi|\beta_{n}^{-(r+1)/2}\,.$ (3.7)

Consequently, $\gamma_{i,n}$ eventually encircles no root of $\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)$ other than
$\bar{\lambda}_{i}$ (and no roots occur on $\gamma$). Otherwise, there exists
a sequence of perturbations $\xi_{n}\neq 0$ such that $\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu_{n}(\bar{\lambda}_{i}+\xi_{n})=0$, contradicting (3.7). This proves
Claim (1). As a consequence, by the winding number theorem,

$\displaystyle\phantom{\,.}\frac{1}{2\pi
i}\int_{\gamma_{i,n}}\frac{\frac{d}{dz}\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)}{\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)}dz=1\,.$ (3.8)

To prove Claim (2), it suffices to show that almost surely eventually,

$\displaystyle\phantom{\,.}\bigg{|}\frac{1}{2\pi
i}\int_{\gamma_{i,n}}\frac{\frac{d}{dz}\det\widetilde{M}_{n}(z)}{\det\widetilde{M}_{n}(z)}dz-\frac{1}{2\pi
i}\int_{\gamma_{i,n}}\frac{\frac{d}{dz}\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)}{\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)}dz\bigg{|}<1\,,$

as the above integrals are integer-valued. Writing
$\frac{a}{c}-\frac{b}{d}=\frac{1}{d}\big{(}\frac{d-c}{c}a+a-b\big{)}$, an
upper bound on the left-hand side is

$\displaystyle\,n^{-\ell}\sqrt{\beta_{n}}\sup_{z\in\gamma_{i,n}}\bigg{|}\frac{\frac{d}{dz}\det\widetilde{M}_{n}(z)}{\det\widetilde{M}_{n}(z)}-\frac{\frac{d}{dz}\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)}{\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)}\bigg{|}$
$\displaystyle=$
$\displaystyle\,n^{-\ell}\sqrt{\beta_{n}}\sup_{z\in\gamma_{i,n}}\bigg{|}\frac{1}{\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu_{n}}\bigg{|}\bigg{|}\frac{\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern
1.5mu_{n}-\det\widetilde{M}_{n}}{\det\widetilde{M}_{n}}\cdot\frac{d}{dz}\det\widetilde{M}_{n}+\frac{d}{dz}\big{(}\det\widetilde{M}_{n}-\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}\big{)}\bigg{|}\,.$
(3.9)

Below, the almost-sure bounds we have developed on the terms of (3.9) are
summarized. Let $\ell^{\prime}\in(\ell,1/4)$ and
$\ell^{\prime\prime}\in(0,1/8)$. By Lemmas 3.1 and 3.2 (applied to
$a_{n}=\bar{\lambda}_{i}$ and
$\eta\in(0,\tau_{i_{0}}^{2}+\tau_{i_{0}}^{-2}-2)$),

$\displaystyle\sup_{z\in\gamma_{i,n}}|\det\widetilde{M}_{n}(z)-\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)|\lesssim
n^{-\ell^{\prime}}\beta_{n}^{-r/2}\,,$ (3.10)
$\displaystyle\sup_{z\in\gamma_{i,n}}\Big{|}\frac{d}{dz}(\det\widetilde{M}_{n}(z)-\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z))\Big{|}\lesssim
n^{-\ell^{\prime\prime}}\beta_{n}^{-(r+1)/2}\,,$ (3.11)
$\displaystyle\sup_{z\in\gamma_{i,n}}\Big{|}\frac{d}{dz}\det\widetilde{M}_{n}(z)\Big{|}\lesssim\beta_{n}^{-(r+1)/2}\,.$
(3.12)

As (3.7) depend on $\xi$ only through $|\xi|$,

$\displaystyle\sup_{z\in\gamma_{i,n}}|\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)|\asymp
n^{-\ell}\beta_{n}^{-r/2}\,.$ (3.13)

Finally, (3.10), (3.13), and $\ell<\ell^{\prime}$ imply,

$\displaystyle\sup_{z\in\gamma_{i,n}}|\det\widetilde{M}_{n}(z)|\asymp
n^{-\ell}\beta_{n}^{-r/2}\,.$ (3.14)

Thus, from (3.9) - (3.14), almost surely,

$\displaystyle
n^{-\ell}\sqrt{\beta_{n}}\sup_{z\in\gamma_{i,n}}\bigg{|}\frac{\frac{d}{dz}\det\widetilde{M}_{n}(z)}{\det\widetilde{M}_{n}(z)}-\frac{\frac{d}{dz}\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)}{\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)}\bigg{|}\lesssim$
$\displaystyle\,\frac{n^{-\ell}\sqrt{\beta_{n}}}{n^{-\ell}\beta_{n}^{-r/2}}\bigg{(}\frac{n^{-\ell^{\prime}}\beta_{n}^{-r/2}}{n^{-\ell}\beta_{n}^{-r/2}}\cdot\beta_{n}^{-(r+1)/2}+n^{-\ell^{\prime\prime}}\beta_{n}^{-(r+1)/2}\bigg{)}$
$\displaystyle\lesssim$
$\displaystyle\,n^{\ell-\ell^{\prime}}+n^{-\ell^{\prime\prime}}\longrightarrow
0\,.$ (3.15)

This completes the proof of Claim (2): almost surely eventually, there exist
roots $\tilde{\lambda}_{(1)},\ldots,\tilde{\lambda}_{(i_{0})}$ respectively
encircled by $\gamma_{1,n},\ldots,\gamma_{i_{0},n}$. Claim (3)—that
$\tilde{\lambda}_{(1)},\ldots,\tilde{\lambda}_{(i_{0})}$ are eigenvalues of
$\widetilde{S}_{n}$—follows from Lemma 2.1 and the fact that
$\widetilde{M}_{n}(z)$ is invertible for $z\not\in\mathbb{R}$ (Lemma A.1 of
[11]).

It remains to prove Claim (4):
$\tilde{\lambda}_{1}=\tilde{\lambda}_{(1)},\ldots,\tilde{\lambda}_{i_{0}}=\tilde{\lambda}_{(i_{0})}$.
Suppose $\det\widetilde{M}_{n}(z)$ has a sequence of roots
$\tilde{\lambda}\in[1+(2+\eta)\sqrt{\beta_{n}},C]$, for some $\eta>0$, $C>1$
such that infinitely often,
$|\tilde{\lambda}-\bar{\lambda}_{i}|>n^{-\ell}\sqrt{\beta_{n}}$ for all $i\leq
i_{0}$. Let $\gamma_{n}$ denote a sequence of circular contours of radius
$n^{-\ell}\sqrt{\beta_{n}}$ centered at $\tilde{\lambda}$. Then,

$\displaystyle\frac{1}{2\pi
i}\int_{\gamma_{n}}\frac{\frac{d}{dz}\det\widetilde{M}_{n}(z)}{\det\widetilde{M}_{n}(z)}dz=1\,,$
$\displaystyle\frac{1}{2\pi i}\int_{\gamma_{n}}\frac{\frac{d}{dz}\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)}{\det\mkern
1.5mu\overline{\mkern-1.5muM\mkern-1.5mu}\mkern 1.5mu_{n}(z)}dz=0\,.$

Note that on $\gamma_{n}$, (3.10) - (3.13) hold while (3.14) improves to
$\beta_{n}^{-r/2}$. By (3.15), a contradiction is obtained. Furthermore,
eventually $\widetilde{S}_{n}$ has no eigenvalues greater than $C$:

$\phantom{\,.}\frac{1}{\sqrt{m}}\sigma_{max}(\widetilde{X}_{n})\leq\sum_{i=1}^{r}\theta_{i}\|u_{i}\|_{2}\|v_{i}\|_{2}+\frac{1}{\sqrt{m}}\sigma_{max}(X_{n})\leq
1+\eta\,,$

the last inequality holding almost surely eventually. This establishes Claim
(4). We conclude that almost surely eventually, the leading eigenvalues of
$\widetilde{S}_{n}$ satisfy

$\displaystyle|\tilde{\lambda}_{i}-\bar{\lambda}_{i}|\leq
n^{-\ell}\sqrt{\beta_{n}}\,,$ $\displaystyle i\leq i_{0}\,,$

which is (1.4) in the case $\varepsilon_{i,n}=0$. Fix $i>i_{0}$. Almost surely
eventually, no eigenvalues other than
$\tilde{\lambda}_{1},\ldots,\tilde{\lambda}_{i_{0}}$ occur in
$[1+(2+\eta)\sqrt{\beta_{n}},\infty)$. As this holds for any $\eta>0$, we
obtain (1.2):

$\displaystyle\frac{\tilde{\lambda}_{i}-1}{2\sqrt{\beta_{n}}}\xrightarrow{a.s.}1\,.$

For general signal strengths
$\theta_{i}=\tau\beta_{n}^{1/4}(1+\varepsilon_{i,n})$, the above argument may
be used to show that $\tilde{\lambda}_{i}$ localizes about
$D_{n}^{(-1)}(\theta_{i}^{-2})$. Recalling that
$D_{n}^{(-1)}(t)=\frac{(t+1)(\beta_{n}t+1)}{t}$ (Lemma 2.2),

$\displaystyle\phantom{\,.}\big{|}D_{n}^{(-1)}(\theta_{i}^{-2})-\bar{\lambda}_{i}\big{|}$
$\displaystyle=\big{|}D_{n}^{(-1)}(\theta_{i}^{-2})-D_{n}^{(-1)}\big{(}(\tau_{i}\beta_{n}^{1/4})^{-2}\big{)}\big{|}$
$\displaystyle=(\tau_{i}^{2}+\tau_{i}^{-2}(1+\varepsilon_{i,n})^{-2})|\varepsilon_{i,n}(2+\varepsilon_{i,n})|\sqrt{\beta_{n}}$
$\displaystyle\lesssim|\varepsilon_{i,n}|\sqrt{\beta_{n}}\,.$ (3.16)

Thus, almost surely eventually,

$\displaystyle\phantom{\,.}|\tilde{\lambda}_{i}-\bar{\lambda}_{i}|$
$\displaystyle\leq\big{|}\tilde{\lambda}_{i}-D_{n}^{(-1)}(\theta_{i}^{-2})\big{|}+\big{|}D_{n}^{(-1)}(\theta_{i}^{-2})-\bar{\lambda}_{i}\big{|}$
$\displaystyle\lesssim(n^{-\ell}+|\varepsilon_{i,n}|)\sqrt{\beta_{n}}\,,$

which is (1.4) in the general case $\varepsilon_{i,n}\rightarrow 0$. (1.1) is
a direct consequence of (1.4). ∎

##  4 Proof of Theorem 1.2

For notational lightness, this section assumes $\varepsilon_{i,n}=0$. All
bounds are understood to hold only almost surely.

######  Lemma 4.1.

Let $i\leq i_{0}$, $j\leq r$, and $\ell<1/4$. Let
$\tilde{u}_{i},\tilde{v}_{i}$ be the singular vectors corresponding to
$\tilde{\sigma}_{i}=\sqrt{\tilde{\lambda}_{i}}$. Almost surely,

$\displaystyle\phantom{\,.}|\bar{\sigma}_{i}\bar{s}_{n}(\bar{\lambda}_{i})\theta_{j}\langle\tilde{v}_{i},v_{j}\rangle+\langle\tilde{u}_{i},u_{j}\rangle|\lesssim
n^{-\ell}(\beta_{n}^{-1/4}\|V_{m}^{\prime}\tilde{v}_{i}\|_{1}+\beta_{n}^{1/4})\,,$
(4.1)

and for $j\neq i$,

$\displaystyle\phantom{\,.}|\langle\tilde{v}_{i},v_{j}\rangle|\lesssim
n^{-\ell}(|\langle\tilde{v}_{i},v_{i}\rangle|+\sqrt{\beta_{n}})\,.$ (4.2)

###### Proof.

Recall Lemma 2.3: the column vector

$\displaystyle\begin{bmatrix}\Theta V_{m}^{\prime}\tilde{v}_{i}\\\ \Theta
U_{n}^{\prime}\tilde{u}_{i}\end{bmatrix}\hskip 199.16928pt$ (4.3)

belongs to the kernel of $\widetilde{M}_{n}(\tilde{\lambda}_{i})$. As (4.3) is
orthogonal to the $j$-th row of $\widetilde{M}_{n}(\tilde{\lambda}_{i})$,

$\displaystyle\phantom{\,.}\sum_{k=1}^{r}\tilde{\sigma}_{i}u_{j}^{\prime}(S_{n}-\tilde{\lambda}_{i}I_{n})^{-1}u_{k}\theta_{k}\langle\tilde{v}_{i},v_{k}\rangle+\sum_{k=1}^{r}\Big{(}\theta_{k}^{-1}{\bf
1}_{\\{j=k\\}}+\frac{1}{\sqrt{m}}u_{j}^{\prime}(S_{n}-\tilde{\lambda}_{i}I_{n})^{-1}X_{n}v_{k}\Big{)}\theta_{k}\langle\tilde{u}_{i},u_{k}\rangle=0\,.$

By Lemma 2.5,

$\displaystyle|\tilde{\sigma}_{i}u_{j}^{\prime}(S_{n}-\tilde{\lambda}_{i}I_{n})^{-1}u_{j}\theta_{j}\langle\tilde{v}_{i},v_{j}\rangle+\langle\tilde{u}_{i},u_{j}\rangle|$
$\displaystyle\leq\tilde{\sigma}_{i}\sum_{k\neq
j}\theta_{k}|u_{j}^{\prime}(S_{n}-\tilde{\lambda}_{i}I_{n})^{-1}u_{k}||\langle\tilde{v}_{i},v_{k}\rangle|$
$\displaystyle+\frac{1}{\sqrt{m}}\sum_{k=1}^{r}\theta_{k}|u_{j}^{\prime}(S_{n}-\tilde{\lambda}_{i}I_{n})^{-1}X_{n}v_{k}|$
$\displaystyle\lesssim n^{-\ell}\beta_{n}^{-1/4}\sum_{k\neq
j}|\langle\tilde{v}_{i},v_{k}\rangle|+n^{-\ell}\beta_{n}^{1/4}\,,$ (4.4)
$\displaystyle|\tilde{\sigma}_{i}s_{n}(\tilde{\lambda}_{i})\theta_{j}\langle\tilde{v}_{i},v_{j}\rangle+\langle\tilde{u}_{i},u_{j}\rangle|$
$\displaystyle\leq|\tilde{\sigma}_{i}u_{j}^{\prime}(S_{n}-\tilde{\lambda}_{i}I_{n})^{-1}u_{j}\theta_{j}\langle\tilde{v}_{i},v_{j}\rangle+\langle\tilde{u}_{i},u_{j}\rangle|$
$\displaystyle+\tilde{\sigma}_{i}\theta_{j}|u_{j}^{\prime}(S_{n}-\tilde{\lambda}_{i}I_{n})^{-1}u_{j}-s_{n}(\tilde{\lambda}_{i})||\langle\tilde{v}_{i},v_{j}\rangle|$
$\displaystyle\lesssim
n^{-\ell}\beta_{n}^{-1/4}\sum_{k=1}^{r}|\langle\tilde{v}_{i},v_{k}\rangle|+n^{-\ell}\beta_{n}^{1/4}\,.$
(4.5)

Note that eventually,
$|s_{n}(\tilde{\lambda}_{i})-s_{n}(\bar{\lambda}_{i})|\leq\frac{|\tilde{\lambda}_{i}-\bar{\lambda}_{i}|}{|\lambda_{1}-\tilde{\lambda}_{i}||\lambda_{1}-\bar{\lambda}_{i}|}$.
By an application of Theorems 1.1 and 1.3,

$\displaystyle|\tilde{\sigma}_{i}s_{n}(\tilde{\lambda}_{i})-\bar{\sigma}_{i}\bar{s}_{n}(\bar{\lambda}_{i})|$
$\displaystyle\leq|\tilde{\sigma}_{i}-\bar{\sigma}_{i}||s_{n}(\tilde{\lambda}_{i})|+|\bar{\sigma}_{i}||s_{n}(\tilde{\lambda}_{i})-s_{n}(\bar{\lambda}_{i})|+|\bar{\sigma}_{i}||s_{n}(\bar{\lambda}_{i})-\bar{s}_{n}(\bar{\lambda}_{i})|$
$\displaystyle\lesssim
n^{-\ell}+n^{-\ell}\beta_{n}^{-1/2}+n^{-\ell}\beta_{n}^{-1/2}\,.$ (4.6)

(4.1) follows from (4.5) and (4.6):

$\displaystyle\phantom{\,.}|\bar{\sigma}_{i}\bar{s}_{n}(\bar{\lambda}_{i})\theta_{j}\langle\tilde{v}_{i},v_{j}\rangle+\langle\tilde{u}_{i},u_{j}\rangle|\lesssim
n^{-\ell}(\beta_{n}^{-1/4}\|V_{m}^{\prime}\tilde{v}_{i}\|_{1}+\beta_{n}^{1/4})\,.$

By a similar argument for row $j+r$ of
$\widetilde{M}_{n}(\tilde{\lambda}_{i})$,

$\displaystyle\phantom{\,.}\Big{|}\langle\tilde{v}_{i},v_{j}\rangle+\bar{\sigma}_{i}\Big{(}\beta_{n}\bar{s}_{n}(\bar{\lambda}_{i})-\frac{1-\beta_{n}}{\bar{\lambda}_{i}}\Big{)}\theta_{j}\langle\tilde{u}_{i},u_{j}\rangle\Big{|}\lesssim
n^{-\ell}(\beta_{n}^{1/4}\|V_{m}^{\prime}\tilde{v}_{i}\|_{1}+\beta_{n}^{3/4})\,.$
(4.7)

Substitution of $(\ref{912})$ into $(\ref{913})$ yields

$\phantom{\,.}\Big{|}\langle\tilde{v}_{i},v_{j}\rangle-\bar{\lambda}_{i}\bar{s}_{n}(\bar{\lambda}_{i})\Big{(}\beta_{n}\bar{s}_{n}(\bar{\lambda}_{i})-\frac{1-\beta_{n}}{\bar{\lambda}_{i}}\Big{)}\theta_{j}^{2}\langle\tilde{v}_{i},v_{j}\rangle\Big{|}\lesssim
n^{-\ell}(\|V_{m}^{\prime}\tilde{v}_{i}\|_{1}+\sqrt{\beta_{n}})\,.$

Recall that $\mkern 1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu_{n}(z)=\beta_{n}z\bar{s}_{n}(z)^{2}-(1-\beta_{n})\bar{s}_{n}(z)$ and
$\bar{\lambda}_{i}$ is defined by $\mkern
1.5mu\overline{\mkern-1.5muD\mkern-1.5mu}\mkern
1.5mu_{n}(\bar{\lambda}_{i})=\theta_{i}^{-2}$. Thus, for $j\neq i$,

$\displaystyle\phantom{\,.}|\langle\tilde{v}_{i},v_{j}\rangle|\lesssim
n^{-\ell}(\|V_{m}^{\prime}\tilde{v}_{i}\|_{1}+\sqrt{\beta_{n}})\ \,.$

Rewriting this as
$(1-Cn^{-\ell})(\|V_{m}^{\prime}\tilde{v}_{i}\|_{1}-|\langle\tilde{v}_{i},v_{i}\rangle|)\lesssim
n^{-\ell}(|\langle\tilde{v}_{i},v_{i}\rangle|+\sqrt{\beta_{n}})$, we recover
(4.2):

$\displaystyle\phantom{\,.}|\langle\tilde{v}_{i},v_{j}\rangle|\lesssim
n^{-\ell}(|\langle\tilde{v}_{i},v_{i}\rangle|+\sqrt{\beta_{n}})\,.$

∎

###### Proof of Theorem 1.2.

Let $i\leq i_{0}$ and $\ell<1/8$. By (2.8), $a_{n}+b_{n}+2c_{n}=1$ with

$\displaystyle\phantom{\,.}a_{n}$
$\displaystyle=\tilde{\lambda}_{i}\tilde{v}_{i}^{\prime}P_{n}^{\prime}(S_{n}-\tilde{\lambda}_{i})^{-2}P_{n}\tilde{v}_{i}=\tilde{\lambda}_{i}\sum_{j,k=1}^{r}\theta_{j}\theta_{k}\langle\tilde{v}_{i},v_{j}\rangle\langle\tilde{v}_{i},v_{k}\rangle
u_{j}^{\prime}(S_{n}-\tilde{\lambda}_{i}I_{n})^{-2}u_{k}\,,$
$\displaystyle\phantom{\,.}b_{n}$
$\displaystyle=\frac{1}{m}\tilde{u}_{i}^{\prime}P_{n}X_{n}^{\prime}(S_{n}-\tilde{\lambda}I_{n})^{-2}X_{n}P_{n}^{\prime}\tilde{u}_{i}=\frac{1}{m}\sum_{j,k=1}^{r}\theta_{j}\theta_{k}\langle\tilde{u}_{i},u_{j}\rangle\langle\tilde{u}_{i},u_{k}\rangle
v_{j}^{\prime}X_{n}^{\prime}(S_{n}-\tilde{\lambda}_{i}I_{n})^{-2}X_{n}v_{k}\,,$
$\displaystyle\phantom{\,.}c_{n}$
$\displaystyle=\frac{\tilde{\sigma}_{i}}{\sqrt{m}}\tilde{u}_{i}^{\prime}P_{n}X_{n}^{\prime}(S_{n}-\tilde{\lambda}I_{n})^{-2}P_{n}\tilde{v}_{i}=\frac{\tilde{\sigma}_{i}}{\sqrt{m}}\sum_{j,k=1}^{r}\theta_{j}\theta_{k}\langle\tilde{u}_{i},u_{j}\rangle\langle\tilde{v}_{i},v_{k}\rangle
v_{j}^{\prime}X_{n}^{\prime}(S_{n}-\tilde{\lambda}_{i}I_{n})^{-2}u_{k}\,.$
(4.8)

By Theorem 1.1 and Corollary 1.3.1,

$\displaystyle\Big{|}\tilde{\lambda}_{i}\frac{d}{dz}s_{n}(\tilde{\lambda}_{i})-\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})\Big{|}=\Big{|}\tilde{\lambda}_{i}\frac{d}{dz}s_{n}(\tilde{\lambda}_{i})-\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})\Big{|}$
$\displaystyle\leq\,$
$\displaystyle|\tilde{\lambda}_{i}-\bar{\lambda}_{i}|\Big{|}\frac{d}{dz}s_{n}(\tilde{\lambda}_{i})\Big{|}+|\bar{\lambda}_{i}|\Big{|}\frac{d}{dz}(s_{n}(\tilde{\lambda}_{i})-s_{n}(\bar{\lambda}_{i})\Big{|}+|\bar{\lambda}_{i}|\Big{|}\frac{d}{dz}(s_{n}(\bar{\lambda}_{i})-\bar{s}_{n}(\bar{\lambda}_{i})\Big{|}$
$\displaystyle\phantom{\,.}\lesssim\,$ $\displaystyle
n^{-2\ell}\beta_{n}^{-1/2}+n^{-2\ell}\beta_{n}^{-1}+n^{-\ell}\beta_{n}^{-1}\,.$

Together with (2.24) of Lemma 2.6,

$\displaystyle a_{n}$
$\displaystyle=\sum_{j,k=1}^{r}\theta_{j}\theta_{k}\langle\tilde{v}_{i},v_{j}\rangle\langle\tilde{v}_{i},v_{k}\rangle\Big{(}\delta_{jk}\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})+O(n^{-\ell}\beta_{n}^{-1})\Big{)}$
$\displaystyle=\sum_{j=1}^{r}\theta_{j}^{2}|\langle\tilde{v}_{i},v_{j}\rangle|^{2}\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})+O(n^{-\ell}\beta_{n}^{-1/2}\|V_{m}^{\prime}\tilde{v}_{i}\|_{1}^{2})\,.$
(4.9)

Similarly, using

$\displaystyle\phantom{\,,}\frac{1}{m}\mathrm{tr}(S_{n}-\tilde{\lambda}_{i})^{-2}S_{n}$
$\displaystyle=\frac{1}{m}\mathrm{tr}\big{(}(S_{n}-\tilde{\lambda}_{i}I_{n})^{-1}+\tilde{\lambda}_{i}(S_{n}-\tilde{\lambda}_{i}I_{n})^{-2}\big{)}$
$\displaystyle=\beta_{n}\Big{(}s_{n}(\tilde{\lambda}_{i})+\tilde{\lambda}_{i}\frac{d}{dz}s_{n}(\tilde{\lambda}_{i})\Big{)}\,,$

(2.27), (2.28), and (2.25), it may be shown that

$\displaystyle b_{n}$
$\displaystyle=\sum_{j,k=1}^{r}\theta_{j}\theta_{k}\langle\tilde{u}_{i},u_{j}\rangle\langle\tilde{u}_{i},u_{k}\rangle\Big{(}\delta_{jk}\beta_{n}\Big{(}\bar{s}_{n}(\bar{\lambda}_{i})+\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})\Big{)}+O(n^{-\ell})\Big{)}$
$\displaystyle=\sum_{j=1}^{r}\theta_{j}^{2}|\langle\tilde{u}_{i},u_{j}\rangle|^{2}\beta_{n}\Big{(}\bar{s}_{n}(\bar{\lambda}_{i})+\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})\Big{)}+O(n^{-\ell}\sqrt{\beta_{n}})\,,$
$\displaystyle\phantom{\,.}|c_{n}|$ $\displaystyle\lesssim
n^{-\ell}\beta_{n}^{-1/2}\sum_{j,k=1}^{r}\theta_{j}\theta_{k}|\langle\tilde{u}_{i},u_{j}\rangle\langle\tilde{v}_{i},v_{k}\rangle|$
$\displaystyle\lesssim n^{-\ell}\,.$ (4.10)

Thus,

$\displaystyle\sum_{j=1}^{r}\theta_{j}^{2}|\langle\tilde{v}_{i},v_{j}\rangle|^{2}\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})+\sum_{j=1}^{r}\theta_{j}^{2}|\langle\tilde{u}_{i},u_{j}\rangle|^{2}\beta_{n}\Big{(}\bar{s}_{n}(\bar{\lambda}_{i})+\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})\Big{)}$
$\displaystyle=\,$ $\displaystyle
1+O\big{(}n^{-\ell}(1+\beta_{n}^{-1/2}\|V_{m}^{\prime}\tilde{v}_{i}\|_{1}^{2})\big{)}\,.$
(4.11)

Terms on the left-hand side with $j\neq i$ are negligible: by (4.2),

$\displaystyle\bigg{|}\sum_{j\neq
i}\theta_{j}^{2}|\langle\tilde{v}_{i},v_{j}\rangle|^{2}\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})\bigg{|}\lesssim
n^{-4\ell}(\beta_{n}^{-1/2}|\langle\tilde{v}_{i},v_{i}\rangle|^{2}+\sqrt{\beta_{n}})\,,$
$\displaystyle\bigg{|}\sum_{j\neq
i}\theta_{j}^{2}|\langle\tilde{u}_{i},u_{j}\rangle|^{2}\beta_{n}\Big{(}\bar{s}_{n}(\bar{\lambda}_{i})+\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})\Big{)}\bigg{|}\lesssim\sqrt{\beta_{n}}\,,$

implying

$\displaystyle\theta_{i}^{2}|\langle\tilde{v}_{i},v_{i}\rangle|^{2}\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})+\theta_{i}^{2}|\langle\tilde{u}_{i},u_{i}\rangle|^{2}\beta_{n}\Big{(}\bar{s}_{n}(\bar{\lambda}_{i})+\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})\Big{)}$
$\displaystyle=\,$ $\displaystyle
1+O\big{(}n^{-\ell}(1+\beta_{n}^{-1/2}\|V_{m}^{\prime}\tilde{v}_{i}\|_{1}^{2})+\sqrt{\beta_{n}}\big{)}\,.$
(4.12)

Substitution of (4.1) into (4.12) yields

$\displaystyle|\langle\tilde{v}_{i},v_{i}\rangle|^{2}\Big{(}\theta_{i}^{2}\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})+\theta_{i}^{4}\bar{\lambda}_{i}\bar{s}_{n}(\bar{\lambda}_{i})^{2}\beta_{n}\Big{(}\bar{s}_{n}(\bar{\lambda}_{i})+\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})\Big{)}\Big{)}$
$\displaystyle=\,$
$\displaystyle|\langle\tilde{v}_{i},v_{i}\rangle|^{2}\bigg{(}\theta_{i}^{2}\int\frac{\bar{\lambda}_{i}}{(t-\bar{\lambda}_{i})^{2}}d\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern
1.5mu_{n}(t)+\theta_{i}^{4}\bar{\lambda}_{i}\bar{s}_{n}(\bar{\lambda}_{i})^{2}\beta_{n}\int\frac{t}{(t-\bar{\lambda}_{i})^{2}}d\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{n}(t)\bigg{)}$
$\displaystyle=\,$ $\displaystyle
1+O\big{(}n^{-\ell}(1+\beta_{n}^{-1/2}\|V_{m}^{\prime}\tilde{v}_{i}\|_{1}^{2})+\sqrt{\beta_{n}}\big{)}\,.$
(4.13)

(4.13) is included to facilitate comparison with Theorem 2.10 of [11]. In the
regime where $\beta_{n}\rightarrow\beta>0$ and $\theta_{i}>1$ is constant, the
term multiplying $|\langle\tilde{v}_{i},v_{i}\rangle|^{2}$ converges to a
positive limit, and $|\langle\tilde{v}_{i},v_{i}\rangle|^{2}$ converges to the
limit’s inverse. Here, since

$\phantom{}\Big{|}\theta_{i}^{2}|\langle\tilde{u}_{i},u_{i}\rangle|^{2}\beta_{n}\Big{(}\bar{s}_{n}(\bar{\lambda}_{i})+\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})\Big{)}\Big{|}\lesssim\sqrt{\beta_{n}}\,,$

(4.2) and (4.12) imply

$\displaystyle\theta_{i}^{2}|\langle\tilde{v}_{i},v_{i}\rangle|^{2}\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})=1+O\big{(}n^{-\ell}(1+\beta_{n}^{-1/2}\|V_{m}^{\prime}\tilde{v}_{i}\|_{1}^{2})+\sqrt{\beta_{n}}\big{)}$
(4.14)

Evaluated at $z=\bar{\lambda}_{i}$, Lemma 2.4 is tight up to constants:
$\bar{\lambda}_{i}\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})\asymp\beta_{n}^{-1}$.
Thus, for $j\neq i$,

$\displaystyle(1-Cn^{-\ell})|\langle\tilde{v}_{i},v_{i}\rangle|^{2}\lesssim\sqrt{\beta_{n}}\,,$
$\displaystyle|\langle\tilde{v}_{i},v_{i}\rangle|\lesssim\beta_{n}^{1/4}\,,$
$\displaystyle|\langle\tilde{v}_{i},v_{j}\rangle|\lesssim
n^{-2\ell}\beta_{n}^{1/4}\,.$ (4.15)

The third inequality follows from (4.2). We have established (1.8): right
singular vectors asymptotically do not correlate with right signal vectors.

Now, by (4.1), (4.14), and (4.15), we obtain

$\displaystyle|\langle\tilde{u}_{i},u_{i}\rangle|^{2}$
$\displaystyle=(\bar{\sigma}_{i}\bar{s}_{n}(\bar{\lambda}_{i})\theta_{i}\langle\tilde{v}_{i},v_{i}\rangle)^{2}+O(n^{-4\ell})$
$\displaystyle=\frac{\bar{s}_{n}(\bar{\lambda}_{i})^{2}}{\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})}+O(n^{-\ell}+\sqrt{\beta_{n}})\,.$
(4.16)

Direct calculation yields

$\displaystyle\bar{s}_{n}(\bar{\lambda}_{i})=\frac{-(\tau_{i}^{2}+\tau_{i}^{-2})+\sqrt{(\tau_{i}^{2}+\tau_{i}^{-2})^{2}-4}}{2\sqrt{\beta_{n}}}+O(1)\,,$
$\displaystyle\frac{d}{dz}\bar{s}_{n}(\bar{\lambda}_{i})=-\frac{1}{2\beta_{n}\bar{\lambda}_{i}}\bigg{(}1-\frac{\tau_{i}^{2}+\tau_{i}^{-2}}{\sqrt{(\tau_{i}^{2}+\tau_{i}^{-2})^{2}-4}}\bigg{)}+O(\beta_{n}^{-1/2})\,,$

from which we conclude (1.7):

$\displaystyle\phantom{\,.}|\langle\tilde{u}_{i},u_{i}\rangle|^{2}=1-\tau_{i}^{4}+O(n^{-\ell}+\sqrt{\beta_{n}})\,.$
(4.17)

Therefore,
$|\langle\tilde{u}_{i},u_{i}\rangle|^{2}\xrightarrow{a.s.}1-\tau_{i}^{-4}$.
For $j\neq i$, $|\langle\tilde{u}_{i},u_{j}\rangle|\lesssim n^{-2\ell}$
follows from (4.1).

∎

##  5 Proof of Theorem 1.3

This section develops bounds on $|s_{n}(z)-\bar{s}_{n}(z)|$ and
$|\frac{d}{dz}(s_{n}(z)-\bar{s}_{n}(z))|$ based on the work of Zhidong Bai,
Jack Silverstein, Jiang Hu, and Wang Zhou, in particular, Section 4.1 of [2]
and Section 8 of [5]. The bounds are novel in that (1) dependence on
$\beta_{n}$ is more carefully tracked and (2) the bound applies to $z\geq
1+(2+\eta)\sqrt{\beta_{n}}$ (rather than to $z$ with $\Im(z)>1/\sqrt{m}$). (2)
is critical since the proof of Theorem 1.1 requires bounding
$|s_{n}(z)-\bar{s}_{n}(z)|$ and $|\frac{d}{dz}(s_{n}(z)-\bar{s}_{n}(z))|$
along a contour centered at a real point.

Furthermore, (2) enables improvement of previous bounds using the
concentration of the maximum eigenvalue of $S_{n}$. For example, in place of
deterministic bounds such as

$\phantom{\,,}\frac{1}{n}\mathbf{E}\,\mathrm{tr}(S_{n}-zI_{n})^{-1}(S_{n}-\bar{z}I_{n})^{-1}\leq\Im(z)^{-2}\,,$

we will argue using Lemma 6.2 that
$\frac{1}{n}\mathrm{tr}(S_{n}-zI_{n})^{-1}(S_{n}-\bar{z}I_{n})^{-1}\lesssim\beta_{n}^{-1}$
with high probability. Indeed, following the discussion in Section 2.2, it
suffices to prove Theorem 1.3 in the truncated and normalized setting of Lemma
6.2. For the sake of completeness, we note that Theorem 1.3 and Corollary
1.3.1 hold for non-truncated noise as well. By Lemma 6.3, truncation and
normalization perturbs the Stieltjes transform by at most
$C/(n\sqrt{\beta_{n}})$, a negligible amount compared to the rate claimed in
the theorem. Similarly, the derivative of the Stieltjes transform is perturbed
negligibly by at most $C/(n\beta_{n})$.

Let $x_{k}^{\prime}$ denote the $k$th-row of $X_{n}$, $X_{nk}$ consist of the
remaining $n-1$ rows, and $\mathbf{E}_{k}(\cdot)$ denote the conditional
expectation given $\\{x_{ij},i\leq k,j\leq m\\}$. Define

$\displaystyle\phantom{\,,}s_{kk}$
$\displaystyle=\frac{1}{m}\sum_{j=1}^{m}|x_{kj}|^{2}\,,$
$\displaystyle\phantom{\,,}S_{nk}$
$\displaystyle=\frac{1}{m}X_{nk}X_{nk}^{\prime}\,,$
$\displaystyle\phantom{\,,}\alpha_{k}$ $\displaystyle=X_{nk}x_{k}\,,$
$\displaystyle\phantom{\,,}\sigma_{k}$
$\displaystyle=\mathrm{tr}(S_{n}-zI_{n})^{-1}-\mathrm{tr}(S_{nk}-zI_{n-1})^{-1}\,,$
$\displaystyle\phantom{\,,}\gamma_{k}$
$\displaystyle=(\mathbf{E}_{k}-\mathbf{E}_{k-1})\sigma_{k}\,,$
$\displaystyle\phantom{\,,}b_{k}$
$\displaystyle=\frac{1}{1-z-\beta_{n}-\frac{z}{m}\mathrm{tr}(S_{nk}-zI_{n-1})^{-1}}\,,$
$\displaystyle\phantom{\,,}\tilde{b}_{k}$
$\displaystyle=\frac{1}{s_{kk}-z-\frac{1}{m^{2}}\alpha_{k}^{\prime}(S_{nk}-zI_{n-1})^{-1}\alpha_{k}}\,,$
$\displaystyle\phantom{\,.}\bar{b}_{n}$
$\displaystyle=\frac{1}{1-z-\beta_{n}-\beta_{n}z\mathbf{E}s_{n}(z)}\,,$
$\displaystyle\phantom{\,,}\varepsilon_{k}$
$\displaystyle=s_{kk}-1-\frac{1}{m^{2}}\alpha_{k}^{\prime}(S_{nk}-zI_{n-1})^{-1}\alpha_{k}+\frac{1}{m}\mathrm{tr}(S_{nk}-zI_{n-1})^{-1}S_{nk}+\frac{1}{m}\,,$
$\displaystyle\phantom{\,,}\bar{\varepsilon}_{k}$
$\displaystyle=s_{kk}-1+\beta_{n}+\beta_{n}z\mathbf{E}s_{n}(z)-\frac{1}{m^{2}}\alpha_{k}^{\prime}(S_{nk}-zI_{n-1})^{-1}\alpha_{k}\,.$
(5.1)

We have adopted notation similar to [5]—$\varepsilon_{k}$ and
$\bar{\varepsilon}_{k}$ are not to be confused with the signal strength
perturbations $\varepsilon_{i,n}$ that appear in Sections 1-4. Standard
properties of these definitions are stated below. See Theorem A.5, Lemma 8.18,
and (8.4.19) of [5].

######  Lemma 5.1.

For $z=u+iv\in\mathbb{C}^{+}$,

$\displaystyle\sigma_{k}=\frac{1+\frac{1}{m^{2}}\alpha_{k}^{\prime}(S_{nk}-zI_{n-1})^{-2}\alpha_{k}}{s_{kk}-z-\frac{1}{m^{2}}\alpha_{k}^{\prime}(S_{nk}-zI_{n-1})^{-1}\alpha_{k}}\,,$
$\displaystyle|\sigma_{k}|\leq\frac{1}{\Im(z)}\,,$
$\displaystyle|\tilde{b}_{k}|\leq\frac{1}{\Im(z)}\,,$
$\displaystyle|\bar{b}_{n}|\leq\frac{1}{\sqrt{\beta_{n}|\Im(z)|}}\,.$

Furthermore, for $\Im(z)\geq\frac{1}{\sqrt{m}}$,

$\phantom{\,.}|b_{k}|\lesssim\frac{1}{\sqrt{\beta_{n}|z|}}\,.$

In the following lemmas, we will use $u_{n}$ and $v_{n}$ to refer to the real
and imaginary parts of a complex sequence $z_{n}$. The subscripts of $z_{n}$,
$u_{n}$, and $v_{n}$ will be suppressed for notational lightness. Lemmas 5.2
and 5.3 respectively bound $|s_{n}(z)-\mathbf{E}\bar{s}_{n}(z)|$ and
$|\mathbf{E}s_{n}(z)-\bar{s}_{n}(z)|$ for $z$ with imaginary part at least
$1/\sqrt{m}$. The proof of Theorem 1.3 extends the bound to the real axis.

######  Lemma 5.2.

Let $z=u+iv$ be a bounded sequences where $u\geq 1+(2+\eta)\sqrt{\beta_{n}}$
and $v\geq 1/\sqrt{m}$. Then,

$\phantom{\,.}\mathbf{E}|s_{n}(z)-\mathbf{E}s_{n}(z)|^{2}\lesssim\frac{1}{n^{2}}\Big{(}\frac{1}{\beta_{n}}+\frac{1}{v^{2}}+\frac{1}{mv^{4}}\Big{)}\,.$

###### Proof.

Begin with a standard decomposition of $s_{n}(z)-\mathbf{E}s_{n}(z)$:

$\displaystyle s_{n}(z)-\mathbf{E}s_{n}(z)$
$\displaystyle=\frac{1}{n}\sum_{k=1}^{n}(\mathbf{E}_{k}-\mathbf{E}_{k-1})\big{(}\mathrm{tr}(S_{n}-zI_{n})^{-1}-\mathrm{tr}(S_{nk}-zI_{n-1})^{-1}\big{)}$
$\displaystyle=\frac{1}{n}\sum_{k=1}^{n}\gamma_{k}\,.$

As $\\{\gamma_{k}\\}_{k=1}^{n}$ forms a martingale difference sequence, the
Burkholder inequality (Lemma 2.12 of [5]) yields

$\phantom{\,.}\mathbf{E}|s_{n}(z)-\mathbf{E}s_{n}(z)|^{2}\lesssim\frac{1}{n^{2}}\sum_{k=1}^{n}\mathbf{E}|\gamma_{k}|^{2}\,.$

This martingale decomposition, together with the bound $|\gamma_{k}|\leq
2/v_{n}$, appear in proofs of convergence to the Marchenko-Pastur distribution
as $\beta_{n}\rightarrow\beta>0$ [1, 6]. Such proofs consider $z$ fixed. Here
and in [2, 5], as $v_{n}$ may decay rapidly, a tighter bound on the moments of
$\gamma_{k}$ is needed. Using the identity

$\displaystyle\phantom{\,.}S_{nk}(S_{nk}-zI_{n-1})^{-1}=(S_{nk}-zI_{n-1})^{-1}S_{nk}=I_{n-1}+z(S_{nk}-zI_{n-1})^{-1}\,,$
(5.2)

we obtain

$\displaystyle\phantom{\,,}\tilde{b}_{k}^{-1}-b_{k}^{-1}=\varepsilon_{k}\,,$
$\displaystyle\tilde{b}_{k}=\frac{b_{k}}{1+b_{k}\varepsilon_{k}}\,.$

Thus,

$\displaystyle\sigma_{k}$
$\displaystyle=\frac{b_{k}}{1+b_{k}\varepsilon_{k}}\Big{(}1+\frac{1}{m^{2}}\alpha_{k}^{\prime}(S_{nk}-zI_{n-1})^{-2}\alpha_{k}\Big{)}$
$\displaystyle=-\sigma_{k}b_{k}\varepsilon_{k}+b_{k}\Big{(}1+\frac{1}{m^{2}}\alpha_{k}^{\prime}(S_{nk}-zI_{n-1})^{-2}\alpha_{k}\Big{)}$

and

$\displaystyle\phantom{\,,}\gamma_{k}$
$\displaystyle=-(\mathbf{E}_{k}-\mathbf{E}_{k-1})\sigma_{k}b_{k}\varepsilon_{k}+\frac{1}{m^{2}}(\mathbf{E}_{k}-\mathbf{E}_{k-1})b_{k}\alpha_{k}^{\prime}(S_{nk}-zI_{n-1})^{-2}\alpha_{k}$
$\displaystyle=-(\mathbf{E}_{k}-\mathbf{E}_{k-1})\sigma_{k}b_{k}\varepsilon_{k}+\frac{1}{m^{2}}\mathbf{E}_{k}b_{k}\big{[}\alpha_{k}^{\prime}(S_{nk}-zI_{n-1})^{-2}\alpha_{k}-\mathrm{tr}(X_{nk}^{\prime}(S_{nk}-zI_{n-1})^{-2}X_{nk})\big{]}\,.$
(5.3)

(5.3) holds as $b_{k}$ does not depend on $x_{k}$, so
$(\mathbf{E}_{k}-\mathbf{E}_{k-1})b_{k}=0$. By Lemmas 5.1 and 6.6,

$\displaystyle\frac{1}{m^{4}}\mathbf{E}b_{k}^{2}\big{|}\alpha_{k}^{\prime}(S_{nk}-\,$
$\displaystyle
zI_{n-1})^{-2}\alpha_{k}-\,\mathrm{tr}(X_{nk}^{\prime}(S_{nk}-zI_{n-1})^{-2}X_{nk})\big{|}^{2}$
$\displaystyle\lesssim\,$
$\displaystyle\frac{1}{m^{4}\beta_{n}}\,\mathbf{E}\mathrm{tr}\,X_{nk}^{\prime}(S_{nk}-zI_{n-1})^{-2}X_{nk}(X_{nk}^{\prime}(S_{nk}-\bar{z}I_{n-1})^{-2}X_{nk})^{\prime}$
$\displaystyle=\,$
$\displaystyle\frac{1}{nm}\mathbf{E}\mathrm{tr}\,S_{nk}(S_{nk}-zI_{n-1})^{-2}S_{nk}(S_{nk}-\bar{z}I_{n-1})^{-2}$
$\displaystyle=\,$
$\displaystyle\frac{1}{m}\mathbf{E}\bigg{(}\frac{1}{n}\sum_{i=1}^{n-1}\frac{\lambda_{k,i}^{2}}{|\lambda_{k,i}-z|^{4}}\bigg{)}\,.$
(5.4)

Let $\lambda_{k,1}\geq\cdots\geq\lambda_{k,n-1}$ denote the eigenvalues of
$S_{nk}$. By Lemma 6.2,

$\phantom{\,,}\mathbf{P}\big{(}\lambda_{k,1}\geq
1+(2+\eta/2)\sqrt{\beta_{n}}\text{ for some }k\big{)}\lesssim\frac{1}{n}\,.$

On this event, the integrand of (5.4) is bounded by
$16|z|/(\eta\sqrt{\beta_{n}})^{4}$. In addition, almost surely,

$\displaystyle\frac{\lambda_{k,i}^{2}}{|\lambda_{k,i}-z|^{2}}\leq
1+\frac{u^{2}}{v^{2}}\,,$
$\displaystyle\frac{\lambda_{k,i}^{2}}{|\lambda_{k,i}-z|^{4}}\leq\frac{|z|^{2}}{v^{4}}\,.$

Therefore,

$\displaystyle\phantom{\,.}\frac{1}{m^{4}}\mathbf{E}b_{k}^{2}\big{|}\alpha_{k}^{\prime}(S_{nk}-zI_{n-1})^{-2}\alpha_{k}-\mathrm{tr}(X_{nk}^{\prime}(S_{nk}-zI_{n-1})^{-2}X_{nk})\big{|}^{2}\lesssim\frac{1}{m}\Big{(}\frac{1}{\beta_{n}^{2}}+\frac{1}{nv_{n}^{4}}\Big{)}\,.$

Note that [5] bounds terms such as $(\ref{957})$ deterministically. Similarly,

$\displaystyle\phantom{\,.}\mathbf{E}|\varepsilon_{k}|^{2}$
$\displaystyle\lesssim\mathbf{E}|s_{kk}-1|^{2}+\frac{1}{m^{2}}+\frac{1}{m^{4}}\mathbf{E}|\alpha_{k}^{\prime}(S_{nk}-zI_{n-1})^{-1}\alpha_{k}-\mathrm{tr}(X_{nk}^{\prime}(S_{nk}-zI_{n-1})^{-1}X_{nk})|^{2}$
$\displaystyle\lesssim\frac{1}{m}+\frac{1}{m^{2}}\mathbf{E}\mathrm{tr}\,S_{nk}(S_{nk}-zI_{n-1})^{-1}S_{nk}(S_{nk}-\bar{z}I_{n-1})^{-1}$
$\displaystyle\lesssim\frac{1}{m}\Big{(}1+\frac{1}{mv^{2}}\Big{)}\,.$ (5.5)

By Lemma 5.1 and (5.5),

$\displaystyle\phantom{\,.}\mathbf{E}|\sigma_{k}b_{k}\varepsilon_{k}|^{2}$
$\displaystyle\lesssim\frac{1}{v^{2}\beta_{n}}\mathbf{E}|\varepsilon_{k}|^{2}\lesssim\frac{1}{nv^{2}}\Big{(}1+\frac{1}{mv^{2}}\Big{)}\,.$
(5.6)

Thus,

$\displaystyle\phantom{\,.}\mathbf{E}|s_{n}(z)-\mathbf{E}s_{n}(z)|^{2}$
$\displaystyle\lesssim\frac{1}{n^{2}}\sum_{k=1}^{n}\mathbf{E}|\gamma_{k}|^{2}$
$\displaystyle\lesssim\frac{1}{n^{2}}\Big{(}\frac{1}{\beta_{n}}+\frac{1}{v^{2}}+\frac{1}{mv^{4}}\Big{)}\,.$
(5.7)

∎

######  Lemma 5.3.

Let $z=u+iv$ be a bounded sequence where $u\geq 1+(2+\eta)\sqrt{\beta_{n}}$
and $v\geq 1/\sqrt{m}$. Then,

$\phantom{\,.}|\mathbf{E}s_{n}(z)-\bar{s}_{n}(z)|\lesssim\frac{1}{nv}\,.$

###### Proof.

Recall definitions (5.1). We have

$\displaystyle\phantom{\,,}\tilde{b}_{k}^{-1}-\bar{b}_{n}^{-1}=\bar{\varepsilon}_{k}\,,$
$\displaystyle\tilde{b}_{k}-\bar{b}_{n}=-\bar{b}_{n}^{2}\bar{\varepsilon}_{k}+\bar{b}_{n}^{2}\tilde{b}_{k}\bar{\varepsilon}_{k}^{2}\,.$

Together with Theorem A.4 of [5], this leads to the following decomposition of
$s_{n}(z)$:

$\displaystyle\phantom{\,.}s_{n}(z)$
$\displaystyle=\frac{1}{n}\sum_{k=1}^{n}\tilde{b}_{k}=\bar{b}_{n}+\frac{1}{n}\sum_{k=1}^{n}(-\bar{b}_{n}^{2}\bar{\varepsilon}_{k}+\bar{b}_{n}^{2}\tilde{b}_{k}\bar{\varepsilon}_{k}^{2})\,.$
(5.8)

(8.3.12) of [5] proves the moment bound $|\mathbf{E}\bar{\varepsilon}_{k}|\leq
1/(mv_{n})$. The second moment of $\bar{\varepsilon}_{k}$ is bounded as
follows:

$\displaystyle\phantom{\,.}\mathbf{E}|\bar{\varepsilon}_{k}|^{2}$
$\displaystyle\lesssim\mathbf{E}|\bar{\varepsilon}_{k}-\mathbf{E}(\bar{\varepsilon}_{k}|X_{nk})|^{2}+\mathbf{E}|\mathbf{E}(\bar{\varepsilon}_{k}|X_{nk})-\mathbf{E}\bar{\varepsilon}_{k}|^{2}+|\mathbf{E}\bar{\varepsilon}_{k}|^{2}\,,$
(5.9)

$\mathbf{E}|\bar{\varepsilon}_{k}-\mathbf{E}(\bar{\varepsilon}_{k}|X_{nk})|^{2}=\mathbf{E}|\varepsilon_{k}|^{2}$
is bounded in the previous lemma. By (5.2),

$\displaystyle\mathbf{E}|\mathbf{E}(\bar{\varepsilon}_{k}|X_{nk})-\mathbf{E}\bar{\varepsilon}_{k}|^{2}$
$\displaystyle=\frac{1}{m^{2}}\mathbf{E}\big{|}\mathrm{tr}(S_{nk}-zI_{n-1})^{-1}S_{nk}-\mathbf{E}\mathrm{tr}(S_{nk}-zI_{n-1})^{-1}S_{nk}\big{|}^{2}$
$\displaystyle=\frac{|z|^{2}}{m^{2}}\mathbf{E}\big{|}\mathrm{tr}(S_{nk}-zI_{n-1})^{-1}-\mathbf{E}\mathrm{tr}(S_{nk}-zI_{n-1})^{-1}\big{|}^{2}$
$\displaystyle\leq|z|^{2}\beta_{n}^{2}\mathbf{E}|s_{n}(z)-\mathbf{E}s_{n}(z)|^{2}+\frac{2|z|^{2}}{m^{2}v^{2}}\,.$
(5.10)

By (5.8) - (5.10) and Lemmas 5.1 and 5.2,

$\displaystyle\phantom{\,.}|\mathbf{E}s_{n}(z)-\bar{b}_{n}|$
$\displaystyle\lesssim\frac{1}{n\beta_{n}}\sum_{k=1}^{n}|\mathbf{E}\bar{\varepsilon}_{k}|+\frac{1}{nv\beta_{n}}\sum_{k=1}^{n}\mathbf{E}|\bar{\varepsilon}_{k}|^{2}$
$\displaystyle\lesssim\frac{1}{nv}+\frac{1}{v\beta_{n}}\Big{(}\frac{1}{m}+\frac{1}{m^{2}v^{2}}+\beta_{n}^{2}\mathbf{E}|s_{n}(z)-\mathbf{E}s_{n}(z)|^{2}\Big{)}$
$\displaystyle\lesssim\frac{1}{nv}\,.$ (5.11)

The above bound describes an equation that is quadratic in
$\mathbf{E}s_{n}(z)$:

$\displaystyle\phantom{\,,}\mathbf{E}s_{n}(z)-\frac{1}{1-z-\beta_{n}-\beta_{n}z\mathbf{E}s_{n}(z)}=\delta_{n}\,,$
(5.12)

where $\delta_{n}\coloneqq\mathbf{E}s_{n}(z)-\bar{b}_{n}$ obeys
$|\delta_{n}|\lesssim 1/(nv)\leq 1/\sqrt{n\beta_{n}}$ (note that
$\bar{s}_{n}(z)$ is a solution of the related equation
$s=(1-z-\beta_{n}s)^{-1})$. By (3.3.8) of [5], (5.12) has a unique solution
satisfying the requirement that $\mathbf{E}s_{n}(u+iv)\rightarrow 0$ as
$v\rightarrow\infty$:

$\phantom{\,.}\mathbf{E}s_{n}(z)=\frac{1}{2\beta_{n}z}\big{(}1-z-\beta_{n}+\beta_{n}z\delta_{n}+\sqrt{(z+\beta_{n}-1+\beta_{n}z\delta_{n})^{2}-4\beta_{n}z}\big{)}\,.$

Thus,

$\displaystyle\phantom{\,.}|\mathbf{E}s_{n}(z)-\bar{s}_{n}(z)|$
$\displaystyle=\frac{1}{2}\bigg{|}\delta_{n}+\frac{2(z+\beta_{n}-1)\delta_{n}+\beta_{n}z\delta_{n}^{2}}{\sqrt{(z+\beta_{n}-1)^{2}-4\beta_{n}z}+\sqrt{(z+\beta_{n}-1+\beta_{n}z\delta_{n})^{2}-4\beta_{n}z}}\bigg{|}$
$\displaystyle\leq\frac{|\delta_{n}|}{2}\bigg{(}1+\frac{|2(z+\beta_{n}-1)+\beta_{n}z\delta_{n})|}{|\sqrt{(z+\beta_{n}-1)^{2}-4\beta_{n}z}+\sqrt{(z+\beta_{n}-1+\beta_{n}z\delta_{n})^{2}-4\beta_{n}z}|}\bigg{)}$
$\displaystyle\lesssim\frac{1}{nv}\,.$ (5.13)

∎

###### Proof of Theorem 1.3.

Consider $z$ satisfying $|z-u|\leq n^{-1/4}\sqrt{\beta_{n}}$. Let
$z^{\prime}=u+in^{-1/4}\sqrt{\beta_{n}}$. We will decompose
$|s_{n}(z)-\bar{s}_{n}(z)|$ as

$\displaystyle\phantom{\,.}|s_{n}(z)-\bar{s}_{n}(z)|$
$\displaystyle\leq|s_{n}(z)-s_{n}(z^{\prime})|+|s_{n}(z^{\prime})-\bar{s}_{n}(z^{\prime})|+|\bar{s}_{n}(z)-\bar{s}_{n}(z^{\prime})|\,.$

and bound each term. $|s_{n}(z)-s_{n}(z^{\prime})|$ is bounded in the proof of
Lemma 2.17. By Lemmas 5.2 and 5.3,

$\displaystyle\phantom{\,.}|s_{n}(z^{\prime})-\bar{s}_{n}(z^{\prime})|\lesssim\frac{1}{n^{\ell}\sqrt{\beta_{n}}}\,,$
(5.14)

almost surely. As $u$ is bounded away from the support of $\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{n}$ by a constant
multiple of $\sqrt{\beta_{n}}$ (2.10),

$\displaystyle\phantom{\,.}|\bar{s}_{n}(z)-\bar{s}_{n}(z^{\prime})|$
$\displaystyle\leq\int\Big{|}\frac{1}{\lambda-z}-\frac{1}{\lambda-z^{\prime}}\Big{|}d\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{n}(\lambda)$
$\displaystyle=\int\frac{|z-z^{\prime}|}{|\lambda-z||\lambda-z^{\prime}|}d\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{n}(\lambda)$
$\displaystyle\lesssim\frac{1}{n^{1/4}\sqrt{\beta_{n}}}\,.$ (5.15)

∎

###### Proof of Corollary 1.3.1.

Consider $z$ satisfying $|z-u|\leq n^{-1/8}\sqrt{\beta_{n}}$. Let
$v=n^{-1/8}\sqrt{\beta_{n}}$ and $z^{\prime}=u+iv$. We will decompose
$|\frac{d}{dz}(s_{n}(z)-\bar{s}_{n}(z))|$ as

$\displaystyle\Big{|}\frac{d}{dz}\big{(}s_{n}(z)-\bar{s}_{n}(z)\big{)}\Big{|}$
$\displaystyle\leq\Big{|}\frac{d}{dz}\big{(}s_{n}(z)-s_{n}(z^{\prime})\big{)}\Big{|}+\Big{|}\frac{d}{dz}\big{(}s_{n}(z^{\prime})-\bar{s}_{n}(z^{\prime})\big{)}\Big{|}+\Big{|}\frac{d}{dz}\big{(}\bar{s}_{n}(z)-\bar{s}_{n}(z^{\prime})\big{)}\Big{|}$

and bound each term. For $1\leq\alpha\leq n$, by the almost-sure eventual
spacing bound (2.11) and $|z-z^{\prime}|\leq 2n^{-1/8}\sqrt{\beta_{n}}$,

$\phantom{\,.}\bigg{|}\frac{1}{(\lambda_{\alpha}-z)^{2}}-\frac{1}{(\lambda_{\alpha}-z^{\prime})^{2}}\bigg{|}=\frac{|z-z^{\prime}||2\lambda_{\alpha}-z-z^{\prime}|}{|\lambda_{\alpha}-z|^{2}|\lambda_{\alpha}-z^{\prime}|^{2}}\leq\frac{32}{\eta^{3}n^{1/8}\beta_{n}}\,.$

Thus, almost surely,

$\displaystyle\Big{|}\frac{d}{dz}\big{(}s_{n}(z)-s_{n}(z^{\prime})\big{)}\Big{|}$
$\displaystyle\leq\sum_{\alpha=1}^{n}\bigg{|}\frac{1}{(\lambda_{\alpha}-z)^{2}}-\frac{1}{(\lambda_{\alpha}-z^{\prime})^{2}}\bigg{|}$
$\displaystyle\lesssim\frac{1}{n^{1/8}\beta_{n}}\,.$ (5.16)

Note that

$\displaystyle\bigg{|}\frac{1}{(\lambda-z^{\prime})^{2}}-\frac{1}{(\lambda-u)^{2}+v^{2}}\bigg{|}\leq\frac{2v}{|\lambda-u|^{3}}\,,$
$\displaystyle\frac{1}{(\lambda-u)^{2}+v^{2}}=\Im\Big{(}\frac{1}{v(\lambda-z)}\Big{)}\,.$

Hence,

$\displaystyle\Big{|}\frac{d}{dz}\big{(}s_{n}(z^{\prime})-\bar{s}_{n}(z^{\prime})\big{)}\Big{|}$
$\displaystyle=\bigg{|}\int\frac{1}{(\lambda-z^{\prime})^{2}}dF_{n}(\lambda)-\int\frac{1}{(\lambda-z^{\prime})^{2}}d\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{n}(\lambda)\bigg{|}$
$\displaystyle\leq\bigg{|}\int\frac{1}{(\lambda-z^{\prime})^{2}}-\frac{1}{(\lambda-u)^{2}+v^{2}}(dF_{n}-d\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern
1.5mu_{n})(\lambda)\bigg{|}+\frac{1}{v}\bigg{|}\int\frac{1}{\lambda-z^{\prime}}(dF_{n}-d\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{n})(\lambda)\bigg{|}$
$\displaystyle\leq 2v\int\frac{1}{|\lambda-u|^{3}}(dF_{n}+d\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern
1.5mu_{n})(\lambda)+\frac{1}{v}|s_{n}(z^{\prime})-\bar{s}_{n}(z^{\prime})|\,.$

We bound the first term above using Lemma 2.4 and the second using Theorem
1.3: almost surely,

$\displaystyle\phantom{\,.}\Big{|}\frac{d}{dz}\big{(}s_{n}(z^{\prime})-\bar{s}_{n}(z^{\prime})\big{)}\Big{|}\lesssim\frac{v}{\beta_{n}^{3/2}}+\frac{1}{n^{\ell+1/8}v\sqrt{\beta_{n}}}\,.$
(5.17)

Finally, by (2.10),

$\displaystyle\Big{|}\frac{d}{dz}\big{(}\bar{s}_{n}(z)-\bar{s}_{n}(z^{\prime})\big{)}\Big{|}$
$\displaystyle\leq\int\bigg{|}\frac{1}{(\lambda-z)^{2}}-\frac{1}{(\lambda-z)^{2}}\bigg{|}d\mkern
1.5mu\overline{\mkern-1.5muF\mkern-1.5mu}\mkern 1.5mu_{n}(\lambda)$
$\displaystyle\lesssim\frac{1}{n^{1/8}\beta_{n}}\,.$ (5.18)

∎

##  6 Appendix

######  Lemma 6.1.

(Theorem 1 of [13]) Let $X_{n}=(X_{i,j}:1\leq i\leq n,1\leq j\leq m)$ be an
array of i.i.d. real-valued random variables with $\mathbf{E}X_{11}=0$,
$\mathbf{E}X_{11}^{2}=1$, and $\mathbf{E}X_{11}^{4}<\infty$. Suppose that as
$n\rightarrow\infty$, $\beta_{n}=n/m_{n}\rightarrow 0$. Define

$\phantom{\,.}A_{n}=\frac{1}{2\sqrt{\beta_{n}}}\Big{(}\frac{1}{m}X_{n}X_{n}^{\prime}-I_{n}\Big{)}\,.$

Then,

$\phantom{\,,}\lambda_{max}(A_{n})\xrightarrow{a.s.}1\,,$

where $\lambda_{max}(A_{n})$ represents the largest eigenvalue of $A_{n}$.

######  Lemma 6.2.

(Theorem 2 of [13]) In the setting of Lemma 6.1, let $\widetilde{X}_{n}$
denote $X_{n}$ after truncation and normalization:

$\displaystyle\widehat{X}_{ij}=X_{ij}I(|X_{ij}|\leq\delta_{n}(nm)^{1/4})\,,$
$\displaystyle\widetilde{X}_{ij}=\frac{\widehat{X}_{ij}-\mathbf{E}\widehat{X}_{11}}{\sigma}\,,$

where
$\sigma^{2}=\mathbf{E}(\widehat{X}_{11}-\mathbf{E}\widehat{X}_{11})^{2}$.
$\delta_{n}$ is a sequence constructed in Section 2 of [13], satisfying
$\delta_{n}\rightarrow 0$ and $\delta_{n}(nm)^{1/4}\rightarrow\infty$. Define

$\phantom{\,.}\widetilde{A}_{n}=\frac{1}{2\sqrt{\beta_{n}}}\Big{(}\frac{1}{m}\widetilde{X}_{n}\widetilde{X}_{n}^{\prime}-I_{n}\Big{)}\,.$

Then, for any $\varepsilon>0,\ell>0$,

$\phantom{\,.}\mathbf{P}(\lambda_{max}(\widetilde{A}_{n})\geq
1+\varepsilon)=o(n^{-\ell})\,.$

Furthermore, $\mathbf{P}(X_{n}\neq\widehat{X}_{n}\,\,i.o.)=0$,

$\displaystyle|\mathbf{E}\widehat{X}_{11}|\lesssim\frac{1}{(nm)^{3/4}}\,,$
$\displaystyle|\sigma^{2}-1|=o\Big{(}\frac{1}{\sqrt{nm}}\Big{)}\,.$

######  Lemma 6.3.

In the setting of Lemma 6.2, let $S_{n}=\frac{1}{m}X_{n}X_{n}^{\prime}$ and
$\widetilde{S}_{n}=\frac{1}{m}\widetilde{X}_{n}\widetilde{X}_{n}^{\prime}$.
Almost surely,

$\phantom{\,,}|\lambda_{i}(S_{n})-\lambda_{i}(\widetilde{S}_{n})|\lesssim\frac{1}{\sqrt{nm}}\,,\hskip
56.9055pt1\leq i\leq n\,.$

Moreover, let $s_{n}(z)$ and $\tilde{s}_{n}(z)$ denote the Stieltjes
transforms of $S_{n}$ and $\widetilde{S}_{n}$, respectively. For $\eta>0$ and
$z=z_{n}$ such that $\Re(z)\geq 1+(2+\eta)\sqrt{\beta_{n}}$, almost surely,

$\displaystyle|s_{n}(z)-\tilde{s}_{n}(z)|\lesssim\frac{1}{n\sqrt{\beta_{n}}}\,,$
$\displaystyle\Big{|}\frac{d}{dz}(s_{n}(z)-\tilde{s}_{n}(z))\Big{|}\lesssim\frac{1}{n\beta_{n}}\,.$

###### Proof.

By Lemma 6.2, almost surely eventually,

$\displaystyle\phantom{\,.}\frac{1}{\sqrt{m}}\|X_{n}-\widetilde{X}_{n}\|_{2}$
$\displaystyle=\frac{1}{\sqrt{m}}\|\widehat{X}_{n}-\widetilde{X}_{n}\|_{2}$
$\displaystyle=\frac{1}{\sqrt{m}}\|\widehat{X}_{n}-\sigma\widetilde{X}_{n}-(1-\sigma)\widetilde{X}_{n}\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{m}}\|(\mathbf{E}\widehat{X}_{11}){\bf
1}_{n}{\bf
1}_{m}^{\prime}\|_{2}+\frac{(\sigma-1)}{\sqrt{m}}\|\widetilde{X}_{n}\|_{2}$
$\displaystyle=\sqrt{n}|\mathbf{E}\widehat{X}_{11}|+\frac{(\sigma^{2}-1)}{\sigma+1}\sqrt{1+2\beta_{n}\lambda_{max}(\widetilde{A}_{n})}$
$\displaystyle\lesssim\frac{1}{\sqrt{nm}}\,.$ (6.1)

Lemmas 6.1 and 6.2 imply almost surely eventually, both $\sigma_{1}(X_{n})\leq
2\sqrt{m}$ and $\sigma_{1}(\widetilde{X}_{n})\leq 2\sqrt{m}$. Using Weyl’s
inequality,

$\displaystyle\phantom{\,.}|\lambda_{i}(S_{n})-\lambda_{i}(\widetilde{S}_{n})|$
$\displaystyle=\frac{1}{m}|\sigma_{i}(X_{n})-\sigma_{i}(\widetilde{X}_{n})||\sigma_{i}(X_{n})+\sigma_{i}(\widetilde{X}_{n})|$
$\displaystyle\lesssim\frac{1}{\sqrt{m}}\|X_{n}-\widetilde{X}_{n}\|_{2}$
$\displaystyle\lesssim\frac{1}{\sqrt{nm}}\,.$

Thus,

$\displaystyle|s_{n}(z)-\tilde{s}_{n}(z)|$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\bigg{|}\frac{1}{\lambda_{i}(S_{n})-z}-\frac{1}{\lambda_{i}(\widetilde{S}_{n})-z}\bigg{|}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\frac{|\lambda_{i}(S_{n})-\lambda_{i}(\widetilde{S}_{n})|}{|\lambda_{i}(S_{n})-z||\lambda_{i}(\widetilde{S}_{n})-z|}$
$\displaystyle\lesssim\frac{1}{n\sqrt{\beta_{n}}}\,,$

$\displaystyle\Big{|}\frac{d}{dz}(s_{n}(z)-\tilde{s}_{n}(z))\Big{|}$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\bigg{|}\frac{1}{(\lambda_{i}(S_{n})-z)^{2}}-\frac{1}{(\lambda_{i}(\widetilde{S}_{n})-z)^{2}}\bigg{|}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\frac{|\lambda_{i}(S_{n})-\lambda_{i}(\widetilde{S}_{n})||\lambda_{i}(S_{n})-\lambda_{i}(\widetilde{S}_{n})-2z|}{|\lambda_{i}(S_{n})-z|^{2}|\lambda_{i}(\widetilde{S}_{n})-z|^{2}}$
$\displaystyle\lesssim\frac{1}{n\beta_{n}}\,.$

∎

######  Lemma 6.4.

Consider the setting of Lemma 6.3. For $i\leq n$ and $P_{n}$ an $n\times m$
matrix, let $U$ and $\widetilde{U}$ denote the first $i$ columns of the left
singular matrices of $P_{n}+\frac{1}{\sqrt{m}}X_{n}$ and
$P_{n}+\frac{1}{\sqrt{m}}\widetilde{X}_{n}$ respectively. Assume that
eventually almost surely,

$\phantom{\,.}\sigma_{i}\big{(}P_{n}+\tfrac{1}{\sqrt{m}}X_{n}\big{)}-\sigma_{i+1}\big{(}P_{n}+\tfrac{1}{\sqrt{m}}X_{n}\big{)}\asymp\sqrt{\beta_{n}}\,.$

Then, almost surely,

$\phantom{\,.}\sqrt{1-\sigma_{i}^{2}(\widetilde{U}^{\prime}U)}\lesssim\frac{1}{n}\,.$

###### Proof.

This follows from the Davis-Kahan sin $\Theta$ theorem (Lemma 6.5) and (6.1).
∎

######  Lemma 6.5.

(Davis-Kahan sin $\Theta$ theorem, Theorem 4.4 of [22]) Let $A$ and
$\widetilde{A}$ be $n\times m$ matrices. For $i\leq\min(n,m)$, let $U$ and
$\widetilde{U}$ denote the first $i$ columns of the left singular matrices of
$A$ and $\widetilde{A}$ respectively. Let
$\gamma=\sigma_{i}(A)-\sigma_{i+1}(A)$. If $\gamma\geq
2\|A-\widetilde{A}\|_{2}$, we have

$\phantom{\,.}\sqrt{1-\sigma_{i}^{2}(\widetilde{U}^{\prime}U)}\leq\frac{\|A-\widetilde{A}\|_{2}}{\gamma-\|A-\widetilde{A}\|_{2}}\,.$

######  Lemma 6.6.

(Lemma 2.7 of [4]) Let $A$ be an $n\times n$ nonrandom matrix and
$x=(x_{1},\ldots,x_{n})^{\prime}$ be a random vector of independent entries.
Assume that $\mathbf{E}x_{i}=0$, $\mathbf{E}|x_{i}|^{2}=1$, and
$\mathbf{E}|x_{j}|^{\ell}\leq\nu_{\ell}$. Then, for any $\ell\geq 1$,

$\phantom{\,,}\mathbf{E}|x^{*}Ax-\mathrm{tr}A|^{\ell}\lesssim_{\ell}(\nu_{4}\mathrm{tr}A^{*}A)^{\ell/2}+\nu_{2\ell}\mathrm{tr}(A^{*}A)^{\ell/2}\,.$

######  Lemma 6.7.

Let $A$ be an $n\times m$ nonrandom matrix and $x\in\mathbb{C}^{n}$,
$y\in\mathbb{C}^{m}$ random vectors. Assume $x$ and $y$ are independent with
entries satisfying the moment conditions of Lemma 6.6. Then, for any $\ell\geq
2$,

$\phantom{\,,}\mathbf{E}|x^{*}Ay|^{\ell}\lesssim_{\ell}(1+\nu_{4}^{\ell/4}+\nu_{\ell})\big{(}(\nu_{4}\mathrm{tr}(A^{*}A)^{2})^{\ell/4}+\nu_{\ell}\mathrm{tr}(A^{*}A)^{\ell/2}+(\mathrm{tr}A^{*}A)^{\ell/2}\big{)}\,.$

###### Proof.

Condition on $y$ and apply Lemma 6.6:

$\displaystyle\phantom{\,.}\mathbf{E}|x^{*}Ay|^{\ell}$
$\displaystyle=\mathbf{E}|x^{*}Ayy^{*}A^{*}x|^{\ell/2}$
$\displaystyle\lesssim_{\ell}\mathbf{E}\Big{(}\mathbf{E}\big{(}|x^{*}Ayy^{*}A^{*}x-\mathrm{tr}Ayy^{*}A^{*}|^{\ell/2}\big{|}y\big{)}+\
(\mathrm{tr}Ayy^{*}A^{*})^{\ell/2}\Big{)}$
$\displaystyle\lesssim_{\ell}\mathbf{E}\big{(}(\nu_{4}\mathrm{tr}Ayy^{*}Ayy^{*}A^{*})^{\ell/4}+\nu_{\ell}\mathrm{tr}(Ayy^{*}A^{*})^{\ell/2}+(\mathrm{tr}Ayy^{*}A^{*})^{\ell/2}\big{)}\,.$

For a positive semi-definite matrix $M$,
$\mathrm{tr}M^{2}\leq(\mathrm{tr}M)^{2}$. Thus,

$\displaystyle\phantom{\,.}\mathbf{E}|x^{*}Ay|^{\ell}$
$\displaystyle\lesssim_{\ell}(1+\nu_{4}^{\ell/4}+\nu_{\ell})\mathbf{E}|y^{*}A^{*}Ay|^{\ell/2}$
$\displaystyle\lesssim_{\ell}(1+\nu_{4}^{\ell/4}+\nu_{\ell})\big{(}\mathbf{E}|y^{*}A^{*}Ay-\mathrm{tr}A^{*}A|^{\ell/2}+(\mathrm{tr}A^{*}A)^{\ell/2}\big{)}$
$\displaystyle\lesssim_{\ell}(1+\nu_{4}^{\ell/4}+\nu_{\ell})\big{(}(\nu_{4}\mathrm{tr}(A^{*}A)^{2})^{\ell/4}+\nu_{\ell}\mathrm{tr}(A^{*}A)^{\ell/2}+(\mathrm{tr}A^{*}A)^{\ell/2}\big{)}\,.$

∎

######  Lemma 6.8.

For any $n\times n$ matrices $A$ and $B$,

$\phantom{\,.}|\det A-\det
B|\lesssim_{n}(\|A\|_{\infty}+\|B\|_{\infty})^{n-1}\|A-B\|_{\infty}\,.$

###### Proof.

Let $a_{1},a_{2},\ldots,a_{n}$ and $b_{1},b_{2},\ldots,b_{n}$ denote real
numbers. We claim

$\phantom{\,.}\bigg{|}\prod_{i=1}^{n}a_{i}-\prod_{i=1}^{n}b_{i}\bigg{|}\leq\Big{(}\max_{1\leq
i\leq n}|a_{i}|+\max_{1\leq i\leq n}|b_{i}|\Big{)}^{n-1}\cdot\max_{1\leq i\leq
n}|a_{i}-b_{i}|\,.$

Clearly the claim holds for $n=1$. By induction,

$\displaystyle\phantom{\,.}\bigg{|}\prod_{i=1}^{n}a_{i}-\prod_{i=1}^{n}b_{i}\bigg{|}$
$\displaystyle\leq|a_{1}-b_{1}|\prod_{i=2}^{n}|a_{2}|+|b_{1}|\bigg{|}\prod_{i=2}^{n}a_{i}-\prod_{i=2}^{n}b_{i}\bigg{|}$
$\displaystyle\leq\Big{(}\max_{1\leq i\leq n}|a_{i}|+\max_{1\leq i\leq
n}|b_{i}|\Big{)}^{n-1}\cdot\max_{1\leq i\leq n}|a_{i}-b_{i}|\,.$

Let $A=(a_{ij})_{n\times n}$ and $B=(b_{ij})_{n\times n}$. The lemma is
obtained by applying the above claim to each term of the Leibniz determinant
formula:

$\phantom{\,.}|\det A-\det B|\leq\sum_{\sigma\in
S_{n}}\bigg{|}\prod_{i=1}^{n}a_{i,\sigma(i)}-\prod_{i=1}^{n}b_{i,\sigma(i)}\bigg{|}\,.$

∎

######  Lemma 6.9.

For any $n\times n$ matrices $A(z)$ and $B(z)$,

$\phantom{\,.}\Big{|}\frac{d}{dz}(\det A-\det
B)\Big{|}\lesssim_{n}\|A\|_{\infty}^{n-1}\Big{\|}\frac{d}{dz}(A-B)\Big{\|}_{\infty}+(\|A\|_{\infty}+\|B\|_{\infty})^{n-2}\Big{\|}\frac{d}{dz}B\Big{\|}_{\infty}\|A-B\|_{\infty}\,.$

Additionally,

$\phantom{\,,}\Big{|}\frac{d}{dz}\det
A\Big{|}\lesssim_{n}\Big{\|}\frac{d}{dz}A\Big{\|}_{\infty}\,.$

###### Proof.

$\displaystyle\phantom{\,.}\Big{|}\frac{d}{dz}(\det A-\det B)\Big{|}$
$\displaystyle\leq\sum_{\sigma\in
S_{n}}\sum_{i=1}^{n}\bigg{|}\Big{(}\frac{d}{dz}a_{i,\sigma(i)}\Big{)}\prod_{j\neq
i}a_{j,\sigma(j)}-\Big{(}\frac{d}{dz}b_{i,\sigma(i)}\Big{)}\prod_{j\neq
i}b_{j,\sigma(j)}\bigg{|}$ $\displaystyle=\sum_{\sigma\in
S_{n}}\sum_{i=1}^{n}\bigg{|}\Big{(}\frac{d}{dz}(a_{i,\sigma(i)}-b_{i,\sigma(i)})\Big{)}\prod_{j\neq
i}a_{j,\sigma(j)}+\Big{(}\frac{d}{dz}b_{i,\sigma(i)}\Big{)}\bigg{(}\prod_{j\neq
i}a_{j,\sigma(j)}-\prod_{j\neq i}b_{j,\sigma(j)}\bigg{)}\bigg{|}\,.$

By Lemma 6.8,

$\phantom{\,.}\bigg{|}\prod_{j\neq i}a_{j,\sigma(j)}-\prod_{j\neq
i}b_{j,\sigma(j)}\bigg{|}\leq(\|A\|_{\infty}+\|B\|_{\infty})^{n-2}\|A-B\|_{\infty}\,.$

∎

###  6.1 Lemmas involving right singular vectors

Consider an array $X_{n}$ satisfying assumption A1 and a vector $v$ satisfying
the assumptions A2 places on right signal vectors. Let $W$ be a matrix
containing as columns the first $n$ (normalized) eigenvectors of
$X_{n}^{\prime}X_{n}$.

######  Lemma 6.10.

Let $S_{n}=\frac{1}{m}X_{n}X_{n}^{\prime}$ and
$A_{n}=\frac{1}{m}X_{n}^{\prime}S_{n}^{-1}X_{n}=WW^{\prime}$. Almost surely,

$\phantom{\,.}v^{\prime}A_{n}v=\|W^{\prime}v\|_{2}^{2}\lesssim\beta_{n}\log(n)\,.$

The proof requires the following two lemmas:

######  Lemma 6.11.

Let $n/m\leq\beta$ for some $\beta\in(0,1]$. There exists constants
$c_{0},c_{1},c_{2}$ depending only on $\mathbf{E}X_{11}^{4}$ such that with
probability at least $1-c_{0}\log(e/\beta)\exp(-c_{1}\beta m)$,

$\phantom{\,.}\frac{1}{\sqrt{m}}\sigma_{\min}(X_{n})\geq
1-c_{2}\sqrt{\beta}\,.$

###### Proof.

This is one case of Theorem 1.3 of [18]. ∎

######  Lemma 6.12.

Let
$\widetilde{A}_{n}=\frac{1}{m}X_{n}^{\prime}(S_{n}+\frac{1}{m}I_{n})^{-1}X_{n}$.
The fourth moment condition on the entries of $\sqrt{m}v$ implies

$\displaystyle\mathbf{E}(v^{\prime}\widetilde{A}_{n}v)\leq\beta_{n}\,,$
$\displaystyle
Var(v^{\prime}\widetilde{A}_{n}v)\lesssim\frac{\beta_{n}^{2}}{n}\,.$

###### Proof of Lemma 6.10.

By Lemma 6.12, eventually,

$\displaystyle\phantom{\,.}\mathbf{P}(v^{\prime}\widetilde{A}_{n}v\geq\beta_{n}\log(n))$
$\displaystyle\leq\mathbf{P}\big{(}v^{\prime}\widetilde{A}_{n}v\geq\mathbf{E}(v^{\prime}\widetilde{A}_{n}v)+\sqrt{n}\log(n)\cdot
SD(v^{\prime}\widetilde{A}_{n}v)\big{)}$
$\displaystyle\leq\frac{1}{n\log^{2}(n)}\,.$

Summability of the right-hand-side gives
$v^{\prime}\widetilde{A}_{n}v\leq\beta_{n}\log(n)$ almost surely eventually.

Let $\lambda_{1}\geq\lambda_{2}\cdots\geq\lambda_{n}$ denote the eigenvalues
of $S_{n}$ and $\Lambda=\text{diag}(\lambda_{1},\ldots,\lambda_{n})$. Observe
that the eigenvalues of
$\widetilde{A}_{n}=W\Lambda^{1/2}(\Lambda+\frac{1}{m}I_{n})^{-1}\Lambda^{1/2}W^{\prime}$
are $\frac{\lambda_{j}}{\lambda_{j}+\frac{1}{m}}$, $j=1,\ldots,n$, joined by a
zero eigenvalue with multiplicity $m-n$. A first consequence of Lemma 6.11 is
$\lambda_{n}\gtrsim 1$ almost surely. Hence,

$\displaystyle\phantom{\,.}v^{\prime}A_{n}v$ $\displaystyle\leq
v^{\prime}\widetilde{A}_{n}v+\|v\|_{2}^{2}\lambda_{\max}(A_{n}-\widetilde{A}_{n})$
$\displaystyle\leq
v^{\prime}\widetilde{A}_{n}v+\frac{\|v\|_{2}^{2}}{1+m\lambda_{n}}$
$\displaystyle\lesssim\beta_{n}\log(n)\,,\,$

almost surely. ∎

###### Proof of Lemma 6.12.

As $X_{n}$ and $v$ are independent,

$\displaystyle\mathbf{E}(v^{\prime}\widetilde{A}_{n}v)^{2}$
$\displaystyle=\sum_{j_{1},j_{2},j_{3},j_{4}=1}^{m}\mathbf{E}(v_{j_{1}}v_{j_{2}}v_{j_{3}}v_{j_{4}})\mathbf{E}(\widetilde{A}_{j_{1}j_{2}}\widetilde{A}_{j_{3}j_{4}})\,.$
(6.2)

Any term $\mathbf{E}(v_{j_{1}}v_{j_{2}}v_{j_{3}}v_{j_{4}})$ containing a
singleton index vanishes, leaving the following terms:

$\displaystyle j_{1}=\dots=j_{4}:$
$\displaystyle\frac{\nu_{4}}{m^{2}}\sum_{j}\mathbf{E}\widetilde{A}_{jj}^{2}\,,$
$\displaystyle\hskip 102.43008ptj_{1}=j_{2},j_{3}=j_{4},j_{1}\neq j_{3}:$
$\displaystyle\frac{1}{m^{2}}\sum_{j_{1},j_{3}}\mathbf{E}(\widetilde{A}_{j_{1}j_{1}}\widetilde{A}_{j_{3}j_{3}})\,,$
$\displaystyle j_{1}=j_{3},j_{2}=j_{4},j_{1}\neq j_{2}:$
$\displaystyle\frac{1}{m^{2}}\sum_{j_{1},j_{2}}\mathbf{E}\widetilde{A}_{j_{1}j_{2}}^{2}\,,$
$\displaystyle j_{1}=j_{4},j_{2}=j_{3},j_{1}\neq j_{2}:$
$\displaystyle\frac{1}{m^{2}}\sum_{j_{1},j_{2}}\mathbf{E}\widetilde{A}_{j_{1}j_{2}}^{2}\,,$

where $\nu_{4}=m^{2}\mathbf{E}v_{1}^{4}<\infty$. Let $x_{j}$ denote the $j$-th
column of $X_{n}$ and $B_{j}=S_{n}+\frac{1}{m}(I_{n}-x_{j}x_{j}^{\prime})$. By
the Sherman-Morrison formula,

$\displaystyle\mathbf{E}\widetilde{A}_{jj}^{2}$
$\displaystyle=\frac{1}{m^{2}}\mathbf{E}\big{(}x_{j}^{\prime}(S_{n}+\tfrac{1}{m}I_{n})^{-1}x_{j}\big{)}^{2}$
$\displaystyle=\frac{1}{m^{2}}\mathbf{E}\bigg{(}x_{j}^{\prime}B_{j}^{-1}x_{j}-\frac{(x_{j}^{\prime}B_{j}^{-1}x_{j})^{2}}{m+x_{j}^{\prime}B_{j}^{-1}x_{j}}\bigg{)}^{2}$
$\displaystyle=\frac{1}{m^{2}}\mathbf{E}\bigg{(}\frac{x_{j}^{\prime}B_{j}^{-1}x_{j}}{1+\tfrac{1}{m}x_{j}^{\prime}B_{j}^{-1}x_{j}}\bigg{)}^{2}$
$\displaystyle\leq\frac{1}{m^{2}}\mathbf{E}(x_{j}^{\prime}B_{j}^{-1}x_{j})^{2}$
$\displaystyle\leq\frac{1}{m^{2}}\mathbf{E}\|x_{j}\|_{2}^{4}\,\mathbf{E}\lambda_{\max}(B_{j}^{-1})^{2}\,,$

where the final inequality follows from the independence of $x_{j}$ and
$B_{j}$. Lemma 6.11 and the almost-sure lower bound $\lambda_{\min}(B_{j})\geq
1/m$ imply $\mathbf{E}\lambda_{\max}(B_{j}^{-1})^{2}\lesssim 1$. Moreover,
$\mathbf{E}\|x_{j}\|_{2}^{4}=n\nu_{4}+(n^{2}-n)\nu_{2}^{2}$. Thus,

$\displaystyle\phantom{\,.}\mathbf{E}|\widetilde{A}_{jj}|^{2}\lesssim\beta_{n}^{2}\,.$
(6.3)

Next, consider terms of the third and fourth types. Let
$B_{j_{1},j_{2}}=S_{n}+\frac{1}{m}(I_{n}-x_{j_{1}}x_{j_{1}}^{\prime}-x_{j_{2}}x_{j_{2}}^{\prime})$.
By the Woodbury formula,

$\displaystyle\mathbf{E}\widetilde{A}_{j_{1},j_{2}}^{2}$
$\displaystyle=\frac{1}{m^{2}}\mathbf{E}\big{(}x_{j_{1}}^{\prime}(S_{n}+\tfrac{1}{m}I_{n})^{-1}x_{j_{2}}\big{)}^{2}$
$\displaystyle=\frac{1}{m^{2}}\mathbf{E}\bigg{(}\frac{x_{j_{1}}^{\prime}B_{j_{1},j_{2}}^{-1}x_{j_{2}}}{(1+\tfrac{1}{m}x_{j_{1}}^{\prime}B_{j_{1},j_{2}}^{-1}x_{j_{1}})(1+\tfrac{1}{m}x_{j_{2}}^{\prime}B_{j_{1},j_{2}}^{-1}x_{j_{2}})-(\tfrac{1}{m}x_{j_{1}}^{\prime}B_{j_{1},j_{2}}^{-1}x_{j_{2}})^{2}}\bigg{)}^{2}$
$\displaystyle\leq\frac{1}{m^{2}}\mathbf{E}(x_{j_{1}}^{\prime}B_{j_{1},j_{2}}^{-1}x_{j_{2}})^{2}$
$\displaystyle\leq\frac{1}{m^{2}}\mathbf{E}\langle
x_{j_{1}},x_{j_{2}}\rangle^{2}\mathbf{E}\lambda_{\max}(B_{j_{1},j_{2}}^{-1})^{2}\,.$

The second-to-last inequality follows from the Cauchy-Schwarz inequality. The
final step uses the independence of $B_{j_{1},j_{2}}$ from $x_{j_{1}}$ and
$x_{j_{2}}$. We have that
$\mathbf{E}\lambda_{\max}(B_{j_{1},j_{2}}^{-1})^{2}\lesssim 1$ and
$\mathbf{E}\langle x_{j_{1}},x_{j_{2}}\rangle^{2}=n$. Therefore,

$\displaystyle\phantom{\,.}\mathbf{E}\widetilde{A}_{j_{1},j_{2}}^{2}\lesssim\frac{\beta_{n}}{m}\,.$
(6.4)

As the non-zero eigenvalues of
$\widetilde{A}_{n}=W\Lambda^{1/2}(\Lambda+\frac{1}{m}I_{n})^{-1}\Lambda^{1/2}W^{\prime}$
are $\frac{\lambda_{j}}{\lambda_{j}+\frac{1}{m}}$, $j=1,\ldots,n$,

$\displaystyle\mathbf{E}(v^{\prime}\widetilde{A}_{n}v)$
$\displaystyle=\frac{1}{m}\mathbf{E}\mathrm{tr}\widetilde{A}_{n}=\frac{1}{m}\sum_{j=1}^{n}\mathbf{E}\Big{(}\frac{\lambda_{j}}{\lambda_{j}+\frac{1}{m}}\Big{)}$
$\displaystyle\leq\beta_{n}\,,$
$\displaystyle\mathbf{E}|\mathrm{tr}\widetilde{A}_{n}-n|$
$\displaystyle\leq\sum_{j=1}^{n}\mathbf{E}\Big{|}\frac{1}{1+m\lambda_{j}}\Big{|}$
$\displaystyle\lesssim\beta_{n}\,,$
$\displaystyle\mathbf{E}\big{|}(\mathrm{tr}\widetilde{A}_{n})^{2}-n^{2}\big{|}$
$\displaystyle\leq\sum_{j_{1},j_{2}=1}^{n}\mathbf{E}\Big{|}\frac{1+m(\lambda_{j_{1}}+\lambda_{j_{2}})}{(1+m\lambda_{j_{1}})(1+m\lambda_{j_{2}})}\Big{|}$
$\displaystyle\lesssim n\beta_{n}\,.$

We have used that by Lemma 6.11, there exists $c>0$ such that with high
probability, $\lambda_{n}\geq c$. On this event,

$\displaystyle\phantom{\,.}\Big{|}\frac{1+m(\lambda_{j_{1}}+\lambda_{j_{2}})}{(1+m\lambda_{j_{1}})(1+m\lambda_{j_{2}})}\Big{|}$
$\displaystyle=\frac{\lambda_{j_{1}}^{-1}\lambda_{j_{2}}^{-1}+m(\lambda_{j_{1}}^{-1}+\lambda_{j_{2}}^{-1})}{\lambda_{j_{1}}^{-1}\lambda_{j_{2}}^{-1}+m(\lambda_{j_{1}}^{-1}+\lambda_{j_{2}}^{-1})+m^{2}}\leq\frac{c^{-2}+2c^{-1}m}{c^{-2}+2c^{-1}m+m^{2}}\,.$

Thus,

$\displaystyle\bigg{|}\frac{1}{m^{2}}\sum_{j_{1},j_{3}}\mathbf{E}(\widetilde{A}_{j_{1}j_{1}}\widetilde{A}_{j_{3}j_{3}})-(\mathbf{E}v^{\prime}\widetilde{A}_{n}v)^{2}\bigg{|}$
$\displaystyle=\frac{Var(\mathrm{tr}\widetilde{A}_{n})}{m^{2}}$
$\displaystyle\leq\frac{1}{m^{2}}|\mathbf{E}(\mathrm{tr}\widetilde{A}_{n})^{2}-n^{2}|+\frac{1}{m^{2}}|(\mathbf{E}\mathrm{tr}\widetilde{A}_{n})^{2}-n^{2}|$
$\displaystyle\lesssim\frac{\beta_{n}^{2}}{m}\,.$ (6.5)

$Var(v^{\prime}\widetilde{A}_{n}v)\lesssim n^{-1}\beta_{n}^{2}$ follows from
(6.2) - (6.5). ∎

## References

  * [1] R. Adamczak. On the Marchenko-Pastur and circular laws for some classes of random matrices with dependent entries. Electronic Journal of Probability, 16:1068-1095, 2011.
  * [2] Z. Bai, J. Hu, and W. Zhou. Convergence rates to the Marchenko-Pastur type distribution. Stochastic Processes and their Applications, 122:68-92, 2012.
  * [3] Z. Bai and Y. Yin. Convergence to the Semicircle Law. The Annals of Probability, 16(2):863-875, 1988.
  * [4] Z. Bai and J. Silverstein. No eigenvalues outside the support of the limiting spectral distribution of large-dimensional sample covariance matrices. The Annals of Probability, 26:316–345, 1998.
  * [5] Z. Bai and J. Silverstein. Spectral Analysis of Large Dimensional Random Matrices. Springer, 2010.
  * [6] Z. Bai and W. Zhou. Large Sample Covariance Matrices without Independence Structures in Columns. Statistica Sinica, 18:425-442, 2008.
  * [7] J. Baik and J. Silverstein. Eigenvalues of large sample covariance matrices of spiked population models. Journal of Multivariate Analysis, 97(6):1382–1408, 2006.
  * [8] G. Ben Arous, S. Mei, A. Montanari, and M. Nica. The landscape of the spiked tensor model. Communications on Pure and Applied Mathematics, 72:2282-2330, 2019.
  * [9] F. Benaych-Georges, A. Guionnet, and M. Maïda. Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices. Electronic Journal of Probability, 16:1621-1662, 2011.
  * [10] F. Benaych-Georges and R. Rao Nadakuditi. The eigenvalues and eigenvectors of low rank perturbations of large random matrices. Advances in Mathematics, 227(1):494–521, 2011.
  * [11] F. Benaych-Georges and R. Rao Nadakuditi. The singular values and vectors of low rank perturbations of large rectangular random matrices. Journal of Multivariate Analysis, 111:120–135, 2012.
  * [12] T. Cai, X. Han, and G. Pan. Limiting Laws for Divergent Spiked Eigenvalues and Largest Nonspiked Eigenvalue of Sample Covariance Matrices. The Annals of Statistics, 48(3):1255-1280, 2020.
  * [13] B. Chen and G. Pan. Convergence of the largest eigenvalue of normalized sample covariance matrices when p and n both tend to infinity with their ratio converging to zero. Bernoulli, 18(4):1405-1420, 2012.
  * [14] D. Donoho, M. Gavish, and I. Johnstone. Optimal Shrinkage of Eigenvalues in the Spiked Covariance Model. The Annals of Statistics, 46(4):1742-1778, 2018.
  * [15] D. Donoho, M. Gavish, and I. Johnstone. Supplementary Material for “Optimal Shrinkage of Eigenvalues in the Spiked Covariance Model.” http://purl.stanford.edu/xy031gt1574. 2016.
  * [16] M. Gavish and D. Donoho. The Optimal Hard Threshold for Singular Values is $4/\sqrt{3}$. IEEE Transactions on Information Theory, 60:5040-5053, 2014.
  * [17] S. Hopkins, T. Schramm, J. Shi, D. Steurer. Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 178–191, 2016.
  * [18] V. Koltchinskii and S. Mendelson. Bounding the Smallest Singular Value of a Random Matrix Without Concentration. International Mathematics Research Notices, 2015(23):12991-13008, 2015.
  * [19] A. Montanari and E. Richard. A statistical model for tensor PCA. Proceedings of the 27th International Conference on Neural Information Processing Systems, 2:2897–2905, 2014.
  * [20] J. Novembre et. al. Genes mirror geography within Europe. Nature, 456:98-101, 2008.
  * [21] D. Paul. Asymptotics of Sample Eigenstructure for a Large Dimensional Spiked Covariance Model. Statistica Sinica, 17:1617-1642, 2007.
  * [22] G. Stewart and J. Sun. Matrix Perturbation Theory (Computer Science and Scientific Computing. Academic Press Boston, 1990.
  * [23] R. Vershynin. How Close is the Sample Covariance Matrix to the Actual Covariance Matrix? Journal of Theoretical Probability, 25:655–686, 2012.
  * [24] M. Wainwright. High-Dimensional Statistics. Cambridge, 2019.
  * [25] J. Yao, S. Zheng, and Z. Bai. Large Sample Covariance Matrices and High-Dimensional Data Analysis. Cambridge, 2015.