nr\max_{i,j}\mathbb{P}\bigg{(}|I_{1}^{ij}\mathcal{|}>\frac{C_{1}}{4\sqrt{r}}(C_{2}\delta)^{p}\|U\|_{2,\infty}\cap\mathcal{B}\cap\mathcal{A}_{ij}\bigg{)}+nr\max_{i,j}\mathbb{P}(\mathcal{B}\cap\mathcal{A}_{ij}^{c})$
$\displaystyle\qquad+nr\max_{i,j}\mathbb{P}\bigg{(}|I_{2}^{ij}|>\frac{C_{1}}{4\sqrt{r}}(C_{2}\delta)^{p}\|U\|_{2,\infty}\cap\mathcal{B}\bigg{)}+\mathbb{P}(\mathcal{B}^{c}).$
(21)

In Lemma 12 we show for all $i$ and $j$ that
$\mathbb{P}(\mathcal{B}\cap\mathcal{A}_{ij}^{c})=0$ and

$\displaystyle\mathbb{P}\bigg{(}|I_{2}^{ij}|>\frac{C_{1}}{4\sqrt{r}}(C_{2}\delta)^{p}\|U\|_{2,\infty}\cap\mathcal{B}\bigg{)}$
$\displaystyle=0.$

In addition, from our previous analysis,

$\displaystyle\mathbb{P}\bigg{(}|I_{1}^{ij}|>\frac{C_{1}(C_{2}\delta)^{p}}{4\sqrt{r}}\|U\|_{2,\infty}\cap\mathcal{A}_{ij}\bigg{)}\leq
4(n\vee d)^{-20}.$

Finally, $\mathbb{P}(\mathcal{B}^{c})\leq p(n\vee d)^{-5}+12(n\vee d)^{-6}$ by
the induction hypothesis. Plugging these results into Expression (21), we
obtain

$\displaystyle
nr\mathbb{P}\bigg{(}|I_{1}^{ij}|>\frac{C_{1}}{4\sqrt{r}}(C_{2}\delta)^{p}\|U\|_{2,\infty}\cap\mathcal{A}_{ij}\bigg{)}+nr$
$\displaystyle\mathbb{P}(\mathcal{B}\cap\mathcal{A}_{ij}^{c})+\mathbb{P}\bigg{(}|I_{2}^{ij}|>\frac{C_{1}}{4\sqrt{r}}(C_{2}\delta)^{p}\|U\|_{2,\infty}\cap\mathcal{B}\bigg{)}+\mathbb{P}(\mathcal{B}^{c})$
$\displaystyle\leq 4(nr)(n\vee d)^{-20}+p(n\vee d)^{-5}+12(n\vee d)^{-6}$
$\displaystyle\leq(p+1)(n\vee d)^{-5}$

as desired. ∎

######  Lemma 12.

Define $X^{-i}$ and $X$ as in the proof of Lemma 6. Let $\mathcal{A}_{ij}$ and
$\mathcal{B}$ be the events defined via

$\displaystyle\mathcal{A}_{ij}:=\bigg{\\{}\max_{k}|X_{kj}^{-i}|\leq
2C_{1}(C_{2}\delta)^{p-1}\|U\|_{2,\infty}\bigg{\\}}$
$\displaystyle\mathcal{B}:=\bigg{\\{}\|U_{\perp}U_{\perp}^{\top}(U_{\perp}U_{\perp}^{\top}WU_{\perp}U_{\perp}^{\top})^{p_{0}-1}WU\|_{2,\infty}$
$\displaystyle\leq C_{1}(C_{2}\delta)^{p_{0}}\|U\|_{2,\infty}\text{ for all
$1\leq p_{0}\leq p-1$}\bigg{\\}}$
$\displaystyle\bigcap\bigg{\\{}\|W\|\leq\frac{\delta}{\sqrt{r\log(n\vee
d)}}\bigg{\\}}$
$\displaystyle\bigcap\bigg{\\{}\|\Gamma(EE^{\top})\|\leq\frac{\delta}{\sqrt{r\log(n\vee
d)}}\bigg{\\}}.$

Then $\mathcal{B}\cap\mathcal{A}^{c}_{ij}$ is empty for all $i$ and $j$.
Define also $I_{2}^{ij}:=e_{i}^{\top}\Gamma(EE^{\top})(X-X^{-i})e_{j}.$ as in
the proof of Lemma 6. Then again for all $i$ and $j$,

$\displaystyle\mathbb{P}\bigg{(}|I_{2}^{ij}|>\frac{C_{1}}{4\sqrt{r}}(C_{2}\delta)^{p}\|U\|_{2,\infty}\cap\mathcal{B}\bigg{)}=0.$

###### Proof of Lemma 12.

The proof will be split up into steps, the first of which will be expanding
out the difference $X-X^{-i}$ in terms of a matrix telescoping series, the
second of which will be bounding individual terms, and the final step will
prove the two results.

Step 1: A useful expansion

We have that

$\displaystyle X$
$\displaystyle=(U_{\perp}U_{\perp}^{\top}WU_{\perp}U_{\perp}^{\top})^{p-2}WU$
$\displaystyle X^{-i}$
$\displaystyle=(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})^{p-2}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U.$

Define the matrix $\xi:=W-(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})$. We
note that

$\displaystyle X-X^{-i}$
$\displaystyle=(U_{\perp}U_{\perp}^{\top}WU_{\perp}U_{\perp}^{\top})^{p-2}WU-(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})^{p-2}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U$
$\displaystyle=(U_{\perp}U_{\perp}^{\top}WU_{\perp}U_{\perp}^{\top})^{p-2}WU-(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})^{p-2}(W-\xi)U$
$\displaystyle=\bigg{[}(U_{\perp}U_{\perp}^{\top}WU_{\perp}U_{\perp}^{\top})^{p-2}-(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})^{p-2}\bigg{]}WU$
$\displaystyle\qquad+(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})^{p-2}\xi
U$
$\displaystyle=\bigg{[}(U_{\perp}U_{\perp}^{\top}WU_{\perp}U_{\perp}^{\top})^{p-2}-(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})^{p-3}(U_{\perp}U_{\perp}^{\top}(W-\xi)U_{\perp}U_{\perp}^{\top})\bigg{]}WU$
$\displaystyle\qquad+(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})^{p-2}\xi
U$
$\displaystyle=\bigg{[}\bigg{(}(U_{\perp}U_{\perp}^{\top}WU_{\perp}U_{\perp}^{\top})^{p-3}-(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})^{p-3}\bigg{)}(U_{\perp}U_{\perp}^{\top}WU_{\perp}U_{\perp}^{\top})\bigg{]}WU$
$\displaystyle\qquad+(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})^{p-3}(U_{\perp}U_{\perp}^{\top}\xi
U_{\perp}U_{\perp}^{\top})WU$
$\displaystyle\qquad+(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})^{p-2}\xi
U.$

Note that if $p=2$ then we simply have $\xi U$. Define the matrices

$\displaystyle S_{\xi}$ $\displaystyle:=U_{\perp}U_{\perp}^{\top}\xi
U_{\perp}U_{\perp}^{\top}$ $\displaystyle S_{-i}:$
$\displaystyle=(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})$
$\displaystyle S:$
$\displaystyle=U_{\perp}U_{\perp}^{\top}WU_{\perp}U_{\perp}^{\top}.$

Then iterating the process above, it holds that

$\displaystyle X-X^{-i}$
$\displaystyle=\sum_{m=1}^{p-2}(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})^{m-1}(U_{\perp}U_{\perp}^{\top}\xi
U_{\perp}U_{\perp}^{\top})(U_{\perp}U_{\perp}^{\top}WU_{\perp}U_{\perp}^{\top})^{p-m-2}WU$
$\displaystyle+(U_{\perp}U_{\perp}^{\top}(I-e_{i}e_{i}^{\top})W(I-e_{i}e_{i}^{\top})U_{\perp}U_{\perp}^{\top})^{p-2}\xi
U$
$\displaystyle=\sum_{m=1}^{p-2}S_{-i}^{m-1}S_{\xi}S^{p-m-2}WU+S_{-i}^{p-2}\xi
U,$

where the sum is understood to be the empty sum if $p=2$.

Step 2: Analyzing each term in the sum

We now analyze each individual term in the sum on the event $\mathcal{B}$,
where we also analyze each row of $W(X-X^{-i})$. Let the matrix
$B\in\\{\Gamma(EE^{\top}),I\\}$ be fixed. We ignore the boundary term
$BS_{-i}^{p-2}\xi U$ for now.

Note that the $k$’th row of such term can be written as

$\displaystyle e_{k}^{\top}BS_{-i}^{m-1}S_{\xi}S^{p-m-2}WU,$

Recall that

$\displaystyle S_{\xi}$ $\displaystyle=U_{\perp}U_{\perp}^{\top}\xi
U_{\perp}U_{\perp}^{\top}$
$\displaystyle=U_{\perp}U_{\perp}^{\top}\bigg{(}e_{i}e_{i}^{\top}W+We_{i}e_{i}^{\top}-e_{i}e_{i}^{\top}We_{i}e_{i}^{\top}\bigg{)}U_{\perp}U_{\perp}^{\top}$
$\displaystyle=U_{\perp}U_{\perp}^{\top}e_{i}e_{i}^{\top}WU_{\perp}U_{\perp}^{\top}+U_{\perp}U_{\perp}^{\top}We_{i}e_{i}^{\top}U_{\perp}U_{\perp}^{\top}-U_{\perp}U_{\perp}^{\top}e_{i}e_{i}^{\top}We_{i}e_{i}^{\top}U_{\perp}U_{\perp}^{\top}.$

Therefore, by homogeneity of the vector norm, we have that

$\displaystyle\|e_{k}^{\top}B$ $\displaystyle
S_{-i}^{m-1}S_{\xi}S^{p-m-2}WU\|$
$\displaystyle\leq\|e_{k}^{\top}BS_{-i}^{m-1}U_{\perp}U_{\perp}^{\top}e_{i}e_{i}^{\top}WU_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|+\|e_{k}^{\top}BS_{-i}^{m-1}U_{\perp}U_{\perp}^{\top}We_{i}e_{i}^{\top}U_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|$
$\displaystyle\qquad+\|e_{k}^{\top}BS_{-i}^{m-1}U_{\perp}U_{\perp}^{\top}e_{i}e_{i}^{\top}We_{i}e_{i}^{\top}U_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|$
$\displaystyle\leq\|e_{k}^{\top}BS_{-i}^{m-1}U_{\perp}U_{\perp}^{\top}e_{i}\|\|e_{i}^{\top}WU_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|+\|e_{k}^{\top}BS_{-i}^{m-1}U_{\perp}U_{\perp}^{\top}We_{i}\|\|e_{i}^{\top}U_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|$
$\displaystyle\qquad+\|e_{k}^{\top}BS_{-i}^{m-1}U_{\perp}U_{\perp}^{\top}e_{i}\|\|e_{i}^{\top}We_{i}\|\|e_{i}^{\top}U_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|$
$\displaystyle\leq\|e_{k}^{\top}BS_{-i}^{m-1}U_{\perp}U_{\perp}^{\top}e_{i}\|\bigg{(}\|e_{i}^{\top}U_{\perp}U_{\perp}^{\top}WU_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|+\|e_{i}^{\top}UU^{\top}WU_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|\bigg{)}$
$\displaystyle\qquad+\|e_{k}^{\top}BS_{-i}^{m-1}U_{\perp}U_{\perp}^{\top}We_{i}\|\|e_{i}^{\top}U_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|+\|e_{k}^{\top}BS_{-i}^{m-1}U_{\perp}U_{\perp}^{\top}e_{i}\|\|e_{i}^{\top}We_{i}\|\|e_{i}^{\top}U_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|$
$\displaystyle\leq\|BS_{-i}^{m-1}\|\|U_{\perp}U_{\perp}^{\top}WU_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|_{2,\infty}+\|BS_{-i}^{m-1}\|\|U\|_{2,\infty}\|WU_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|$
$\displaystyle\qquad+\|BS_{-i}^{m-1}U_{\perp}U_{\perp}^{\top}W\|\|U_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|_{2,\infty}+\|BS_{-i}^{m-1}\|\|W\|\|U_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|_{2,\infty}$
$\displaystyle\leq\|BS_{-i}^{m-1}\|\|S^{p-m-1}WU\|_{2,\infty}+\|U\|_{2,\infty}\|BS_{-i}^{m-1}\|\|W\|^{p-m}+\|BS_{-i}^{m-1}\|\|W\|\|U_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|_{2,\infty}$
$\displaystyle\qquad+\|BS_{-i}^{m-1}\|\|W\|\|U_{\perp}U_{\perp}^{\top}S^{p-m-2}WU\|_{2,\infty}$
$\displaystyle\leq\|BS_{-i}^{m-1}\|\bigg{(}C_{1}(C_{2}\delta)^{p-m}\|U\|_{2,\infty}+\|U\|_{2,\infty}\|W\|^{p-m}+2\|W\|C_{1}(C_{2}\delta)^{p-m-1}\|U\|_{2,\infty}\bigg{)}$
$\displaystyle\leq\|BS_{-i}^{m-1}\|\|U\|_{2,\infty}\bigg{(}C_{1}(C_{2}\delta)^{p-m}+\bigg{[}\frac{\delta}{\sqrt{r\log(n\vee
d)}}\bigg{]}^{p-m}+2\frac{\delta}{\sqrt{r\log(n\vee
d)}}C_{1}(C_{2}\delta)^{p-m-1}\bigg{)}.$

But for $\|BS_{-i}^{m-1}\|$, this bound is uniform in $i$ and $j$. Finally,
for the boundary term, we note that the same strategy can be applied in
precisely the same manner, yielding the same bound.

Step 3: Putting it together

First we show the upper bound on $I_{2}^{ij}$ on $\mathcal{B}$. Recall that

$\displaystyle I_{2}^{ij}=e_{i}^{\top}\Gamma(EE^{\top})(X-X^{-i})e_{j}.$

By the bounds on each term, we have that

$\displaystyle|e_{i}^{\top}\Gamma(EE^{\top})(X-X^{-i})e_{j}|$
$\displaystyle\leq\|e_{i}^{\top}\Gamma(EE^{\top})(X-X^{-i})\|$
$\displaystyle\leq\sum_{m=1}^{p-2}\|\Gamma(EE^{\top})\|\|W\|^{m-1}\|U\|_{2,\infty}\bigg{(}C_{1}(C_{2}\delta)^{p-m}+\bigg{[}\frac{\delta}{\sqrt{r\log(n\vee
d)}}\bigg{]}^{p-m}+2\frac{\delta}{\sqrt{r\log(n\vee
d)}}C_{1}(C_{2}\delta)^{p-m-1}\bigg{)}$ $\displaystyle\leq
4C_{1}\|U\|_{2,\infty}\sum_{m=1}^{p-2}\|\Gamma(EE^{\top})\|\|W\|^{m-1}(C_{2}\delta)^{p-m}$
$\displaystyle\leq
4C_{1}\|U\|_{2,\infty}\sum_{m=1}^{p-2}\bigg{(}\frac{\delta}{\sqrt{r\log(n\vee
d)}}\bigg{)}^{m}(C_{2}\delta)^{p-m}$
$\displaystyle\leq\frac{4C_{1}\|U\|_{2,\infty}}{\sqrt{r\log(n\vee
d)}}(C_{2}\delta)^{p}\sum_{m=1}^{p-2}C_{2}^{-m}$
$\displaystyle\leq\frac{C_{1}}{4\sqrt{r}}(C_{2}\delta)^{p}\|U\|_{2,\infty}$

as long as $C_{2}\geq 48$.

Next we show that $\mathcal{B}\cap\mathcal{A}^{c}_{ij}$ is empty for all $i$
and $j$. More specifically, we show that

$\displaystyle|X_{kj}^{-i}-X_{kj}|$ $\displaystyle\leq
C_{1}(C_{2}\delta)^{p-1}\|U\|_{2,\infty},$

Again upper bounding the $k,j$ entry by the $k$’th row norm, we note that the
$k$’th row of $X-X^{-i}$ can be written as $e_{k}^{\top}(X-X^{-i}).$ Using the
expansion and the bounds on each term in the summation, we have that

$\displaystyle\|e_{k}^{\top}(X-X^{-i})\|$
$\displaystyle\leq\sum_{m=1}^{p-1}\|W\|^{m-1}\|U\|_{2,\infty}\bigg{(}C_{1}(C_{2}\delta)^{p-m}+\bigg{[}\frac{\delta}{\sqrt{r\log(n\vee
d)}}\bigg{]}^{p-m}+\frac{\delta}{\sqrt{r\log(n\vee
d)}}C_{1}(C_{2}\delta)^{p-m-1}\bigg{)}$ $\displaystyle\leq
4C_{1}\|U\|_{2,\infty}(C_{2}\delta)^{p-1}\sum_{m=1}C_{2}^{-m}$
$\displaystyle\leq C_{1}\|U\|_{2,\infty}(C_{2}\delta)^{p-1},$

and hence on $\mathcal{B}$ we have that

$\displaystyle\|e_{k}^{\top}X^{-i}e_{j}\|$
$\displaystyle\leq\|X\|_{2,\infty}+\|e_{k}^{\top}(X-X^{-i})\|$
$\displaystyle\leq 2C_{1}(C_{2}\delta)^{p-1}\|U\|_{2,\infty}$

as desired. Therefore $\mathcal{B}\cap\mathcal{A}^{c}_{ij}$ is empty.

∎

##  Appendix F Proof of Lemmas in Section B

###  F.1 Proof of Lemma 2

We will need the following lemma, adapted from Zhang et al. (2021).

######  Lemma 13 (Lemma 1 in Zhang et al. (2021)).

Let $U,V\in\mathbb{O}(n,r)$ and let $A$ be a fixed $n\times n$ matrix. Then

$\displaystyle\|G(UU^{{}^{\top}}A)\|$ $\displaystyle\leq\|U\|_{2,\infty}\|A\|$
$\displaystyle\|G(AVV^{\top})\|$ $\displaystyle\leq\|V\|_{2,\infty}\|A\|.$

###### Proof of Lemma 2.

We have that

$\displaystyle\|N_{T}-\tilde{A}\|$ $\displaystyle=\|G(N_{T}-\tilde{A})\|$
$\displaystyle\leq\left\|G\left(\left(P_{U^{T-1}}-P_{\tilde{U}}\right)\left(N_{T-1}-\tilde{A}\right)\right)\right\|+\left\|G\left(P_{\tilde{U}}\left(N_{T-1}-\tilde{A}\right)\right)\right\|+\left\|G\left(P_{U_{\perp}^{T-1}}\tilde{A}\right)\right\|$
$\displaystyle\leq\left\|G\left(\left(P_{U^{T-1}}-P_{\tilde{U}}\right)\left(N_{T-1}-\tilde{A}\right)\right)\right\|+\left\|G\left(P_{\tilde{U}}\left(N_{T-1}-\tilde{A}\right)\right)\right\|+\left\|G\left(P_{U_{\perp}^{T-1}}A\right)\right\|+\|G(P_{U_{\perp}^{T-1}}\Gamma(Z))\|$
$\displaystyle\leq\left\|G\left(\left(P_{U^{T-1}}-P_{\tilde{U}}\right)\left(N_{T-1}-\tilde{A}\right)\right)\right\|+\left\|G\left(P_{\tilde{U}}\left(N_{T-1}-\tilde{A}\right)\right)\right\|+\left\|G\left(P_{U_{\perp}^{T-1}}A\right)\right\|$
$\displaystyle\qquad+\|G(P_{U_{\perp}^{T-1}}-P_{\tilde{U}_{\perp}})\Gamma(Z))\|+\|G(P_{\tilde{U}_{\perp}}\Gamma(Z))\|$
$\displaystyle=J_{1}+J_{2}+J_{3}+J_{4}+J_{5}.$

we now bound each term.

The term $J_{1}$: We use the restricted-rank operator norm of $G$ to bound
this term, since $\mathrm{rank}(P_{U^{T-1}}-P_{\tilde{U}})\leq 2r$:

$\|G((P_{U^{T-1}}-P_{\tilde{U}})(N_{T-1}-\tilde{A}))\|\leq\|P_{U^{T-1}}-P_{\tilde{U}}\|\|N_{T-1}-\tilde{A}\|.$

The term $J_{2}$: By Lemma 13,

$\|G(P_{\tilde{U}}(N_{T-1}-\tilde{A}))\|\leq\|\tilde{U}\|_{2,\infty}\|N_{T-1}-\tilde{A}\|.$

The term $J_{3}$: By Lemmas 13 and 14,

$\|G(P_{U_{\perp}^{T-1}}A)\|=\|G(P_{U_{\perp}^{T-1}}AP_{U})\|\leq\|U\|_{2,\infty}\|P_{U_{\perp}^{T-1}}A\|\leq
2\|U\|_{2,\infty}\|N_{T-1}-A\|.$

The term $J_{4}$: Since
$P_{U_{\perp}^{T-1}}-P_{\tilde{U}_{\perp}}=(I-P_{\tilde{U}_{\perp}})-(I-P_{U_{\perp}^{T-1}})=P_{\tilde{U}}-P_{U^{T-1}},$
we proceed as we did for $J_{1}$, obtaining

$\|G((P_{U_{\perp}^{T-1}}-P_{\tilde{U}_{\perp}})\Gamma(Z)\|\leq\|P_{U^{T-1}}-P_{\tilde{U}}\|\|\Gamma(Z)\|.$

The term $J_{5}$: We have
$G(P_{\tilde{U}_{\perp}}\Gamma(Z))=G(\Gamma(Z))-G(P_{\tilde{U}}\Gamma(Z))=-G(P_{\tilde{U}}\Gamma(Z))$.
By Lemma 13,

$\|G(P_{\tilde{U}_{\perp}}\Gamma(Z))\|\leq\|\tilde{U}\|_{2,\infty}\|\Gamma(Z)\|.$

Putting it together: Let $K_{T-1}:=\|N_{T-1}-A\|$ and let
$\tilde{K}_{T-1}:=\|N_{T-1}-\tilde{A}\|$. Compiling these bounds, we have that

$\displaystyle J_{1}$
$\displaystyle\leq\|P_{U^{T-1}}-P_{\tilde{U}}\|\tilde{K}_{T-1}$ $\displaystyle
J_{2}$ $\displaystyle\leq\|\tilde{U}\|_{2.\infty}\tilde{K}_{T-1}$
$\displaystyle J_{3}$ $\displaystyle\leq 2\|U\|_{2,\infty}K_{T-1}$
$\displaystyle J_{4}$
$\displaystyle\leq\|P_{U^{T-1}}-P_{\tilde{U}}\|\|\Gamma(Z)\|$ $\displaystyle
J_{5}$ $\displaystyle\leq\|\tilde{U}\|_{2,\infty}\|\Gamma(Z)\|.$

These bounds hold regardless of $T$. Hence, we may take $T$ such that
$\|N_{T-1}-A\|\leq 3\|\Gamma(Z)\|$ (which exists by Zhang et al. (2021) under
our assumptions). The proof of Lemma 7 shows that
$\|\Gamma(Z)\|\leq\lambda_{r}^{2}/12$, so $\tilde{K}_{T-1}\leq
4(\lambda_{r}^{2}/12)\leq\lambda_{r}^{2}/2$, and by the Davis-Kahan theorem,
we have that

$\displaystyle\|P_{U^{T-1}}-P_{\tilde{U}}\|$ $\displaystyle\leq
2\frac{\tilde{K}_{T-1}}{\lambda_{r}^{2}}.$

Applying this to the above bounds, we see that

$\displaystyle J_{1}$ $\displaystyle\leq
2\frac{\tilde{K}_{T-1}^{2}}{\lambda_{r}^{2}}$ $\displaystyle J_{4}$
$\displaystyle\leq 2\frac{\tilde{K}_{T-1}}{\lambda_{r}^{2}}\|\Gamma(Z)\|.$

Moreover, we have the trivial bound

$\displaystyle K_{T-1}$ $\displaystyle\leq\tilde{K}_{T-1}+\|\Gamma(Z)\|.$

Hence, we see that

$\displaystyle J_{1}$ $\displaystyle\leq
2\frac{\tilde{K}_{T-1}^{2}}{\lambda_{r}^{2}}$ $\displaystyle J_{2}$
$\displaystyle\leq\|\tilde{U}\|_{2.\infty}\tilde{K}_{T-1}$ $\displaystyle
J_{3}$ $\displaystyle\leq
2\|U\|_{2,\infty}\bigg{(}\tilde{K}_{T-1}+\|\Gamma(Z)\|\bigg{)}$ $\displaystyle
J_{4}$ $\displaystyle\leq
2\frac{\tilde{K}_{T-1}}{\lambda_{r}^{2}}\|\Gamma(Z)\|$ $\displaystyle J_{5}$
$\displaystyle\leq\|\tilde{U}\|_{2,\infty}\|\Gamma(Z)\|.$

Now, for $T_{0}$ such that $K_{T_{0}}\leq 3\|\Gamma(Z)\|$,
$\tilde{K}_{T_{0}}\leq 4\|\Gamma(Z)\|,$ and we see that we have the initial
bound

$\displaystyle\tilde{K}_{T_{0}+1}$ $\displaystyle\leq
40\frac{\|\Gamma(Z)\|^{2}}{\lambda_{r}^{2}}+5\|\tilde{U}\|_{2,\infty}\|\Gamma(Z)\|+10\|U\|_{2,\infty}\|\Gamma(Z)\|.$

On the event in Theorem 3 and Assumption 2, once $n$ and $d$ are large enough,
$\|\tilde{U}-UU^{\top}\tilde{U}\|_{2,\infty}\leq\|U\|_{2,\infty}$, so

$\|\tilde{U}\|_{2,\infty}\leq\|\tilde{U}-UU^{\top}\tilde{U}\|_{2,\infty}+\|UU^{\top}\tilde{U}\|_{2,\infty}\leq
2\|U\|_{2,\infty},$

since $\|U^{\top}\tilde{U}\|\leq 1$. This gives

$\tilde{K}_{T_{0}+1}\leq
40\frac{\|\Gamma(Z)\|^{2}}{\lambda_{r}^{2}}+20\|U\|_{2,\infty}\|\Gamma(Z)\|.$

Let $\rho=10\|\Gamma(Z)\|/\lambda_{r}^{2}$, and suppose that for $T-1\geq
T_{0}$ we have the bound

$\displaystyle\tilde{K}_{T-1}$ $\displaystyle\leq
4\rho^{T-1-T_{0}}\|\Gamma(Z)\|+\frac{20}{1-\rho}\|U\|_{2,\infty}\|\Gamma(Z)\|.$

Clearly for $T_{0}$ we have this bound. With the recursion, and using
$\tilde{K}_{T-1}\leq 4\|\Gamma(Z)\|$ and $\|\tilde{U}\|_{2,\infty}\leq
2\|U\|_{2,\infty}$, we get

$\displaystyle\tilde{K}_{T}$ $\displaystyle\leq
10\frac{\tilde{K}_{T-1}}{\lambda_{r}^{2}}\|\Gamma(Z)\|+20\|U\|_{2,\infty}\|\Gamma(Z)\|$
$\displaystyle\leq\frac{10}{\lambda_{r}^{2}}\left[4\rho^{T-1-T_{0}}\|\Gamma(Z)\|+\frac{20}{1-\rho}\|U\|_{2,\infty}\|\Gamma(Z)\|\right]\|\Gamma(Z)\|+20\|U\|_{2,\infty}\|\Gamma(Z)\|$
$\displaystyle\leq
4\rho^{T-T_{0}}\|\Gamma(Z)\|+\left(1+\frac{\rho}{1-\rho}\right)20\|U\|_{2,\infty}\|\Gamma(Z)\|$
$\displaystyle=4\rho^{T-T_{0}}\|\Gamma(Z)\|+\frac{20}{1-\rho}\|U\|_{2,\infty}\|\Gamma(Z)\|$

as required. ∎

##  Appendix G Proof of Lemmas in Section C

Recall Lemma 8. See 8

###### Proof of Lemma 8.

Recall the definitions of $R_{1}$, $R_{2}$ and $R_{3}$ via

$\displaystyle R_{1}:$
$\displaystyle=e_{i}^{\top}UU^{\top}\bigg{(}EM^{\top}+\Gamma(EE^{\top})\bigg{)}U\Lambda^{-2}e_{j};$
$\displaystyle R_{2}:$
$\displaystyle=e_{i}^{\top}\bigg{(}\tilde{U}_{D}\tilde{U}_{D}^{\top}-\tilde{U}\tilde{U}^{\top}\bigg{)}Ue_{j};$
$\displaystyle R_{3}:$ $\displaystyle=e_{i}^{\top}\sum_{k\geq
2}S_{MM^{\top},k}(W)Ue_{j}.$

We analyze each in turn.

The term $R_{1}$: We will split this into two terms, $R_{11}$ and $R_{12}$.
From the identity $M^{\top}U=V\Lambda$, the $i,j$ entry of $R_{1}$ can be
written as

$\displaystyle\frac{1}{\lambda_{j}}e_{i}^{\top}UU^{\top}EV_{\cdot
j}+\frac{1}{\lambda_{j}^{2}}\sum_{k\neq l}(UU^{\top})_{ik}U_{lj}\langle
E_{k},E_{l}\rangle:$ $\displaystyle=R_{11}+R_{12},$

where

$\displaystyle R_{11}:$
$\displaystyle=\frac{1}{\lambda_{j}}\sum_{k=1}^{n}(UU^{\top})_{ik}\langle
E_{k},V_{\cdot j}\rangle;$ $\displaystyle R_{12}:$
$\displaystyle=\frac{1}{\lambda_{j}^{2}}\sum_{k\neq
l}(UU^{\top})_{ik}U_{lj}\langle E_{k},E_{l}\rangle.$

Dividing $R_{11}$ by $\sigma_{ij}$ reveals it is of the form

$\displaystyle\frac{1}{\|\Sigma_{i}^{1/2}V_{\cdot
j}\|}\sum_{k=1}^{n}(UU^{\top})_{ik}\langle E_{k},V_{\cdot j}\rangle.$

To calculate an upper bound, we need to calculate the $\psi_{2}$ norm squared:

$\displaystyle\frac{1}{\|\Sigma_{i}^{1/2}V_{\cdot
j}\|^{2}}\sum_{k=1}^{n}(UU^{\top})_{ik}^{2}V_{\cdot
j}^{\top}\Sigma_{k}V_{\cdot j}$
$\displaystyle\leq\frac{\sigma^{2}}{\|\Sigma_{i}^{1/2}V_{\cdot
j}\|^{2}}\sum_{k=1}^{n}(UU^{\top})_{ik}^{2}$
$\displaystyle\leq\kappa_{\sigma}^{2}\|U\|_{2,\infty}^{2}$

which by Hoeffding’s inequality shows that this is less than
$\tilde{C}_{R_{1}}\kappa_{\sigma}\|U\|_{2,\infty}t$ with probability at least
$1-2\exp(-ct^{2})$. Hence, we obtain the bound
$C_{R_{1}}\kappa_{\sigma}\|U\|_{2,\infty}\sqrt{\log(n\vee d)}$ with
probability at least $1-2(n\vee d)^{-4}$.

We now analyze $R_{12}$. Note that

$\displaystyle R_{12}:=\frac{1}{\lambda_{j}^{2}}\sum_{k\neq
l}(UU^{\top})_{ik}U_{lj}\langle E_{k},E_{l}\rangle$

resembles the random variable in the Hanson-Wright inequality (e.g. Vershynin
(2020); Chen and Yang (2020)). By the generalized Hanson-Wright inequality
(e.g. Exercise 6.2.7 in Vershynin (2018)), we have that

$\displaystyle\mathbb{P}\bigg{\\{}\bigg{|}\sum_{k\neq l}B_{kl}\langle
E_{k},E_{l}\rangle\bigg{|}\geq t\bigg{)}$ $\displaystyle\leq
2\exp\bigg{[}-c\min\bigg{(}\frac{t^{2}}{\sigma^{4}d\|B\|_{F}^{2}},\frac{t}{\sigma^{2}\|B\|}\bigg{)}\bigg{]}$

where $B_{kl}:=(UU^{\top})_{il}U_{kj}$. Note that its Frobenius norm can be
evaluated via

$\displaystyle\|B\|_{F}^{2}$ $\displaystyle=\sum_{k\neq
l}(UU^{\top})_{il}^{2}U_{kj}^{2}$
$\displaystyle\leq\sum_{l=1}^{n}(UU^{\top})_{il}^{2}\sum_{k=1}^{n}U_{kj}^{2}$
$\displaystyle\leq\sum_{l=1}^{n}(UU^{\top})_{il}^{2}$
$\displaystyle\leq\|U\|_{2,\infty}^{2}.$

Similarly,

$\displaystyle\|B\|:$
$\displaystyle=\sup_{\|x\|=1,\|y\|=1}\sum_{k=1}^{n}x_{k}(UU^{\top})_{ik}\sum_{l=1}^{n}U_{lj}y_{l}$
$\displaystyle\leq\sup_{\|x\|=1}\sum_{k=1}^{n}x_{k}(UU^{\top})_{ik}$
$\displaystyle=\|(UU^{\top})_{i}\|_{2}$ $\displaystyle\leq\|U\|_{2,\infty}.$

Therefore,

$\displaystyle\mathbb{P}\bigg{\\{}\bigg{|}\sum_{k\neq l}B_{kl}\langle
E_{k}E_{l}\rangle\bigg{|}\geq t\bigg{)}$ $\displaystyle\leq
2\exp\bigg{[}-c\min\bigg{(}\frac{t^{2}}{\sigma^{4}d\|U\|_{2,\infty}^{2}},\frac{t}{\sigma^{2}\|U\|_{2,\infty}}\bigg{)}\bigg{]}.$

Taking $t=s\sqrt{d}\|U\|_{2,\infty}\sigma^{2}$ shows that

$\displaystyle\mathbb{P}\bigg{\\{}\bigg{|}\sum_{k\neq l}B_{kl}\langle
E_{k}E_{l}\rangle\bigg{|}\geq s\sqrt{d}\|U\|_{2,\infty}\sigma^{2}\bigg{)}$
$\displaystyle\leq
2\exp\bigg{(}-c\min\bigg{(}s^{2},s\sqrt{d}\bigg{)}\bigg{)},$

and hence taking $s=\frac{1}{\sqrt{c}}\sqrt{4\log(n\vee d)}$ we see that with
probability at least $1-2(n\vee d)^{-4}$

$\displaystyle\bigg{|}\frac{1}{\lambda_{j}^{2}}\sum_{k\neq l}B_{kl}\langle
E_{k}E_{l}\rangle\bigg{|}$ $\displaystyle\leq
C_{R_{1}}\frac{\sigma^{2}}{\lambda_{j}^{2}}\|U\|_{2,\infty}\sqrt{d\log(n\vee
d)}.$

Dividing by $\sigma_{ij}$ reveals that with this same probability,

$\displaystyle|R_{22}/\sigma_{ij}|$ $\displaystyle\leq
C_{R_{1}}\kappa_{\sigma}\kappa\frac{\sigma\sqrt{d}}{\lambda_{j}}\|U\|_{2,\infty}\sqrt{\log(n\vee
d)}$ $\displaystyle\leq
C_{R_{1}}\kappa_{\sigma}\kappa\mu_{0}\frac{\sigma\sqrt{rd}}{\lambda_{r}}\sqrt{\frac{\log(n\vee
d)}{n}}$ $\displaystyle\leq
C_{R_{1}}\kappa_{\sigma}\kappa\mu_{0}\frac{1}{\mathrm{SNR}}\sqrt{\frac{\log(n\vee
d)}{n}}.$

The term $R_{2}$: Note that $\tilde{U}_{D}$ and $\tilde{U}$ were already
analyzed in Lemma 4, which shows that

$\displaystyle\|\tilde{U}_{D}\tilde{U}_{D}^{\top}-\tilde{U}\tilde{U}^{\top}\|$
$\displaystyle\leq\frac{C_{R_{2}}\lambda_{1}\sigma\sqrt{\log(n\vee
d)}}{\lambda_{r}^{2}}\|U\|_{2,\infty}$ $\displaystyle\leq
C_{R_{2}}\|U\|_{2,\infty}\kappa\frac{\sigma}{\lambda_{r}}\sqrt{\log(n\vee d)}$

with probability at least $1-2(n\vee d)^{-4}$. Multiplying by
$\frac{1}{\sigma_{ij}}$ yields the upper bound

$\displaystyle
C_{R_{2}}\kappa_{\sigma}\|U\|_{2,\infty}\kappa^{2}\sqrt{\log(n\vee d)}$
$\displaystyle\leq
C_{R_{2}}\kappa_{\sigma}\mu_{0}\kappa^{2}\sqrt{\frac{r\log(n\vee d)}{n}}.$

with probability at least $1-2(n\vee d)^{-4}$.

The term $R_{3}$: First, note that

$\displaystyle\bigg{|}e_{i}^{\top}\sum_{k\geq
2}S_{MM^{\top},k}(W)Ue_{j}\bigg{|}$ $\displaystyle\leq\|\sum_{k\geq
2}S_{MM^{\top},k}(W)U\|_{2,\infty}$ $\displaystyle\leq\sum_{k\geq
2}\|S_{MM^{\top},k}(W)U\|_{2,\infty}.$

Examining the proof of Theorem 3 shows that the exact same result holds, only
now we start the summation at $k=2$. Consequently, using the definition of
$\delta$ as in the proof of Theorem 3, by Lemma 6 we have that with
probability $1-c\log(n\vee d)(n\vee d)^{-5}$ that

$\displaystyle\sum_{k=2}^{\infty}\|S_{MM^{\top},k}(W)U\|_{2,\infty}$
$\displaystyle\leq\|U\|_{2,\infty}\sum_{k=2}^{c\log(n\vee
d)}C_{1}\bigg{(}\frac{4C_{2}\delta}{\lambda_{r}^{2}}\bigg{)}^{k}+\sum_{k=c\log(n\vee
d)}^{\infty}\bigg{(}\frac{4\delta}{\lambda_{r}^{2}}\bigg{)}^{k}$
$\displaystyle\leq
C_{R_{3}}\|U\|_{2,\infty}\frac{\delta^{2}}{\lambda_{r}^{4}}.$

Hence, with probability at least $1-(n\vee d)^{-4}$,

$\displaystyle\frac{1}{\sigma_{ij}}|R_{3}|$ $\displaystyle\leq
C_{R_{3}}\|U\|_{2,\infty}\frac{\delta^{2}}{\lambda_{r}^{4}}\frac{1}{\sigma_{ij}}$
$\displaystyle\leq
C_{R_{3}}\|U\|_{2,\infty}\frac{1}{\sigma_{ij}\lambda_{r}^{4}}\bigg{(}\sqrt{rnd}\log(\max(n,d))\sigma^{2}+\sqrt{rn\log(n)}\lambda_{1}\sigma\bigg{)}^{2}$
$\displaystyle\leq
C_{R_{3}}\|U\|_{2,\infty}\frac{rnd\log^{2}(d)\sigma^{4}+rn\log(n\vee
d)\lambda_{1}^{2}\sigma^{2}+rn\sqrt{d}\log^{3/2}(n)\sigma^{3}}{\sigma_{ij}\lambda_{r}^{4}}$
$\displaystyle\leq
C_{R_{3}}\kappa\kappa_{\sigma}\|U\|_{2,\infty}\frac{rnd\log^{2}(d)\sigma^{3}+rn\log(n\vee
d)\lambda_{1}^{2}\sigma+rn\sqrt{d}\log^{3/2}(n)\sigma^{2}}{\lambda_{r}^{3}}$
$\displaystyle\leq
C_{R_{3}}\kappa\kappa_{\sigma}\|U\|_{2,\infty}\bigg{(}\frac{rnd\log^{2}(n)\sigma^{3}+rn\sqrt{d}\log^{3/2}(n)\sigma^{2}}{\lambda_{r}^{3}}+\frac{rn\log(n\vee
d)\kappa^{2}\sigma}{\lambda_{r}}\bigg{)}$ $\displaystyle\leq
C_{R_{3}}\kappa\kappa_{\sigma}\mu_{0}\bigg{(}\frac{r^{3/2}\sqrt{n}d\sigma^{3}}{\lambda_{r}^{3}}\log^{2}(n\vee
d)+\frac{r^{3/2}\sqrt{nd}\sigma^{2}}{\lambda_{r}^{3}}\log^{3/2}(n\vee
d)+\frac{r^{3/2}\sqrt{n}\kappa^{2}\sigma}{\lambda_{r}}\log(n\vee d)\bigg{)}$
$\displaystyle\leq
C_{R_{3}}\kappa\kappa_{\sigma}\mu_{0}\bigg{(}\frac{\log^{2}(n)}{\mathrm{SNR}^{3}}+\frac{\sqrt{r}}{\lambda_{r}}\frac{\log^{3/2}(n\vee
d)}{\mathrm{SNR}^{2}}+\frac{\kappa^{2}r\log(n\vee d)}{\mathrm{SNR}}\bigg{)}$
$\displaystyle\leq C_{R_{3}}\kappa^{3}\kappa_{\sigma}\mu_{0}\frac{r\log(n\vee
d)}{\mathrm{SNR}},$

where we have absorbed extra constants into $C_{R_{3}}$ since
$\mathrm{SNR}\geq\kappa\sqrt{\log(n\vee d)}$ by Assumption 2. Therefore,
summing up the probabilities and absorbing the constants, we see that with
probability at least $1-5(n\vee d)^{-4}$ that

$\displaystyle\frac{1}{\sigma_{ij}}\bigg{(}|R_{1}|+|R_{2}|+|R_{3}|\bigg{)}$
$\displaystyle\leq
C_{R_{1}}\kappa_{\sigma}\kappa\mu_{0}\frac{1}{\mathrm{SNR}}\sqrt{\frac{\log(n\vee
d)}{n}}+C_{R_{2}}\kappa_{\sigma}\mu_{0}\kappa^{2}\sqrt{\frac{r\log(n\vee
d)}{n}}+C_{R_{3}}\kappa^{3}\kappa_{\sigma}\mu_{0}\frac{r\log(n\vee
d)}{\mathrm{SNR}}$ $\displaystyle\leq
C_{6}\kappa_{\sigma}\kappa^{2}\mu_{0}\sqrt{\frac{r\log(n\vee
d)}{n}}+C_{7}\kappa^{3}\kappa_{\sigma}\mu_{0}\frac{r\log(n\vee
d)}{\mathrm{SNR}}$

as required. ∎

See 9

###### Proof of Lemma 9.

Recall the definitions of $R_{4}$ and $R_{5}$ via

$\displaystyle R_{4}:$
$\displaystyle=e_{i}^{\top}\widehat{U}(\mathcal{O}_{*}-\widehat{U}^{\top}\tilde{U}\tilde{U}^{\top}U)e_{j};$
$\displaystyle R_{5}:$
$\displaystyle=e_{i}^{\top}\bigg{(}\widehat{U}\widehat{U}^{\top}\tilde{U}\tilde{U}^{\top}U-\tilde{U}\tilde{U}^{\top}U\bigg{)}e_{j}.$

On the event in Theorem 2,
$\|\widehat{U}\|_{2,\infty}\leq\|U\|_{2,\infty}+\inf_{\mathcal{O}_{*}}\|\widehat{U}-U\mathcal{O}_{*}\|_{2,\infty}\leq
C\|U\|_{2,\infty}$ by Assumption 2. Therefore, the term $R_{4}$ can be bounded
in a similar manner to the proof of Lemma 3 (see Appendix H) via

$\displaystyle\bigg{|}e_{i}^{\top}\widehat{U}(\mathcal{O}_{*}-\widehat{U}^{\top}\tilde{U}\tilde{U}^{\top}U)e_{j}\bigg{|}$
$\displaystyle\leq\|\widehat{U}\|_{2,\infty}\|\mathcal{O}_{*}-\widehat{U}^{\top}\tilde{U}\tilde{U}^{\top}U\|$
$\displaystyle\leq
C\|U\|_{2,\infty}\bigg{(}\|\sin(\widehat{U},\tilde{U})\|^{2}+\|\sin(\tilde{U},U)\|^{2}\bigg{)}$
$\displaystyle\leq
C\|U\|_{2,\infty}\frac{\|\Gamma(Z)\|^{2}}{\lambda_{r}^{4}},$

where the final inequality is by the Davis-Kahan Theorem and Lemmas 1 and 2.
On the event in Lemma 1, the numerator can be bounded by

$\displaystyle
C_{\mathrm{spectral}}^{2}\bigg{(}\sigma^{2}(n+\sqrt{nd})+\sigma\lambda_{1}\sqrt{n}\bigg{)}^{2}.$

Consequently, there exists a universal constant $C_{R_{4}}$ such that

$\displaystyle\frac{1}{\sigma_{ij}}|R_{4}|$
$\displaystyle\leq\frac{1}{\sigma_{ij}}C_{R_{4}}\|U\|_{2,\infty}\frac{\sigma^{3}n\sqrt{d}+\sigma^{2}\lambda_{1}^{2}n+\sigma^{4}nd}{\lambda_{r}^{4}}$
$\displaystyle=C_{R_{4}}\frac{\lambda_{j}}{\|\Sigma_{i}^{1/2}V_{\cdot
j}\|}\|U\|_{2,\infty}\frac{\sigma^{3}n\sqrt{d}+\sigma^{2}\lambda_{1}^{2}n+\sigma^{4}nd}{\lambda_{r}^{4}}$
$\displaystyle\leq
C_{R_{4}}\kappa\kappa_{\sigma}\|U\|_{2,\infty}\frac{\sigma^{2}n\sqrt{d}+\sigma\lambda_{1}^{2}n+\sigma^{3}nd}{\lambda_{r}^{3}}$
$\displaystyle\leq
C_{R_{4}}\kappa\kappa_{\sigma}\mu_{0}\frac{\sigma^{2}\sqrt{rnd}+\sigma\lambda_{1}^{2}\sqrt{rn}+\sigma^{3}\sqrt{rn}d}{\lambda_{r}^{3}}$
$\displaystyle\leq
C_{R_{4}}\kappa\kappa_{\sigma}\mu_{0}\bigg{(}\frac{1}{\lambda_{r}\mathrm{SNR}^{2}}+\frac{\kappa^{2}}{\mathrm{SNR}}+\frac{1}{\mathrm{SNR}^{3}}\bigg{)}$
$\displaystyle\leq
C_{8}\kappa^{3}\kappa_{\sigma}\mu_{0}\frac{1}{\mathrm{SNR}}.$

The term $R_{5}$ satisfies

$\displaystyle\frac{1}{\sigma_{ij}}\bigg{|}e_{i}^{\top}\bigg{(}\widehat{U}\widehat{U}^{\top}\tilde{U}\tilde{U}^{\top}U-\tilde{U}\tilde{U}^{\top}U\bigg{)}e_{j}\bigg{|}$
$\displaystyle\leq\frac{1}{\sigma_{ij}}\|\widehat{U}\widehat{U}^{\top}\tilde{U}\tilde{U}^{\top}U-\tilde{U}\tilde{U}^{\top}U\|_{2,\infty}$
$\displaystyle\leq\frac{1}{\sigma_{ij}}\|\widehat{U}\widehat{U}^{\top}\tilde{U}-\tilde{U}\|_{2,\infty}.$

The definition of $\tilde{H}$ in the proof of Theorem 4 shows that
$\tilde{H}^{\top}=\widehat{U}^{\top}\tilde{U}$. Define

$\mathcal{O}_{1}:=\operatorname*{arg\,min}_{\mathcal{O}\in\mathbb{O}(r)}\|\widehat{U}-\tilde{U}\mathcal{O}\|_{F}.$

Then

$\displaystyle\frac{1}{\sigma_{ij}}\|\widehat{U}\widehat{U}^{\top}\tilde{U}-\tilde{U}\|_{2,\infty}$
$\displaystyle=\frac{1}{\sigma_{ij}}\|\widehat{U}\tilde{H}^{\top}-\tilde{U}\|_{2,\infty}$
$\displaystyle\leq\frac{1}{\sigma_{ij}}\bigg{(}\|\widehat{U}\tilde{H}^{\top}-\widehat{U}\mathcal{O}_{1}^{\top}\|_{2,\infty}+\|\widehat{U}\mathcal{O}_{1}^{\top}-\tilde{U}\|_{2,\infty}\bigg{)}$
$\displaystyle=\frac{1}{\sigma_{ij}}\bigg{(}\|\widehat{U}\tilde{H}^{\top}-\widehat{U}\mathcal{O}_{1}^{\top}\|_{2,\infty}+\|\widehat{U}-\tilde{U}\mathcal{O}_{1}\|_{2,\infty}\bigg{)}$
$\displaystyle\leq\frac{1}{\sigma_{ij}}\bigg{(}\|\widehat{U}(\tilde{H}^{\top}-\mathcal{O}_{1}^{\top})\|_{2,\infty}+\|\widehat{U}-\tilde{U}\tilde{H}\|_{2,\infty}+\|\tilde{U}(\mathcal{O}_{1}-\tilde{H})\|_{2,\infty}\bigg{)}$
$\displaystyle\leq\frac{1}{\sigma_{ij}}\bigg{(}\|\widehat{U}\|_{2,\infty}\|\tilde{H}-\mathcal{O}_{1}\|+\|\tilde{U}\|_{2,\infty}\|\mathcal{O}_{1}-\tilde{H}\|+\|\widehat{U}-\tilde{U}\tilde{H}\|_{2,\infty}\bigg{)}$
$\displaystyle\leq\frac{1}{\sigma_{ij}}\bigg{(}2C\|U\|_{2,\infty}\|\sin(\widehat{U},\tilde{U})\|_{2}^{2}+\|\widehat{U}-\tilde{U}\tilde{H}\|_{2,\infty}\bigg{)}$
$\displaystyle\leq\frac{1}{\sigma_{ij}}\bigg{(}2C\|U\|_{2,\infty}\frac{\|\Gamma(Z)\|^{2}}{\lambda_{r}^{4}}+\|\widehat{U}-\tilde{U}\tilde{H}\|_{2,\infty}\bigg{)},$

where the final line follows from the Davis-Kahan Theorem. By Theorem 4 we
have that

$\displaystyle\|\widehat{U}-\tilde{U}\tilde{H}\|_{2,\infty}$
$\displaystyle\leq
C_{D}\kappa^{2}\|U\|_{2,\infty}^{2}\frac{\|\Gamma(Z)\|}{\lambda_{r}^{2}}.$
(22)

We have already shown that

$\displaystyle\frac{1}{\sigma_{ij}}\|U\|_{2,\infty}\frac{\|\Gamma(Z)\|^{2}}{\lambda_{r}^{4}}$
$\displaystyle\leq
C_{8}\frac{\kappa^{3}\kappa_{\sigma}\mu_{0}}{\mathrm{SNR}},$

which matches the bound for $R_{4}$, so by increasing the constant $C_{8}$, we
need only bound the term in Equation (22). We have that

$\displaystyle\frac{1}{\sigma_{ij}}C_{D}\kappa^{2}\|U\|_{2,\infty}^{2}\frac{\|\Gamma(Z)\|}{\lambda_{r}^{2}}$
$\displaystyle\leq\frac{C_{9}}{\sigma_{ij}}\kappa^{2}\|U\|_{2,\infty}^{2}\frac{\sigma^{2}(n+\sqrt{nd})+\sigma\lambda_{1}\sqrt{n}}{\lambda_{r}^{2}}$
$\displaystyle\leq
C_{9}\kappa_{\sigma}\kappa^{3}\|U\|_{2,\infty}^{2}\frac{\sigma(n+\sqrt{nd})+\lambda_{1}\sqrt{n}}{\lambda_{r}}$
$\displaystyle\leq
C_{9}\kappa_{\sigma}\kappa^{3}\mu_{0}^{2}\frac{r\sigma(n+\sqrt{nd})+\lambda_{1}r\sqrt{n}}{n\lambda_{r}}$
$\displaystyle\leq
C_{9}\kappa_{\sigma}\kappa^{3}\mu_{0}^{2}\bigg{(}\frac{r\sigma}{\lambda_{r}}+\frac{r\sigma\sqrt{d}}{\sqrt{n}\lambda_{r}}+\kappa\frac{r}{\sqrt{n}}\bigg{)}$
$\displaystyle\leq
C_{9}\kappa^{4}\kappa_{\sigma}\mu_{0}^{2}\frac{r}{\sqrt{n}}$

which is the desired upper bound. ∎

See 10

###### Proof of Lemma 10.

First, conditionally on $E_{i}$ the sum is a sum of independent random
variables each with $\psi_{2}$ norm bounded by

$\displaystyle\bigg{\|}\langle E_{i},E_{k}\rangle
U_{kj}\lambda_{j}^{-2}\bigg{\|}_{\psi_{2}}$
$\displaystyle\leq\max_{k}\|\langle
E_{i},E_{k}\rangle\|_{\psi_{2}}|U_{kj}|\lambda_{j}^{-2}$ $\displaystyle\leq
C\|E_{i}\|\sigma\|U\|_{2,\infty}\lambda_{j}^{-2},$

where $C$ is a universal constant. Hence, for any $t\geq 0$, we have that

$\displaystyle\bigg{|}\sum_{k\neq i}\langle E_{i},E_{k}\rangle
U_{kj}\lambda_{j}^{-2}\bigg{|}$ $\displaystyle\leq
C\sigma\sqrt{n}\|E_{i}\|\|U\|_{2,\infty}\lambda_{j}^{-2}t$

with probability at least $1-2\exp(-ct^{2})$. Furthermore, for some other
universal constant $C$, $\|E_{i}\|\leq C\sigma_{i}\sqrt{d}s$ with probability
at least $1-2\exp(-cs^{2})$ (uniformly over $i$). Hence,

$\displaystyle\bigg{|}\sum_{k\neq i}\langle E_{i},E_{k}\rangle
U_{kj}\lambda_{j}^{-2}\bigg{|}$ $\displaystyle\leq
C_{10}\sigma\sqrt{nd}\lambda_{j}^{-2}\|U\|_{2,\infty}\sigma_{i}t$

with probability at least $1-4\exp(-ct)$. Recall
$\sigma^{2}_{ij}:=\|\Sigma_{i}^{1/2}V_{\cdot j}\|^{2}\lambda_{j}^{-2}$. Then

$\displaystyle\frac{1}{\sigma_{ij}}\bigg{|}\sum_{k\neq i}\langle
E_{i},E_{k}\rangle U_{kj}\lambda_{j}^{-2}\bigg{|}$
$\displaystyle\leq\frac{C_{10}}{\sigma_{ij}}\sigma\sqrt{nd}\lambda_{j}^{-2}\|U\|_{2,\infty}\sigma_{i}t$
$\displaystyle\leq
C_{10}\frac{\sigma\sqrt{d}}{\lambda_{j}}\frac{\sigma_{i}}{\|\Sigma_{i}^{1/2}V_{\cdot
j}\|}\sqrt{n}\|U\|_{2,\infty}t$ $\displaystyle\leq
C_{10}\kappa_{\sigma}\frac{\sigma\sqrt{d}}{\lambda_{j}}\sqrt{n}\|U\|_{2,\infty}t$

with probability at least $1-4e^{-ct}$, since
$\sigma_{i}/\|\Sigma_{i}^{1/2}V_{\cdot j}\|\leq\kappa_{\sigma}$ remains
bounded away from zero and infinity. Taking $t=C(4/c)\log(n\vee d)$ and
absorbing the constants shows that with probability at least $1-4(n\vee
d)^{-4}$, uniformly over $i$ and $j$ that

$\displaystyle\frac{1}{\sigma_{ij}}\bigg{|}\sum_{k\neq i}\langle
E_{i},E_{k}\rangle U_{kj}\lambda_{j}^{-2}\bigg{|}$ $\displaystyle\leq
C_{10}\kappa_{\sigma}\frac{\sigma\sqrt{d}}{\lambda_{j}}\sqrt{n}\|U\|_{2,\infty}\log(n\vee
d)$ $\displaystyle\leq C_{10}\mu_{0}\kappa_{\sigma}\frac{\log(n\vee
d)}{\mathrm{SNR}}$

as required. ∎

##  Appendix H Proof of Auxiliary Lemmas

First, recall Lemma 3. See 3

###### Proof of Lemma 3.

We have that for any orthogonal matrices $\mathcal{O}$ and
$\tilde{\mathcal{O}}$ that

$\displaystyle\|UU^{\top}\tilde{U}\tilde{U}^{\top}\widehat{U}-U\mathcal{O}\|_{2,\infty}$
$\displaystyle\leq\|U\|_{2,\infty}\|U^{\top}\tilde{U}\tilde{U}^{\top}\widehat{U}-\mathcal{O}\|$
$\displaystyle\leq\|U\|_{2,\infty}\bigg{(}\|U^{\top}\tilde{U}\tilde{U}^{\top}\widehat{U}-\tilde{\mathcal{O}}\tilde{U}^{\top}\widehat{U}\|+\|\mathcal{O}-\tilde{\mathcal{O}}\tilde{U}^{\top}\widehat{U}\|\bigg{)}$
$\displaystyle\leq\|U\|_{2,\infty}\bigg{(}\|U^{\top}\tilde{U}-\tilde{\mathcal{O}}\|+\|\mathcal{O}-\tilde{\mathcal{O}}\tilde{U}^{\top}\widehat{U}\|\bigg{)}.$

Let $\mathcal{O}^{(1)}$ and $\mathcal{O}^{(2)}$ be the orthogonal matrices
satisfying

$\displaystyle\mathcal{O}^{(1)}:$
$\displaystyle=\operatorname*{arg\,min}\|U-\tilde{U}\mathcal{O}\|_{F};$
$\displaystyle\mathcal{O}^{(2)}:$
$\displaystyle=\operatorname*{arg\,min}\|\tilde{U}-\widehat{U}\mathcal{O}\|_{F}.$

Define $\mathcal{O}_{*}:=(\mathcal{O}^{(1)}\mathcal{O}^{(2)})^{\top}.$ Letting
$\tilde{\mathcal{O}}=\mathcal{O}^{(1)}$ and
$\mathcal{O}=\mathcal{O}_{*}^{\top}$ implies that this is less than or equal
to

$\displaystyle\|U\|_{2,\infty}\bigg{(}\|\sin\Theta(U,\tilde{U})\|^{2}+\|\sin\Theta(\tilde{U},\widehat{U})\|^{2}\bigg{)}.$

By the Davis-Kahan Theorem, under Assumptions 2 and 4 and under the event in
Lemma 1 by Lemma 2 and 1 we have that for some constant $C$,

$\displaystyle\|U\|_{2,\infty}\bigg{(}\|\sin\Theta(U,\tilde{U})\|^{2}+\|\sin\Theta(\tilde{U},\widehat{U})\|^{2}\bigg{)}$
$\displaystyle\leq
C\|U\|_{2,\infty}\bigg{(}\frac{\|\Gamma(Z)\|^{2}}{\lambda_{r}^{4}}+\|U\|_{2,\infty}^{4}\frac{\|\Gamma(Z)\|^{2}}{\lambda_{r}^{4}}\bigg{)}$
$\displaystyle\leq C\|U\|_{2,\infty}\frac{\|\Gamma(Z)\|^{2}}{\lambda_{r}^{4}}$

since $\|\Gamma(Z)\|/\lambda_{r}^{2}\leq C$ under these assumptions and the
event in Lemma 1. ∎

######  Lemma 14.

If $M$ has rank $r$, and $\widehat{U}$ is the projector onto the top $r$ left
singular vectors of $M+E$, and if $\lambda_{r}\geq 2\|E\|$, then

$\|(I-P_{\widehat{U}})M\|\leq 2\|E\|.$

###### Proof.

We have that

$\displaystyle\|(I-P_{\tilde{U}})M\|$
$\displaystyle\leq\|(I-P_{\tilde{U}})(M+E)\|+\|(I-P_{\tilde{U}})E\|$
$\displaystyle\leq\lambda_{r+1}(M+E)+\|E\|$ $\displaystyle\leq 2\|E\|$

by Weyl’s inequality. ∎

## References

  * Abbe et al. (2020a) Emmanuel Abbe, Jianqing Fan, and Kaizheng Wang.  An $\ell_p$ theory of PCA and spectral clustering.  _arXiv:2006.14062 [cs, math, stat]_ , June 2020a.  URL http://arxiv.org/abs/2006.14062.  arXiv: 2006.14062.
  * Abbe et al. (2020b) Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong.  Entrywise eigenvector analysis of random matrices with low expected rank.  _The Annals of Statistics_ , 48(3):1452–1474, June 2020b.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/19-AOS1854.  URL https://projecteuclid.org/journals/annals-of-statistics/volume-48/issue-3/Entrywise-eigenvector-analysis-of-random-matrices-with-low-expected-rank/10.1214/19-AOS1854.full.  Publisher: Institute of Mathematical Statistics.
  * Agterberg et al. (2020) Joshua Agterberg, Minh Tang, and Carey Priebe.  Nonparametric Two-Sample Hypothesis Testing for Random Graphs with Negative and Repeated Eigenvalues.  _arXiv:2012.09828 [math, stat]_ , December 2020.  URL http://arxiv.org/abs/2012.09828.  arXiv: 2012.09828.
  * Amini and Razaee (2021) Arash A. Amini and Zahra S. Razaee.  Concentration of kernel matrices with application to kernel spectral clustering.  _The Annals of Statistics_ , 49(1):531–556, February 2021.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/20-AOS1967.  URL https://projecteuclid.org/journals/annals-of-statistics/volume-49/issue-1/Concentration-of-kernel-matrices-with-application-to-kernel-spectral-clustering/10.1214/20-AOS1967.full.  Publisher: Institute of Mathematical Statistics.
  * Athreya et al. (2017) Avanti Athreya, Donniell E. Fishkind, Keith Levin, Vince Lyzinski, Youngser Park, Yichen Qin, Daniel L. Sussman, Minh Tang, Joshua T. Vogelstein, and Carey E. Priebe.  Statistical inference on random dot product graphs: A survey.  _Journal of Machine Learning Research_ , 18, September 2017.
  * Bao et al. (2021) Zhigang Bao, Xiucai Ding, and and Ke Wang.  Singular vector and singular subspace distribution for the matrix denoising model.  _The Annals of Statistics_ , 49(1):370–392, February 2021.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/20-AOS1960.  URL https://projecteuclid.org/journals/annals-of-statistics/volume-49/issue-1/Singular-vector-and-singular-subspace-distribution-for-the-matrix-denoising/10.1214/20-AOS1960.full.  Publisher: Institute of Mathematical Statistics.
  * Berry (1941) Andrew C. Berry.  The Accuracy of the Gaussian Approximation to the Sum of Independent Variates.  _Transactions of the American Mathematical Society_ , 49(1):122–136, 1941.  ISSN 0002-9947.  doi: 10.2307/1990053.  URL https://www.jstor.org/stable/1990053.  Publisher: American Mathematical Society.
  * Bhatia (1997) Rajendra Bhatia.  _Matrix Analysis_ , volume 169.  Springer, 1997.  ISBN 0-387-94846-5.
  * Cai et al. (2020) Changxiao Cai, Gen Li, Yuejie Chi, H. Vincent Poor, and Yuxin Chen.  Subspace Estimation from Unbalanced and Incomplete Data Matrices: $\ell_{2,\infty}$ Statistical Guarantees.  _Annals of Statistics, to appear_ , November 2020.  URL http://arxiv.org/abs/1910.04267.  arXiv: 1910.04267.
  * Cai and Zhang (2018) T. Tony Cai and Anru Zhang.  Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics.  _The Annals of Statistics_ , 46(1):60–89, February 2018.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/17-AOS1541.  URL https://projecteuclid.org/euclid.aos/1519268424.
  * Cai et al. (2021) Tony Cai, Hongzhe Li, and Rong Ma.  Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates.  _Journal of Machine Learning Research_ , 22(46):1–45, 2021.
  * Cape (2020) Joshua Cape.  Orthogonal Procrustes and norm-dependent optimality.  _The Electronic Journal of Linear Algebra_ , 36(36):158–168, March 2020.  ISSN 1081-3810.  doi: 10.13001/ela.2020.5009.  URL https://journals.uwyo.edu/index.php/ela/article/view/5009.  Number: 36.
  * Cape et al. (2019a) Joshua Cape, Minh Tang, and Carey E. Priebe.  Signal-plus-noise matrix models: eigenvector deviations and fluctuations.  _Biometrika_ , 106(1):243–250, March 2019a.  ISSN 0006-3444.  doi: 10.1093/biomet/asy070.  URL https://academic.oup.com/biomet/article/106/1/243/5280315.
  * Cape et al. (2019b) Joshua Cape, Minh Tang, and Carey E. Priebe.  The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics.  _Annals of Statistics_ , 47(5):2405–2439, October 2019b.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/18-AOS1752.  URL https://projecteuclid.org/euclid.aos/1564797852.
  * Chen and Yang (2020) Xiaohui Chen and Yun Yang.  Hanson-Wright inequality in Hilbert spaces with application to $K$-means clustering for non-Euclidean data.  _arXiv:1810.11180 [math, stat]_ , July 2020.  URL http://arxiv.org/abs/1810.11180.  arXiv: 1810.11180.
  * Chen et al. (2019) Yuxin Chen, Jianqing Fan, Cong Ma, and Yuling Yan.  Inference and Uncertainty Quantification for Noisy Matrix Completion.  _Proceedings of the National Academy of Sciences_ , 116(46):22931–22937, November 2019.  ISSN 0027-8424, 1091-6490.  doi: 10.1073/pnas.1910053116.  URL http://arxiv.org/abs/1906.04159.  arXiv: 1906.04159.
  * Chen et al. (2020) Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma.  Spectral Methods for Data Science: A Statistical Perspective.  _arXiv:2012.08496 [cs, eess, math, stat]_ , December 2020.  URL http://arxiv.org/abs/2012.08496.  arXiv: 2012.08496.
  * Chen et al. (2021) Yuxin Chen, Chen Cheng, and Jianqing Fan.  Asymmetry helps: Eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices.  _The Annals of Statistics_ , 49(1):435–458, February 2021.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/20-AOS1963.  URL https://projecteuclid.org/journals/annals-of-statistics/volume-49/issue-1/Asymmetry-helps--Eigenvalue-and-eigenvector-analyses-of-asymmetrically-perturbed/10.1214/20-AOS1963.full.  Publisher: Institute of Mathematical Statistics.
  * Cheng et al. (2020) Chen Cheng, Yuting Wei, and Yuxin Chen.  Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise.  _arXiv:2001.04620 [cs, eess, math, stat]_ , April 2020.  URL http://arxiv.org/abs/2001.04620.  arXiv: 2001.04620.
  * Chi et al. (2019) Yuejie Chi, Yue M. Lu, and Yuxin Chen.  Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview.  _IEEE Transactions on Signal Processing_ , 67(20):5239–5269, October 2019.  ISSN 1053-587X, 1941-0476.  doi: 10.1109/TSP.2019.2937282.  URL http://arxiv.org/abs/1809.09573.  arXiv: 1809.09573.
  * Damle and Sun (2019) Anil Damle and Yuekai Sun.  Uniform bounds for invariant subspace perturbations.  _arXiv:1905.07865 [math, stat]_ , May 2019.  URL http://arxiv.org/abs/1905.07865.  arXiv: 1905.07865.
  * Ding (2020) Xiucai Ding.  High dimensional deformed rectangular matrices with applications in matrix denoising.  _Bernoulli_ , 26(1):387–417, February 2020.  ISSN 1350-7265.  doi: 10.3150/19-BEJ1129.  URL https://projecteuclid.org/euclid.bj/1574758832.
  * Ding and Sun (2019) Xiucai Ding and Qiang Sun.  Modified Multidimensional Scaling and High Dimensional Clustering.  _arXiv:1810.10172 [cs, math, stat]_ , January 2019.  URL http://arxiv.org/abs/1810.10172.  arXiv: 1810.10172.
  * Du and Tang (2021) Xinjie Du and Minh Tang.  Hypothesis Testing for Equality of Latent Positions in Random Graphs.  _arXiv:2105.10838 [stat]_ , May 2021.  URL http://arxiv.org/abs/2105.10838.  arXiv: 2105.10838.
  * Eldridge et al. (2018) Justin Eldridge, Mikhail Belkin, and Yusu Wang.  Unperturbed: spectral analysis beyond Davis-Kahan.  In _Algorithmic Learning Theory_ , pages 321–358, April 2018\.  URL http://proceedings.mlr.press/v83/eldridge18a.html.
  * Fan et al. (2018) Jianqing Fan, Weichen Wang, and Yiqiao Zhong.  An $\ell_{\infty}$ Eigenvector Perturbation Bound and Its Application.  _Journal of Machine Learning Research_ , 18(207):1–42, 2018.  ISSN 1533-7928.  URL http://jmlr.org/papers/v18/16-140.html.
  * Fan et al. (2019) Jianqing Fan, Yingying Fan, Xiao Han, and Jinchi Lv.  SIMPLE: Statistical Inference on Membership Profiles in Large Networks.  _arXiv:1910.01734 [math, stat]_ , October 2019.  URL http://arxiv.org/abs/1910.01734.  arXiv: 1910.01734.
  * Fan et al. (2020) Jianqing Fan, Yingying Fan, Xiao Han, and Jinchi Lv.  Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes.  _Journal of the American Statistical Association_ , 0(0):1–14, October 2020.  ISSN 0162-1459.  doi: 10.1080/01621459.2020.1840990.  URL https://doi.org/10.1080/01621459.2020.1840990.  Publisher: Taylor & Francis _eprint: https://doi.org/10.1080/01621459.2020.1840990.
  * Florescu and Perkins (2016) Laura Florescu and Will Perkins.  Spectral thresholds in the bipartite stochastic block model.  In _Conference on Learning Theory_ , pages 943–959. PMLR, June 2016.  URL http://proceedings.mlr.press/v49/florescu16.html.  ISSN: 1938-7228.
  * Han et al. (2020) Xiao Han, Qing Yang, and Yingying Fan.  Universal Rank Inference via Residual Subsampling with Application to Large Networks.  _arXiv:1912.11583 [math, stat]_ , July 2020.  URL http://arxiv.org/abs/1912.11583.  arXiv: 1912.11583.
  * Jin et al. (2019) Jiashun Jin, Zheng Tracy Ke, and Shengming Luo.  Estimating network memberships by simplex vertex hunting.  _arXiv:1708.07852 [stat]_ , September 2019.  URL http://arxiv.org/abs/1708.07852.  arXiv: 1708.07852.
  * Johnstone and Lu (2009) Iain M. Johnstone and Arthur Yu Lu.  On Consistency and Sparsity for Principal Components Analysis in High Dimensions.  _Journal of the American Statistical Association_ , 104(486):682–693, June 2009.  ISSN 0162-1459.  doi: 10.1198/jasa.2009.0121.  URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2898454/.
  * Koltchinskii and Giné (2000) Vladimir Koltchinskii and Evarist Giné.  Random matrix approximation of spectra of integral operators.  _Bernoulli_ , 6(1):113–167, February 2000.  ISSN 1350-7265.  URL https://projecteuclid.org/journals/bernoulli/volume-6/issue-1/Random-matrix-approximation-of-spectra-of-integral-operators/bj/1082665383.full.  Publisher: Bernoulli Society for Mathematical Statistics and Probability.
  * Koltchinskii and Lounici (2016) Vladimir Koltchinskii and Karim Lounici.  Asymptotics and concentration bounds for bilinear forms of spectral projectors of sample covariance.  _Annales de l’Institut Henri Poincaré, Probabilités et Statistiques_ , 52(4):1976–2013, November 2016.  ISSN 0246-0203.  doi: 10.1214/15-AIHP705.  URL https://projecteuclid.org/euclid.aihp/1479373255.  Publisher: Institut Henri Poincaré.
  * Koltchinskii and Lounici (2017) Vladimir Koltchinskii and Karim Lounici.  Normal approximation and concentration of spectral projectors of sample covariance.  _The Annals of Statistics_ , 45(1):121–157, February 2017.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/16-AOS1437.  URL https://projecteuclid.org/euclid.aos/1487667619.  Publisher: Institute of Mathematical Statistics.
  * Koltchinskii and Xia (2016) Vladimir Koltchinskii and Dong Xia.  Perturbation of Linear Forms of Singular Vectors Under Gaussian Noise.  In Christian Houdré, David M. Mason, Patricia Reynaud-Bouret, and Jan Rosiński, editors, _High Dimensional Probability VII_ , Progress in Probability, pages 397–423, Cham, 2016. Springer International Publishing.  ISBN 978-3-319-40519-3.  doi: 10.1007/978-3-319-40519-3_18.
  * Koltchinskii et al. (2020) Vladimir Koltchinskii, Matthias Löffler, and Richard Nickl.  Efficient estimation of linear functionals of principal components.  _Annals of Statistics_ , 48(1):464–490, February 2020.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/19-AOS1816.  URL http://projecteuclid.org/euclid.aos/1581930143.  Publisher: Institute of Mathematical Statistics.
  * Koltchinskii (1998) Vladimir I. Koltchinskii.  Asymptotics of Spectral Projections of Some Random Matrices Approximating Integral Operators.  In Ernst Eberlein, Marjorie Hahn, and Michel Talagrand, editors, _High Dimensional Probability_ , Progress in Probability, pages 191–227, Basel, 1998. Birkhäuser.  ISBN 978-3-0348-8829-5.  doi: 10.1007/978-3-0348-8829-5_11.
  * Leeb and Romanov (2021) William Leeb and Elad Romanov.  Optimal Spectral Shrinkage and PCA With Heteroscedastic Noise.  _IEEE Transactions on Information Theory_ , 67(5):3009–3037, May 2021.  ISSN 1557-9654.  doi: 10.1109/TIT.2021.3055075.  Conference Name: IEEE Transactions on Information Theory.
  * Lei and Lin (2021) Jing Lei and Kevin Z. Lin.  Bias-adjusted spectral clustering in multi-layer stochastic block models.  _arXiv:2003.08222 [math, stat]_ , March 2021.  URL http://arxiv.org/abs/2003.08222.  arXiv: 2003.08222.
  * Lei and Rinaldo (2015) Jing Lei and Alessandro Rinaldo.  Consistency of spectral clustering in stochastic block models.  _Annals of Statistics_ , 43(1):215–237, February 2015.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/14-AOS1274.  URL https://projecteuclid.org/euclid.aos/1418135620.  Publisher: Institute of Mathematical Statistics.
  * Lei (2019) Lihua Lei.  Unified $\ell_{2\rightarrow\infty}$ Eigenspace Perturbation Theory for Symmetric Random Matrices.  _arXiv:1909.04798 [math, stat]_ , September 2019.  URL http://arxiv.org/abs/1909.04798.  arXiv: 1909.04798.
  * Li et al. (2021) Gen Li, Changxiao Cai, Yuantao Gu, H. Vincent Poor, and Yuxin Chen.  Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps.  _arXiv:2104.03298 [cs, math, stat]_ , April 2021.  URL http://arxiv.org/abs/2104.03298.  arXiv: 2104.03298.
  * Li et al. (2020) Gongkai Li, Minh Tang, Nicolas Charon, and Carey Priebe.  Central limit theorems for classical multidimensional scaling.  _Electronic Journal of Statistics_ , 14(1):2362–2394, January 2020.  ISSN 1935-7524, 1935-7524.  doi: 10.1214/20-EJS1720.  URL https://projecteuclid.org/journals/electronic-journal-of-statistics/volume-14/issue-1/Central-limit-theorems-for-classical-multidimensional-scaling/10.1214/20-EJS1720.full.  Publisher: Institute of Mathematical Statistics and Bernoulli Society.
  * Li and Li (2018) Yezheng Li and Hongzhe Li.  Two-sample Test of Community Memberships of Weighted Stochastic Block Models.  _arXiv:1811.12593 [math, stat]_ , November 2018.  URL http://arxiv.org/abs/1811.12593.  arXiv: 1811.12593.
  * Little et al. (2020) Anna Little, Yuying Xie, and Qiang Sun.  Exact Cluster Recovery via Classical Multidimensional Scaling.  _arXiv:1812.11954 [math, stat]_ , July 2020.  URL http://arxiv.org/abs/1812.11954.  arXiv: 1812.11954.
  * Lounici (2013) Karim Lounici.  Sparse Principal Component Analysis with Missing Observations.  In Christian Houdré, David M. Mason, Jan Rosiński, and Jon A. Wellner, editors, _High Dimensional Probability VI_ , Progress in Probability, pages 327–356, Basel, 2013. Springer.  ISBN 978-3-0348-0490-5.  doi: 10.1007/978-3-0348-0490-5_20.
  * Lounici (2014) Karim Lounici.  High-dimensional covariance matrix estimation with missing observations.  _Bernoulli_ , 20(3):1029–1058, August 2014.  ISSN 1350-7265.  doi: 10.3150/12-BEJ487.  URL https://projecteuclid.org/euclid.bj/1402488933.  Publisher: Bernoulli Society for Mathematical Statistics and Probability.
  * Lu and Li (2017) Yue M. Lu and Gen Li.  Spectral initialization for nonconvex estimation: High-dimensional limit and phase transitions.  In _2017 IEEE International Symposium on Information Theory (ISIT)_ , pages 3015–3019, June 2017.  doi: 10.1109/ISIT.2017.8007083.  ISSN: 2157-8117.
  * Luo and Zhang (2020) Yuetian Luo and Anru R. Zhang.  A Schatten-$q$ Matrix Perturbation Theory via Perturbation Projection Error Bound.  _arXiv:2008.01312 [cs, math, stat]_ , August 2020.  URL http://arxiv.org/abs/2008.01312.  arXiv: 2008.01312.
  * Löffler et al. (2020) Matthias Löffler, Anderson Y. Zhang, and Harrison H. Zhou.  Optimality of Spectral Clustering in the Gaussian Mixture Model.  _Annals of Statistics, to appear_ , August 2020.  URL http://arxiv.org/abs/1911.00538.  arXiv: 1911.00538.
  * Ma et al. (2020) Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen.  Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution.  _Foundations of Computational Mathematics_ , 20(3):451–632, June 2020.  ISSN 1615-3383.  doi: 10.1007/s10208-019-09429-9.  URL https://doi.org/10.1007/s10208-019-09429-9.
  * Mao et al. (2020) Xueyu Mao, Purnamrita Sarkar, and Deepayan Chakrabarti.  Estimating Mixed Memberships With Sharp Eigenvector Deviations.  _Journal of the American Statistical Association_ , 0(0):1–13, April 2020.  ISSN 0162-1459.  doi: 10.1080/01621459.2020.1751645.  URL https://doi.org/10.1080/01621459.2020.1751645.  Publisher: Taylor & Francis _eprint: https://doi.org/10.1080/01621459.2020.1751645.
  * O’Rourke et al. (2018) Sean O’Rourke, Van Vu, and Ke Wang.  Random perturbation of low rank matrices: Improving classical bounds.  _Linear Algebra and its Applications_ , 540:26–59, March 2018.  ISSN 0024-3795.  doi: 10.1016/j.laa.2017.11.014.  URL http://www.sciencedirect.com/science/article/pii/S0024379517306420.
  * Rohe and Zeng (2020) Karl Rohe and Muzhe Zeng.  Vintage Factor Analysis with Varimax Performs Statistical Inference.  _arXiv:2004.05387 [math, stat]_ , April 2020.  URL http://arxiv.org/abs/2004.05387.  arXiv: 2004.05387.
  * Rubin-Delanchy et al. (2020) Patrick Rubin-Delanchy, Joshua Cape, Minh Tang, and Carey E. Priebe.  A statistical interpretation of spectral embedding: the generalised random dot product graph.  _arXiv:1709.05506 [cs, stat]_ , January 2020.  URL http://arxiv.org/abs/1709.05506.  arXiv: 1709.05506.
  * Schiebinger et al. (2015) Geoffrey Schiebinger, Martin J. Wainwright, and Bin Yu.  The geometry of kernelized spectral clustering.  _The Annals of Statistics_ , 43(2):819–846, April 2015.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/14-AOS1283.  URL https://projecteuclid.org/journals/annals-of-statistics/volume-43/issue-2/The-geometry-of-kernelized-spectral-clustering/10.1214/14-AOS1283.full.  Publisher: Institute of Mathematical Statistics.
  * Srivastava et al. (2021) Prateek R. Srivastava, Purnamrita Sarkar, and Grani A. Hanasusanto.  A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers.  _arXiv:1912.07546 [cs, math, stat]_ , January 2021.  URL http://arxiv.org/abs/1912.07546.  arXiv: 1912.07546.
  * Vempala and Wang (2004) Santosh Vempala and Grant Wang.  A spectral algorithm for learning mixture models.  _Journal of Computer and System Sciences_ , 68(4):841–860, June 2004.  ISSN 0022-0000.  doi: 10.1016/j.jcss.2003.11.008.  URL https://www.sciencedirect.com/science/article/pii/S0022000003001806.
  * Vershynin (2018) Roman Vershynin.  _High-Dimensional Probability: An Introduction with Applications in Data Science_.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.  doi: 10.1017/9781108231596.
  * Vershynin (2020) Roman Vershynin.  Concentration inequalities for random tensors.  _arXiv:1905.00802 [math]_ , June 2020.  URL http://arxiv.org/abs/1905.00802.  arXiv: 1905.00802.
  * von Luxburg (2007) Ulrike von Luxburg.  A tutorial on spectral clustering.  _Statistics and Computing_ , 17(4):395–416, December 2007.  ISSN 1573-1375.  doi: 10.1007/s11222-007-9033-z.  URL https://doi.org/10.1007/s11222-007-9033-z.
  * Wang and Fan (2017) Weichen Wang and Jianqing Fan.  Asymptotics of empirical eigenstructure for high dimensional spiked covariance.  _The Annals of Statistics_ , 45(3):1342–1374, June 2017.  ISSN 0090-5364, 2168-8966.  doi: 10.1214/16-AOS1487.  URL https://projecteuclid.org/euclid.aos/1497319697.
  * Xia (2019a) Dong Xia.  Confidence Region of Singular Subspaces for Low-Rank Matrix Regression.  _IEEE Transactions on Information Theory_ , 65(11):7437–7459, November 2019a.  ISSN 1557-9654.  doi: 10.1109/TIT.2019.2924900.  Conference Name: IEEE Transactions on Information Theory.
  * Xia (2019b) Dong Xia.  Normal Approximation and Confidence Region of Singular Subspaces.  _arXiv:1901.00304 [cs, math, stat]_ , July 2019b.  URL http://arxiv.org/abs/1901.00304.  arXiv: 1901.00304.
  * Xia and Yuan (2020) Dong Xia and Ming Yuan.  Statistical inferences of linear forms for noisy matrix completion.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , n/a(n/a), November 2020.  ISSN 1467-9868.  doi: https://doi.org/10.1111/rssb.12400.  URL https://rss.onlinelibrary.wiley.com/doi/abs/10.1111/rssb.12400.  _eprint: https://rss.onlinelibrary.wiley.com/doi/pdf/10.1111/rssb.12400.
  * Xie (2021) Fangzheng Xie.  Euclidean Representation of Low-Rank Matrices and Its Statistical Applications.  _arXiv:2103.04220 [math, stat]_ , March 2021.  URL http://arxiv.org/abs/2103.04220.  arXiv: 2103.04220.
  * Xie and Xu (2020) Fangzheng Xie and Yanxun Xu.  Efficient Estimation for Random Dot Product Graphs via a One-step Procedure.  _arXiv:1910.04333 [math, stat]_ , November 2020.  URL http://arxiv.org/abs/1910.04333.  arXiv: 1910.04333.
  * Xie et al. (2019) Fangzheng Xie, Yanxun Xu, Carey E. Priebe, and Joshua Cape.  Bayesian Estimation of Sparse Spiked Covariance Matrices in High Dimensions.  _arXiv:1808.07433 [math, stat]_ , January 2019.  URL http://arxiv.org/abs/1808.07433.  arXiv: 1808.07433.
  * Yang et al. (2020) Congyuan Yang, Carey E. Priebe, Youngser Park, and David J. Marchette.  Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering.  _Journal of Computational and Graphical Statistics_ , 0(0):1–20, September 2020.  ISSN 1061-8600.  doi: 10.1080/10618600.2020.1824870.  URL https://doi.org/10.1080/10618600.2020.1824870.  Publisher: Taylor & Francis _eprint: https://doi.org/10.1080/10618600.2020.1824870.
  * Yu et al. (2014) Yi Yu, Tengyao Wang, and Richard Samworth.  A useful variant of the Davis–Kahan theorem for statisticians.  _Biometrika_ , 102, April 2014.  doi: 10.1093/biomet/asv008.
  * Zhang et al. (2021) Anru R. Zhang, T. Tony Cai, and Yihong Wu.  Heteroskedastic PCA: Algorithm, Optimality, and Applications.  _Annals of Statistics, to appear_ , April 2021.  URL http://arxiv.org/abs/1810.08316.  arXiv: 1810.08316.
  * Zhang et al. (2020) Yuan Zhang, Elizaveta Levina, and Ji Zhu.  Detecting Overlapping Communities in Networks Using Spectral Methods.  _SIAM Journal on Mathematics of Data Science_ , 2(2):265–283, January 2020.  doi: 10.1137/19M1272238.  URL https://epubs.siam.org/doi/abs/10.1137/19M1272238.  Publisher: Society for Industrial and Applied Mathematics.
  * Zhong and Boumal (2018) Yiqiao Zhong and Nicolas Boumal.  Near-optimal bounds for phase synchronization.  _SIAM Journal on Optimization_ , 28(2):989–1016, January 2018.  ISSN 1052-6234, 1095-7189.  doi: 10.1137/17M1122025.  URL http://arxiv.org/abs/1703.06605.  arXiv: 1703.06605.
  * Zhu and Ghodsi (2006) Mu Zhu and Ali Ghodsi.  Automatic dimensionality selection from the scree plot via the use of profile likelihood.  _Computational Statistics & Data Analysis_, 51(2):918–930, November 2006.  ISSN 0167-9473.  doi: 10.1016/j.csda.2005.09.010.  URL https://www.sciencedirect.com/science/article/pii/S0167947305002343.
  * Zhu et al. (2019) Ziwei Zhu, Tengyao Wang, and Richard J. Samworth.  High-dimensional principal component analysis with heterogeneous missingness.  _arXiv:1906.12125 [math, stat]_ , June 2019.  URL http://arxiv.org/abs/1906.12125.  arXiv: 1906.12125.