$\displaystyle\mathbb{P}\Big{(}M_{i,j}^{\star}\in\mathsf{CI}_{i,j}^{1-\alpha}\Big{)}=1-\alpha+o(1).$
(4.81)

In order to help interpret the applicable range of Theorem 4.7.1, let us focus
on the simple scenario with $\kappa,\mu,r\asymp 1$ to simplify discussion.

  * •

First of all, Condition (4.79) can be simplified as

$np\gtrsim\log n\quad\text{and}\quad\sigma_{\eta}\sqrt{\frac{n\log
n}{p}}\lesssim|\lambda_{r}^{\star}|.$

The first condition on the sampling size coincides with the fundamental
requirement even if the goal is merely to enable reliable estimation
[candes2010NearOptimalMC], whereas the second condition on the signal-to-noise
ratio is also necessary—up to some log factor—to ensure an estimation quality
better than that of a random guess [cai2019subspace, Theorem 3.3].

  * •

Next, we move on to interpret the other condition (4.80) imposed in our
theory, which simplifies to

$\frac{\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}}{\big{\|}\bm{U}^{\star}\big{\|}_{\mathrm{F}}^{2}}\gtrsim\frac{\log^{3}n}{n\sqrt{np}}+\frac{\sigma_{\eta}\log^{3}n}{|\lambda_{r}^{\star}|\sqrt{np}}.$

Let us consider the most challenging case where $np\gtrsim\mathrm{poly}\log n$
and $\sigma_{\eta}\sqrt{\frac{n\mathrm{poly}\log
n}{p}}\lesssim|\lambda_{r}^{\star}|$ (for some sufficiently large poly-log
factor). In such a case, the above condition only requires

$\frac{\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}}{\big{\|}\bm{U}^{\star}\big{\|}_{\mathrm{F}}^{2}}\gtrsim\frac{1}{n\mathrm{poly}\log
n},$

indicating that the associated signal power
$\|\bm{U}_{j,\cdot}^{\star}\|_{2}^{2}+\|\bm{U}_{i,\cdot}^{\star}\|_{2}^{2}$ is
allowed to be much smaller than the average signal power across all rows
(which can be captured by $\|\bm{U}^{\star}\|_{\mathrm{F}}^{2}/n$).

In a nutshell, the validity of our inference procedure is ensured for broad
settings. Additionally, we have conducted a series of numerical experiments to
examine the entrywise distributions of $\bm{M}$. As illustrated in Figure 4.3,
the normalized estimation error
$(\widehat{v}_{i,j})^{-1/2}(\widehat{M}_{i,j}-M_{i,j}^{\star})$ is close in
distribution to a standard Gaussian random variable, which corroborates our
theory on the confidence interval construction.

Before concluding, we would like to remark that: while the distributional
theory for spectral methods allows for valid construction of confidence
intervals for an unseen entry, it is oftentimes not among the most effective
statistical inference procedures that one can put forward. There exist other
alternatives that are provably more efficient, including but not limited to
inference procedures based on convex relaxation and nonconvex optimization
[chen2019inference, xia2021statistical], and the ones based on more refined
spectral methods [yan2021inference, chernozhukov2021inference].

|
---|---
(a) | (b)
Figure 4.3: Entrywise numerical distribution for noisy matrix completion. We
generate $\bm{M}^{\star}=\bm{U}^{\star}\bm{U}^{\star\top}$ with
$\bm{U}^{\star}$ being a random orthonormal matrix, and analyze the behavior
of $Z_{1,2}=(\widehat{v}_{1,2})^{-0.5}(\widehat{M}_{1,2}-M_{1,2}^{\star})$,
where $\widehat{\bm{M}}$ is defined in (4.63) and $\widehat{v}_{i,j}$ is
defined in (4.71). The results are reported for 500 Monte Carlo trials when
$p=0.3$, $n=1000$, $\sigma_{\eta}=10^{-4}$, and $r=3$. (a) Histogram of the
empirical distribution of $Z_{1,2}$; (b) Q-Q (quantile-quantile) plot of
$Z_{1,2}$ vs. the standard normal distribution.

###### Proof of Theorem 4.7.1.

Given that $\eta_{i,j}$ is a Gaussian random variable and hence possibly
unbounded, we find it convenient to introduce a truncated version as follows

$\widetilde{\eta}_{i,j}=\eta_{i,j}\mathbbm{1}\big{\\{}|\eta_{i,j}|\leq
5\sigma_{\eta}\sqrt{\log n}\big{\\}},\qquad 1\leq i,j\leq n.$

and

$\widetilde{M}_{i,j}=\begin{cases}\frac{1}{p}\big{(}M_{i,j}^{\star}+\widetilde{\eta}_{i,j}\big{)},\qquad&\text{if
}(i,j)\in\Omega,\\\ 0,&\text{else}.\end{cases}$

Repeating the analysis in Section 3.2.3, we can show that

$\mathbb{P}\big{\\{}\bm{M}=\widetilde{\bm{M}}\big{\\}}=\mathbb{P}\big{\\{}\eta_{i,j}=\widetilde{\eta}_{i,j},\forall
i,j\in[n]\big{\\}}\geq 1-n^{-10},$

meaning that $\bm{M}$ and $\widetilde{\bm{M}}$ are equivalent with high
probability. As a result, we shall concentrate on validating the confidence
interval computed based on $\widetilde{\bm{M}}$ in the subsequent analysis.
Before proceeding, we record several key properties about
$\widetilde{\eta}_{i,j}$ as follows:

$\displaystyle\mathbb{E}[\widetilde{\eta}_{i,j}]=0,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\mathbb{E}[\widetilde{\eta}^{2}_{i,j}]=(1-o(1))\sigma_{\eta}^{2},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\big{|}\widetilde{\eta}_{i,j}\big{|}\leq 5\sigma_{\eta}\sqrt{\log n}.$ (4.82)

The proof follows by invoking Theorem 4.6.2, as long as the conditions
required therein are satisfied. To begin with, the associated variance
parameters are given by

$\displaystyle\sigma_{i,j}^{2}$
$\displaystyle\coloneqq\mathbb{E}\left[\big{(}\widetilde{M}_{i,j}-M_{i,j}^{\star}\big{)}^{2}\right]$
$\displaystyle=p\mathbb{E}\left[\left(\frac{1-p}{p}M_{i,j}^{\star}+\frac{1}{p}\widetilde{\eta}_{i,j}\right)^{2}\right]+(1-p)\big{(}M_{i,j}^{\star}\big{)}^{2}$
$\displaystyle=\frac{\left(1-p\right)^{2}}{p}\big{(}M_{i,j}^{\star}\big{)}^{2}+\frac{1}{p}\mathbb{E}\left[\widetilde{\eta}_{i,j}^{2}\right]+(1-p)\big{(}M_{i,j}^{\star}\big{)}^{2}$
$\displaystyle=\frac{1-p}{p}\big{(}M_{i,j}^{\star}\big{)}^{2}+\frac{1-o(1)}{p}\sigma_{\eta}^{2},$

thus leading to

$\displaystyle\sigma_{\min}^{2}$
$\displaystyle\coloneqq\min_{i,j}\sigma_{i,j}^{2}=\frac{1-p}{p}\min_{i,j}\big{(}M_{i,j}^{\star}\big{)}^{2}+\frac{1-o(1)}{p}\sigma_{\eta}^{2},$
$\displaystyle\sigma^{2}$
$\displaystyle\coloneqq\max_{i,j}\sigma_{i,j}^{2}=\frac{1-p}{p}\|\bm{M}^{\star}\|_{\infty}^{2}+\frac{1-o(1)}{p}\sigma_{\eta}^{2}.$

Apparently, $\sigma^{2}/\sigma_{\min}^{2}=O(1)$ holds true under the
assumptions of Theorem 4.7.1. In addition, the random variables
$\\{\widetilde{M}_{i,j}-M_{i,j}^{\star}\\}$ are all bounded obeying

$\big{|}\widetilde{M}_{i,j}-M_{i,j}^{\star}\big{|}\leq\frac{1-p}{p}\big{|}M_{i,j}^{\star}\big{|}+\frac{1}{p}\big{|}\widetilde{\eta}_{i,j}\big{|}\leq\frac{(1-p)\|\bm{M}^{\star}\|_{\infty}+\sigma_{\eta}\sqrt{5\log
n}}{p}\eqqcolon B.$

These bounds readily imply that

$\frac{B}{\sigma}\asymp\frac{\leavevmode\nobreak\
\frac{(1-p)\|\bm{M}^{\star}\|_{\infty}+\sigma_{\eta}\sqrt{5\log
n}}{p}\leavevmode\nobreak\
}{\sqrt{\frac{1-p}{p}}\|\bm{M}^{\star}\|_{\infty}+\frac{1}{\sqrt{p}}\sigma_{\eta}}\lesssim\sqrt{\frac{\log
n}{p}}.$ (4.83)

Moving to the condition $\sigma\kappa\sqrt{n\log
n}\lesssim|\lambda_{r}^{\star}|$ in Theorem 4.7.1, it can be guaranteed if

$\|\bm{M}^{\star}\|_{\infty}\kappa\sqrt{\frac{(1-p)n\log
n}{p}}\lesssim|\lambda_{r}^{\star}|\quad\text{and}\quad\sigma_{\eta}\kappa\sqrt{\frac{n\log
n}{p}}\lesssim|\lambda_{r}^{\star}|.$

Given the assumption
$\frac{\max_{k,l}|M_{k,l}^{\star}|}{\min_{k,l}|M_{k,l}^{\star}|}=O(1)$, one
has

$\|\bm{M}^{\star}\|_{\infty}\asymp\frac{1}{n}\|\bm{M}^{\star}\|_{\mathrm{F}}\leq\frac{\sqrt{r}}{n}\|\bm{M}^{\star}\|=\frac{\kappa\sqrt{r}}{n}|\lambda_{r}^{\star}|.$
(4.84)

As a consequence, the condition $\sigma\kappa\sqrt{n\log
n}\lesssim|\lambda_{r}^{\star}|$ can be ensured under Condition (4.79).

It remains to certify Condition (4.74). By virtue of the above calculations of
$\sigma$ and $B$ as well as the property (4.83), it is easily seen that
Condition (4.74) is valid as long as the following holds:

$\displaystyle\frac{\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}}{\big{\|}\bm{U}^{\star}\big{\|}_{\mathrm{F}}^{2}}$
$\displaystyle\gtrsim\frac{\kappa^{2}\mu^{2}r^{2}\log^{5/2}n}{n\sqrt{np}}+\frac{\sqrt{1-p}\,\|\bm{M}^{\star}\|_{\infty}\mu^{2}r\kappa^{3}\log^{3}n}{|\lambda_{r}^{\star}|\sqrt{np}}$
$\displaystyle\qquad+\frac{\sigma_{\eta}\mu^{2}r\kappa^{3}\log^{3}n}{|\lambda_{r}^{\star}|\sqrt{np}}.$

Taking this together with the relation (4.84), we can demonstrate
straightforwardly that Condition (4.74) is guaranteed to hold as long as
Condition (4.80) is satisfied. This completes the proof.

###  4.8 Appendix A: Proof of Theorem 4.2.3

To simplify notation, we assume throughout the proof that
$\lambda_{r}^{\star}>0$, namely,

$\displaystyle|\lambda_{1}^{\star}|\geq\cdots\geq|\lambda_{r-1}^{\star}|\geq\lambda_{r}^{\star}>0.$
(4.85)

The challenge of the proof arises due to the complicated statistical
dependency between $\bm{M}$ and $\bm{U}$, and the leave-one-out analysis paves
a plausible path to decouple the dependency.

####  4.8.1 Construction of leave-one-out auxiliary estimates

As elucidated in the rank-1 matrix denoising example in Section 4.1, the key
to enabling fine-grained analysis is to seek assistance from a collection of
leave-one-out estimates. Akin to Section 4.1.3, for each $1\leq l\leq n$, we
construct two auxiliary matrices $\bm{M}^{(l)}$ and
$\bm{E}^{(l)}=\big{[}E^{(l)}_{i,j}\big{]}_{1\leq i,j\leq n}$ as follows:

$\displaystyle\bm{M}^{(l)}\coloneqq\bm{M}^{\star}+\bm{E}^{(l)},\quad
E_{i,j}^{(l)}\coloneqq\begin{cases}E_{i,j},&\text{if }i\neq l\text{ and }j\neq
l,\\\ 0,&\text{else},\end{cases}$ (4.86)

which are generated by simply discarding all random noise incurred in the
$l$-th column/row of the data matrix. In addition, let
$\lambda_{1}^{(l)},\cdots,\lambda_{n}^{(l)}$ be the eigenvalues of
$\bm{M}^{(l)}$ sorted by

$\displaystyle\big{|}\lambda_{1}^{(l)}\big{|}\geq\big{|}\lambda_{2}^{(l)}\big{|}\geq\cdots\geq\big{|}\lambda_{n}^{(l)}\big{|},$
(4.87)

and denote by $\bm{u}_{i}^{(l)}$ the eigenvector of $\bm{M}^{(l)}$ associated
with $\lambda_{i}^{(l)}$. The leave-one-out spectral estimates $\bm{U}^{(l)}$
and $\bm{\Lambda}^{(l)}$ are, therefore, given by

$\displaystyle\bm{U}^{(l)}\coloneqq\big{[}\bm{u}_{1}^{(l)},\cdots,\bm{u}_{r}^{(l)}\big{]}\in\mathbb{R}^{n\times
r};\quad\bm{\Lambda}^{(l)}\coloneqq\mathsf{diag}\big{(}\big{[}\lambda_{1}^{(l)},\cdots,\lambda_{r}^{(l)}\big{]}\big{)}.$
(4.88)

We emphasize again that the main advantage of introducing the leave-one-out
estimate $\bm{U}^{(l)}$ stems from its statistical independence from the
$l$-th row of $\bm{M}$, which substantially simplifies the analysis for the
$l$-th row of the estimate. In principle, our analysis employs the leave-one-
out estimates to help decouple delicate statistical dependency in a row-by-row
fashion. Another crucial aspect of the analysis lies in the exploitation of
the proximity of all these auxiliary estimates, a feature that is enabled by
the “stability” of the spectral method.

####  4.8.2 Preliminary facts

Before embarking on the $\ell_{\infty}$ and $\ell_{2,\infty}$ analyses, we
gather a couple of useful facts, whose proofs are postponed to Section 4.8.4.
In what follows, $\bm{\Theta}$ (resp. $\bm{\Theta}^{(l)}$) denotes a diagonal
matrix whose diagonal entries are the principal angles between $\bm{U}$ (resp.
$\bm{U}^{(l)}$) and $\bm{U}^{\star}$. In addition, we find it helpful to
introduce the following matrices

$\bm{H}\coloneqq\bm{U}^{\top}\bm{U}^{\star}\qquad\text{and}\qquad\bm{H}^{(l)}\coloneqq\bm{U}^{(l)\top}\bm{U}^{\star},$
(4.89)

which turn out to be close to being orthonormal.

The first set of results follows from the statistical nature of the
perturbation matrix $\bm{E}$ (cf. Assumption 4.1), which is immediately
available from the matrix tail bounds.

######  Lemma 4.8.1.

Consider the setting in Section 4.2. There is some constant $c_{2}>0$ such
that with probability at least $1-O(n^{-7})$,

$\max_{l}\big{\|}\bm{E}^{(l)}\big{\|}\leq\|\bm{E}\|\leq c_{2}\sigma\sqrt{n}.$
(4.90)

Moreover, for any fixed matrix $\bm{A}\in\mathbb{R}^{n\times d}$ with $d\leq
n$, one has

$\displaystyle\|\bm{E}\bm{A}\|_{2,\infty}\leq 4\sigma\sqrt{\log
n}\,\|\bm{A}\|_{\mathrm{F}}+(6B\log n)\|\bm{A}\|_{2,\infty}.$ (4.91)

######  Remark 4.8.2.

In view of (4.91), with probability at least $1-2n^{-5}$,

$\displaystyle\|\bm{E}\bm{U}^{\star}\|_{2,\infty}\leq 4\sigma\sqrt{\log
n}\,\|\bm{U}^{\star}\|_{\mathrm{F}}+(6B\log n)\|\bm{U}^{\star}\|_{2,\infty}$
$\displaystyle\qquad=4\sigma\sqrt{r\log n}+6B\sqrt{\frac{\mu
r\log^{2}n}{n}}=(4+6c_{\mathsf{b}})\sigma\sqrt{r\log n},$ (4.92)

which relies on the definition (4.24) and the definition of $c_{\mathsf{b}}$
in (4.29). As a result,

$\displaystyle\big{\|}\bm{M}\bm{U}^{\star}\big{\|}_{2,\infty}$
$\displaystyle\leq\big{\|}\bm{M}^{\star}\bm{U}^{\star}\big{\|}_{2,\infty}+\big{\|}\bm{E}\bm{U}^{\star}\big{\|}_{2,\infty}$
$\displaystyle\leq\sqrt{\frac{\mu
r}{n}}|\lambda_{1}^{\star}|+(4+6c_{\mathsf{b}})\sigma\sqrt{r\log n},$ (4.93)

which follows from the fact
$\bm{M}^{\star}\bm{U}^{\star}=\bm{U}^{\star}\bm{\Lambda}^{\star}$ (so that
$\|\bm{M}^{\star}\bm{U}^{\star}\|_{2,\infty}\leq\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}\|\bm{\Lambda}^{\star}\|=\sqrt{\mu
r/n}\,|\lambda_{1}^{\star}|$).

With the size of the perturbations (i.e., $\|\bm{E}^{(l)}\|$ and $\|\bm{E}\|$)
under control, the $\ell_{2}$ perturbation theory established in Chapter 2
leads to the following set of conclusions.

######  Lemma 4.8.3.

Suppose that $c_{2}\sigma\sqrt{n}\leq(1-1/\sqrt{2})\lambda_{r}^{\star}$, where
$c_{2}$ is the same constant as in Lemma 4.8.1. Then with probability at least
$1-O(n^{-7})$, one has

$\displaystyle\mathsf{dist}(\bm{U},\bm{U}^{\star})$
$\displaystyle\leq\frac{2c_{2}\sigma\sqrt{n}}{\lambda_{r}^{\star}},\leavevmode\nobreak\
\leavevmode\nobreak\ $
$\displaystyle\mathsf{dist}\big{(}\bm{U}^{(l)},\bm{U}^{\star}\big{)}$
$\displaystyle\leq\frac{2c_{2}\sigma\sqrt{n}}{\lambda_{r}^{\star}},$ (4.94a)
$\displaystyle\big{\|}\sin\bm{\Theta}\big{\|}$
$\displaystyle\leq\frac{c_{2}\sigma\sqrt{2n}}{\lambda_{r}^{\star}},\leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle\big{\|}\sin\bm{\Theta}^{(l)}\big{\|}$
$\displaystyle\leq\frac{c_{2}\sigma\sqrt{2n}}{\lambda_{r}^{\star}},$ (4.94b)
$\displaystyle\max_{1\leq j\leq r}|\lambda_{j}|$
$\displaystyle\geq\lambda_{r}^{\star}-c_{2}\sigma\sqrt{n},$
$\displaystyle\max_{1\leq j\leq r}|\lambda_{j}^{(l)}|$
$\displaystyle\geq\lambda_{r}^{\star}-c_{2}\sigma\sqrt{n},$ (4.94c)
$\displaystyle\max_{j:j>r}|\lambda_{j}|$ $\displaystyle\leq
c_{2}\sigma\sqrt{n},$ $\displaystyle\max_{j:j>r}|\lambda_{j}^{(l)}|$
$\displaystyle\leq c_{2}\sigma\sqrt{n}$ (4.94d) hold simultaneously for all
$1\leq l\leq n$. In addition,
$\displaystyle\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{\mathrm{F}}\leq\frac{2c_{2}\sigma\sqrt{rn}}{\lambda_{r}^{\star}}.$
(4.94e)

with probability exceeding $1-2n^{-5}$.

######  Remark 4.8.4.

Lemmas 4.8.1 and 4.8.3 allow us to bound the eigengap and perturbation size as
follows

$\displaystyle\big{|}\lambda_{r}^{(l)}\big{|}-\big{|}\lambda_{r+1}^{(l)}\big{|}$
$\displaystyle\geq\lambda_{r}^{\star}-c_{2}\sigma\sqrt{n}-c_{2}\sigma\sqrt{n}\geq\lambda_{r}^{\star}/2,$
(4.95a) $\displaystyle\|\bm{M}-\bm{M}^{(l)}\|$
$\displaystyle\leq\|\bm{M}-\bm{M}^{\star}\|+\|\bm{M}^{\star}-\bm{M}^{(l)}\|=\|\bm{E}\|+\|\bm{E}^{(l)}\|$
$\displaystyle\leq
2c_{2}\sigma\sqrt{n}\leq(1-1/\sqrt{2})\big{(}\big{|}\lambda_{r}^{(l)}\big{|}-\big{|}\lambda_{r+1}^{(l)}\big{|}\big{)},$
(4.95b)

which are valid as long as $20c_{2}\sigma\sqrt{n}\leq\lambda_{r}^{\star}$.
These will prove useful when bounding the approximation error of $\bm{U}$
using $\bm{U}^{(l)}$.

Another collection of results is concerned with $\bm{H}$ and $\bm{H}^{(l)}$.

######  Lemma 4.8.5.

Suppose that the assumptions of Lemma 4.8.3 hold. With probability at least
$1-O(n^{-7})$,

$\displaystyle\|\bm{H}^{-1}\|$ $\displaystyle\leq 2,\quad$
$\displaystyle\big{\|}\big{(}\bm{H}^{(l)}\big{)}^{-1}\big{\|}$
$\displaystyle\leq 2,$ (4.96a)
$\displaystyle\big{\|}\bm{H}-\mathsf{sgn}(\bm{H})\big{\|}$
$\displaystyle\leq\frac{2c_{2}^{2}n\sigma^{2}}{(\lambda_{r}^{\star})^{2}},\leavevmode\nobreak\
\leavevmode\nobreak\ $
$\displaystyle\big{\|}\bm{H}^{(l)}-\mathsf{sgn}(\bm{H}^{(l)})\big{\|}$
$\displaystyle\leq\frac{2c_{2}^{2}n\sigma^{2}}{(\lambda_{r}^{\star})^{2}}$
(4.96b)

hold simultaneously for all $1\leq l\leq n$.

######  Remark 4.8.6.

As a consequence of (4.96) and Proposition 2.1.2, one has

$\displaystyle{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{A}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
$\displaystyle={\big{|}\kern-1.07639pt\big{|}\kern-1.07639pt\big{|}\bm{A}\bm{H}\bm{H}^{-1}\big{|}\kern-1.07639pt\big{|}\kern-1.07639pt\big{|}}\leq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{A}\bm{H}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\,\big{\|}\bm{H}^{-1}\big{\|}\leq
2{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{A}\bm{H}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|},$
(4.97a)
$\displaystyle{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{A}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
$\displaystyle\leq{\big{|}\kern-1.07639pt\big{|}\kern-1.07639pt\big{|}\bm{A}\bm{H}^{(l)}\big{|}\kern-1.07639pt\big{|}\kern-1.07639pt\big{|}}\,\big{\|}\big{(}\bm{H}^{(l)}\big{)}^{-1}\big{\|}\leq
2{\big{|}\kern-1.07639pt\big{|}\kern-1.07639pt\big{|}\bm{A}\bm{H}^{(l)}\big{|}\kern-1.07639pt\big{|}\kern-1.07639pt\big{|}}$
(4.97b)

for any matrix $\bm{A}$. Here,
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{A}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
could either be the Frobenius norm or the $\ell_{2,\infty}$ norm
$\|\cdot\|_{2,\infty}$.

####  4.8.3 Leave-one-out analysis

Now we move on to the main part of the analysis, which is further decomposed
into four steps.

##### Step 1: decomposing the $\ell_{2,\infty}$ estimation error of $\bm{U}$

By virtue of the proximity of $\bm{H}$ and $\mathsf{sgn}(\bm{H})$ unveiled in
Lemma 4.8.5, we are allowed to employ $\bm{U}\bm{H}$ as a surrogate for
$\bm{U}\mathsf{sgn}(\bm{H})$, which is more convenient to work with. As it
turns out, the discrepancy between $\bm{U}\bm{H}$ and the first-order
approximation $\bm{M}\bm{U}^{\star}(\bm{\Lambda}^{\star})^{-1}$, and the
discrepancy between $\bm{U}\bm{H}$ and the truth, can be bounded by three
important terms, as asserted below. The proof is built upon elementary algebra
and basic $\ell_{2}$ perturbation bounds in Section 4.8.2, and is deferred to
Section 4.8.4.

######  Lemma 4.8.7.

Suppose that $2c_{2}\sigma\sqrt{n}\leq\lambda_{r}^{\star}$ for some
sufficiently large constant $c_{2}>0$. Then with probability at least
$1-O(n^{-7})$, one has

$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{M}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}_{2,\infty}$
$\displaystyle\leq\mathcal{E}_{1}+\mathcal{E}_{2},$ (4.98a)
$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}$
$\displaystyle\leq\mathcal{E}_{1}+\mathcal{E}_{2}+\mathcal{E}_{3},$ (4.98b)

where
$\mathcal{E}_{1}\coloneqq\frac{2\|\bm{M}(\bm{U}\bm{H}-\bm{U}^{\star})\|_{2,\infty}}{\lambda_{r}^{\star}}$,
$\mathcal{E}_{2}\coloneqq\frac{4\|\bm{M}\bm{U}^{\star}\|_{2,\infty}\|\bm{E}\|}{(\lambda_{r}^{\star})^{2}}$,
and
$\mathcal{E}_{3}\coloneqq\frac{\|\bm{E}\bm{U}^{\star}\|_{2,\infty}}{\lambda_{r}^{\star}}$.

Lemma 4.8.7 leaves us with three important terms to deal with. The term
$\mathcal{E}_{1}$ is most complicated as it involves the product of two random
matrices, whereas $\mathcal{E}_{2}$ and $\mathcal{E}_{3}$ can be controlled
straightforwardly through our preliminary facts in Section 4.8.2.
Specifically, the term $\mathcal{E}_{2}$ can be bounded by combining (4.93)
with the bound (4.90) on $\bm{E}$ to obtain

$\displaystyle\mathcal{E}_{2}$
$\displaystyle\leq\frac{4c_{2}\kappa\sigma\sqrt{\mu
r}}{\lambda_{r}^{\star}}+\frac{4c_{2}(4+6c_{\mathsf{b}})\sigma^{2}\sqrt{rn\log
n}}{(\lambda_{r}^{\star})^{2}}.$ (4.99)

Regarding the term $\mathcal{E}_{3}$, the inequality (4.92) readily gives

$\displaystyle\mathcal{E}_{3}\leq\frac{(4+6c_{\mathsf{b}})\sigma\sqrt{r\log
n}}{\lambda_{r}^{\star}}.$ (4.100)

Turning to controlling the remaining term $\mathcal{E}_{1}$, a closer
inspection, however, reveals substantial challenges, due to the complicated
statistical dependency between $\bm{M}$ and $\bm{U}$. To further complicate
matters, the term $\mathcal{E}_{1}$—as we shall demonstrate momentarily—depend
on some intrinsic properties of interest about $\bm{U}$ (e.g.,
$\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{2,\infty}$), which might lead to circular
reasoning if not handled properly. In order to circumvent this issue, we
intend to establish the following relation

$\mathcal{E}_{1}\leq\mathcal{E}_{1,1}+\rho_{1}\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}$
(4.101)

for some quantity $\mathcal{E}_{1,1}>0$ that does not involve
$\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{2,\infty}$ as well as some contraction
factor $0<\rho_{1}\leq 1/2$. Assuming the relation (4.101) holds for the
moment, we have the following useful claim (the proof is straightforward and
again postponed to Section 4.8.4).

######  Lemma 4.8.8.

If Conditions (4.98) and (4.101) hold with $0<\rho_{1}\leq 1/2$, then we have

$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}$
$\displaystyle\leq
2\big{(}\mathcal{E}_{1,1}+\mathcal{E}_{2}+\mathcal{E}_{3}\big{)},$ (4.102a)
$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{M}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}_{2,\infty}$
$\displaystyle\leq
2\big{(}\mathcal{E}_{1,1}+\mathcal{E}_{2}+\rho_{1}\mathcal{E}_{3}\big{)},$
(4.102b)
$\displaystyle\big{\|}\bm{U}\mathsf{sgn}(\bm{H})-\bm{U}^{\star}\big{\|}_{2,\infty}\leq
4\big{(}\mathcal{E}_{1,1}+\mathcal{E}_{2}+\mathcal{E}_{3}\big{)}+\frac{4c_{2}^{2}\sigma^{2}\sqrt{\mu
rn}}{(\lambda_{r}^{\star})^{2}},$ (4.102c)
$\displaystyle\big{\|}\bm{U}\mathsf{sgn}(\bm{H})-\bm{M}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}_{2,\infty}$
$\displaystyle\qquad\leq
3\mathcal{E}_{1,1}+3\mathcal{E}_{2}+\Big{(}2\rho_{1}+\frac{8c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}}\Big{)}\mathcal{E}_{3}+\frac{4c_{2}^{2}\sigma^{2}\sqrt{\mu
rn}}{(\lambda_{r}^{\star})^{2}}.$ (4.102d)

######  Remark 4.8.9.

When $\mathcal{E}_{3}$ is the dominant term, the bound (4.102b) might be
stronger than (4.102a) if $\rho_{1}$ is small.

With this lemma in mind, everything boils down to (i) establishing the
relation (4.101) and (ii) deriving a tight bound on $\mathcal{E}_{1,1}$, which
form the main content of the rest of the proof. In light of the triangle
inequality

$\displaystyle\big{\|}\bm{M}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}\leq\big{\|}\bm{E}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}+\big{\|}\bm{M}^{\star}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty},$

we dedicate the next two steps to bounding
$\|\bm{E}(\bm{U}\bm{H}-\bm{U}^{\star})\|_{2,\infty}$ and
$\|\bm{M}^{\star}(\bm{U}\bm{H}-\bm{U}^{\star})\|_{2,\infty}$ respectively.

##### Step 2: bounding $\|\bm{E}(\bm{U}\bm{H}-\bm{U}^{\star})\|_{2,\infty}$
via leave-one-out analysis

To obtain tight row-wise control of
$\bm{E}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}$, one needs to carefully
decouple the statistical dependency between $\bm{E}$ and $\bm{U}$, which is
where the leave-one-out idea comes into play.

###### Step 2.1: a convenient decomposition.

We start by invoking the triangle inequality to decompose the target quantity
as follows

$\displaystyle\big{\|}\bm{E}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}=\max_{l}\big{\|}\bm{E}_{l,\cdot}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2}$
$\displaystyle\leq\max_{l}\Big{\\{}\big{\|}\bm{E}_{l,\cdot}\big{(}\bm{U}^{(l)}\bm{H}^{(l)}-\bm{U}^{\star}\big{)}\big{\|}_{2}+\big{\|}\bm{E}_{l,\cdot}\big{(}\bm{U}\bm{H}-\bm{U}^{(l)}\bm{H}^{(l)}\big{)}\big{\|}_{2}\Big{\\}}$
$\displaystyle\leq\max_{l}\Big{\\{}\big{\|}\bm{E}_{l,\cdot}\big{(}\bm{U}^{(l)}\bm{H}^{(l)}-\bm{U}^{\star}\big{)}\big{\|}_{2}+\|\bm{E}\|\big{\|}\bm{U}\bm{H}-\bm{U}^{(l)}\bm{H}^{(l)}\big{\|}_{\mathrm{F}}\Big{\\}}.$
(4.103)

In words, when controlling the $l$-th row of
$\bm{E}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}$, we attempt to employ
$\bm{U}^{(l)}\bm{H}^{(l)}$ as a surrogate of $\bm{U}\bm{H}$. The benefits to
be harvested from this decomposition are:

  * •

The statistical independence between $\bm{E}_{l,\cdot}$ and
$\bm{U}^{(l)}\bm{H}^{(l)}$ allows for convenient upper bounds on
$\big{\|}\bm{E}_{l,\cdot}\big{(}\bm{U}^{(l)}\bm{H}^{(l)}-\bm{U}^{\star}\big{)}\big{\|}_{2}$;

  * •

$\bm{U}\bm{H}$ and $\bm{U}^{(l)}\bm{H}^{(l)}$ are expected to be exceedingly
close, so that the discrepancy incurred by replacing $\bm{U}\bm{H}$ with
$\bm{U}^{(l)}\bm{H}^{(l)}$ is negligible.

In what follows, we flesh out the proof details.

###### Step 2.2: the proximity of $\bm{U}\bm{H}$ and
$\bm{U}^{(l)}\bm{H}^{(l)}$.

Given that

$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{U}^{(l)}\bm{H}^{(l)}\big{\|}_{\mathrm{F}}$
$\displaystyle=\big{\|}\bm{U}\bm{U}^{\top}\bm{U}^{\star}-\bm{U}^{(l)}\bm{U}^{(l)\top}\bm{U}^{\star}\big{\|}_{\mathrm{F}}$
$\displaystyle\leq\big{\|}\bm{U}\bm{U}^{\top}-\bm{U}^{(l)}\bm{U}^{(l)\top}\big{\|}_{\mathrm{F}}\big{\|}\bm{U}^{\star}\big{\|}$
$\displaystyle=\big{\|}\bm{U}\bm{U}^{\top}-\bm{U}^{(l)}\bm{U}^{(l)\top}\big{\|}_{\mathrm{F}},$
(4.104)

it boils down to bounding
$\|\bm{U}\bm{U}^{\top}-\bm{U}^{(l)}\bm{U}^{(l)\top}\|_{\mathrm{F}}$. Under
simple conditions on the eigengap and the perturbation size (see (4.95) in
Remark 4.8.4), the Davis-Kahan theorem (cf. Corollary 2.3.4) yields

$\displaystyle\big{\|}\bm{U}\bm{U}^{\top}-\bm{U}^{(l)}\bm{U}^{(l)\top}\big{\|}_{\mathrm{F}}$
$\displaystyle\leq\frac{2\big{\|}\big{(}\bm{M}-\bm{M}^{(l)}\big{)}\bm{U}^{(l)}\big{\|}_{\mathrm{F}}}{\big{|}\lambda_{r}^{(l)}\big{|}-\big{|}\lambda_{r+1}^{(l)}\big{|}}$
$\displaystyle\leq\frac{4\big{\|}\big{(}\bm{M}-\bm{M}^{(l)}\big{)}\bm{U}^{(l)}\big{\|}_{\mathrm{F}}}{\lambda_{r}^{\star}}.$
(4.105)

It remains to develop an upper bound on
$\|(\bm{M}-\bm{M}^{(l)})\bm{U}^{(l)}\|$. The way we construct $\bm{M}^{(l)}$
(see Section 4.8.1) allows us to express

$\big{(}\bm{M}-\bm{M}^{(l)}\big{)}\bm{U}^{(l)}=\bm{e}_{l}\bm{E}_{l,\cdot}\bm{U}^{(l)}+\big{(}\bm{E}_{\cdot,l}-E_{l,l}\bm{e}_{l}\big{)}\bm{e}_{l}^{\top}\bm{U}^{(l)}.$

This together with the triangle inequality and the fact (4.97) gives

$\displaystyle\big{\|}\big{(}\bm{M}-\bm{M}^{(l)}\big{)}\bm{U}^{(l)}\big{\|}_{\mathrm{F}}\leq\big{\|}\bm{E}_{l,\cdot}\bm{U}^{(l)}\big{\|}_{2}+\big{\|}\bm{E}_{\cdot,l}-E_{l,l}\bm{e}_{l}\big{\|}_{2}\,\big{\|}\bm{U}^{(l)}\big{\|}_{2,\infty}$
$\displaystyle\quad\leq\big{\|}\bm{E}_{l,\cdot}\bm{U}^{(l)}\big{\|}_{2}+2\big{\|}\bm{E}\big{\|}\,\big{\|}\bm{U}^{(l)}\bm{H}^{(l)}\big{\|}_{2,\infty}$
$\displaystyle\quad\leq\big{\|}\bm{E}_{l,\cdot}\bm{U}^{(l)}\big{\|}_{2}+2\big{\|}\bm{E}\big{\|}\,\big{\|}\bm{U}\bm{H}\big{\|}_{2,\infty}+2\big{\|}\bm{E}\big{\|}\,\big{\|}\bm{U}\bm{H}-\bm{U}^{(l)}\bm{H}^{(l)}\big{\|}_{\mathrm{F}}.$

Substitution into (4.104) and (4.105) gives

$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{U}^{(l)}\bm{H}^{(l)}\big{\|}_{\mathrm{F}}\leq\big{\|}\bm{U}\bm{U}^{\top}-\bm{U}^{(l)}\bm{U}^{(l)\top}\big{\|}_{\mathrm{F}}$
$\displaystyle\quad\leq\frac{4\big{\|}\bm{E}_{l,\cdot}\bm{U}^{(l)}\big{\|}_{2}+8\big{\|}\bm{E}\big{\|}\,\big{\|}\bm{U}\bm{H}\big{\|}_{2,\infty}+8\big{\|}\bm{E}\big{\|}\,\big{\|}\bm{U}\bm{H}-\bm{U}^{(l)}\bm{H}^{(l)}\big{\|}_{\mathrm{F}}}{\lambda_{r}^{\star}}.$

As long as $\|\bm{E}\|/\lambda_{r}^{\star}\leq 1/16$, one can further
rearrange terms to obtain

$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{U}^{(l)}\bm{H}^{(l)}\big{\|}_{\mathrm{F}}$
$\displaystyle\leq\frac{8\big{\|}\bm{E}_{l,\cdot}\bm{U}^{(l)}\big{\|}_{2}+16\big{\|}\bm{E}\big{\|}\,\big{\|}\bm{U}\bm{H}\big{\|}_{2,\infty}}{\lambda_{r}^{\star}}.$
(4.106)

In addition, the fact (4.97) combined with the triangle inequality yields

$\tfrac{1}{2}\big{\|}\bm{E}_{l,\cdot}\bm{U}^{(l)}\big{\|}_{2}\leq\big{\|}\bm{E}_{l,\cdot}\bm{U}^{(l)}\bm{H}^{(l)}\big{\|}_{2}\leq\big{\|}\bm{E}_{l,\cdot}\big{(}\bm{U}^{(l)}\bm{H}^{(l)}-\bm{U}^{\star}\big{)}\big{\|}_{2}+\big{\|}\bm{E}_{l,\cdot}\bm{U}^{\star}\big{\|}_{2},$

which taken collectively with (4.106) reveals that

$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{U}^{(l)}\bm{H}^{(l)}\big{\|}_{\mathrm{F}}\leq\frac{16\big{\|}\bm{E}_{l,\cdot}\big{(}\bm{U}^{(l)}\bm{H}^{(l)}-\bm{U}^{\star}\big{)}\big{\|}_{2}}{\lambda_{r}^{\star}}$
$\displaystyle\quad+\frac{16\Big{\\{}\big{\|}\bm{E}_{l,\cdot}\bm{U}^{\star}\big{\|}_{2}+\big{\|}\bm{E}\big{\|}\,\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}+\big{\|}\bm{E}\big{\|}\,\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}\Big{\\}}}{\lambda_{r}^{\star}}.$
(4.107)

###### Step 2.3: bounding
$\|\bm{E}_{l,\cdot}(\bm{U}^{(l)}\bm{H}^{(l)}-\bm{U}^{\star})\|_{2}$.

Recognizing that $\bm{E}_{l,\cdot}$ is statistically independent of
$\bm{U}^{(l)}$ (since $\bm{U}^{(l)}$ is computed without using
$\bm{E}_{l,\cdot}$), we invoke Lemma 4.8.1 (more precisely, we use the proof
of this lemma) to demonstrate that with probability exceeding $1-2n^{-6}$,

$\displaystyle\big{\|}\bm{E}_{l,\cdot}\big{(}\bm{U}^{(l)}\bm{H}^{(l)}-\bm{U}^{\star}\big{)}\big{\|}_{2}$
$\displaystyle\leq 4\sigma\sqrt{\log
n}\,\|\bm{U}^{(l)}\bm{H}^{(l)}-\bm{U}^{\star}\|_{\mathrm{F}}+(6B\log
n)\|\bm{U}^{(l)}\bm{H}^{(l)}-\bm{U}^{\star}\|_{2,\infty}$ $\displaystyle\leq
4\sigma\sqrt{\log n}\,\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{\mathrm{F}}+(6B\log
n)\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{2,\infty}$ $\displaystyle\qquad+(10B\log
n)\|\bm{U}\bm{H}-\bm{U}^{(l)}\bm{H}^{(l)}\|_{\mathrm{F}}$ (4.108)

holds simultaneously for all $1\leq l\leq n$, where the last line results from
the triangle inequality and the fact $4\sigma\sqrt{\log n}+6B\log n\leq
10B\log n$.

###### Step 2.4: combining the above bounds.

The careful reader would immediately remark that the inequalities (4.107) and
(4.108) are convoluted, both of which involve the terms
$\|\bm{E}_{l,\cdot}(\bm{U}^{(l)}\bm{H}^{(l)}-\bm{U}^{\star})\|_{2}$ and
$\|\bm{U}\bm{H}-\bm{U}^{(l)}\bm{H}^{(l)}\|_{\mathrm{F}}$. Fortunately, one can
substitute (4.108) into (4.107) to produce a cleaner bound. By doing so and
exploiting the condition $320B\log n\leq\lambda_{r}^{\star}$, we rearrange
terms to reach

$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{U}^{(l)}\bm{H}^{(l)}\big{\|}_{\mathrm{F}}\leq\frac{32\big{\|}\bm{E}_{l,\cdot}\bm{U}^{\star}\big{\|}_{2}+32\big{\|}\bm{E}\big{\|}\,\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}}{\lambda_{r}^{\star}}$
$\displaystyle+\frac{128\sigma\sqrt{\log
n}\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}+(32c_{2}\sigma\sqrt{n}+192B\log
n)\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}}{\lambda_{r}^{\star}},$

where we have also used the upper bound on $\|\bm{E}\|$ derived in (4.94).
Meanwhile, plugging the above inequality into (4.108) yields

$\displaystyle\big{\|}\bm{E}_{l,\cdot}\big{(}\bm{U}^{(l)}\bm{H}^{(l)}-\bm{U}^{\star}\big{)}\big{\|}_{2}\leq\frac{320B\log
n}{\lambda_{r}^{\star}}\big{(}\big{\|}\bm{E}_{l,\cdot}\bm{U}^{\star}\big{\|}_{2}+\big{\|}\bm{E}\big{\|}\,\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}\big{)}$
$\displaystyle\quad+5\sigma\sqrt{\log
n}\,\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{\mathrm{F}}+(7B\log
n)\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{2,\infty},$ (4.109)

provided that $\max\\{\sigma\sqrt{n},B\log n\\}\leq c_{3}\lambda_{r}^{\star}$
for some small constant $c_{3}$.

Substituting the preceding two bounds into (4.103) and combining terms reveal
the existence of some constant $c_{4}>0$ such that

$\displaystyle\big{\|}\bm{E}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}$
$\displaystyle\qquad\leq\alpha_{0}+\alpha_{1}+c_{4}\big{(}\sigma\sqrt{n}+B\log
n\big{)}\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{2,\infty}$ (4.110)

provided that $\max\\{\sigma\sqrt{n},B\log n\\}\leq c_{3}\lambda_{r}^{\star}$
for some constant $c_{3}>0$ small enough, where

$\displaystyle\begin{array}[]{ll}&\alpha_{0}\coloneqq\frac{32c_{2}\sigma\sqrt{n}+320B\log
n}{\lambda_{r}^{\star}}\big{(}\big{\|}\bm{E}\bm{U}^{\star}\big{\|}_{2,\infty}+\big{\|}\bm{E}\big{\|}\,\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}\big{)},\\\
&\alpha_{1}\coloneqq 6\sigma\sqrt{\log
n}\,\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{\mathrm{F}}.\end{array}$ (4.113)

Before continuing, note that we are already well-equipped to bound the above
two quantities. First, $\alpha_{0}$ can be bounded by

$\displaystyle\alpha_{0}$
$\displaystyle\leq\frac{32c_{2}\sigma\sqrt{n}+320B\log
n}{\lambda_{r}^{\star}}$ $\displaystyle\qquad\cdot\Big{(}4\sigma\sqrt{r\log
n}+6B\sqrt{\frac{\mu r}{n}}\log n+c_{2}\sigma\sqrt{\mu r}\Big{)},$ (4.114)

where we have used the bounds concerning $\bm{E}$ from Lemma 4.8.1 as well as
the definition (4.24). Regarding $\alpha_{1}$, it is seen from (4.94e) that

$\displaystyle\alpha_{1}\leq\frac{12c_{2}\sigma^{2}\sqrt{rn\log
n}}{\lambda_{r}^{\star}}.$ (4.115)

##### Step 3: bounding
$\|\bm{M}^{\star}(\bm{U}\bm{H}-\bm{U}^{\star})\|_{2,\infty}$

We make the key observation that

$\displaystyle\big{\|}\bm{M}^{\star}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}$
$\displaystyle=\big{\|}\bm{U}^{\star}\bm{\Lambda}^{\star}\bm{U}^{\star\top}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}$
$\displaystyle\leq\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}\|\bm{\Lambda}^{\star}\|\,\big{\|}\bm{U}^{\star\top}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}$
$\displaystyle=\sqrt{\frac{\mu
r}{n}}\|\bm{\Lambda}^{\star}\|\,\big{\|}\bm{U}\bm{U}^{\top}-\bm{U}^{\star}\bm{U}^{\star\top}\big{\|}^{2}.$
(4.116)

Here, the last identity holds true due to the following observation

$\displaystyle\big{\|}\bm{U}^{\star\top}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}$
$\displaystyle=\big{\|}\bm{U}^{\star\top}\bm{U}\bm{U}^{\top}\bm{U}^{\star}-\bm{U}^{\star\top}\bm{U}^{\star}\big{\|}=\big{\|}\bm{U}^{\star\top}\bm{U}\bm{U}^{\top}\bm{U}^{\star}-\bm{I}\big{\|}$
$\displaystyle=\big{\|}\bm{Y}(\cos^{2}\bm{\Theta})\bm{Y}^{\top}-\bm{I}\big{\|}=\big{\|}\cos^{2}\bm{\Theta}-\bm{I}\big{\|}$
$\displaystyle=\big{\|}\sin^{2}\bm{\Theta}\big{\|}=\big{\|}\sin\bm{\Theta}\big{\|}^{2},$

where we denote by $\bm{X}(\cos\bm{\Theta})\bm{Y}^{\top}$ the SVD of
$\bm{U}^{\top}\bm{U}^{\star}$, with $\bm{X}$ and $\bm{Y}$ being orthonormal
matrices and $\bm{\Theta}$ the diagonal matrix consisting of the principal
angles between $\bm{U}$ and $\bm{U}^{\star}$ (see the definition in (2.5)).
The above bounds combined with (4.94b) indicate that

$\displaystyle\big{\|}\bm{M}^{\star}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}$
$\displaystyle\leq\big{|}\lambda_{1}^{\star}\big{|}\sqrt{\frac{\mu
r}{n}}\,\big{\|}\sin\bm{\Theta}\big{\|}^{2}$
$\displaystyle\leq\frac{4c_{2}^{2}\kappa\sigma^{2}\sqrt{\mu
rn}}{\lambda_{r}^{\star}}\eqqcolon\alpha_{2}.$ (4.117)

##### Step 4: putting all pieces together

Combining the bounds (4.110) and (4.117) in Steps 2-3 and using the definition
of $\mathcal{E}_{1}$ (see Lemma 4.8.7) give

$\displaystyle\mathcal{E}_{1}$
$\displaystyle\leq\frac{2\big{\|}\bm{E}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}+2\big{\|}\bm{M}^{\star}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}}{\lambda_{r}^{\star}}$
$\displaystyle\leq\mathcal{E}_{1,1}+\rho_{1}\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{2,\infty},$
(4.118)

where

$\mathcal{E}_{1,1}\coloneqq\frac{2\big{(}\alpha_{0}+\alpha_{1}+\alpha_{2}\big{)}}{\lambda_{r}^{\star}}\quad\text{and}\quad\rho_{1}\coloneqq\frac{2c_{4}(\sigma\sqrt{n}+B\log
n)}{\lambda_{r}^{\star}}.$ (4.119)

This matches precisely the relation hypothesized in (4.101). In particular,
one has $0<\rho\leq 1/2$ as long as $4c_{4}(\sigma\sqrt{n}+B\log
n)\leq\lambda_{r}^{\star}$, which holds whenever $\sigma\sqrt{n\log n}\leq
c_{\sigma}\lambda_{r}^{\star}$ for a sufficiently small $c_{\sigma}>0$ in view
of our assumption on $B$ (cf. (4.29)).

Recall that $\mathcal{E}_{1,1}$, $\mathcal{E}_{2}$, $\mathcal{E}_{3}$,
$\alpha_{0}$, $\alpha_{1}$, $\alpha_{2}$ and $\rho_{1}$ have been controlled
in (4.119), (4.99), (4.100), (4.114), (4.115), (4.117) and (4.119),
respectively. In addition, recall our assumption (4.29) and suppose that
$\sigma{\sqrt{n}}\leq c_{\sigma}\lambda_{r}^{\star}$ for some sufficiently
small constant $c_{\sigma}>0$. With these bounds and assumptions in mind,
invoking Lemma 4.8.8 and combining terms immediately conclude the proof.

######  Remark 4.8.10.

We shall also make note of an immediate consequence of the above argument as
follows

$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}$
$\displaystyle\lesssim\frac{\sigma\kappa\sqrt{\mu r}+\sigma\sqrt{r\log
n}}{\lambda_{r}^{\star}},$ (4.120)

which will prove useful for deriving other important results.

####  4.8.4 Proof of auxiliary lemmas

###### Proof of Lemma 4.8.1.

Under Assumption 4.1, Theorem 3.1.5 (in particular (3.9)) reveals the
existence of some constant $c_{2}>0$ such that

$\max_{l}\big{\|}\bm{E}^{(l)}\big{\|}\leq\|\bm{E}\|\leq c_{2}\sigma\sqrt{n},$

holds with probability exceeding $1-O(n^{-7})$.

When it comes to $\bm{E}\bm{A}$, we proceed by viewing its $l$-th row
$\bm{E}_{l,\cdot}\bm{A}$ as a sum of independent random vectors as follows

$\bm{E}_{l,\cdot}\bm{A}=\sum\nolimits_{j}E_{l,j}\bm{A}_{j,\cdot}\eqqcolon\sum\nolimits_{j}\bm{z}_{j},$

which can be controlled by the matrix Bernstein inequality. Specifically, it
is seen from Assumption 4.1 that

$\displaystyle v$
$\displaystyle\coloneqq\sum\nolimits_{j}\mathbb{E}\big{[}\|\bm{z}_{j}\|_{2}^{2}\big{]}\leq\sigma^{2}\sum\nolimits_{j}\big{\|}\bm{A}_{j,\cdot}\big{\|}_{2}^{2}=\sigma^{2}\|\bm{A}\|_{\mathrm{F}}^{2};$
$\displaystyle L$
$\displaystyle\coloneqq\max_{j}\|\bm{z}_{j}\|_{2}=\max_{j}|E_{l,j}|\,\big{\|}\bm{Z}_{j,\cdot}\big{\|}_{2}\leq
B\|\bm{Z}\|_{2,\infty}.$

Invoke the matrix Bernstein inequality (cf. Corollary 3.1.4) and take the
union bound to demonstrate that: with probability exceeding $1-2n^{-6}$,

$\displaystyle\big{\|}\bm{E}_{l,\cdot}\bm{A}\big{\|}_{2}$ $\displaystyle\leq
4\sqrt{v\log n}+6L\log n\leq 4\sigma\sqrt{\log
n}\,\|\bm{A}\|_{\mathrm{F}}+(6B\log n)\|\bm{A}\|_{2,\infty}$

holds simultaneously for all $1\leq l\leq n$, thus concluding the proof.

###### Proof of Lemma 4.8.3.

Lemma 4.8.1 tells us that

$\max_{l}\big{\|}\bm{E}^{(l)}\big{\|}\leq\|\bm{E}\|\leq c_{2}\sigma\sqrt{n}$
(4.121)

holds with probability exceeding $1-O(n^{-7})$. Repeating the argument in the
proof of Corollary 2.3.4 reveals that

$\displaystyle\max_{1\leq j\leq r}|\lambda_{j}|$
$\displaystyle\geq\lambda_{r}^{\star}-\|\bm{E}\|,\quad$
$\displaystyle\max_{1\leq j\leq r}|\lambda_{j}^{(l)}|$
$\displaystyle\geq\lambda_{r}^{\star}-\|\bm{E}^{(l)}\|,$ (4.122a)
$\displaystyle\max_{j:j>r}|\lambda_{j}|$ $\displaystyle\leq\|\bm{E}\|,$
$\displaystyle\max_{j:j>r}|\lambda_{j}^{(l)}|$
$\displaystyle\leq\|\bm{E}^{(l)}\|,$ (4.122b)

which taken together with (4.121) validates (4.94c)-(4.94d).

Regarding (4.94a) and (4.94b), apply Corollary 2.3.4 to reach

$\displaystyle\mathsf{dist}(\bm{U},\bm{U}^{\star})\leq\sqrt{2}\|\sin\bm{\Theta}\|\leq\frac{2\|\bm{E}\|}{\lambda_{r}^{\star}}\leq\frac{2c_{2}\sigma\sqrt{n}}{\lambda_{r}^{\star}}$
(4.123)

as long as $\|\bm{E}\|\leq
c_{2}\sigma\sqrt{n}\leq(1-1/\sqrt{2})\lambda_{r}^{\star}$, where we have used
$\lambda_{r+1}^{\star}=0$. The bound on
$\mathsf{dist}\big{(}\bm{U}^{(l)},\bm{U}^{\star}\big{)}$ follows from the same
argument.

Additionally, regarding $\bm{U}\bm{H}-\bm{U}^{\star}$ we can derive

$\displaystyle\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{\mathrm{F}}=\|\bm{U}\bm{U}^{\top}\bm{U}^{\star}-\bm{U}^{\star}\bm{U}^{\star\top}\bm{U}^{\star}\|_{\mathrm{F}}$
$\displaystyle\qquad\quad\leq\|\bm{U}\bm{U}^{\top}-\bm{U}^{\star}\bm{U}^{\star\top}\|\,\|\bm{U}^{\star}\|_{\mathrm{F}}$
$\displaystyle\qquad\quad=\|\sin\bm{\Theta}\|\,\|\bm{U}^{\star}\|_{\mathrm{F}}\leq\frac{2c_{2}\sigma\sqrt{rn}}{\lambda_{r}^{\star}},$
(4.124)

where the last line arises from Lemma 2.2.2, (4.94b), and
$\|\bm{U}^{\star}\|_{\mathrm{F}}=\sqrt{r}$.

###### Proof of Lemma 4.8.5.

We shall only prove the result for $\bm{H}$; the proof for $\bm{H}^{(l)}$
follows from identical arguments and is hence omitted.

From our discussion in Section 2.2.2, one can express the SVD of
$\bm{H}=\bm{U}^{\top}\bm{U}^{\star}$ as
$\bm{H}=\bm{X}(\cos\bm{\Theta})\bm{Y}^{\top}$, where the columns of $\bm{X}$
(resp. $\bm{Y}$) are the left (resp. right) singular vectors of $\bm{H}$, and
$\bm{\Theta}$ is a diagonal matrix composed of the principal angles between
$\bm{U}$ and $\bm{U}^{\star}$. In light of this and the definition (4.30), we
can establish (4.96b) as follows

$\displaystyle\big{\|}\bm{H}-\mathsf{sgn}(\bm{H})\big{\|}$
$\displaystyle=\big{\|}\bm{X}\big{(}\cos\bm{\Theta}-\bm{I}\big{)}\bm{Y}^{\top}\big{\|}=\big{\|}\bm{I}-\cos\bm{\Theta}\big{\|}$
$\displaystyle\leq\big{\|}\bm{I}-\cos^{2}\bm{\Theta}\big{\|}=\|\sin\bm{\Theta}\|^{2}$
$\displaystyle\leq\frac{2c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}},$
(4.125)

where the middle line holds since $1-\cos\theta\leq 1-\cos^{2}\theta$, and the
last line follows from (4.94b).

Coming back to the claim (4.96a), it suffices to justify that
$\sigma_{\min}(\bm{H})\geq 1/2$. Recognizing that
$\mathsf{sgn}(\bm{H})=\bm{X}\bm{Y}^{\top}$, we see that all singular values of
$\mathsf{sgn}(\bm{H})$ equal 1. Thus, Weyl’s inequality together with (4.125)
gives

$\sigma_{\min}(\bm{H})\geq\sigma_{\min}\big{(}\mathsf{sgn}(\bm{H})\big{)}-\|\bm{H}-\mathsf{sgn}(\bm{H})\|\geq
1-\frac{2c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}}\geq\frac{1}{2},$

with the proviso that $2c_{2}\sigma\sqrt{n}\leq\lambda_{r}^{\star}$.

###### Proof of Lemma 4.8.7.

We start by connecting $\bm{U}\bm{H}\bm{\Lambda}^{\star}$ more explicitly with
$\bm{M}\bm{U}^{\star}$ as follows (the invertibility of $\bm{\Lambda}$ can be
deduced from (4.94c))

$\displaystyle\bm{U}\bm{H}\bm{\Lambda}^{\star}$
$\displaystyle=\bm{U}\bm{\Lambda}\bm{\Lambda}^{-1}\bm{H}\bm{\Lambda}^{\star}=\bm{M}\bm{U}\bm{\Lambda}^{-1}\bm{U}^{\top}\bm{U}^{\star}\bm{\Lambda}^{\star},$
(4.126)

which relies on the definition (4.89) and the eigendecomposition
$\bm{M}\bm{U}=\bm{U}\bm{\Lambda}$. In addition, the eigendecomposition
$\bm{M}^{\star}\bm{U}^{\star}=\bm{U}^{\star}\bm{\Lambda}^{\star}$ gives

$\displaystyle\bm{U}^{\top}\bm{U}^{\star}\bm{\Lambda}^{\star}$
$\displaystyle=\bm{U}^{\top}\bm{M}^{\star}\bm{U}^{\star}=\bm{U}^{\top}\bm{M}\bm{U}^{\star}-\bm{U}^{\top}\bm{E}\bm{U}^{\star}$
$\displaystyle=\bm{\Lambda}\bm{U}^{\top}\bm{U}^{\star}-\bm{U}^{\top}\bm{E}\bm{U}^{\star},$
(4.127)

which taken collectively with (4.126) demonstrates that

$\displaystyle\bm{U}\bm{H}\bm{\Lambda}^{\star}$
$\displaystyle=\bm{M}\bm{U}\bm{\Lambda}^{-1}\bm{\Lambda}\bm{U}^{\top}\bm{U}^{\star}-\bm{M}\bm{U}\bm{\Lambda}^{-1}\bm{U}^{\top}\bm{E}\bm{U}^{\star}$
$\displaystyle=\bm{M}\bm{U}\bm{H}-\bm{M}\bm{U}\bm{\Lambda}^{-1}\bm{U}^{\top}\bm{E}\bm{U}^{\star}$
$\displaystyle=\bm{M}\bm{U}^{\star}+\bm{M}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}-\bm{M}\bm{U}\bm{\Lambda}^{-1}\bm{U}^{\top}\bm{E}\bm{U}^{\star}.$

Consequently, the difference between $\bm{U}\bm{H}\bm{\Lambda}^{\star}$ and
$\bm{M}\bm{U}^{\star}$ obeys

$\displaystyle\big{\|}\bm{U}\bm{H}\bm{\Lambda}^{\star}-\bm{M}\bm{U}^{\star}\big{\|}_{2,\infty}\leq\big{\|}\bm{M}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}$
$\displaystyle\qquad\qquad\qquad+\big{\|}\bm{M}\bm{U}\bm{\Lambda}^{-1}\bm{U}^{\top}\bm{E}\bm{U}^{\star}\big{\|}_{2,\infty}.$
(4.128)

Regarding the second term in (4.128), one can deduce that

$\displaystyle\big{\|}\bm{M}\bm{U}\bm{\Lambda}^{-1}\bm{U}^{\top}\bm{E}\bm{U}^{\star}\big{\|}_{2,\infty}$
$\displaystyle\quad\leq\big{\|}\bm{M}\bm{U}\big{\|}_{2,\infty}\big{\|}\bm{\Lambda}^{-1}\big{\|}\cdot\big{\|}\bm{U}\big{\|}\cdot\big{\|}\bm{E}\big{\|}\cdot\big{\|}\bm{U}^{\star}\big{\|}$
$\displaystyle\quad\overset{(\mathrm{i})}{\leq}\frac{2\big{\|}\bm{M}\bm{U}\big{\|}_{2,\infty}\big{\|}\bm{E}\big{\|}}{\lambda_{r}^{\star}}\overset{(\mathrm{ii})}{\leq}\frac{4\big{\|}\bm{M}\bm{U}\bm{H}\big{\|}_{2,\infty}\big{\|}\bm{E}\big{\|}}{\lambda_{r}^{\star}}$
$\displaystyle\quad\overset{(\mathrm{iii})}{\leq}\frac{4\big{\|}\bm{M}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}\big{\|}\bm{E}\big{\|}}{\lambda_{r}^{\star}}+\frac{4\big{\|}\bm{M}\bm{U}^{\star}\big{\|}_{2,\infty}\big{\|}\bm{E}\big{\|}}{\lambda_{r}^{\star}}$
$\displaystyle\quad\overset{(\mathrm{iv})}{\leq}\big{\|}\bm{M}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}+\frac{4\big{\|}\bm{M}\bm{U}^{\star}\big{\|}_{2,\infty}\big{\|}\bm{E}\big{\|}}{\lambda_{r}^{\star}}.$
(4.129)

Here, (i) follows from the facts $\|\bm{U}\|=\|\bm{U}^{\star}\|=1$ and
$|\lambda_{r}|\geq\lambda_{r}^{\star}-c_{2}\sigma\sqrt{n}\geq\lambda_{r}^{\star}/2$
(see Lemma 4.8.3), (ii) holds due to (4.97), (iii) invokes the triangle
inequality, whereas (iv) holds true provided that
$4\|\bm{E}\|\leq\lambda^{\star}_{r}$. Combine (4.128) and (4.129) to reach

$\displaystyle\big{\|}\bm{U}\bm{H}\bm{\Lambda}^{\star}-\bm{M}\bm{U}^{\star}\big{\|}_{2,\infty}\leq
2\big{\|}\bm{M}\big{(}\bm{U}\bm{H}-\bm{U}^{\star}\big{)}\big{\|}_{2,\infty}+\frac{4\big{\|}\bm{M}\bm{U}^{\star}\big{\|}_{2,\infty}\big{\|}\bm{E}\big{\|}}{\lambda_{r}^{\star}},$

which together with the fact that
$\|(\bm{\Lambda}^{\star})^{-1}\|=1/\lambda^{\star}_{r}$ and the elementary
relation
$\|\bm{A}\|_{2,\infty}=\|\bm{A}\bm{\Lambda}^{\star}(\bm{\Lambda}^{\star})^{-1}\|_{2,\infty}\leq\|\bm{A}\bm{\Lambda}^{\star}\|_{2,\infty}\|(\bm{\Lambda}^{\star})^{-1}\|$
yields the desired claim (4.98a).

When it comes to the second claim (4.98b), combining (4.98a) with the triangle
inequality

$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}$
$\displaystyle=\big{\|}\bm{U}\bm{H}-\bm{M}^{\star}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}_{2,\infty}$
$\displaystyle\leq\big{\|}\bm{U}\bm{H}-\bm{M}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}_{2,\infty}+\big{\|}\bm{E}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}_{2,\infty}$
$\displaystyle\leq\big{\|}\bm{U}\bm{H}-\bm{M}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}_{2,\infty}+\big{\|}\bm{E}\bm{U}^{\star}\big{\|}_{2,\infty}\,/\,\lambda_{r}^{\star}$

immediately establishes the advertised bound. Here the last relation again
arises from the elementary inequality
$\|\bm{A}\bm{B}\|_{2,\infty}\leq\|\bm{A}\|_{2,\infty}\|\bm{B}\|$.

###### Proof of Lemma 4.8.8.

First of all, taking Condition (4.101) collectively with (4.98b) and
rearranging terms yield (4.102a):

$\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}\leq\frac{1}{1-\rho_{1}}\big{(}\mathcal{E}_{1,1}+\mathcal{E}_{2}+\mathcal{E}_{3}\big{)}\leq
2\big{(}\mathcal{E}_{1,1}+\mathcal{E}_{2}+\mathcal{E}_{3}\big{)},$ (4.130)

where the last inequality follows from $\rho\leq 1/2$. Substituting (4.101)
and (4.102a) into (4.98a) then gives (4.102b):

$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{M}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}_{2,\infty}$
$\displaystyle\leq\mathcal{E}_{1,1}+2\rho_{1}\big{(}\mathcal{E}_{1,1}+\mathcal{E}_{2}+\mathcal{E}_{3}\big{)}+\mathcal{E}_{2}$
$\displaystyle\leq
2\mathcal{E}_{1,1}+2\mathcal{E}_{2}+2\rho_{1}\mathcal{E}_{3},$ (4.131)

where once again we use the assumption that $\rho\leq 1/2$. In addition, the
following observation connects $\bm{U}\bm{H}$ with
$\bm{U}\mathsf{sgn}(\bm{H})$:

$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{U}\mathsf{sgn}(\bm{H})\big{\|}_{2,\infty}\leq\|\bm{U}\|_{2,\infty}\big{\|}\bm{H}-\mathsf{sgn}(\bm{H})\big{\|}$
$\displaystyle\qquad\overset{(\mathrm{i})}{\leq}\frac{2c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}}\big{\|}\bm{U}\big{\|}_{2,\infty}\overset{(\mathrm{ii})}{\leq}\frac{4c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}}\big{\|}\bm{U}\bm{H}\big{\|}_{2,\infty}$
$\displaystyle\qquad\overset{(\mathrm{iii})}{\leq}\frac{4c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}}\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}+\frac{4c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}}\sqrt{\frac{\mu
r}{n}},$ (4.132)

where (i) results from (4.96b), (ii) relies on (4.97a), and (iii) comes from
the triangle inequality
$\|\bm{U}\bm{H}\|_{2,\infty}\leq\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{2,\infty}+\|\bm{U}^{\star}\|_{2,\infty}$
and the definition (4.24).

The preceding bound together with the triangle inequality gives (4.102c):

$\displaystyle\big{\|}\bm{U}\mathsf{sgn}(\bm{H})-\bm{U}^{\star}\big{\|}_{2,\infty}$
$\displaystyle\leq\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}+\big{\|}\bm{U}\bm{H}-\bm{U}\mathsf{sgn}(\bm{H})\big{\|}_{2,\infty}$
$\displaystyle\leq\Big{(}1+\frac{4c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}}\Big{)}\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}+\frac{4c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}}\sqrt{\frac{\mu
r}{n}}$ $\displaystyle\leq
4\big{(}\mathcal{E}_{1,1}+\mathcal{E}_{2}+\mathcal{E}_{3}\big{)}+\frac{4c_{2}^{2}\sigma^{2}\sqrt{\mu
rn}}{(\lambda_{r}^{\star})^{2}},$

where the last inequality holds as long as
$4c_{2}^{2}\sigma^{2}n\leq(\lambda_{r}^{\star})^{2}$. Additionally, the
inequalities (4.131) and (4.132) further allow us to deduce (4.102d):

$\displaystyle\big{\|}\bm{U}\mathsf{sgn}(\bm{H})-\bm{M}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}_{2,\infty}$
$\displaystyle\quad\leq\big{\|}\bm{U}\bm{H}-\bm{M}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}_{2,\infty}+\big{\|}\bm{U}\bm{H}-\bm{U}\mathsf{sgn}(\bm{H})\big{\|}_{2,\infty}$
$\displaystyle\quad\leq
2\mathcal{E}_{1,1}+2\mathcal{E}_{2}+2\rho_{1}\mathcal{E}_{3}+\frac{8c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}}\big{(}\mathcal{E}_{1,1}+\mathcal{E}_{2}+\mathcal{E}_{3}\big{)}+\frac{4c_{2}^{2}\sigma^{2}\sqrt{\mu
rn}}{(\lambda_{r}^{\star})^{2}}$ $\displaystyle\quad\leq
3\mathcal{E}_{1,1}+3\mathcal{E}_{2}+\Big{(}2\rho_{1}+\frac{8c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}}\Big{)}\mathcal{E}_{3}+\frac{4c_{2}^{2}\sigma^{2}\sqrt{\mu
rn}}{(\lambda_{r}^{\star})^{2}}.$

Here, the penultimate line combines (4.102a), (4.102b) and (4.132), while the
last inequality relies on the assumption
$8c_{2}^{2}\sigma^{2}n\leq(\lambda_{r}^{\star})^{2}$.

###  4.9 Appendix B: Proof of Corollary 4.2.4

Moving on to the proof of Corollary 4.2.4, we start by pointing out the main
issue that deserves particular attention. Roughly speaking, we have learned
from Theorem 4.2.3 (and its analysis) that $\bm{U}^{\star}\approx\bm{U}\bm{H}$
under mild conditions, which naturally suggests that

$\bm{M}^{\star}=\bm{U}^{\star}\bm{\Lambda}^{\star}\bm{U}^{\star\top}\approx\bm{U}\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}\bm{U}^{\top}.$

As a result, in order to enable
$\bm{M}^{\star}\approx\bm{U}\bm{\Lambda}\bm{U}^{\top}$, one would need to
ensure $\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}\approx\bm{\Lambda}$.

The above argument, while highly informal, reveals the core idea underlying
the proof. Our proof is based upon the following observation

$\displaystyle\big{\|}\bm{U}\bm{\Lambda}\bm{U}^{\top}-\bm{U}^{\star}\bm{\Lambda}^{\star}\bm{U}^{\star\top}\big{\|}_{\infty}\leq\underset{\eqqcolon\mathcal{\gamma}_{1}}{\underbrace{\big{\|}\bm{U}\big{(}\bm{\Lambda}-\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}\big{)}\bm{U}^{\top}\big{\|}_{\infty}}}$
$\displaystyle\quad\quad\quad\quad+\underset{\eqqcolon\gamma_{2}}{\underbrace{\big{\|}\bm{U}\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}\bm{U}^{\top}-\bm{U}^{\star}\bm{\Lambda}^{\star}\bm{U}^{\star\top}\big{\|}_{\infty}}},$
(4.133)

which leaves us with two terms to cope with.

##### Step 1: bounding $\gamma_{1}$

Regarding $\gamma_{1}$ defined in (4.133), it is seen that

$\displaystyle\gamma_{1}$
$\displaystyle\leq\big{\|}\bm{U}\big{\|}_{2,\infty}^{2}\big{\|}\bm{\Lambda}-\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}\big{\|}\leq\frac{4\mu
r}{n}\big{\|}\bm{\Lambda}-\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}\big{\|}.$
(4.134)

In the last relation, we have exploited the fact that

$\displaystyle\big{\|}\bm{U}\big{\|}_{2,\infty}$
$\displaystyle=\big{\|}\bm{U}\mathsf{sgn}(\bm{H})\big{\|}_{2,\infty}\leq\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}+\big{\|}\bm{U}\mathsf{sgn}(\bm{H})-\bm{U}^{\star}\big{\|}_{2,\infty}$
$\displaystyle\leq 2\sqrt{\mu r/n},$ (4.135)

where the last inequality relies on (4.31a) and the assumption
$\sigma\sqrt{n}(\kappa+\sqrt{\log n})\leq c_{1}\lambda_{r}^{\star}$ for some
sufficiently small constant $c_{1}>0$.

It then boils down to bounding
$\|\bm{\Lambda}-\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}\|$. Towards this, it
is seen from the identity (4.127) and the definition
$\bm{H}=\bm{U}^{\top}\bm{U}^{\star}$ that

$\displaystyle\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}-\bm{\Lambda}$
$\displaystyle=\bm{\Lambda}\bm{H}\bm{H}^{\top}-\bm{U}^{\top}\bm{E}\bm{U}^{\star}\bm{H}^{\top}-\bm{\Lambda},$

which together with the triangle inequality reveals that

$\displaystyle\big{\|}\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}-\bm{\Lambda}\big{\|}$
$\displaystyle\leq\big{\|}\bm{\Lambda}\big{(}\bm{H}\bm{H}^{\top}-\bm{I}\big{)}\big{\|}+\big{\|}\bm{U}^{\top}\bm{E}\bm{U}^{\star}\bm{H}^{\top}\big{\|}.$
(4.136)

The rest of this step is devoted to controlling the above two terms.

With regards to the first term on the right-hand side of (4.136), we make the
observation that

$\|\bm{H}\bm{H}^{\top}-\bm{I}\|=\|\cos^{2}\bm{\Theta}-\bm{I}\|=\|\sin^{2}\bm{\Theta}\|\leq\frac{2c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}},$

where, as usual, $\bm{\Theta}$ denotes a diagonal matrix composed of the
principal angles between $\bm{U}$ and $\bm{U}^{\star}$, and the last
inequality results from Lemma 4.8.3. This combined with Weyl’s inequality and
Lemma 4.8.3 leads to

$\displaystyle\|\bm{\Lambda}(\bm{H}\bm{H}^{\top}-\bm{I})\|$
$\displaystyle\leq\|\bm{\Lambda}\|\,\|\bm{H}\bm{H}^{\top}-\bm{I}\|\leq(\|\bm{\Lambda}^{\star}\|+\|\bm{E}\|)\,\|\bm{H}\bm{H}^{\top}-\bm{I}\|$
$\displaystyle\leq\big{(}\big{|}\lambda_{1}^{\star}\big{|}+c_{2}\sigma\sqrt{n}\big{)}\frac{2c_{2}^{2}\sigma^{2}n}{(\lambda_{r}^{\star})^{2}}\leq\frac{4c_{2}^{2}\kappa\sigma^{2}n}{\lambda_{r}^{\star}},$
(4.137)

provided that
$c_{2}\sigma\sqrt{n}\leq\lambda_{r}^{\star}\leq|\lambda_{1}^{\star}|$.

When it comes to the second term on the right-hand side of (4.136), let us
introduce an orthonormal matrix
$\bm{R}\coloneqq\arg\min_{\bm{Q}\in\mathcal{O}^{r\times
r}}\|\bm{U}\bm{Q}-\bm{U}^{\star}\|$, which helps us derive

$\displaystyle\big{\|}\bm{U}^{\top}\bm{E}\bm{U}^{\star}\bm{H}^{\top}\big{\|}$
$\displaystyle\leq\big{\|}\bm{U}^{\top}\bm{E}\bm{U}^{\star}\big{\|}=\big{\|}\bm{R}^{\top}\bm{U}^{\top}\bm{E}\bm{U}^{\star}\big{\|}$
$\displaystyle\leq\big{\|}\bm{U}^{\star\top}\bm{E}\bm{U}^{\star}\big{\|}+\big{\|}\big{(}\bm{U}\bm{R}-\bm{U}^{\star}\big{)}^{\top}\bm{E}\bm{U}^{\star}\big{\|}$
$\displaystyle\leq\big{\|}\bm{U}^{\star\top}\bm{E}\bm{U}^{\star}\big{\|}+\|\bm{E}\|\,\mathsf{dist}\big{(}\bm{U},\bm{U}^{\star}\big{)}.$
(4.138)

Here, the first inequality holds since
$\|\bm{H}\|=\|\bm{U}^{\top}\bm{U}^{\star}\|\leq 1$, while the last line
follows since $\|\bm{U}^{\star}\|=1$ and
$\|\bm{U}\bm{R}-\bm{U}^{\star}\|=\mathsf{dist}(\bm{U},\bm{U}^{\star})$. In
addition, we claim that with probability at least $1-2n^{-7}$,

$\|\bm{U}^{\star\top}\bm{E}\bm{U}^{\star}\|\leq(6+12c_{\mathsf{b}})\sigma\sqrt{r\log
n}.$ (4.139)

If this claim were valid, then one could continue the derivation (4.138) and
invoke Lemma 4.8.3 to demonstrate that

$\big{\|}\bm{U}^{\top}\bm{E}\bm{U}^{\star}\bm{H}^{\top}\big{\|}\leq(6+12c_{\mathsf{b}})\sigma\sqrt{r\log
n}+\frac{2c_{2}^{2}\sigma^{2}n}{\lambda_{r}^{\star}}.$ (4.140)

To finish up, substituting (4.137) and (4.140) into (4.136) yields

$\displaystyle\big{\|}\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}-\bm{\Lambda}\big{\|}\leq\frac{6c_{2}^{2}\kappa\sigma^{2}n}{\lambda_{r}^{\star}}+(6+12c_{\mathsf{b}})\sigma\sqrt{r\log
n},$ (4.141)

which combined with (4.134) leads to

$\gamma_{1}\lesssim\frac{\sigma^{2}\kappa\mu
r}{\lambda_{r}^{\star}}+\frac{\sigma\mu\sqrt{r^{3}\log n}}{n}.$ (4.142)

##### Step 2: bounding $\gamma_{2}$

Before proceeding, we recall from (4.120) that

$\displaystyle\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}\lesssim\frac{\sigma\kappa\sqrt{\mu
r}+\sigma\sqrt{r\log
n}}{\lambda_{r}^{\star}}\lesssim\frac{\sigma\kappa\sqrt{\mu r\log
n}}{\lambda_{r}^{\star}}$ (4.143)

Recognizing the basic decomposition

$\displaystyle\gamma_{2}=\big{\|}\bm{U}\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}\bm{U}^{\top}-\bm{U}^{\star}\bm{\Lambda}^{\star}\bm{U}^{\star\top}\big{\|}_{\infty}=\big{\|}\bm{A}_{1}+\bm{A}_{1}^{\top}+\bm{A}_{2}\big{\|}_{\infty}$

with
$\bm{A}_{1}\coloneqq(\bm{U}\bm{H}-\bm{U}^{\star})\bm{\Lambda}^{\star}\bm{U}^{\star\top}$
and
$\bm{A}_{2}\coloneqq(\bm{U}\bm{H}-\bm{U}^{\star})\bm{\Lambda}^{\star}(\bm{U}\bm{H}-\bm{U}^{\star})^{\top}$,
we can control each of these terms separately. Firstly, observe that

$\displaystyle\big{\|}\bm{A}_{1}\big{\|}_{\infty}$
$\displaystyle\leq\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{2,\infty}\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}\big{\|}\bm{\Lambda}^{\star}\big{\|}$
$\displaystyle\lesssim\big{|}\lambda_{1}^{\star}\big{|}\sqrt{\frac{\mu
r}{n}}\cdot\frac{\sigma\kappa\sqrt{\mu r\log
n}}{\lambda_{r}^{\star}}\asymp\sigma\kappa^{2}\mu r\sqrt{\frac{\log n}{n}},$

where we have made use of (4.143). Similarly,

$\displaystyle\big{\|}\bm{A}_{2}\big{\|}_{\infty}$
$\displaystyle\leq\|\bm{U}\bm{H}-\bm{U}^{\star}\|_{2,\infty}^{2}\big{\|}\bm{\Lambda}^{\star}\big{\|}\lesssim\big{|}\lambda_{1}^{\star}\big{|}\frac{\sigma^{2}\kappa^{2}\mu
r\log n}{\big{(}\lambda_{r}^{\star}\big{)}^{2}}$
$\displaystyle\asymp\frac{\sigma^{2}\kappa^{3}\mu r\log
n}{\lambda_{r}^{\star}}\lesssim\sigma\kappa^{2}\mu r\sqrt{\frac{\log n}{n}},$

provided that $\sigma\kappa\sqrt{n\log n}\lesssim\lambda_{r}^{\star}$.
Consequently,

$\displaystyle\gamma_{2}$ $\displaystyle\leq
2\big{\|}\bm{A}_{1}\big{\|}_{\infty}+\big{\|}\bm{A}_{2}\big{\|}_{\infty}\lesssim\sigma\kappa^{2}\mu
r\sqrt{\frac{\log n}{n}}.$

##### Step 3: putting all this together

Combining the above bounds, we demonstrate that

$\displaystyle\big{\|}\bm{U}\bm{\Lambda}\bm{U}^{\top}-\bm{U}^{\star}\bm{\Lambda}^{\star}\bm{U}^{\star\top}\big{\|}_{\infty}\leq\gamma_{1}+\gamma_{2}$
$\displaystyle\lesssim\sigma\kappa^{2}\mu r\sqrt{\frac{\log
n}{n}}+\frac{\kappa\mu r\sigma^{2}}{\lambda_{r}^{\star}}+\frac{\sigma\mu
r\sqrt{r\log n}}{n}\asymp\sigma\kappa^{2}\mu r\sqrt{\frac{\log n}{n}},$
(4.144)

provided that $\sigma\sqrt{n}\lesssim\lambda_{r}^{\star}$. This concludes the
proof of Corollary 4.2.4, as long as the claim (4.139) can be validated.

##### Proof of the claim (4.139)

Let us start by expressing $\bm{U}^{\star\top}\bm{E}\bm{U}^{\star}$ as a sum
of independent random matrices as follows

$\bm{U}^{\star\top}\bm{E}\bm{U}^{\star}=\sum_{i,j:\,i\geq
j}E_{i,j}\Big{\\{}\big{(}\bm{U}_{i,\cdot}^{\star}\big{)}^{\top}\bm{U}_{j,\cdot}^{\star}+\big{(}\bm{U}_{j,\cdot}^{\star}\big{)}^{\top}\bm{U}_{i,\cdot}^{\star}\Big{\\}}\eqqcolon\sum_{i,j:\,i\geq
j}\bm{Z}_{i,j}.$

From the elementary inequality $(\bm{A}+\bm{A}^{\top})^{2}\preceq
2\bm{A}\bm{A}^{\top}+2\bm{A}^{\top}\bm{A}$, we have

$\displaystyle\mathbb{E}\big{[}\bm{Z}_{i,j}^{2}\big{]}$
$\displaystyle\preceq\sigma^{2}\Big{\\{}\big{(}\bm{U}_{i,\cdot}^{\star}\big{)}^{\top}\bm{U}_{j,\cdot}^{\star}+\big{(}\bm{U}_{j,\cdot}^{\star}\big{)}^{\top}\bm{U}_{i,\cdot}^{\star}\Big{\\}}\Big{\\{}\big{(}\bm{U}_{i,\cdot}^{\star}\big{)}^{\top}\bm{U}_{j,\cdot}^{\star}+\big{(}\bm{U}_{j,\cdot}^{\star}\big{)}^{\top}\bm{U}_{i,\cdot}^{\star}\Big{\\}}^{\top}$
$\displaystyle\preceq
2\sigma^{2}\Big{\\{}\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}\big{(}\bm{U}_{i,\cdot}^{\star}\big{)}^{\top}\bm{U}_{i,\cdot}^{\star}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}\big{(}\bm{U}_{j,\cdot}^{\star}\big{)}^{\top}\bm{U}_{j,\cdot}^{\star}\Big{\\}},$

thus indicating that

$\displaystyle v$ $\displaystyle=\Big{\|}\sum_{i,j:i\geq
j}\mathbb{E}\big{[}\bm{Z}_{i,j}^{2}\big{]}\Big{\|}\leq
2\sigma^{2}\Big{\|}\sum_{i=1}^{n}\sum_{j=1}^{n}\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}\big{(}\bm{U}_{i,\cdot}^{\star}\big{)}^{\top}\bm{U}_{i,\cdot}^{\star}\Big{\|}$
$\displaystyle=2\sigma^{2}\|\bm{U}^{\star}\|_{\mathrm{F}}^{2}\Big{\|}\sum_{i}\big{(}\bm{U}_{i,\cdot}^{\star}\big{)}^{\top}\bm{U}_{i,\cdot}^{\star}\Big{\|}=2\sigma^{2}r\big{\|}\bm{U}^{\star\top}\bm{U}^{\star}\big{\|}=2\sigma^{2}r.$

In addition, each matrix $\bm{Z}_{i,j}$ can be bounded in size by

$\max_{i,j}\|\bm{Z}_{i,j}\|\leq
2\max_{i,j}\big{|}E_{i,j}\big{|}\max_{i,j}\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}\leq
2B\frac{\mu r}{n}\eqqcolon L,$

where we have used the definition of the incoherence parameter $\mu$. Apply
the matrix Bernstein inequality (see Corollary 3.1.4) to reach

$\displaystyle\big{\|}\bm{U}^{\star\top}\bm{E}\bm{U}^{\star}\big{\|}$
$\displaystyle\leq 4\sqrt{v\log n}+6L\log n\leq\sigma\sqrt{32r\log
n}+12B\frac{\mu r\log n}{n}$
$\displaystyle\leq(6+12c_{\mathsf{b}})\sigma\sqrt{r\log n}$

with probability exceeding $1-2n^{-7}.$ Here, the last line holds since

$B\frac{\mu r\log n}{n}\leq c_{\mathsf{b}}\sigma\sqrt{\frac{n}{\mu\log
n}}\cdot\frac{\mu r\log n}{n}=c_{\mathsf{b}}\sigma\sqrt{r\log
n}\sqrt{\frac{\mu r}{n}}\leq c_{\mathsf{b}}\sigma\sqrt{r\log n},$

which relies on the assumption (4.29) and the basic fact $\mu\leq n/r$.

###  4.10 Appendix C: Proof of Theorem 4.3.1

###### A symmetrization trick.

As alluded to previously, the proof is built on a “symmetric dilation” trick
that helps symmetrize a general matrix. We start with the following
definition.

######  Definition 4.10.1 (Symmetric dilation).

For any matrix $\bm{A}\in\mathbb{R}^{n_{1}\times n_{2}}$, its symmetric
dilation $\mathcal{S}(\bm{A})\in\mathbb{R}^{(n_{1}+n_{2})\times(n_{1}+n_{2})}$
is defined to be

$\mathcal{S}(\bm{A})=\left[\begin{array}[]{cc}\bm{0}&\bm{A}\\\
\bm{A}^{\top}&\bm{0}\end{array}\right].$

Apart from the symmetry of $\mathcal{S}(\bm{A})$, which is immediate from its
definition, the main benefit of the symmetric dilation lies in the
correspondence between the eigendecomposition of $\mathcal{S}(\bm{A})$ and the
singular value decomposition of $\bm{A}$. More specifically, let
$\bm{U}\bm{\Sigma}\bm{V}^{\top}$ be the SVD of $\bm{A}$. Then one has the
following eigendecomposition for $\mathcal{S}(\bm{A})$:

$\mathcal{S}(\bm{A})=\frac{1}{\sqrt{2}}\left[\begin{array}[]{cc}\bm{U}&\bm{U}\\\
\bm{V}&-\bm{V}\end{array}\right]\cdot\left[\begin{array}[]{cc}\bm{\Sigma}&\bm{0}\\\
\bm{0}&-\bm{\Sigma}\end{array}\right]\cdot\frac{1}{\sqrt{2}}\left[\begin{array}[]{cc}\bm{U}&\bm{U}\\\
\bm{V}&-\bm{V}\end{array}\right]^{\top}.$ (4.145)

Here, the columns of
$\frac{1}{\sqrt{2}}\left[{\scriptsize\begin{array}[]{cc}\bm{U}&\bm{U}\\\
\bm{V}&-\bm{V}\end{array}}\right]$ are orthonormal and represent the
eigenvectors of $\mathcal{S}(\bm{A})$, whereas
$\left[{\scriptsize\begin{array}[]{cc}\bm{\Sigma}&\bm{0}\\\
\bm{0}&-\bm{\Sigma}\end{array}}\right]$ contains all (non-zero) eigenvalues of
$\mathcal{S}(\bm{A})$.

Utilizing this “symmetric dilation” trick, we can translate the observation
model $\bm{M}=\bm{M}^{\star}+\bm{E}$ into the following equivalent form

$\mathcal{S}(\bm{M})=\mathcal{S}(\bm{M}^{\star})+\mathcal{S}(\bm{E}),$

which is in line with the symmetric observation model stated in (4.26).

###### Verifying conditions.

To invoke the general theory in Section 4.2, one is required to first examine
the spectral properties of $\mathcal{S}(\bm{M}^{\star})$ and
$\mathcal{S}(\bm{M})$, as well as the assumptions on the noise part
$\mathcal{S}(\bm{E})$.

Recall that
$\bm{M}^{\star}=\bm{U}^{\star}\bm{\Sigma}^{\star}\bm{V}^{\star\top}$, which
together with the relation (4.145) reveals that: (i)
$\mathcal{S}(\bm{M}^{\star})$ has rank $2r$ and condition number $\kappa$;
(ii) the nonzero eigenvalues of $\mathcal{S}(\bm{M}^{\star})$ and the
corresponding eigenvectors are reflected respectively in the matrices

$\overline{\bm{\Lambda}}^{\star}\coloneqq\left[\begin{array}[]{cc}\bm{\Sigma}^{\star}&\bm{0}\\\
\bm{0}&-\bm{\Sigma}^{\star}\end{array}\right]\quad\text{and}\quad\overline{\bm{U}}^{\star}\coloneqq\frac{1}{\sqrt{2}}\left[\begin{array}[]{cc}\bm{U}^{\star}&\bm{U}^{\star}\\\
\bm{V}^{\star}&-\bm{V}^{\star}\end{array}\right]$ (4.146)

Similarly, given that the SVD of $\bm{M}$ is
$\bm{M}=\bm{U}\bm{\Sigma}\bm{V}^{\top}+\bm{U}_{\perp}\bm{\Sigma}_{\perp}\bm{V}_{\perp}^{\top}$,
we see that the $2r$-leading eigenvalues of $\mathcal{S}(\bm{M})$ and the
corresponding eigenvectors are represented respectively by the matrices

$\overline{\bm{\Lambda}}\coloneqq\left[\begin{array}[]{cc}\bm{\Sigma}&\bm{0}\\\
\bm{0}&-\bm{\Sigma}\end{array}\right]\quad\text{and}\quad\overline{\bm{U}}\coloneqq\frac{1}{\sqrt{2}}\left[\begin{array}[]{cc}\bm{U}&\bm{U}\\\
\bm{V}&-\bm{V}\end{array}\right].$

Further, the incoherence parameter $\overline{\mu}$ of
$\mathcal{S}(\bm{M}^{\star})$ (cf. (4.24)) obeys

$\displaystyle\overline{\mu}$
$\displaystyle\coloneqq\frac{(n_{1}+n_{2})}{2r}\|\overline{\bm{U}}^{\star}\|_{2,\infty}^{2}\overset{(\text{i})}{=}\frac{(n_{1}+n_{2})}{2r}\max\big{\\{}\|\bm{U}^{\star}\|_{2,\infty}^{2},\|\bm{V}^{\star}\|_{2,\infty}^{2}\big{\\}}$
$\displaystyle\overset{(\text{ii})}{\leq}\frac{(n_{1}+n_{2})}{\min\\{n_{1},n_{2}\\}}\frac{\mu}{2}\overset{(\text{iii})}{=}\frac{(n_{1}+n_{2})}{2n_{1}}\mu.$
(4.147)

Here, the relation (i) is based on the definition (4.146), the inequality (ii)
follows from the incoherence of $\bm{M}^{\star}$ (cf. Definition 3.8.1), while
the last one (iii) holds under the assumption $n_{1}\leq n_{2}$.

When it comes to the “symmetrized” noise part, it is straightforward to verify
that under Assumption 4.2, the matrix $\mathcal{S}(\bm{E})$ satisfies
Assumption 4.1 with precisely the quantities $\sigma,B$ and $c_{\mathsf{b}}$.

######  $\ell_{2,\infty}$ and $\ell_{\infty}$ guarantees.

With the above preparations in place, apply Theorem 4.2.3 (more specifically
(4.120)) to demonstrate that

$\displaystyle\|\overline{\bm{U}}\,\overline{\bm{U}}^{\top}\overline{\bm{U}}^{\star}-\overline{\bm{U}}^{\star}\|_{2,\infty}$
$\displaystyle\lesssim\frac{\sigma\kappa\sqrt{\overline{\mu}r}+\sigma\sqrt{r\log
n}}{\sigma_{r}^{\star}}$
$\displaystyle\lesssim\frac{\sigma\kappa\sqrt{n_{2}\mu
r/n_{1}}+\sigma\sqrt{r\log n}}{\sigma_{r}^{\star}},$ (4.148)

where the last relation follows from (4.147). Further, note that

$\displaystyle\overline{\bm{U}}\,\overline{\bm{U}}^{\top}\overline{\bm{U}}^{\star}-\overline{\bm{U}}^{\star}$
$\displaystyle=\frac{1}{\sqrt{2}}\left[\begin{array}[]{cc}\bm{U}\bm{H}_{\bm{U}}-\bm{U}^{\star},&\bm{U}\bm{H}_{\bm{U}}-\bm{U}^{\star}\\\
\bm{V}\bm{H}_{\bm{V}}-\bm{V}^{\star},&-(\bm{V}\bm{H}_{\bm{V}}-\bm{V}^{\star})\end{array}\right],$

where $\bm{H}_{\bm{U}}\coloneqq\bm{U}^{\top}\bm{U}^{\star}$ and
$\bm{H}_{\bm{V}}\coloneqq\bm{V}^{\top}\bm{V}^{\star}$. Combining this with the
upper bound (4.148) then yields

$\max\big{\\{}\|\bm{U}\bm{H}_{\bm{U}}-\bm{U}^{\star}\|_{2,\infty},\|\bm{V}\bm{H}_{\bm{V}}-\bm{V}^{\star}\|_{2,\infty}\big{\\}}\lesssim\frac{\sigma\kappa\sqrt{n_{2}\mu
r/n_{1}}+\sigma\sqrt{r\log n}}{\sigma_{r}^{\star}}.$

We can then repeat the same analysis as in the proof of Lemma 4.8.8 to connect
$\|\bm{U}\bm{H}_{\bm{U}}-\bm{U}^{\star}\|_{2,\infty}$ (resp.
$\|\bm{V}\bm{H}_{\bm{V}}-\bm{V}^{\star}\|_{2,\infty}$) with
$\|\bm{U}\mathsf{sgn}(\bm{H}_{\bm{U}})-\bm{U}^{\star}\|_{2,\infty}$ (resp.
$\|\bm{V}\mathsf{sgn}(\bm{H}_{\bm{V}})-\bm{V}^{\star}\|_{2,\infty}$), and
obtain the desired bound in (4.41); the details are omitted here for the sake
of conciseness.

We now proceed to the second claim (4.42). Towards this, invoke Corollary
4.2.4 and the inequality (4.147) to obtain

$\big{\|}\overline{\bm{U}}\,\overline{\bm{\Lambda}}\,\overline{\bm{U}}^{\top}-\mathcal{S}(\bm{M}^{\star})\big{\|}_{\infty}\lesssim\sigma\kappa^{2}\overline{\mu}r\sqrt{\frac{\log
n}{n}}\lesssim\sigma\kappa^{2}\mu r\sqrt{\frac{n\log n}{n_{1}^{2}}}.$

This in conjunction with the following observations

$\displaystyle\overline{\bm{U}}\,\overline{\bm{\Lambda}}\,\overline{\bm{U}}^{\top}$
$\displaystyle=\mathcal{S}\big{(}\bm{U}\bm{\Sigma}\bm{V}^{\top}\big{)}$
$\displaystyle\big{\|}\mathcal{S}\big{(}\bm{U}\bm{\Sigma}\bm{V}^{\top}\big{)}-\mathcal{S}\big{(}\bm{M}^{\star}\big{)}\big{\|}_{\infty}$
$\displaystyle=\big{\|}\bm{U}\bm{\Sigma}\bm{V}^{\top}-\bm{M}^{\star}\big{\|}_{\infty}$

immediately establishes the second claim.

###  4.11 Appendix D: Proof of Theorem 4.6.1

As before (see (4.85)), we assume throughout the proof that
$\lambda_{r}^{\star}>0$ for the purpose of simplifying notation.

####  4.11.1 Proof outline

We now outline the proof of our distributional guarantees in Theorem 4.6.1.
The first step consists of justifying the heuristic first-order approximation
in (4.65). This is stated in the lemma below, with the proof deferred to
Section 4.11.2.

######  Lemma 4.11.1 (First-order approximation).

Suppose that the assumptions of Theorem 4.2.3 hold. Then with probability at
least $1-O(n^{-5})$, one can write

$\displaystyle\bm{U}\mathsf{sgn}(\bm{H})-\bm{U}^{\star}$
$\displaystyle=\underset{\eqqcolon\,\bm{Z}}{\underbrace{\bm{E}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}}}+\bm{\Psi},$
(4.149a) $\displaystyle\bm{M}-\bm{M}^{\star}$
$\displaystyle=\underset{\eqqcolon\,\bm{W}}{\underbrace{\bm{E}\bm{U}^{\star}\bm{U}^{\star\top}+\bm{U}^{\star}\bm{U}^{\star\top}\bm{E}}}+\bm{\Phi}$
(4.149b)

for some matrices $\bm{\Psi}$ and $\bm{\Phi}$ obeying

$\displaystyle\|\bm{\Psi}\|_{2,\infty}$
$\displaystyle\lesssim\frac{\sigma^{2}\kappa\sqrt{\mu
rn\log^{2}n}}{(\lambda_{r}^{\star})^{2}}+\frac{\kappa\sigma^{2}\sqrt{\mu
rn}}{(\lambda_{r}^{\star})^{2}}+\frac{\sigma}{\lambda_{r}^{\star}}\sqrt{\frac{\mu
r^{2}\log n}{n}},$ (4.150a) $\displaystyle\big{\|}\bm{\Phi}\big{\|}_{\infty}$
$\displaystyle\lesssim\frac{\sigma^{2}\mu r\kappa^{2}\log
n}{\lambda_{r}^{\star}}+\frac{\sigma\kappa\mu\sqrt{r^{3}\log n}}{n}.$ (4.150b)

######  Remark 4.11.2.

In addition to quantifying the goodness of the approximation (4.149b), Lemma
4.11.1 also delivers a more refined characterization for the first-order
approximation
$\bm{U}\mathsf{sgn}(\bm{H})-\bm{U}^{\star}\approx\bm{E}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}$
in comparison to Theorem 4.2.3. As it turns out, this result (4.149a) also
assists in performing statistical inference on the low-rank factors
$\bm{U}^{\star}$. The interested reader is referred to yan2021inference for
details.

In turn, Lemma 4.11.1 motivates one to pin down the distribution of the matrix
$\bm{W}$ in (4.149b). This can be accomplished by invoking the Berry-Esseen
Theorem (e.g., chen2010normal), which gives rise to the following
distributional characterization. The proof of this lemma can be found in
Section 4.11.3.

######  Lemma 4.11.3 (Gaussian approximation).

Suppose that the assumptions of Theorem 4.2.3 hold, and that

$\displaystyle\frac{\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}}{\big{\|}\bm{U}^{\star}\big{\|}_{\mathrm{F}}^{2}}$
$\displaystyle\gtrsim\frac{B^{2}\kappa^{2}\mu^{2}r^{2}\log^{2}n}{\sigma_{\min}^{2}n^{2}}+\frac{\sigma^{4}\mu^{2}r\kappa^{4}\log^{3}n}{\sigma_{\min}^{2}(\lambda_{r}^{\star})^{2}}.$
(4.151)

Let
$\bm{W}=\bm{E}\bm{U}^{\star}\bm{U}^{\star\top}+\bm{U}^{\star}\bm{U}^{\star\top}\bm{E}$.
For any $1\leq i,j\leq n$, one has

$\displaystyle\sup_{z\in\mathbb{R}}\left|\mathbb{P}\left(W_{i,j}\leq
z\sqrt{v_{i,j}^{\star}}\right)-\Phi(z)\right|$ $\displaystyle=o(1),$ (4.152a)
$\displaystyle\big{\|}\bm{\Phi}\big{\|}_{\infty}$
$\displaystyle=o\left(\sqrt{v_{i,j}^{\star}}\right),$ (4.152b)

where $v_{i,j}^{\star}$ is defined in (4.68), and $\Phi(\cdot)$ denotes the
CDF of the standard Gaussian distribution.

To finish up, invoke Lemma 4.11.1 and (4.152b) to yield

$M_{i,j}-M_{i,j}^{\star}=W_{i,j}+\delta_{\phi}\sqrt{v_{i,j}^{\star}}\qquad\text{with
}\delta_{\phi}=o(1).$

A little algebra further gives

$\displaystyle\left|\mathbb{P}\left(M_{i,j}-M_{i,j}^{\star}\leq
z\sqrt{v_{i,j}^{\star}}\right)-\Phi(z)\right|=\left|\mathbb{P}\left(W_{i,j}\leq\left(z-\delta_{\phi}\right)\sqrt{v_{i,j}^{\star}}\right)-\Phi(z)\right|$
$\displaystyle\qquad\leq\left|\mathbb{P}\left(W_{i,j}\leq\left(z-\delta_{\phi}\right)\sqrt{v_{i,j}^{\star}}\right)-\Phi(z-\delta_{\phi})\right|+\left|\Phi(z-\delta_{\phi})-\Phi(z)\right|$
$\displaystyle\qquad\leq o(1)+\delta_{\phi}=o(1),$

where the last line invokes Lemma 4.11.3 and the fact that
$|\Phi(u)-\Phi(v)|\leq|u-v|$ for any $u,v\in\mathbb{R}$. This completes the
proof of Theorem 4.6.1, as long as Lemmas 4.11.1 and 4.11.3 can be
established. The rest of this section is thus devoted to proving Lemmas 4.11.1
and 4.11.3.

####  4.11.2 Proof of Lemma 4.11.1

Before proceeding to the proof, we make note of several preliminary facts that
are all direct consequences of the analysis of Theorem 4.2.3 and Corollary
4.2.4. The proof of these preliminary results can be found in Section 4.11.4.

######  Lemma 4.11.4.

With probability exceeding $1-O(n^{-5})$, one can write

$\displaystyle\bm{U}\bm{\Lambda}\mathsf{sgn}(\bm{H})$
$\displaystyle=\bm{M}\bm{U}^{\star}+\bm{\Delta}_{1},$ (4.153a)
$\displaystyle\mathsf{sgn}(\bm{H})\bm{\Lambda}^{\star}\mathsf{sgn}(\bm{H})^{\top}$
$\displaystyle=\bm{\Lambda}+\bm{\Delta}_{2}$ (4.153b)

for some matrices $\bm{\Delta}_{1}$ and $\bm{\Delta}_{2}$ obeying

$\displaystyle\big{\|}\bm{\Delta}_{1}\big{\|}_{2,\infty}$
$\displaystyle\lesssim\frac{\sigma^{2}\kappa\sqrt{\mu
rn\log^{2}n}}{\lambda_{r}^{\star}},$ (4.154a)
$\displaystyle\big{\|}\bm{\Delta}_{2}\big{\|}$
$\displaystyle\lesssim\frac{\kappa\sigma^{2}n}{\lambda_{r}^{\star}}+\sigma\sqrt{r\log
n}.$ (4.154b)

We are now ready to embark on the proof of Lemma 4.11.1. In order to analyze
the behavior of $\bm{U}\mathsf{sgn}(\bm{H})$, we first point out the following
decomposition:

$\displaystyle\bm{U}\mathsf{sgn}(\bm{H})\bm{\Lambda}^{\star}$
$\displaystyle=\bm{U}\bm{\Lambda}\mathsf{sgn}(\bm{H})+\bm{U}\big{(}\mathsf{sgn}(\bm{H})\bm{\Lambda}^{\star}-\bm{\Lambda}\mathsf{sgn}(\bm{H})\big{)}$
$\displaystyle=\bm{M}\bm{U}^{\star}+\bm{\Delta}_{1}+\bm{U}\big{(}\mathsf{sgn}(\bm{H})\bm{\Lambda}^{\star}\mathsf{sgn}(\bm{H})^{\top}-\bm{\Lambda}\big{)}\mathsf{sgn}(\bm{H})$
$\displaystyle=\bm{M}^{\star}\bm{U}^{\star}+\bm{E}\bm{U}^{\star}+\bm{\Delta}_{1}+\bm{U}\bm{\Delta}_{2}\,\mathsf{sgn}(\bm{H})$
$\displaystyle=\bm{U}^{\star}\bm{\Lambda}^{\star}+\bm{E}\bm{U}^{\star}+\bm{\Delta}_{1}+\bm{U}\bm{\Delta}_{2}\,\mathsf{sgn}(\bm{H}),$

where the second and the third identities result from Lemma 4.11.4 (cf.
(4.153)). The key point of this decomposition is to establish a connection
between $\bm{U}\mathsf{sgn}(\bm{H})\bm{\Lambda}^{\star}$ and
$\bm{U}^{\star}\bm{\Lambda}^{\star}+\bm{E}\bm{U}^{\star}$, with the assistance
of the matrices $\bm{\Delta}_{1}$ and $\bm{\Delta}_{2}$ studied in Lemma
4.11.4. A little algebra then yields

$\displaystyle\bm{U}\mathsf{sgn}(\bm{H})-\bm{U}^{\star}=\underset{\eqqcolon\,\bm{Z}}{\underbrace{\bm{E}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}}}$
$\displaystyle+\underset{\eqqcolon\,\bm{\Psi}}{\underbrace{\bm{\Delta}_{1}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}+\bm{U}\bm{\Delta}_{2}\,\mathsf{sgn}(\bm{H})\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}}}.$
(4.155)

In view of Lemma 4.11.4, the residual matrix $\bm{\Psi}$ obeys

$\displaystyle\|\bm{\Psi}\|_{2,\infty}$
$\displaystyle\leq\big{\|}\bm{\Delta}_{1}\big{\|}_{2,\infty}\big{\|}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}+\big{\|}\bm{U}\big{\|}_{2,\infty}\big{\|}\bm{\Delta}_{2}\big{\|}\,\big{\|}\mathsf{sgn}(\bm{H})\big{\|}\,\big{\|}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}$
$\displaystyle\lesssim\frac{1}{\lambda_{r}^{\star}}\big{\|}\bm{\Delta}_{1}\big{\|}_{2,\infty}+\frac{1}{\lambda_{r}^{\star}}\sqrt{\frac{\mu
r}{n}}\big{\|}\bm{\Delta}_{2}\big{\|}$
$\displaystyle\lesssim\frac{\sigma^{2}\kappa\sqrt{\mu
rn\log^{2}n}}{(\lambda_{r}^{\star})^{2}}+\frac{\kappa\sigma^{2}\sqrt{\mu
rn}}{(\lambda_{r}^{\star})^{2}}+\frac{\sigma}{\lambda_{r}^{\star}}\sqrt{\frac{\mu
r^{2}\log n}{n}}$ (4.156)

as claimed.

The next step lies in analyzing the matrix estimator
$\bm{M}=\bm{U}\bm{\Lambda}\bm{U}^{\top}$. Towards this, we make the
observation that

$\displaystyle\bm{M}-\bm{M}^{\star}$
$\displaystyle=\bm{U}\bm{\Lambda}\bm{U}^{\top}-\bm{M}^{\star}$
$\displaystyle=\bm{U}\big{(}\mathsf{sgn}(\bm{H})\bm{\Lambda}^{\star}\mathsf{sgn}(\bm{H})^{\top}\big{)}\bm{U}^{\top}-\bm{U}\bm{\Delta}_{2}\bm{U}^{\top}-\bm{M}^{\star}$
$\displaystyle=(\bm{U}^{\star}+\bm{Z}+\bm{\Psi})\bm{\Lambda}^{\star}(\bm{U}^{\star}+\bm{Z}+\bm{\Psi})^{\top}-\bm{U}\bm{\Delta}_{2}\bm{U}^{\top}-\bm{U}^{\star}\bm{\Lambda}^{\star}\bm{U}^{\star\top}$
$\displaystyle=\bm{Z}\bm{\Lambda}^{\star}\bm{U}^{\star\top}+\bm{U}^{\star}\bm{\Lambda}^{\star}\bm{Z}^{\top}+\bm{\Phi}$
$\displaystyle=\bm{E}\bm{U}^{\star}\bm{U}^{\star\top}+\bm{U}^{\star}\bm{U}^{\star\top}\bm{E}+\bm{\Phi},$
(4.157)

where the second line relies on Lemma 4.11.4 (cf. (4.153b)), the third
identity makes use of (4.155), and the residual matrix $\bm{\Phi}$ is defined
as

$\bm{\Phi}\coloneqq\bm{\Psi}\bm{\Lambda}^{\star}\big{(}\bm{U}\mathsf{sgn}(\bm{H})\big{)}^{\top}+\bm{U}^{\star}\bm{\Lambda}^{\star}\bm{\Psi}^{\top}+\bm{Z}\bm{\Lambda}^{\star}\big{(}\bm{U}\mathsf{sgn}(\bm{H})-\bm{U}^{\star}\big{)}^{\top}-\bm{U}\bm{\Delta}_{2}\bm{U}^{\top}.$
(4.158)

In addition, it is seen from (4.92) that

$\|\bm{Z}\|_{2,\infty}\leq\big{\|}\bm{E}\bm{U}^{\star}\big{(}\bm{\Lambda}^{\star}\big{)}^{-1}\big{\|}_{2,\infty}\leq\frac{1}{\lambda_{r}^{\star}}\big{\|}\bm{E}\bm{U}^{\star}\big{\|}_{2,\infty}\lesssim\frac{\sigma\sqrt{r\log
n}}{\lambda_{r}^{\star}}.$ (4.159)

Consequently, one can deduce that

$\displaystyle\big{\|}\bm{\Phi}\big{\|}_{\infty}$
$\displaystyle\leq\big{\|}\bm{\Lambda}^{\star}\big{\|}\left\\{\|\bm{Z}\|_{2,\infty}^{2}+\|\bm{Z}\|_{2,\infty}\big{\|}\bm{U}\mathsf{sgn}(\bm{H})-\bm{U}^{\star}\big{\|}_{2,\infty}\right\\}$
$\displaystyle\quad+\big{\|}\bm{\Lambda}^{\star}\big{\|}\|\bm{\Psi}\|_{2,\infty}\left(\big{\|}\bm{U}\big{\|}_{2,\infty}+\|\bm{U}^{\star}\|_{2,\infty}\right)+\|\bm{U}\|_{2,\infty}^{2}\|\bm{\Delta}_{2}\|$
$\displaystyle\lesssim\big{|}\lambda_{1}^{\star}\big{|}\left\\{\frac{\sigma^{2}r\log
n}{(\lambda_{r}^{\star})^{2}}+\frac{\sigma\sqrt{r\log
n}}{\lambda_{r}^{\star}}\cdot\frac{\sigma\kappa\sqrt{\mu r\log
n}}{\lambda_{r}^{\star}}\right\\}$
$\displaystyle\quad+\big{|}\lambda_{1}^{\star}\big{|}\sqrt{\frac{\mu
r}{n}}\left\\{\frac{\sigma^{2}\kappa\sqrt{\mu
rn\log^{2}n}}{(\lambda_{r}^{\star})^{2}}+\frac{\kappa\sigma^{2}\sqrt{\mu
rn}}{(\lambda_{r}^{\star})^{2}}+\frac{\sigma}{\lambda_{r}^{\star}}\sqrt{\frac{\mu
r^{2}\log n}{n}}\right\\}$ $\displaystyle\quad+\frac{\mu
r}{n}\left\\{\frac{\kappa\sigma^{2}n}{\lambda_{r}^{\star}}+\sigma\sqrt{r\log
n}\right\\}$ $\displaystyle\lesssim\frac{\sigma^{2}\mu r\kappa^{2}\log
n}{\lambda_{r}^{\star}}+\frac{\sigma\kappa\mu\sqrt{r^{3}\log n}}{n},$

where the second inequality follows from (4.156), (4.159), (4.135), Theorem
4.2.3, and Lemma 4.11.4.

####  4.11.3 Proof of Lemma 4.11.3

In what follows, we shall only focus on the case with $i\neq j$. The case with
$i=j$ can be analyzed in an analogous manner; we omit it for the sake of
brevity. Before proceeding to the proof, we make note of a couple of basic
facts about $\bm{P}^{\star}$ that will prove useful. The first property
asserts that, for any $1\leq j\leq n$,

$\displaystyle\sum_{l=1}^{n}P_{j,l}^{\star 2}$
$\displaystyle=\sum_{l=1}^{n}P_{l,j}^{\star
2}=\big{\|}\big{(}\bm{U}^{\star}\bm{U}^{\star\top}\big{)}_{\cdot,j}\big{\|}_{2}^{2}=\big{\|}\bm{U}^{\star}\big{(}\bm{U}_{j,\cdot}^{\star}\big{)}^{\top}\big{\|}_{2}^{2}=\bm{U}_{j,\cdot}^{\star}\bm{U}^{\star\top}\bm{U}^{\star}\big{(}\bm{U}_{j,\cdot}^{\star}\big{)}^{\top}$
$\displaystyle=\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}=P_{j,j}^{\star}.$
(4.160)

The second property is concerned with the term $\|\bm{P}^{\star}\|_{\infty}$:

$\|\bm{P}^{\star}\|_{\infty}=\|\bm{U}^{\star}\bm{U}^{\star\top}\|_{\infty}\leq\|\bm{U}^{\star}\|_{2,\infty}^{2}\leq\frac{\mu
r}{n},$ (4.161)

where the last inequality follows from the incoherence assumption.

In view of the definition (4.66) of $\bm{P}^{\star}$, we can express
$\bm{W}=\bm{E}\bm{P}^{\star}+\bm{P}^{\star}\bm{E}$, which reveals that

$W_{i,j}=\sum_{l:\,l\neq j}E_{i,l}P^{\star}_{l,j}+\sum_{l:\,l\neq
i}P^{\star}_{i,l}E_{l,j}+E_{i,j}(P^{\star}_{i,i}+P^{\star}_{j,j}).$ (4.162)

In other words, $W_{i,j}$ can be viewed as a weighted sum of independent
random variables $\\{E_{i,l}\mid l\neq j\\}\cup\\{E_{l,j}\mid l\neq
i\\}\cup\\{E_{i,j}\\}$. To pin down the distribution of $W_{i,j}$, we resort
to a non-asymptotic version of the celebrated Berry-Esseen Theorem; see
chen2010normal for a proof using Stein’s method.

######  Theorem 4.11.5 (The Berry-Esseen bound).

Let $\xi_{1},\ldots,\xi_{n}$ be independent zero-mean random variables
satisfying $\sum_{i=1}^{n}\mathsf{Var}(\xi_{i})=v$. Then the quantity
$S=\frac{1}{\sqrt{v}}\sum_{i=1}^{n}\xi_{i}$ satisfies

$\sup_{z\in\mathbb{R}}\big{|}\,\mathbb{P}\left(S\leq
z\right)-\Phi\left(z\right)\big{|}\leq 10\gamma,\qquad\text{where}\
\gamma=\sum_{i=1}^{n}\frac{\mathbb{E}\big{[}|\xi_{i}|^{3}\big{]}}{v^{3/2}}.$

According to the Berry-Esseen bound (cf. Theorem 4.11.5), proving the
approximate Gaussianity of $W_{i,j}$ boils down to characterizing the second
and the third moments of these random variables under consideration.

Let us start with the variance statistics. Given that $\\{E_{i,j}\mid i\geq
j\\}$ are independently generated, we can straightforwardly see that

$\displaystyle v_{i,j}^{\star}$ $\displaystyle=\sum_{l:\,l\neq
j}\sigma_{i,l}^{2}P_{l,j}^{\star 2}+\sum_{l:\,l\neq i}P_{i,l}^{\star
2}\sigma_{l,j}^{2}+\sigma_{i,j}^{2}(P_{i,i}^{\star}+P_{j,j}^{\star})^{2}$
$\displaystyle=\mathsf{Var}(W_{i,j}).$ (4.163)

We now develop a lower bound on this variance term. Given that
$\bm{P}^{\star}\succeq\bm{0}$, one has $P_{i,i}^{\star},P_{j,j}^{\star}\geq
0$, which combined with (4.160) reveals that

$\displaystyle v_{i,j}^{\star}$
$\displaystyle\geq\sigma_{\min}^{2}\Bigg{\\{}\sum_{l=1}^{n}P_{l,j}^{\star
2}+\sum_{l=1}^{n}P_{i,l}^{\star
2}\Bigg{\\}}=\sigma_{\min}^{2}\Big{\\{}\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}\Big{\\}}.$
(4.164)

Next, we move on to bound the third moments. Utilizing the independence of
$\\{E_{i,j}\mid i\geq j\\}$ once again gives

$\displaystyle\gamma$ $\displaystyle\coloneqq\frac{\sum_{l:\,l\neq
j}\mathbb{E}\big{[}\big{|}E_{i,l}\big{|}^{3}\big{]}\big{|}P_{l,j}^{\star}\big{|}^{3}+\sum_{l:\,l\neq
i}\big{|}P_{i,l}\big{|}^{3}\mathbb{E}\big{[}\big{|}E_{l,j}\big{|}^{3}\big{]}+\mathbb{E}\big{[}\big{|}E_{i,j}\big{|}^{3}\big{]}\big{|}P_{i,i}^{\star}+P_{j,j}^{\star}\big{|}^{3}}{\big{(}v_{i,j}^{\star}\big{)}^{3/2}}$
$\displaystyle\leq\frac{2B\|\bm{P}^{\star}\|_{\infty}}{\big{(}v_{i,j}^{\star}\big{)}^{3/2}}\left\\{\sum_{l:\,l\neq
j}\mathbb{E}\big{[}E_{i,l}^{2}\big{]}P_{l,j}^{\star 2}+\sum_{l:\,l\neq
i}P_{i,l}^{\star
2}\mathbb{E}\big{[}E_{l,j}^{2}\big{]}+\mathbb{E}\big{[}E_{i,j}^{2}\big{]}\big{|}P_{i,i}^{\star}+P_{j,j}^{\star}\big{|}^{2}\right\\}$
$\displaystyle=\frac{2B\|\bm{P}^{\star}\|_{\infty}}{\big{(}v_{i,j}^{\star}\big{)}^{3/2}}\cdot
v_{i,j}^{\star}=\frac{2B\|\bm{P}^{\star}\|_{\infty}}{\big{(}v_{i,j}^{\star}\big{)}^{1/2}},$
(4.165)

where we have used the assumption that $|E_{i,j}|\leq B$, and the last line
arises from the expression (4.163). Substituting (4.161) and (4.164) into
(4.165) and invoking the elementary identity
$\|\bm{U}^{\star}\|_{\mathrm{F}}^{2}=r$, we arrive at

$\displaystyle\gamma$ $\displaystyle\leq\frac{2B\mu
r}{n\sigma_{\min}\sqrt{\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}}}=\frac{2B\mu\sqrt{r}\,\big{\|}\bm{U}^{\star}\big{\|}_{\mathrm{F}}}{n\sigma_{\min}\sqrt{\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}}}=o(1),$

provided that Condition (4.151) holds.

With the above calculations in place, invoking Theorem 4.11.5 immediately
leads to

$\sup_{z\in\mathbb{R}}\left|\mathbb{P}\left(W_{i,j}\leq\sqrt{v_{i,j}^{\star}}z\right)-\Phi(z)\right|\leq
10\gamma=o(1).$

as claimed in (4.152a).

Finally, we turn to proving the bound (4.152b). By virtue of Lemma 4.11.1 and
(4.164), we know that

$\displaystyle\big{\|}\bm{\Phi}\big{\|}_{\infty}$
$\displaystyle\lesssim\frac{\sigma^{2}\mu r\kappa^{2}\log
n}{\lambda_{r}^{\star}}+\frac{\sigma\kappa\mu\sqrt{r^{3}\log n}}{n}$
$\displaystyle=o\left(\sigma_{\min}\sqrt{\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}}\right)\leq
o\big{(}\sqrt{v_{i,j}^{\star}}\big{)},$

with the proviso that

$\displaystyle\sqrt{\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}}\gtrsim\frac{\sigma^{2}\mu
r\kappa^{2}\log^{3/2}n}{\sigma_{\min}\lambda_{r}^{\star}}+\frac{\sigma\kappa\mu\sqrt{r^{3}}\log
n}{\sigma_{\min}n}$
$\displaystyle\qquad=\left(\frac{\sigma^{2}\mu\sqrt{r}\kappa^{2}\log^{3/2}n}{\sigma_{\min}\lambda_{r}^{\star}}+\frac{\sigma\kappa\mu
r\log n}{\sigma_{\min}n}\right)\big{\|}\bm{U}^{\star}\big{\|}_{\mathrm{F}}.$
(4.166)

Recognizing the trivial bound
$\sigma^{2}=\max_{i,j}\mathbb{E}[E_{i,j}^{2}]\leq B^{2}$, we know that
Condition (4.166) holds as long as

$\displaystyle\frac{\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}}{\big{\|}\bm{U}^{\star}\big{\|}_{\mathrm{F}}^{2}}$
$\displaystyle\gtrsim\frac{\sigma^{4}\mu^{2}r\kappa^{4}\log^{3}n}{\sigma_{\min}^{2}(\lambda_{r}^{\star})^{2}}+\frac{B^{2}\kappa^{2}\mu^{2}r^{2}\log^{2}n}{\sigma_{\min}^{2}n^{2}},$
(4.167)

which is precisely Condition (4.151). This concludes the proof of Lemma
4.11.3.

####  4.11.4 Proof of Lemma 4.11.4

To begin with, let us begin by proving (4.154a). From the definition of the
quantity $\mathcal{E}_{1}$ (see Lemma 4.8.7), we have

$\displaystyle\big{\|}\bm{M}(\bm{U}\bm{H}-\bm{U}^{\star})\big{\|}_{2,\infty}=\lambda_{r}^{\star}\mathcal{E}_{1}/2$
$\displaystyle\qquad\lesssim\left(\alpha_{0}+\alpha_{1}+\alpha_{2}\right)+\left(\sigma\sqrt{n}+B\log
n\right)\big{\|}\bm{U}\bm{H}-\bm{U}^{\star}\big{\|}_{2,\infty}$
$\displaystyle\qquad\lesssim\left(\alpha_{0}+\alpha_{1}+\alpha_{2}\right)+\left(\sigma\sqrt{n}+B\log
n\right)\frac{\sigma\kappa\sqrt{\mu r\log n}}{\lambda_{r}^{\star}}$
$\displaystyle\qquad\asymp\frac{\sigma^{2}\kappa\sqrt{\mu
rn\log^{2}n}}{\lambda_{r}^{\star}},$

where the first inequality comes from (4.118) and (4.119), the second
inequality is a consequence of Theorem 4.2.3, and the last line relies on our
previous bounds on $\alpha_{0},\alpha_{1},\alpha_{2}$ (see (4.114), (4.115)
and (4.117)) and holds as long as $B\lesssim\sigma\sqrt{n/(\mu\log n)}$.
Additionally, from the elementary identity
$\bm{M}\bm{U}\bm{H}=\bm{U}\bm{\Lambda}\bm{H}$, we obtain

$\displaystyle\big{\|}\bm{U}\bm{\Lambda}\mathsf{sgn}(\bm{H})-\bm{M}\bm{U}\bm{H}\big{\|}_{2,\infty}$
$\displaystyle=\big{\|}\bm{U}\bm{\Lambda}\mathsf{sgn}(\bm{H})-\bm{U}\bm{\Lambda}\bm{H}\big{\|}_{2,\infty}$
$\displaystyle\leq\big{\|}\bm{U}\big{\|}_{2,\infty}\big{\|}\bm{\Lambda}\big{\|}\,\big{\|}\mathsf{sgn}(\bm{H})-\bm{H}\big{\|}$
$\displaystyle\lesssim\sqrt{\frac{\mu
r}{n}}|\lambda_{1}^{\star}|\cdot\frac{\sigma^{2}n}{(\lambda_{r}^{\star})^{2}}=\frac{\kappa\sigma^{2}\sqrt{\mu
rn}}{\lambda_{r}^{\star}},$

where the last line results from Lemma 4.8.5, the fact (4.135), and the
following inequality

$\|\bm{\Lambda}\|\leq\|\bm{\Lambda}^{\star}\|+\|\bm{E}\|\leq|\lambda_{1}^{\star}|+O(\sigma\sqrt{n})\leq
2|\lambda_{1}^{\star}|.$ (4.168)

Taking together the above bounds and applying the triangle inequality
immediately establish (4.154a).

Next, we turn to the proof of the bound (4.154b). Note that it has been shown
in (4.141) that

$\big{\|}\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}-\bm{\Lambda}\big{\|}\lesssim\frac{\kappa\sigma^{2}n}{\lambda_{r}^{\star}}+\sigma\sqrt{r\log
n}.$

In addition, the triangle inequality leads to

$\displaystyle\big{\|}\mathsf{sgn}(\bm{H})\bm{\Lambda}^{\star}\mathsf{sgn}(\bm{H})^{\top}-\bm{H}\bm{\Lambda}^{\star}\bm{H}^{\top}\big{\|}$
$\displaystyle\qquad\leq\big{\|}\mathsf{sgn}(\bm{H})\bm{\Lambda}^{\star}\big{(}\mathsf{sgn}(\bm{H})-\bm{H}\big{)}^{\top}\big{\|}+\big{\|}\big{(}\mathsf{sgn}(\bm{H})-\bm{H}\big{)}\bm{\Lambda}^{\star}\bm{H}^{\top}\big{\|}$
$\displaystyle\qquad\leq\left(\big{\|}\mathsf{sgn}(\bm{H})\big{\|}+\big{\|}\bm{H}\big{\|}\right)\,\big{\|}\bm{\Lambda}^{\star}\big{\|}\,\big{\|}\mathsf{sgn}(\bm{H})-\bm{H}\big{\|}$
$\displaystyle\qquad\leq
2|\lambda_{1}^{\star}|\,\big{\|}\mathsf{sgn}(\bm{H})-\bm{H}\big{\|}$
$\displaystyle\qquad\lesssim|\lambda_{1}^{\star}|\frac{\sigma^{2}n}{\big{(}\lambda_{r}^{\star}\big{)}^{2}}=\frac{\kappa\sigma^{2}n}{\lambda_{r}^{\star}},$

where the third line follows since $\big{\|}\mathsf{sgn}(\bm{H})\big{\|}=1$
and $\|\bm{H}\|\leq\|\bm{U}\|\|\bm{U}^{\star}\|=1$, and the last inequality
comes from (4.125). Combining the above two results and invoking the triangle
inequality lead to the advertised bound (4.154b).

###  4.12 Appendix E: Proof of Theorem 4.6.2

With the distributional guarantees in Theorem 4.6.1 in place, the only
remaining task boils down to verifying the statistical accuracy of the
variance estimator $\widehat{v}_{i,j}$. This can be achieved via the following
lemma, whose proof is provided in Section 4.12.1.

######  Lemma 4.12.1.

Suppose that the assumptions of Theorem 4.2.3 hold. In addition, assume that
$\kappa^{4}\mu^{2}r^{2}\log n\leq n$,
$\sigma\sqrt{n}\lesssim|\lambda_{r}^{\star}|/\kappa$ and

$\displaystyle\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}\gtrsim\frac{B\sigma\kappa^{2}\mu^{2}r^{2}\log
n}{\sigma_{\min}^{2}n^{3/2}}+\frac{\sigma^{3}\kappa\mu^{2}r^{2}\log
n}{\sigma_{\min}^{2}|\lambda_{r}^{\star}|\sqrt{n}}.$ (4.169)

With probability exceeding $1-O(n^{-5})$, one has

$\displaystyle\big{|}\widehat{v}_{i,j}-v_{i,j}^{\star}\big{|}=o\big{(}v_{i,j}^{\star}\big{)}.$
(4.170)

Lemma 4.12.1 essentially enables us to express

$\widehat{v}_{i,j}=(1+\zeta_{v})^{2}v_{i,j}^{\star}\qquad\text{with
}\zeta_{v}=o(1).$

As a consequence, we can further demonstrate that

$\displaystyle\left|\mathbb{P}\left(M_{i,j}^{\star}\in\mathsf{CI}_{i,j}^{1-\alpha}\right)-(1-\alpha)\right|=\left|\mathbb{P}\left(\big{|}\widehat{M}_{i,j}-M_{i,j}^{\star}\big{|}\leq
z_{\alpha/2}\sqrt{\widehat{v}_{i,j}}\right)-(1-\alpha)\right|$
$\displaystyle=\left|\mathbb{P}\left(\big{|}\widehat{M}_{i,j}-M_{i,j}^{\star}\big{|}\leq(1+\zeta_{v})z_{\alpha/2}\sqrt{v_{i,j}^{\star}}\right)-(1-\alpha)\right|$
$\displaystyle\leq\left|\Phi\big{(}(1+\zeta_{v})z_{\alpha/2}\big{)}-\Phi\big{(}-(1+\zeta_{v})z_{\alpha/2}\big{)}-(1-\alpha)\right|+o(1)$
$\displaystyle\leq\left|\Phi\big{(}z_{\alpha/2}\big{)}-\Phi\big{(}-z_{\alpha/2}\big{)}-(1-\alpha)\right|+2\left|\Phi\big{(}(1+\zeta_{v})z_{\alpha/2}\big{)}-\Phi\big{(}z_{\alpha/2}\big{)}\right|+o(1)$
$\displaystyle\leq 2\zeta_{v}z_{\alpha/2}=o(1),$

where the first inequality follows from Theorem 4.6.1 and
$z_{\alpha/2}:=\Phi^{-1}(1-\alpha/2)$, the second inequality applies the
triangle inequality, and the validity of the last line can be seen from the
basic fact $|\Phi(u)-\Phi(v)|\leq|u-v|$.

When $\sigma_{\min}\asymp\sigma$, Condition (4.169) simplifies to

$\displaystyle\frac{\big{\|}\bm{U}_{j,\cdot}^{\star}\big{\|}_{2}^{2}+\big{\|}\bm{U}_{i,\cdot}^{\star}\big{\|}_{2}^{2}}{\big{\|}\bm{U}^{\star}\big{\|}_{\mathrm{F}}^{2}}\gtrsim\frac{B\kappa^{2}\mu^{2}r\log
n}{\sigma n^{3/2}}+\frac{\sigma\kappa\mu^{2}r\log
n}{|\lambda_{r}^{\star}|\sqrt{n}}.$ (4.171)

We still need to ensure that Condition (4.69) is satisfied. It is seen that

$\displaystyle\frac{B^{2}\kappa^{2}\mu^{2}r^{2}\log^{2}n}{\sigma^{2}n^{2}}+\frac{\sigma^{2}\mu^{2}r\kappa^{4}\log^{3}n}{(\lambda_{r}^{\star})^{2}}$
$\displaystyle\lesssim\frac{B\kappa^{2}\mu^{2}r^{2}\log^{2}n}{\sigma
n^{3/2}}+\frac{\sigma\mu^{2}r\kappa^{3}\log^{3}n}{|\lambda_{r}^{\star}|\sqrt{n}},$

which holds if $\sigma\kappa\sqrt{n}\lesssim|\lambda_{r}^{\star}|$ and
$B\lesssim\sigma\sqrt{n}$. As a result, if Condition (4.74) holds, then both
(4.171) and (4.69) are satisfied. This finishes the proof, as long as Lemma
4.12.1 can be established.

####  4.12.1 Proof for Lemma 4.12.1

As before, we shall only present the proof for the case with $i\neq j$ for the
sake of conciseness. In order to justify the goodness of the estimator
$\widehat{v}_{i,j}$, we find it convenient to first look at the surrogate
estimator introduced in (4.70), i.e.,

$\widetilde{v}_{i,j}=\sum_{l=1}^{n}E_{i,l}^{2}P_{l,j}^{\star
2}+\sum_{l=1}^{n}P_{i,l}^{\star
2}E_{l,j}^{2}+2E_{i,j}^{2}P_{i,i}^{\star}P_{j,j}^{\star},$ (4.172)

In the sequel, our proof consists of two main steps:

  * •

Show that the surrogate $\widetilde{v}_{i,j}$ is a reliable estimate of the
truth ${v}^{\star}_{i,j}$, namely,
$\widetilde{v}_{i,j}\approx{v}^{\star}_{i,j}$.

  * •

Show that the estimator in use and the surrogate estimator are sufficiently
close, namely, $\widehat{v}_{i,j}\approx\widetilde{v}_{i,j}$.

##### Step 1: show that $\widetilde{v}_{i,j}\approx{v}^{\star}_{i,j}$

Firstly, the fact that the $E_{i,j}$’s are zero-mean random variables
immediately reveals that $\widetilde{v}_{i,j}$ is an unbiased estimate of
$v_{i,j}^{\star}$, that is,

$\mathbb{E}\big{[}\widetilde{v}_{i,j}\big{]}=v_{i,j}^{\star}.$

Secondly, given that the $E_{i,j}$’s are statistically independent, we intend
to invoke the Bernstein inequality to control the difference
$\widetilde{v}_{i,j}-v_{i,j}^{\star}=\widetilde{v}_{i,j}-\mathbb{E}\big{[}\widetilde{v}_{i,j}\big{]}$.
To do so, one first calculates that

$\displaystyle L_{0}$
$\displaystyle\coloneqq\max\left\\{\max_{l}E_{i,l}^{2}P_{l,j}^{\star
2},\,\max_{l}E_{l,j}^{2}P_{i,l}^{\star
2},\,E_{i,j}^{2}(P_{i,i}^{\star}+P_{j,j}^{\star})^{2}\right\\}\leq
4B^{2}\|\bm{P}^{\star}\|_{\infty}^{2}$

and

$\displaystyle V_{0}$ $\displaystyle\coloneqq\sum_{l:\,l\neq
j}\mathsf{Var}\big{(}E_{i,l}^{2}\big{)}P_{l,j}^{\star 4}+\sum_{l:\,l\neq
i}\mathsf{Var}\big{(}E_{l,j}^{2}\big{)}P_{i,l}^{\star
4}+\mathsf{Var}\big{(}E_{i,j}^{2}\big{)}(P_{i,i}^{\star}+P_{j,j}^{\star})^{4}$
$\displaystyle\lesssim\sum_{l=1}^{n}\mathbb{E}\big{[}E_{i,l}^{4}\big{]}P_{l,j}^{\star
4}+\sum_{l=1}^{n}\mathbb{E}\big{[}E_{l,j}^{4}\big{]}P_{i,l}^{\star
4}+\mathbb{E}\big{[}E_{i,j}^{4}\big{]}P_{i,i}^{\star 2}P_{j,j}^{\star 2}$
$\displaystyle\lesssim
B^{2}\|\bm{P}^{\star}\|_{\infty}^{2}\left\\{\sum_{l=1}^{n}\mathbb{E}\big{[}E_{i,l}^{2}\big{]}P_{l,j}^{2}+\sum_{l=1}^{n}\mathbb{E}\big{[}E_{l,j}^{2}\big{]}P_{i,l}^{\star
2}+\mathbb{E}\big{[}E_{i,j}^{2}\big{]}P_{i,i}^{\star}P_{j,j}^{\star}\right\\}$
$\displaystyle\lesssim\sigma^{2}B^{2}\|\bm{P}^{\star}\|_{\infty}^{2}\left\\{\sum_{l=1}^{n}P_{l,j}^{\star
2}+\sum_{l=1}^{n}P_{i,l}^{\star 2}\right\\}$
$\displaystyle\lesssim\sigma^{2}B^{2}\|\bm{P}^{\star}\|_{\infty}^{3},$

where the last line follows from (4.160). Invoking the Bernstein inequality
(cf. Corollary 3.1.4) reveals that with probability exceeding $1-O(n^{-5})$,

$\displaystyle\big{|}\widetilde{v}_{i,j}-v_{i,j}^{\star}\big{|}$
$\displaystyle=\left|\widetilde{v}_{i,j}-\mathbb{E}\left[\widetilde{v}_{i,j}\right]\right|\lesssim\sqrt{V_{0}\log
n}+L_{0}\log n$ $\displaystyle\lesssim\sigma
B\sqrt{\|\bm{P}^{\star}\|_{\infty}^{3}\log
n}+B^{2}\|\bm{P}^{\star}\|_{\infty}^{2}\log n$
$\displaystyle\lesssim\frac{\sigma B\mu^{3/2}r^{3/2}\sqrt{\log
n}}{n^{3/2}}+\frac{\mu^{2}r^{2}B^{2}\log n}{n^{2}},$ (4.173)

where the last inequality results from (4.161).

##### Step 2: show that $\widehat{v}_{i,j}\approx\widetilde{v}_{i,j}$

In order to accomplish this, we are in need of controlling the difference
between $E_{i,j}$ (resp. $P^{\star}_{i,j}$) and $\widehat{E}_{i,j}$ (resp.
$\widehat{P}_{i,j}$). To this end, apply the entrywise estimation guarantees
in Corollary 4.2.4 to yield

$\displaystyle\big{\|}\widehat{\bm{E}}-\bm{E}\big{\|}_{\infty}$
$\displaystyle=\big{\|}\big{(}\bm{M}-\bm{U}\bm{\Lambda}\bm{U}^{\top}\big{)}-\big{(}\bm{M}-\bm{M}^{\star}\big{)}\big{\|}_{\infty}$
$\displaystyle=\big{\|}\bm{U}\bm{\Lambda}\bm{U}^{\top}-\bm{M}^{\star}\big{\|}_{\infty}\lesssim\sigma\kappa^{2}\mu
r\sqrt{\frac{\log n}{n}},$ (4.174)

and as a result,

$\big{\|}\widehat{\bm{E}}\big{\|}_{\infty}\leq\big{\|}\bm{E}\big{\|}_{\infty}+\big{\|}\widehat{\bm{E}}-\bm{E}\big{\|}_{\infty}\lesssim
B+\sigma\kappa^{2}\mu r\sqrt{\frac{\log n}{n}}\asymp B,$ (4.175)

provided that $B\gtrsim\sigma\kappa^{2}\mu r\sqrt{\frac{\log n}{n}}$ (which is
trivially satisfied if $\kappa^{2}\mu r\sqrt{\frac{\log n}{n}}\leq 1$). Moving
on to the error term $\widehat{P}_{i,j}-P_{i,j}^{\star}$, we observe that

$\displaystyle\big{\|}\widehat{\bm{P}}-\bm{P}^{\star}\big{\|}_{\infty}=\big{\|}\bm{U}\bm{U}^{\top}-\bm{U}^{\star}\bm{U}^{\star\top}\big{\|}_{\infty}$
$\displaystyle\qquad\leq\big{\|}\big{(}\bm{U}\mathsf{sgn}(\bm{H})-\bm{U}^{\star}\big{)}\bm{U}^{\star\top}\big{\|}_{\infty}+\big{\|}\bm{U}\mathsf{sgn}(\bm{H})\big{(}\bm{U}\mathsf{sgn}(\bm{H})-\bm{U}^{\star}\big{)}^{\top}\big{\|}_{\infty}$
$\displaystyle\qquad\leq\big{\|}\bm{U}\mathsf{sgn}(\bm{H})-\bm{U}^{\star}\big{\|}_{2,\infty}\left\\{\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}+\big{\|}\bm{U}\mathsf{sgn}(\bm{H})\big{\|}_{2,\infty}\right\\}$
$\displaystyle\qquad\leq\big{\|}\bm{U}\mathsf{sgn}(\bm{H})-\bm{U}^{\star}\big{\|}_{2,\infty}\left\\{\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}+\big{\|}\bm{U}\big{\|}_{2,\infty}\right\\}.$

Taking this together with the bound (4.31a) in Theorem 4.2.3, the incoherence
assumption, and the inequality (4.135), we arrive at

$\displaystyle\big{\|}\widehat{\bm{P}}-\bm{P}^{\star}\big{\|}_{\infty}$
$\displaystyle\lesssim\frac{(\sigma\kappa\sqrt{\mu r}+\sigma\sqrt{r\log
n})}{|\lambda_{r}^{\star}|}\sqrt{\frac{\mu r}{n}}.$ (4.176)

This taken together with (4.161) indicates that

$\displaystyle\big{\|}\widehat{\bm{P}}\big{\|}_{\infty}$
$\displaystyle\leq\big{\|}\bm{P}^{\star}\big{\|}_{\infty}+\big{\|}\widehat{\bm{P}}-\bm{P}^{\star}\big{\|}_{\infty}$
$\displaystyle\lesssim\frac{\mu r}{n}+\frac{(\sigma\kappa\sqrt{\mu
r}+\sigma\sqrt{r\log n})}{|\lambda_{r}^{\star}|}\sqrt{\frac{\mu
r}{n}}\asymp\frac{\mu r}{n},$ (4.177)

with the proviso that $\sigma\sqrt{n}\lesssim|\lambda_{r}^{\star}|/\kappa$ and
$\sigma\sqrt{n\log n}\lesssim|\lambda_{r}^{\star}|$.

Armed with the preceding bounds, we are now positioned to control
$\widehat{v}_{i,j}-\widetilde{v}_{i,j}$. From the definition of
$\widetilde{v}_{i,j}$ and $v_{i,j}^{\star}$, we recognize that

$\displaystyle\big{|}\widehat{v}_{i,j}-\widetilde{v}_{i,j}\big{|}$
$\displaystyle\leq\underset{\eqqcolon\,\alpha_{1}}{\underbrace{\left|\sum_{l=1}^{n}\left(\widehat{E}_{i,l}^{2}\widehat{P}_{l,j}^{2}-E_{i,l}^{2}P_{l,j}^{\star
2}\right)\right|}}+\underset{\eqqcolon\,\alpha_{2}}{\underbrace{\left|\sum_{l=1}^{n}\left(\widehat{P}_{i,l}^{2}\widehat{E}_{l,j}^{2}-P_{i,l}^{\star
2}E_{l,j}^{2}\right)\right|}}$
$\displaystyle\qquad+2\,\underset{\eqqcolon\,\alpha_{3}}{\underbrace{\left|\widehat{E}_{i,j}^{2}\widehat{P}_{i,i}\widehat{P}_{j,j}-E_{i,j}^{2}P_{i,i}^{\star}P_{j,j}^{\star}\right|}},$
(4.178)

leaving us with three terms to cope with. Regarding the first term
$\alpha_{1}$ on the right-hand side of (4.178), it can be easily verified that

$\displaystyle\alpha_{1}$
$\displaystyle\leq\left|\sum_{l=1}^{n}\left(\widehat{E}_{i,l}^{2}\widehat{P}_{l,j}^{2}-E_{i,l}^{2}\widehat{P}_{l,j}^{2}\right)\right|+\left|\sum_{l=1}^{n}\left(E_{i,l}^{2}\widehat{P}_{l,j}^{2}-E_{i,l}^{2}P_{l,j}^{\star
2}\right)\right|$
$\displaystyle\leq\left(\max_{l}\left|\widehat{E}_{i,l}^{2}-E_{i,l}^{2}\right|\right)\sum_{l=1}^{n}\widehat{P}_{l,j}^{2}+\left(\max_{l}\left|\widehat{P}_{l,j}^{2}-P_{l,j}^{\star
2}\right|\right)\sum_{l=1}^{n}E_{i,l}^{2}$
$\displaystyle\overset{\mathrm{(i)}}{\leq}\left(\|\bm{E}\|_{\infty}+\|\widehat{\bm{E}}\|_{\infty}\right)\big{\|}\widehat{\bm{E}}-\bm{E}\big{\|}_{\infty}\widehat{P}_{j,j}$
$\displaystyle\qquad+\left(\|\bm{P}^{\star}\|_{\infty}+\|\widehat{\bm{P}}\|_{\infty}\right)\big{\|}\widehat{\bm{P}}-\bm{P}^{\star}\big{\|}_{\infty}\|\bm{E}\|^{2}$
$\displaystyle\overset{\mathrm{(ii)}}{\lesssim}B\sigma\kappa^{2}\mu
r\sqrt{\frac{\log n}{n}}\cdot\frac{\mu r}{n}+\frac{\mu
r}{n}\cdot\frac{(\sigma\kappa\sqrt{\mu r}+\sigma\sqrt{r\log
n})}{|\lambda_{r}^{\star}|}\sqrt{\frac{\mu r}{n}}\cdot\sigma^{2}n.$

Here, (i) makes use of (4.160) (with $\bm{P}^{\star}$ replaced by
$\widehat{\bm{P}}$), whereas (ii) holds true due to (4.174), (4.175), (4.161),
(4.176), (4.177), and Lemma 4.8.1. The second term $\alpha_{2}$ on the right-
hand side of (4.178) can be bounded in the same manner and we omit it here for
brevity. When it comes to the last term $\alpha_{3}$ on the right-hand side of
(4.178), one has

$\displaystyle\alpha_{3}$
$\displaystyle\leq\left|\widehat{E}_{i,j}^{2}-E_{i,j}^{2}\right|\left|\widehat{P}_{i,i}\widehat{P}_{j,j}\right|+E_{i,j}^{2}\left|\widehat{P}_{i,i}\widehat{P}_{j,j}-P_{i,i}^{\star}P_{j,j}^{\star}\right|$
$\displaystyle\lesssim\big{\|}\widehat{\bm{E}}-\bm{E}\big{\|}_{\infty}\left\\{\big{\|}\bm{E}\big{\|}_{\infty}+\big{\|}\widehat{\bm{E}}\big{\|}_{\infty}\right\\}\big{\|}\widehat{\bm{P}}\big{\|}_{\infty}^{2}$
$\displaystyle\qquad+B^{2}\big{\|}\widehat{\bm{P}}-\bm{P}^{\star}\big{\|}_{\infty}\left\\{\big{\|}\bm{P}^{\star}\big{\|}_{\infty}+\big{\|}\widehat{\bm{P}}\big{\|}_{\infty}\right\\}$
$\displaystyle\lesssim\sigma\kappa^{2}\mu r\sqrt{\frac{\log n}{n}}\cdot
B\cdot\left(\frac{\mu r}{n}\right)^{2}+B^{2}\cdot\frac{(\sigma\kappa\sqrt{\mu
r}+\sigma\sqrt{r\log n})}{|\lambda_{r}^{\star}|}\sqrt{\frac{\mu
r}{n}}\cdot\frac{\mu r}{n}$ $\displaystyle\lesssim B\sigma\kappa^{2}\mu
r\sqrt{\frac{\log n}{n}}\cdot\frac{\mu r}{n}+\frac{\mu
r}{n}\cdot\frac{(\sigma\kappa\sqrt{\mu r}+\sigma\sqrt{r\log
n})}{|\lambda_{r}^{\star}|}\sqrt{\frac{\mu r}{n}}\cdot\sigma^{2}n,$

where the penultimate inequality is a consequence of (4.174), (4.175),
(4.161), (4.176) and (4.177), and the last line holds true as long as $\mu
r\leq n$ (cf. (4.25)) and $B\lesssim\sigma\sqrt{n}$. Combining the above
inequalities allows one to reach

$\displaystyle\big{|}\widehat{v}_{i,j}-\widetilde{v}_{i,j}\big{|}\leq\alpha_{1}+\alpha_{2}+\alpha_{3}$
$\displaystyle\qquad\lesssim B\sigma\kappa^{2}\mu r\sqrt{\frac{\log
n}{n}}\cdot\frac{\mu r}{n}+\frac{\mu r}{n}\cdot\frac{\sigma\kappa\sqrt{\mu
r}+\sigma\sqrt{r\log n}}{|\lambda_{r}^{\star}|}\sqrt{\frac{\mu
r}{n}}\cdot\sigma^{2}n$
$\displaystyle\qquad\asymp\frac{B\sigma\kappa^{2}\mu^{2}r^{2}\sqrt{\log
n}}{n^{3/2}}+\frac{\sigma^{3}\kappa\mu^{2}r^{2}+\sigma^{3}\mu^{3/2}r^{2}\sqrt{\log
n}}{|\lambda_{r}^{\star}|\sqrt{n}}$

with probability at least $1-O(n^{-5})$.

##### Step 3: combining the above bounds

Putting together the results in the previous steps, we can readily derive

$\displaystyle\big{|}\widehat{v}_{i,j}-v_{i,j}^{\star}\big{|}$
$\displaystyle\leq\big{|}\widetilde{v}_{i,j}-v_{i,j}^{\star}\big{|}+\big{|}\widehat{v}_{i,j}-\widetilde{v}_{i,j}\big{|}$
$\displaystyle\lesssim\left(\frac{\sigma B\mu^{3/2}r^{3/2}\sqrt{\log
n}}{n^{3/2}}+\frac{\mu^{2}r^{2}B^{2}\log n}{n^{2}}\right)$
$\displaystyle\qquad+\left(\frac{B\sigma\kappa^{2}\mu^{2}r^{2}\sqrt{\log
n}}{n^{3/2}}+\frac{\sigma^{3}\kappa\mu^{2}r^{2}+\sigma^{3}\mu^{3/2}r^{2}\sqrt{\log
n}}{|\lambda_{r}^{\star}|\sqrt{n}}\right)$
$\displaystyle\asymp\frac{B\sigma\kappa^{2}\mu^{2}r^{2}\sqrt{\log
n}}{n^{3/2}}+\frac{\sigma^{3}\kappa\mu^{2}r^{2}\sqrt{\log
n}}{|\lambda_{r}^{\star}|\sqrt{n}},$ (4.179)

where the last relation is guaranteed as long as $B\lesssim\sigma\sqrt{n/\log
n}$. Consequently, if Condition (4.169) holds, then it follows from (4.179)
and the lower bound (4.164) that

$\displaystyle\big{|}\widehat{v}_{i,j}-v_{i,j}^{\star}\big{|}\lesssim\frac{1}{\sqrt{\log
n}}v_{i,j}^{\star},$

thus concluding the proof.

###  4.13 Notes

###### Leave-one-out analysis.

The core idea of leave-one-out analysis, which drops a small amount of
randomness to decouple complicated statistical dependency, is deeply rooted in
the probability and statistics literature. For instance, an idea of this kind
was invoked by stein1972a to help establish normal approximation, was paired
with the Stieltjes transform to establish the limiting spectral law of random
matrices (see, e.g., [Tao2012RMT, Section 2.4.3]), and bears some resemblance
to the cavity method in statistical physics [mezard2009information]. When it
comes to statistical estimation, a prominent series of work that unveiled the
striking effectiveness of leave-one-out analysis was el2013robust,
el2015impact, which characterized rigorously the sharp statistical performance
(including pre-constants) of M-estimators in high dimension (i.e., a
challenging regime where the number of samples is comparable to the number of
unknown parameters). The deep analysis framework developed in these papers
inspired much of the follow-up work presented in this chapter. Particularly
worth mentioning are: (1) zhong2017near: which was the first to determine the
entrywise behavior of the generalized projected power method; (2)
abbe2020entrywise, chen2017spectral: which extended the leave-one-out analysis
idea to establish entrywise eigenvector perturbation; and (3) ma2017implicit,
chen2019gradient: which characterized tight convergence guarantees for
nonconvex optimization algorithms with the aid of leave-one-out ideas. For
readers’ reference, we list below several topics for which leave-one-out
analyses prove useful:

  * •

Maximum likelihood estimation and M-estimation: el2013robust, el2015impact,
lei2018asymptotics, sur2019likelihood, sur2019modern, chen2017spectral,
chen2020partial;

  * •

spectral methods: chen2017spectral, abbe2020entrywise, ma2017implicit,
cai2019subspace, lei2019unified, abbe2020ell_p, ling2020near, chen2020partial;

  * •

nonconvex optimization for statistical estimation: ma2017implicit,
chen2019gradient, li2019nonconvex, chen2020nonconvex, cai2019tensor,
dong2018nonconvex, chen2020convex, wang2021entrywise;

  * •

semidefinite relaxation for low-rank matrix factorization: zhong2017near,
ding2020leave, chen2020noisy, chen2020bridging, chen2020convex;

  * •

uncertainty quantification and confidence intervals: javanmard2018debiasing,
chen2019inference, cai2020uncertainty, yan2021inference;

  * •

cross validation: xu2019consistent;

  * •

reinforcement learning: agarwal2020model, li2020breaking,
pananjady2020instance, zhang2020model, cui2020minimax, wang2021sample.

######  $\ell_{\infty}$ and $\ell_{2,\infty}$ perturbation theory.

The $\ell_{\infty}$ and $\ell_{2,\infty}$ perturbation theory for eigenspace
and singular subspaces have been investigated in the literature [fan2016ell,
cape2019two, eldridge2018unperturbed], but only scatteredly until very
recently. A modern and systematic framework was established recently,
empowered by the leave-one-out analysis idea. Its efficacy and tightness were
first demonstrated by abbe2020entrywise in a setting that subsumes the one
presented herein (with applications to SBMs, phase synchronization and matrix
completion), and by chen2017spectral in an asymmetric setting (with
application to top-$K$ ranking). The theoretical framework has subsequently
been extended in several aspects. For instance, (1) cai2019subspace
investigated the “unbalanced” scenario where the column dimension far exceeds
the row dimension of the matrix, resulting in near-optimal fine-grained
guarantees for PCA, bi-clustering and tensor completion; (2) lei2019unified
expanded the setting by accounting for more flexible noise distributions
(including the ones exhibiting certain dependency structure), leading to tight
guarantees for, e.g., spectral clustering with more than two communities, and
hierarchical clustering; (3) abbe2020ell_p explored a more general $\ell_{p}$
perturbation theory that subsumes the $\ell_{\infty}$ perturbation theory as
special cases. Another plausible approach to study $\ell_{\infty}$ eigenvector
perturbation is to analyze instead the dynamics of an iterative procedure
(e.g., the power method) that converges to the leading eigenvector
[zhong2017near], again using the leave-one-out ideas. This iterative approach
offers a perspective complementary to the analysis framework presented herein,
while at the same time playing a pivotal role when studying nonconvex
optimization algorithms (see chi2019nonconvex). Moving beyond the leave-one-
out analysis framework, $\ell_{\infty}$ and $\ell_{2,\infty}$ eigenspace
perturbation theory has been derived via other powerful tools as well, e.g.,
the Neumann trick [eldridge2018unperturbed, chen2018asymmetry,
cheng2020tackling], the Procrustes analysis [cape2019two], and more
specialized techniques tailored to Gaussian ensembles
[koltchinskii2016perturbation, koltchinskii2016asymptotics,
koltchinskii2020efficient]. Perturbations of linear forms and bilinear forms
of eigenvectors have also been investigated in the literature
[koltchinskii2016perturbation, koltchinskii2016asymptotics, chen2018asymmetry,
cheng2020tackling, fan2020asymptotic, koltchinskii2020efficient], which are
beyond the scope of this work. Finally, distributional theory and uncertainty
quantification for spectral methods, which have been recently studied by
xia2019normal, cheng2020tackling, fan2020asymptotic, yan2021inference,
agterberg2021entrywise, are still in their infancy. The results presented in
Section 4.6 follow the analysis framework developed in yan2021inference.

##  Chapter 5 Concluding remarks and open problems

This monograph offered a coherent statistical treatment for spectral methods,
resulting in appealing theoretical guarantees for a wide spectrum of data
science applications ranging from structured signal reconstruction and factor
analysis to clustering and ranking. The important role of statistical thinking
cannot be overstated. As has been illuminated, the suite of modern statistical
techniques not merely empowers classical $\ell_{2}$ perturbation theory by
delivering tight Euclidean error bounds, but also enables fine-grained
$\ell_{\infty}$ and $\ell_{2,\infty}$ performance guarantees that cannot be
derived from classical matrix perturbation theory alone. We highlighted a
unified recipe that underlies our application-driven analyses, which will be
readily applicable to tackle many other problems.

The vignettes presented herein only reflect the tip of an iceberg regarding
the capability of spectral methods. There are multiple aspects about spectral
methods that remain inadequately explored and are worthy of future
investigation. We conclude this monograph by pointing out a few of them.

  * •

Precise performance characterization. The analysis herein falls short of
pinpointing a precise trade-off curve between the statistical accuracy and
sample complexity of spectral methods, and might even be off by some
logarithmic factor. For algorithms that exhibit order-wise equivalent
behavior, comparing their performances requires finer statistical
characterization, ideally with sharp pre-constants.

  * •

Handling dependency structure. Thus far, the $\ell_{\infty}$ and
$\ell_{2,\infty}$ perturbation theory we have presented is restricted to the
case where the entries of the data samples are independently generated. There
is no shortage of applications where the data samples might exhibit across-
entry dependency, examples including blind deconvolution [ahmed2013blind] and
phase retrieval with coded diffraction patterns [candes2015CDP,
gross2017improved]. Handling such scenarios might require ideas beyond the
current leave-one-out framework.

  * •

Functional estimation. In many decision making applications, what ultimately
matters might not be full information about an eigenvector of a matrix, but
rather, some deterministic functions (e.g., certain linear functionals or
polynomials) about the entries of this eigenvector. However, naive “plug-in”
estimators—namely, estimating the eigenvector first and plugging it into the
target functional—might suffer from significant estimation bias, even in the
case of a linear functional. A systematic bias-correction paradigm is
therefore needed to enable optimal functional estimation.

  * •

Small eigengaps. All theory presented in this monograph imposes a stringent
requirement on the associated eigengap, that is, it needs to exceed the
spectral norm of a noise or perturbation matrix. While this eigengap criterion
might be unavoidable in generic matrix perturbation theory (which takes a
worst-case perspective), there is often no statistical lower bound that rules
out the possibility of reliable eigenspace estimation when the eigengap drops
below the perturbation size. It would be of fundamental importance to
understand how a small eigengap impacts the efficacy of spectral methods under
various statistical models.

  * •

Weak and sparse factors. As mentioned previously, low-rank matrices often
admit factor-model interpretations. In many applications, one has to deal with
weak factors, on which only a small fraction of the variables have non-
negligible loadings. This gives rise to sparse patterns on the loading matrix
or the eigenvectors of the covariance matrix. To utilize such a sparsity
structure, a simple method is to apply marginal screening techniques
[fan2008sure, fan2008high]. Examples of this kind include supervised PCA
[bair2006prediction], PCA on “targeted predictors” [bai2008forecasting], and
sparse PCA [zou2006sparse, JohLu09, ma2013sparse]. It remains to develop a
more systematic and unified theory concerning how to efficiently exploit such
special structures in low-rank factorizations, taking into account both
statistical and computational considerations.

  * •

Heterogeneous missing patterns. When it comes to missing data, the theory
presented herein adopts a uniform sampling model where every entry is
independently observed with the same probability. In practice, however, one
might encounter non-uniform sampling mechanisms, where the sampling
probabilities are non-identical across different entries. How to develop an
effective spectral method to automatically account for heterogeneous
observation patterns, ideally without knowing the detailed sampling
probabilities a priori?

  * •

Confidence regions and hypothesis testing for individual eigenvectors. Given
the output of a spectral method, one might be asked to produce valid
confidence regions for an unknown individual eigenvector of interest, a task
that has not been fully resolved by the existing literature. Another closely
related task is hypothesis testing for individual eigenvectors: given two
random samples, how to develop viable statistical tests regarding whether
these two samples are associated with the same individual eigenvectors or not.
An even more challenging task is concerned with performing efficient
statistical inference on some deterministic functions of an individual
eigenvector, which remains largely unknown.

###### Acknowledgements.

The authors thank the Editor-in-Chief Prof. Michael Jordan for his
encouragements, and the publisher Mike Casey for his editorial help. We are
deeply indebted to our wonderful collaborators who have contributed
significantly to, and helped shape our perspectives into, the materials
presented herein, including Emmanuel Abbe, Changxiao Cai, Emmanuel Candès,
Yanxi Chen, Chen Cheng, Yonina Eldar, Yingying Fan, Haoyu Fu, Andrea
Goldsmith, Leonidas Guibas, Qixing Huang, Govinda Kamath, Tracy Ke, Gen Li,
Yuanxin Li, Yingbin Liang, Yuan Liao, Junwei Lu, Yue Lu, Jinchi Lv, Vincent
Monardo, H. Vincent Poor, Changho Suh, Tian Tong, David Tse, Bingyan Wang,
Kaizheng Wang, Weichen Wang, Yuting Wei, Yuling Yan, Zhuorang Yang, Huishuai
Zhang, Yuchen Zhou, Yiqiao Zhong, and Ziwei Zhu. We owe our particular
gratitude to Yuling Yan, who has generously helped with most materials
presented in Sections 4.6-4.7. We also thank Bingyan Wang and Chen Dan for
their helpful comments about an early version of this monograph, Changxiao Cai
for his help in producing Figure 3.5, and Kaizheng Wang for his help in
generating Figure 4.2. We gratefully acknowledge the generous financial
support of multiple agencies. More specifically, Y. Chen acknowledges the
support by the AFOSR YIP award FA9550-19-1-0030, the ONR grant
N00014-19-1-2120, the ARO YIP award W911NF-20-1-0097, the ARO grant
W911NF-18-1-0303, the NSF grants CCF-1907661, IIS-1900140, IIS-2100158 and
DMS-2014279, and the Princeton SEAS innovation award; Y. Chi has been
supported in part by the ONR under the grants N00014-18-1-2142 and
N00014-19-1-2404, by the ARO under the grant W911NF-18-1-0303, and by the NSF
under the grants CAREER ECCS-1818571, CCF-1901199, CCF-1806154, CCF-2007911,
CCF-2106778 and ECCS-2126634; and J. Fan has been supported in part by the ONR
grant N00014-19-1-2120, the NSF grants DMS-1662139, DMS-1712591, DMS-2053832,
DMS-2052926, and the NIH grant R01-GM072611, and the Princeton SEAS innovation
award. Part of this work was done while Y. Chen was visiting the Simons
Institute for the Theory of Computing. Last but not least, this work would not
come to existence without the continuing support of our families, especially
during the difficult time of COVID-19 pandemic when this monograph was
completed. Y. Chen thanks Yuting Wei for bringing love and encouragement
everyday during the writing of this monograph. Y. Chi is deeply grateful to
her parents, husband, and daughter for being the silver lining in the
pandemic. J. Fan enjoys gratefully his wife and daughters’ company and thanks
them for compassionate support. C. Ma thanks Xinyi Liu for her unfailing
support, and Pidan the Cat for bringing surprises and joys everyday. This
monograph is dedicated to them.