$\displaystyle\frac{1}{p}\,\Big{\|}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{s\in[r]}\bm{v}_{s}\otimes\bm{\Delta}_{s}^{\otimes
2}\Big{)}\Big{\|}_{\mathrm{F}}^{2}$
$\displaystyle=\frac{1}{p}\sum_{i\in[d],\underline{j}\in[d]^{2}}\chi_{ij_{1}j_{2}}\big{\langle}\bm{V}_{i,:},\widetilde{\bm{\Delta}}_{\underline{j},:}\big{\rangle}^{2}$
$\displaystyle\leq\frac{1}{p}\sum_{i\in\left[d\right]}\big{\|}\bm{V}_{i,:}\big{\|}_{2}^{2}\sum_{\underline{j}\in\mathcal{S}_{i}}\big{\|}\widetilde{\bm{\Delta}}_{\underline{j},:}\big{\|}_{2}^{2}$
$\displaystyle\leq\frac{1}{p}\max_{i\in[d]}\left|\mathcal{S}_{i}\right|\big{\|}\widetilde{\bm{\Delta}}\big{\|}_{2,\infty}^{2}\left\|\bm{V}\right\|_{\mathrm{F}}^{2}$
$\displaystyle\overset{\text{(i)}}{\lesssim}d^{2}\delta^{4}\left\|\bm{U}^{\star}\right\|_{2,\infty}^{4}\left\|\bm{V}\right\|_{\mathrm{F}}^{2}\lesssim\delta^{4}\mu^{2}r^{2}\lambda_{\max}^{\star
4/3}\left\|\bm{V}\right\|_{\mathrm{F}}^{2},$

where (i) arises from (97) and (98). In a similar manner, we can derive

$\displaystyle\frac{1}{p}\,\Big{\|}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{s\in[r]}\bm{u}_{s}^{\star}\otimes\bm{v}_{s}\otimes\bm{\Delta}_{s}\Big{)}\Big{\|}_{\mathrm{F}}^{2}$
$\displaystyle\lesssim\frac{1}{p}\max_{1\leq i\leq
d}\left|\mathcal{S}_{i}\right|\max_{1\leq s\leq
r}\left\|\bm{u}_{s}^{\star}\right\|_{\infty}^{2}\left\|\bm{\Delta}\right\|_{2,\infty}^{2}\left\|\bm{V}\right\|_{\mathrm{F}}^{2}$
$\displaystyle\lesssim d^{2}\delta^{2}\max_{1\leq i\leq
r}\left\|\bm{u}_{s}^{\star}\right\|_{\infty}^{2}\left\|\bm{U}^{\star}\right\|_{2,\infty}^{2}\left\|\bm{V}\right\|_{\mathrm{F}}^{2}$
$\displaystyle\lesssim\delta^{2}\mu^{2}r\lambda_{\max}^{\star
4/3}\left\|\bm{V}\right\|_{\mathrm{F}}^{2}.$

Regarding
$p^{-1}\big{\|}\mathcal{P}_{\Omega}\big{(}\sum\nolimits_{s\in[r]}\bm{v}_{s}\otimes\bm{u}_{s}^{\star\otimes
2}\big{)}\big{\|}_{\mathrm{F}}^{2}$, we apply [YZ16, Lemma 5] (with slight
modification, which we omit here for brevity) to show that: with probability
exceeding $1-O(d^{-}{10})$

$\displaystyle\frac{1}{\sqrt{p}}\,\Big{\|}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{s\in[r]}\bm{v}_{s}\otimes\bm{u}_{s}^{\star\otimes
2}\Big{)}\Big{\|}_{\mathrm{F}}\leq\frac{3}{2}\,\Big{\|}\sum\nolimits_{s\in[r]}\bm{v}_{s}\otimes\bm{u}_{s}^{\star\otimes
2}\Big{\|}_{\mathrm{F}}=\frac{3}{2}\big{\|}\bm{V}\widetilde{\bm{U}}^{\star\top}\big{\|}_{\mathrm{F}}\leq\frac{3}{2}\,\big{\|}\widetilde{\bm{U}}^{\star}\big{\|}\left\|\bm{V}\right\|_{\mathrm{F}}\lesssim\,\lambda_{\max}^{\star
2/3}\left\|\bm{V}\right\|_{\mathrm{F}}.$

under the sample size assumptin that $p\gg\mu^{2}r^{2}d^{-2}\log d$. Here the
last inequality makes use of (90). It is self-evident that the above bounds
also hold for quantities that appear in (95). Since $0<\delta\ll
1/\sqrt{r}<1$, we obtain

$\displaystyle|\beta_{1}|\lesssim\delta\mu\sqrt{r}\lambda_{\max}^{\star
4/3}\left\|\bm{V}\right\|_{\mathrm{F}}^{2}.$

The same upper bound holds for any other $\beta_{2}$. Therefore, as long as
$0<\delta\ll 1/(\mu\sqrt{r})$ and $\kappa\asymp 1$, we have

$\displaystyle|\alpha_{1}|\leq\frac{1}{10}\lambda^{\star
4/3}_{\min}\left\|\bm{V}\right\|_{\mathrm{F}}^{2}.$ (99)

####  A.1.3 Bounding $\alpha_{2}$

Regarding $\alpha_{2}$, applying [YZ16, Lemma 5] (with slight modification,
which we omit here for brevity) implies that: if $p\gg\mu^{2}r^{2}d^{-2}\log
d$, then with probability exceeding $1-O(d^{-10})$,

$\displaystyle\Bigg{|}\frac{1}{2p}$
$\displaystyle\,\Big{\|}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{s\in[r]}(\bm{v}_{s}\otimes\bm{u}_{s}^{\star\otimes
2}+\bm{u}_{s}^{\star}\otimes\bm{v}_{s}\otimes\bm{u}_{s}^{\star}+\bm{u}_{s}^{\star\otimes
2}\otimes\bm{v}_{s})\Big{)}\Big{\|}_{\mathrm{F}}^{2}$
$\displaystyle-\frac{1}{2}\,\Big{\|}\sum\nolimits_{s\in[r]}(\bm{v}_{s}\otimes\bm{u}_{s}^{\star\otimes
2}+\bm{u}_{s}^{\star}\otimes\bm{v}_{s}\otimes\bm{u}_{s}^{\star}+\bm{u}_{s}^{\star\otimes
2}\otimes\bm{v}_{s})\Big{\|}_{\mathrm{F}}^{2}\Bigg{|}$
$\displaystyle\qquad\leq\frac{1}{100}\,\Big{\|}\sum\nolimits_{s\in[r]}(\bm{v}_{s}\otimes\bm{u}_{s}^{\star\otimes
2}+\bm{u}_{s}^{\star}\otimes\bm{v}_{s}\otimes\bm{u}_{s}^{\star}+\bm{u}_{s}^{\star\otimes
2}\otimes\bm{v}_{s})\Big{\|}_{\mathrm{F}}^{2}=\frac{1}{100}\alpha_{4}\leq\frac{1}{10}\lambda_{\min}^{\star
4/3}\left\|\bm{V}\right\|_{\mathrm{F}}^{2}.$

Here the last inequality arises from (92).

####  A.1.4 Bounding $\alpha_{3}$

We now move on to bounding $\alpha_{3}$. The triangle inequality gives

$\displaystyle\Big{|}\Big{\langle}p^{-1}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{s\in[r]}\bm{u}_{s}^{\otimes
3}-\bm{T}^{\star}\Big{)},\sum\nolimits_{s\in[r]}\bm{v}_{s}^{\otimes
2}\otimes\bm{u}_{s}\Big{\rangle}\Big{|}$
$\displaystyle\leq\sum_{s\in[r]}\Big{|}\Big{\langle}p^{-1}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{i\in[r]}\bm{u}_{i}^{\otimes
3}-\bm{T}^{\star}\Big{)}\times_{3}\bm{u}_{s},\bm{v}_{s}\bm{v}_{s}^{\top}\Big{\rangle}\Big{|}$
$\displaystyle\leq\max_{s\in\left[r\right]}\Big{\|}p^{-1}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{i\in[r]}\bm{u}_{i}^{\otimes
3}-\bm{T}^{\star}\Big{)}\times_{3}\bm{u}_{s}\Big{\|}\sum_{s\in[r]}\left\|\bm{v}_{s}\right\|_{2}^{2}$
$\displaystyle\leq\max_{s\in\left[r\right]}\Big{\|}p^{-1}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{i\in[r]}\bm{u}_{i}^{\otimes
3}-\bm{T}^{\star}\Big{)}\times_{3}\bm{u}_{s}\Big{\|}\left\|\bm{V}\right\|_{\mathrm{F}}^{2}.$

Recall the definitions of $\bm{\Delta}$ and $\bm{\Delta}_{i}$ in (94). Fix an
arbitrary $s\in\left[r\right]$. From the definition of the operator norm and
the triangle inequality, we can derive

$\displaystyle\Big{\|}\,p^{-1}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{i\in[r]}\bm{u}_{i}^{\otimes
3}-\bm{T}^{\star}\Big{)}\times_{3}\bm{u}_{s}\Big{\|}\leq\left\|\bm{u}_{s}\right\|_{2}\Big{\|}\,p^{-1}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{i\in[r]}\bm{u}_{i}^{\otimes
3}-\bm{T}^{\star}\Big{)}\Big{\|}.$ (100)

In order to upper bound
$\big{\|}p^{-1}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{i\in[r]}\bm{u}_{i}^{\otimes
3}-\bm{T}^{\star}\Big{)}\big{\|}$ as required in (100), we invoke the
following simple fact, which follows immediately from the definition of the
operator norm. Here and throughout, for any tensor
$\bm{A}\in\mathbb{R}^{d\times d\times d}$ we denote

$|\bm{A}|:=\big{[}|A_{i,j,k}|\big{]}_{1\leq i,j,k\leq d}\in\mathbb{R}^{d\times
d\times d}.$

######  Lemma A.1.

Consider any tensor $\bm{A},\bm{B}\in\mathbb{R}^{d\times d\times d}$ obeying
$|B_{i,j,k}|\geq|A_{i,j,k}|$ for all $1\leq i,j,k\leq d$. One has

$\displaystyle\left\|\bm{A}\right\|\leq\big{\|}|\bm{A}|\big{\|}\leq\big{\|}|\bm{B}|\big{\|}.$
(101)

With this lemma in mind, we are ready to derive that

$\displaystyle\Big{\|}p^{-1}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{i\in[r]}\bm{u}_{i}^{\otimes
3}-\bm{T}^{\star}\Big{)}\Big{\|}$
$\displaystyle\leq\Big{\|}p^{-1}\mathcal{P}_{\Omega}\Big{(}\Big{|}\sum\nolimits_{i\in[r]}\bm{u}_{i}^{\otimes
3}-\bm{T}^{\star}\Big{|}\Big{)}\Big{\|}$
$\displaystyle\leq\Big{\|}\sum\nolimits_{i\in[r]}\bm{u}_{i}^{\otimes
3}-\bm{T}^{\star}\Big{\|}_{\infty}\left\|p^{-1}\mathcal{P}_{\Omega}\big{(}\bm{1}^{\otimes
3}\big{)}\right\|.$

Here, $\bm{1}$ stands for the all-one vector in $\mathbb{R}^{d}$. This
suggests that we shall upper bound
$\left\|p^{-1}\mathcal{P}_{\Omega}\big{(}\bm{1}^{\otimes 3}\big{)}\right\|$
and $\big{\|}\sum\nolimits_{i\in[r]}\bm{u}_{i}^{\otimes
3}-\bm{T}^{\star}\big{\|}_{\infty}$.

Given that $p\gtrsim d^{-3/2}\log^{3}d$, applying Lemma D.2 indicates that
with probability at least $1-O(d^{-10})$,

$\displaystyle\left\|p^{-1}\mathcal{P}_{\Omega}\big{(}\bm{1}^{\otimes
3}\big{)}-\bm{1}^{\otimes
3}\right\|\lesssim\frac{\log^{3}d}{p}+\sqrt{\frac{d\log^{5}d}{p}}\lesssim
d^{3/2}.$ (102)

Moreover, it is straightforward to see that $\left\|\bm{1}^{\otimes
3}\right\|=\left\|\bm{1}\right\|_{2}^{3}=d^{3/2}$. Therefore, one has

$\displaystyle\left\|p^{-1}\mathcal{P}_{\Omega}\big{(}\bm{1}^{\otimes
3}\big{)}\right\|\lesssim d^{3/2}.$ (103)

Next, we turn to $\left\|\cdot\right\|_{\infty}$. We first expand

$\displaystyle\begin{split}\sum_{i\in[r]}\bm{u}^{\otimes
3}_{i}-\bm{T}^{\star}&=\sum_{i\in[r]}\big{(}(\bm{\Delta}_{i}+\bm{u}^{\star}_{i})^{\otimes
3}-\bm{u}_{i}^{\star\otimes
3}\big{)}=\sum_{i\in[r]}\bm{\Delta}_{i}\otimes\bm{u}^{\star\otimes
2}_{i}+\sum_{i\in[r]}\bm{u}^{\star}_{i}\otimes\bm{\Delta}_{i}\otimes\bm{u}^{\star}_{i}+\sum_{i\in[r]}\bm{u}^{\star\otimes
2}_{i}\otimes\bm{\Delta}_{i}\\\ &\quad+\sum_{i\in[r]}\bm{\Delta}_{i}^{\otimes
2}\otimes\bm{u}^{\star}_{i}+\sum_{i\in[r]}\bm{\Delta}_{i}\otimes\bm{u}^{\star}_{i}\otimes\bm{\Delta}_{i}+\sum_{i\in[r]}\bm{u}^{\star}_{i}\otimes\bm{\Delta}_{i}^{\otimes
2}+\sum_{i\in[r]}\bm{\Delta}_{i}^{\otimes 3}.\end{split}$

By symmetry, it suffices to control
$\big{\|}\sum_{i\in[r]}\bm{u}^{\star\otimes
2}_{i}\otimes\bm{\Delta}_{i}\big{\|}$,
$\big{\|}\sum_{i\in[r]}\bm{\Delta}_{i}^{\otimes
2}\otimes\bm{u}^{\star}_{i}\big{\|}$ and
$\big{\|}\sum_{i\in[r]}\bm{\Delta}_{i}^{\otimes 3}\big{\|}$. Let us look at
the first term. Towards this, for each
$\left(i,j,k\right)\in\left[d\right]^{3}$, we can use the Cauchy-Schwartz
inequality to control

$\displaystyle\Big{|}\Big{(}\sum\nolimits_{1\leq s\leq
r}\bm{u}_{s}^{\star\otimes 2}\otimes\bm{\Delta}_{s}\Big{)}_{i,j,k}\Big{|}$
$\displaystyle=\Big{|}\sum\nolimits_{1\leq s\leq
r}\left(\bm{u}_{s}^{\star}\right)_{i}\left(\bm{u}_{s}^{\star}\right)_{j}\left(\bm{\Delta}_{s}\right)_{k}\Big{|}$
$\displaystyle\leq\Big{(}\sum\nolimits_{1\leq s\leq
r}\big{[}\left(\bm{u}_{s}^{\star}\right)_{i}\big{]}^{2}\Big{)}^{1/2}\Big{(}\sum\nolimits_{1\leq
s\leq
r}\big{[}\left(\bm{u}_{s}^{\star}\right)_{j}\big{]}^{2}\big{[}\left(\bm{\Delta}_{s}\right)_{k}\big{]}^{2}\Big{)}^{1/2}$
$\displaystyle\leq\left\|\bm{U}^{\star}\right\|_{2,\infty}\left\|\bm{\Delta}\right\|_{2,\infty}\max_{1\leq
s\leq r}\left\|\bm{u}_{s}^{\star}\right\|_{\infty}$
$\displaystyle\leq\delta\left\|\bm{U}^{\star}\right\|_{2,\infty}^{2}\max_{1\leq
s\leq r}\left\|\bm{u}_{s}^{\star}\right\|_{\infty},$

which implies that

$\displaystyle\Big{\|}\sum\nolimits_{1\leq s\leq r}\bm{u}_{s}^{\star\otimes
2}\otimes\bm{\Delta}_{s}\Big{\|}_{\infty}\leq\delta\left\|\bm{U}^{\star}\right\|_{2,\infty}^{2}\max_{1\leq
s\leq
r}\left\|\bm{u}_{s}^{\star}\right\|_{\infty}\lesssim\frac{\delta\mu^{3/2}r\lambda_{\max}^{\star}}{d^{3/2}}.$
(104)

In a similar manner, we can control the remaining two terms by

$\displaystyle\Big{\|}\sum\nolimits_{i\in[r]}\bm{\Delta}_{i}^{\otimes
2}\otimes\bm{u}^{\star}_{i}\Big{\|}$
$\displaystyle\leq\left\|\bm{\Delta}\right\|_{2,\infty}^{2}\max_{1\leq s\leq
r}\left\|\bm{u}_{s}^{\star}\right\|_{\infty}\leq\delta^{2}\left\|\bm{U}^{\star}\right\|_{2,\infty}^{2}\max_{1\leq
s\leq
r}\left\|\bm{u}_{s}^{\star}\right\|_{\infty}\leq\frac{\delta^{2}\mu^{3/2}r\lambda_{\max}^{\star}}{d^{3/2}};$
(105) $\displaystyle\Big{\|}\sum\nolimits_{i\in[r]}\bm{\Delta}_{i}^{\otimes
3}\Big{\|}$
$\displaystyle\leq\left\|\bm{\Delta}\right\|_{2,\infty}^{2}\max_{1\leq s\leq
r}\left\|\bm{\Delta}_{s}\right\|_{\infty}\leq\delta^{3}\left\|\bm{U}^{\star}\right\|_{2,\infty}^{3}\leq\frac{\delta^{3}\mu^{3/2}r^{3/2}\lambda_{\max}^{\star}}{d^{3/2}}.$
(106)

Recall that $0<\delta\ll 1/r\leq 1$. Putting these together reveals that

$\displaystyle\Big{\|}\sum\nolimits_{i\in[r]}\bm{u}^{\otimes
3}_{i}-\bm{T}^{\star}\Big{\|}\lesssim\frac{\delta\mu^{3/2}r\lambda_{\max}^{\star}}{d^{3/2}}.$
(107)

This combined with (103) yields

$\displaystyle\Big{\|}\,p^{-1}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{i\in[r]}\bm{u}^{\otimes
3}_{i}-\bm{T}^{\star}\Big{)}\Big{\|}\lesssim\delta\mu^{3/2}r\lambda_{\max}^{\star},$

thus indicating that

$\displaystyle\Big{\|}\,p^{-1}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{i\in[r]}\bm{u}_{i}^{\otimes
3}-\bm{T}^{\star}\Big{)}\times_{3}\bm{u}_{s}\Big{\|}\leq\left\|\bm{u}_{s}\right\|_{2}\Big{\|}p^{-1}\mathcal{P}_{\Omega}\Big{(}\sum\nolimits_{i\in[r]}\bm{u}^{\otimes
3}_{i}-\bm{T}^{\star}\Big{)}\Big{\|}\lesssim\delta\mu^{3/2}r\lambda_{\max}^{\star
4/3},$ (108)

where we use (96c) in the last step. In view of the condition that $\delta\ll
1/(\mu^{3/2}r)$ and the assumption $\kappa\asymp 1$, one has with probability
greater than $1-O(d^{-10})$,

$\displaystyle|\alpha_{3}|\leq\frac{1}{10}\lambda_{\min}^{\star
4/3}\left\|\bm{V}\right\|_{\mathrm{F}}^{2}.$ (109)

####  A.1.5 Putting all this together

Note that the above bounds hold uniformly for all $\bm{V}$. Therefore,
combining upper bounds for $\alpha_{i}$ and the union bound, we conclude that
with probability exceeding $1-O(d^{-10})$,

$\displaystyle\mathsf{vec}(\bm{V})^{\top}\nabla^{2}f(\bm{U})\mathsf{vec}(\bm{V})$
$\displaystyle\geq\alpha_{4}-|\alpha_{1}|-|\alpha_{2}|-|\alpha_{3}|\geq\frac{1}{2}\lambda_{\min}^{\star
4/3}\left\|\bm{V}\right\|_{\mathrm{F}}^{2}$ (110)
$\displaystyle\mathsf{vec}(\bm{V})^{\top}\nabla^{2}f(\bm{U})\mathsf{vec}(\bm{V})$
$\displaystyle\leq\alpha_{4}+|\alpha_{1}|+|\alpha_{2}|+|\alpha_{3}|\leq
4\lambda_{\max}^{\star 4/3}\left\|\bm{V}\right\|_{\mathrm{F}}^{2}$ (111)

as claimed.

###  A.2 Proof of Lemma 5.2

From (47a) and (47c), we use the triangle inequality to obtain

$\displaystyle\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}$
$\displaystyle\leq\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{t}\big{\|}_{\mathrm{F}}+\big{\|}\bm{U}^{t}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}$
$\displaystyle\leq\left(2C_{1}\rho^{t}\mathcal{E}_{\mathsf{local}}+2C_{2}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}$

Similarly, we can combine (47b) and (47c) to obtain that

$\displaystyle\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{2,\infty}$
$\displaystyle\leq\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{t}\big{\|}_{2,\infty}+\left\|\bm{U}^{t}-\bm{U}^{\star}\right\|_{\mathrm{F}}\leq\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{t}\big{\|}_{\mathrm{F}}+\left\|\bm{U}^{t}-\bm{U}^{\star}\right\|_{\mathrm{F}}$
$\displaystyle\leq\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}+\left(C_{3}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{4}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\leq\left(\left(C_{3}+C_{5}\right)\rho^{t}\mathcal{E}_{\mathsf{local}}+\left(C_{4}+C_{6}\right)\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}.$

###  A.3 Proof of Lemma 5.3

In view of the relation (40), one has

$\displaystyle\left\|\bm{U}^{t+1}-\bm{U}^{\star}\right\|_{\mathrm{F}}$
$\displaystyle=\left\|\bm{U}^{t}-\eta\left(\nabla
f_{\mathsf{clean}}\left(\bm{U}^{t}\right)-p^{-1}\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}^{\mathsf{seq}}\bm{U}^{t}\times_{2}^{\mathsf{seq}}\bm{U}^{t}\right)-\bm{U}^{\star}\right\|_{\mathrm{F}}$
$\displaystyle\leq\underbrace{\left\|\bm{U}^{t}-\eta\nabla
f_{\mathsf{clean}}\left(\bm{U}^{t}\right)-\bm{U}^{\star}\right\|_{\mathrm{F}}}_{=:\,\alpha_{1}}+\underbrace{\eta\left\|p^{-1}\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}^{\mathsf{seq}}\bm{U}^{t}\times_{2}^{\mathsf{seq}}\bm{U}^{t}\right\|_{\mathrm{F}}}_{=:\,\alpha_{2}},$

which motivates us to bound $\alpha_{1}$ and $\alpha_{2}$ separately.

(1) We start with $\alpha_{1}$, towards which we find it helpful to define

$\displaystyle\bm{U}^{t}(\tau):=\tau\,\bm{U}^{t}+\left(1-\tau\right)\bm{U}^{\star}.$
(112)

Given that $\nabla f_{\mathsf{clean}}\left(\bm{U}^{\star}\right)=\bm{0}$
(since $\bm{U}^{\star}$ is a global optimizer of $f_{\mathsf{clean}}$), we can
use the fundamental theorem of calculus to obtain

$\displaystyle\mathsf{vec}\left(\bm{U}^{t}-\eta\nabla
f_{\mathsf{clean}}\left(\bm{U}^{t}\right)-\bm{U}^{\star}\right)$
$\displaystyle=\mathsf{vec}\left(\bm{U}^{t}-\eta\nabla
f_{\mathsf{clean}}\left(\bm{U}^{t}\right)-\left(\bm{U}^{\star}-\eta\nabla
f_{\mathsf{clean}}\left(\bm{U}^{\star}\right)\right)\right)$ (113)
$\displaystyle=\mathsf{vec}\left(\bm{U}^{t}-\bm{U}^{\star}\right)-\eta\,\mathsf{vec}\left(\nabla
f_{\mathsf{clean}}\left(\bm{U}^{t}\right)-\nabla
f_{\mathsf{clean}}\left(\bm{U}^{\star}\right)\right)$ (114)
$\displaystyle=\Bigg{(}\bm{I}_{dr}-\eta\underset{=:\,\bm{\Gamma}}{\underbrace{\int_{0}^{1}\nabla^{2}f_{\mathsf{clean}}\left(\bm{U}^{t}\left(\tau\right)\right)\,\mathrm{d}\tau}}\Bigg{)}\,\mathsf{vec}\left(\bm{U}^{t}-\bm{U}^{\star}\right).$
(115)

It then follows that

$\displaystyle\left\|\bm{U}^{t}-\eta\nabla
f_{\mathsf{clean}}\left(\bm{U}^{t}\right)-\bm{U}^{\star}\right\|_{\mathrm{F}}^{2}=\mathsf{vec}\left(\bm{U}^{t}-\bm{U}^{\star}\right)^{\top}\left(\bm{I}_{dr}-\eta\bm{\Gamma}\right)^{2}\mathsf{vec}\left(\bm{U}^{t}-\bm{U}^{\star}\right)$
$\displaystyle\qquad\leq\left\|\bm{U}^{t}-\bm{U}^{\star}\right\|_{\mathrm{F}}^{2}-2\eta\,\mathsf{vec}\left(\bm{U}^{t}-\bm{U}^{\star}\right)^{\top}\bm{\Gamma}\,\mathsf{vec}\left(\bm{U}^{t}-\bm{U}^{\star}\right)+\eta^{2}\left\|\bm{\Gamma}\right\|^{2}\left\|\bm{U}^{t}-\bm{U}^{\star}\right\|_{\mathrm{F}}^{2}.$
(116)

From the hypothesis (47b) as well as our conditions that
$\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}+\mathcal{E}_{\mathsf{local}}\ll\frac{1}{\mu^{3/2}r}$, we know that
$\bm{U}^{t}(\tau)$ ($0\leq\tau\leq 1$) satisfies the conditions required in
Lemma 5.1. Therefore, applying Lemma 5.1 gives that

$\displaystyle\mathsf{vec}\left(\bm{U}^{t}-\bm{U}^{\star}\right)^{\top}\bm{\Gamma}\,\mathsf{vec}\left(\bm{U}^{t}-\bm{U}^{\star}\right)$
$\displaystyle\geq\frac{1}{2}\lambda_{\min}^{\star
4/3}\left\|\bm{U}^{t}-\bm{U}^{\star}\right\|_{\mathrm{F}}^{2},$
$\displaystyle\left\|\bm{\Gamma}\right\|$ $\displaystyle\leq
4\lambda_{\max}^{\star 4/3}.$

Substitution into (116) indicates that: if $0<\eta\leq\lambda_{\min}^{\star
4/3}/\big{(}32\lambda_{\max}^{\star 8/3}\big{)}$, then

$\displaystyle\left\|\bm{U}^{t}-\eta\nabla
f_{\mathsf{clean}}\left(\bm{U}^{t}\right)-\bm{U}^{\star}\right\|_{\mathrm{F}}^{2}\leq\big{(}1-\lambda_{\min}^{\star
4/3}\eta+16\lambda_{\max}^{\star
8/3}\eta^{2}\big{)}\left\|\bm{U}^{t}-\bm{U}^{\star}\right\|_{\mathrm{F}}^{2}\leq\big{(}1-\frac{1}{2}\lambda_{\min}^{\star
4/3}\eta\big{)}\left\|\bm{U}^{t}-\bm{U}^{\star}\right\|_{\mathrm{F}}^{2},$

which implies that (since $1-a/2\geq\sqrt{1-a}$ for $0<a<1$)

$\displaystyle\left\|\bm{U}^{t}-\eta\nabla
f_{\mathsf{clean}}\left(\bm{U}^{t}\right)-\bm{U}^{\star}\right\|_{\mathrm{F}}\leq\big{(}1-\frac{1}{4}\lambda_{\min}^{\star
4/3}\eta\big{)}\left\|\bm{U}^{t}-\bm{U}^{\star}\right\|_{\mathrm{F}}.$ (117)

(2) We now turn to $\alpha_{2}$. To simplify presentation, we shall assume
that $\\{E_{i,j,k}\\}_{i,j,k\in[d]}$ (resp.
$\\{\chi_{i,j,k}\\}_{i,j,k\in[d]}$) are independent random variables. Fix an
arbitrary $s\in[r]$ and $m\in[d]$. The $m$-th entry of
$\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}\bm{u}^{t}_{s}\times_{2}\bm{u}^{t}_{s}$
can be expanded as follows:

$\displaystyle\left|\left(\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}\bm{u}^{t}_{s}\times_{2}\bm{u}^{t}_{s}\right)_{m}\right|$
$\displaystyle=\left|\bm{u}^{t\top}_{s}\left(\mathcal{P}_{\Omega}\left(\bm{E}\right)\right)_{:,:,m}\bm{u}^{t}_{s}\right|$
$\displaystyle\leq\underbrace{\left|\bm{u}^{t,\left(m\right)\top}_{s}\left(\mathcal{P}_{\Omega}\left(\bm{E}\right)\right)_{:,:,m}\bm{u}^{t,\left(m\right)}_{s}\right|}_{=:\,\beta_{1}}+\underbrace{\left|\big{(}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{)}^{\top}\left(\mathcal{P}_{\Omega}\left(\bm{E}\right)\right)_{:,:,m}\bm{u}^{t}_{s}\right|}_{=:\,\beta_{2}}$
$\displaystyle\quad+\underbrace{\left|\bm{u}^{t\top}_{s}\left(\mathcal{P}_{\Omega}\left(\bm{E}\right)\right)_{:,:,m}\big{(}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{)}\right|}_{=:\,\beta_{3}}+\underbrace{\left|\big{(}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{)}^{\top}\left(\mathcal{P}_{\Omega}\left(\bm{E}\right)\right)_{:,:,m}\big{(}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{)}\right|}_{=:\,\beta_{4}}.$
(118)

Before continuing, we make the following observations: from the hypotheses
(47a), (47b), (47c), as well as our assumption that
$\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}+\mathcal{E}_{\mathsf{local}}\ll\frac{1}{\mu^{3/2}r}$, we see that the
following holds for all $s\in\left[r\right]$:

$\displaystyle\big{\|}\bm{u}^{t}_{s}-\bm{u}^{\star}_{s}\big{\|}_{2}$
$\displaystyle\leq\left\|\bm{U}^{t}-\bm{U}^{\star}\right\|_{\mathrm{F}}\ll\frac{1}{r}\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}\lesssim\frac{1}{\sqrt{r}}\lambda_{\max}^{\star
1/3},$ (119a)
$\displaystyle\big{\|}\bm{u}^{t}_{s}-\bm{u}^{\star}_{s}\big{\|}_{\infty}$
$\displaystyle\leq\left\|\bm{U}^{t}-\bm{U}^{\star}\right\|_{2,\infty}\ll\frac{1}{r}\left\|\bm{U}^{\star}\right\|_{2,\infty}\lesssim\sqrt{\frac{\mu}{rd}}\,\lambda_{\max}^{\star
1/3},$ (119b)
$\displaystyle\big{\|}\bm{u}^{t,\left(m\right)}_{s}-\bm{u}^{t}_{s}\big{\|}_{2}$
$\displaystyle\leq\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{t}\big{\|}_{\mathrm{F}}\ll\frac{1}{r}\left\|\bm{U}^{\star}\right\|_{2,\infty}\lesssim\sqrt{\frac{\mu}{rd}}\,\lambda_{\max}^{\star
1/3},$ (119c)
$\displaystyle\Big{|}\big{(}\bm{u}^{t,\left(m\right)}_{s}-\bm{u}^{\star}_{s}\big{)}_{m}\Big{|}$
$\displaystyle\leq\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}\ll\frac{1}{r}\left\|\bm{U}^{\star}\right\|_{2,\infty}\lesssim\sqrt{\frac{\mu}{rd}}\,\lambda_{\max}^{\star},$
(119d)
$\displaystyle\big{\|}\bm{u}^{t,\left(m\right)}_{s}-\bm{u}^{\star}_{s}\big{\|}_{2}$
$\displaystyle\leq\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}\ll\frac{1}{r}\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}\lesssim\frac{1}{\sqrt{r}}\lambda_{\max}^{\star
1/3},$ (119e) $\displaystyle\big{\|}\bm{u}^{t}_{s}\big{\|}_{2}$
$\displaystyle\leq\big{\|}\bm{u}^{t}_{s}-\bm{u}^{\star}_{s}\big{\|}_{2}+\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}\lesssim\lambda_{\max}^{1/3},$
(119f) $\displaystyle\big{\|}\bm{u}^{t}_{s}\big{\|}_{\infty}$
$\displaystyle\leq\big{\|}\bm{u}^{t}_{s}-\bm{u}^{\star}_{s}\big{\|}_{\infty}+\big{\|}\bm{u}^{\star}_{s}\big{\|}_{\infty}\lesssim\sqrt{\frac{\mu}{d}}\,\lambda_{\max}^{1/3},$
(119g) $\displaystyle\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}$
$\displaystyle\leq\big{\|}\bm{u}^{t,\left(m\right)}_{s}-\bm{u}^{t}_{s}\big{\|}_{2}+\big{\|}\bm{u}^{t}_{s}\big{\|}_{2}\lesssim\lambda_{\max}^{\star
1/3},$ (119h)
$\displaystyle\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{\infty}$
$\displaystyle\leq\big{\|}\bm{u}^{t,\left(m\right)}_{s}-\bm{u}^{t}_{s}\big{\|}_{2}+\big{\|}\bm{u}^{t}_{s}\big{\|}_{\infty}\lesssim\sqrt{\frac{\mu}{d}}\,\lambda_{\max}^{1/3},$
(119i) $\displaystyle\big{\|}\bm{U}^{t}\big{\|}_{\mathrm{F}}$
$\displaystyle\leq\big{\|}\bm{U}^{t}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}+\big{\|}\bm{U}^{\star}\big{\|}_{\mathrm{F}}\lesssim\big{\|}\bm{U}^{\star}\big{\|}_{\mathrm{F}},$
(119j) $\displaystyle\big{\|}\bm{U}^{t}\big{\|}_{2,\infty}$
$\displaystyle\leq\big{\|}\bm{U}^{t}-\bm{U}^{\star}\big{\|}_{2,\infty}+\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}\lesssim\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty},$
(119k) $\displaystyle\big{\|}\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}$
$\displaystyle\leq\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{t}\big{\|}_{\mathrm{F}}+\big{\|}\bm{U}^{t}\big{\|}_{\mathrm{F}}\lesssim\big{\|}\bm{U}^{\star}\big{\|}_{\mathrm{F}},$
(119l) $\displaystyle\big{\|}\bm{U}^{t,\left(m\right)}\big{\|}_{2,\infty}$
$\displaystyle\leq\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{t}\big{\|}_{\mathrm{F}}+\big{\|}\bm{U}^{t}\big{\|}_{2,\infty}\lesssim\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}.$
(119m)

With these estimates in place, we can upper bound the above four terms in
(118) separately.

  * •

For $\beta_{1}$, we note that, by construction, $\bm{u}^{t,\left(m\right)}$ is
independent of the $m$-th mode-3 slice of
$\mathcal{P}_{\Omega}\left(\bm{E}\right)$. This tells us that

$\displaystyle\bm{u}^{t,\left(m\right)\top}_{s}\left(\mathcal{P}_{\Omega}\left(\bm{E}\right)\right)_{:,:,m}\bm{u}^{t,\left(m\right)}_{s}=\sum\nolimits_{i,j\in[d]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}E_{i,j,m}\chi_{i,j,m}$

can be viewed as a sum of independent zero-mean random variables (conditional
on $\mathcal{P}_{\Omega_{-m}}\left(\bm{E}\right)$). It is straightforward to
compute that

$\displaystyle\max_{i,j\in[d]}\left\|\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}E_{i,j,m}\chi_{i,j,m}\right\|_{\psi_{1}}\lesssim\sigma\,\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{\infty}^{2}=:L,$
$\displaystyle\sum_{i,j\in[d]}\mathbb{E}\left[\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}^{2}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}^{2}E_{i,j,m}^{2}\chi_{i,j,m}^{2}\right]\lesssim\sigma^{2}p\,\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}^{4}\lesssim\sigma^{2}\lambda_{\max}^{\star
2/3}p\,\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}^{2}=:V,$

where $\|\cdot\|_{\psi_{1}}$ denotes the sub-exponential norm and we use (119)
in the last inequality. Applying the matrix Bernstein inequality [Kol11,
Corollary 2.1] yields that: with probability $1-O(d^{-20})$,

$\displaystyle\left|\bm{u}^{t,\left(m\right)\top}_{s}\left(\mathcal{P}_{\Omega}\left(\bm{E}\right)\right)_{:,:,m}\bm{u}^{t,\left(m\right)}_{s}\right|$
$\displaystyle\lesssim L\log^{2}d+\sqrt{V\log d}$
$\displaystyle\lesssim\sigma\log^{2}d\,\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{\infty}^{2}+\sigma\lambda_{\max}^{\star
1/3}\sqrt{p\log d}\,\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2},$ (120)

  * •

For $\beta_{2}$, we first invoke [CW15, lemma 11] to demonstrate that: with
probability at least $1-O(d^{-11})$,

$\displaystyle\max_{m\in[d]}\big{\|}\left(\mathcal{P}_{\Omega}\left(\bm{E}\right)\right)_{:,:,m}\big{\|}\lesssim\sigma\big{(}\sqrt{dp}+\log
d\big{)}.$ (121)

Next, it is seen that

$\displaystyle\Big{|}\big{(}\bm{u}^{t}_{s}$
$\displaystyle-\bm{u}^{t,\left(m\right)}_{s}\big{)}^{\top}\left(\mathcal{P}_{\Omega}\left(\bm{E}\right)\right)_{:,:,m}\bm{u}^{t}_{s}\Big{|}\leq\big{\|}\left(\mathcal{P}_{\Omega}\left(\bm{E}\right)\right)_{:,:,m}\big{\|}\big{\|}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}\big{\|}\bm{u}^{t}_{s}\big{\|}_{2}$
$\displaystyle\lesssim\sigma\big{(}\sqrt{dp}+\log
d\big{)}\big{\|}\bm{U}^{t}-\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}\big{\|}\bm{u}^{t}_{s}\big{\|}_{2}$
$\displaystyle\lesssim\sigma\big{(}\sqrt{dp}+\log
d\big{)}\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}\big{\|}\bm{u}^{t}_{s}\big{\|}_{2}$
$\displaystyle\ll\frac{\lambda_{\min}^{\star
4/3}}{\sqrt{d}}\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\big{\|}\bm{u}^{t}_{s}\big{\|}_{2},$

where the last inequality follows from the noise condition. Clearly, the above
bound holds for $\beta_{3}$ as well.

  * •

Regarding $\beta_{4}$, it is easily seen that $\beta_{4}\ll\beta_{2}$, given
that
$\|\bm{U}^{t}-\bm{U}^{t,\left(m\right)}\|_{\mathrm{F}}\ll\|\bm{U}^{\star}\|_{2,\infty}/r\leq\lambda_{\min}^{\star}$
holds according to (119) and $\kappa\asymp 1$.

  * •

Taking together the above bounds and substituting them into (118), we obtain

$\displaystyle\left|\left(\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}\bm{u}^{t}_{s}\times_{2}\bm{u}^{t}_{s}\right)_{m}\right|$
$\displaystyle\lesssim\sigma\log^{2}d\,\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{\infty}^{2}+\sigma\lambda_{\max}^{\star
1/3}\sqrt{p\log d}\,\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}$
$\displaystyle\quad+o\left(1\right)\frac{\lambda_{\min}^{\star
4/3}}{\sqrt{d}}\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\big{\|}\bm{u}^{t}_{s}\big{\|}_{2}.$

Recognizing that this holds for any $m\in[d]$ and $s\in[r]$, one can sum over
$m$ and $s$ to deduce that

$\displaystyle\left\|\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}^{\mathsf{seq}}\bm{U}^{t}\times_{2}^{\mathsf{seq}}\bm{U}^{t}\right\|_{\mathrm{F}}$
$\displaystyle\overset{(\mathrm{i})}{\lesssim}\frac{\sigma\lambda_{\max}^{\star
2/3}\mu\sqrt{r}\log^{2}d}{\sqrt{d}}+\sigma\lambda_{\max}^{\star
1/3}\sqrt{dp\log d}\,\big{\|}\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}$
$\displaystyle\quad+o\left(1\right)\lambda_{\min}^{\star
4/3}\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{t}\right\|_{\mathrm{F}}$ $\displaystyle\leq
C\sigma\lambda_{\min}^{\star 1/3}\sqrt{dp\log
d}\,\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}$
$\displaystyle\quad+o\left(1\right)\lambda_{\min}^{\star
4/3}\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{\mathrm{F}},$ (122)

for some absolute constant $C>0$, where (i) is true due to (119); the last
inequality follows from the fact that
$\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}\geq\lambda_{\min}^{\star
1/3}\sqrt{r}$ as well as the assumptions that $p\gg\mu d^{-2}\log^{3}d$ and
$\kappa\asymp 1$.

(3) Combining (117) and (122) yields that: with probability at least
$1-O(d^{-10})$,

$\displaystyle\left\|\bm{U}^{t+1}-\bm{U}^{\star}\right\|_{\mathrm{F}}$
$\displaystyle\leq\big{(}1-\frac{1}{4}\lambda_{\min}^{\star
4/3}\eta\big{)}\left\|\bm{U}^{t}-\bm{U}^{\star}\right\|_{\mathrm{F}}+C\eta\sigma\lambda_{\min}^{\star
1/3}\sqrt{\frac{d\log d}{p}}\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}$
$\displaystyle\qquad+o\left(1\right)\lambda_{\min}^{\star
4/3}\eta\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}$
$\displaystyle\leq\big{(}1-\frac{1}{4}\lambda_{\min}^{\star
4/3}\eta\big{)}\left(C_{1}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{2}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}+C\eta\sigma\lambda_{\min}^{\star
1/3}\sqrt{\frac{d\log d}{p}}\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}$
$\displaystyle\qquad+o\left(1\right)\lambda_{\min}^{\star
4/3}\eta\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}$
$\displaystyle\leq\big{(}1-\frac{1}{5}\lambda_{\min}^{\star
4/3}\eta\big{)}C_{1}\rho^{t}\mathcal{E}_{\mathsf{local}}\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}+\left(\big{(}1-\frac{1}{5}\lambda_{\min}^{\star
4/3}\eta\big{)}C_{2}+C\eta\lambda_{\min}^{\star
3/4}\right)\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}$ $\displaystyle\leq
C_{1}\rho^{t+1}\mathcal{E}_{\mathsf{local}}\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}+C_{2}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\left\|\bm{U}^{\star}\right\|_{\mathrm{F}},$

with the proviso that $0<\eta\leq\lambda_{\min}^{\star
4/3}/\big{(}32\lambda_{\max}^{\star 8/3}\big{)}$,
$1-\big{(}\lambda_{\min}^{\star 4/3}/5\big{)}\eta\leq\rho<1$ and that $C_{2}$
is sufficiently large.

###  A.4 Proof of Lemma 5.4

Fix an arbitrary $m\in[r]$. From the definition of $f^{\left(m\right)}$ in
(45) and (46), we can show that

$\displaystyle\bm{U}^{t+1}-\bm{U}^{t+1,\left(m\right)}=\bm{U}^{t}-\eta\nabla
f\big{(}\bm{U}^{t}\big{)}-\Big{(}\bm{U}^{t,\left(m\right)}-\eta\nabla
f^{\left(m\right)}\big{(}\bm{U}^{t,\left(m\right)}\big{)}\Big{)}$
$\displaystyle\quad=\bm{U}^{t}-\bm{U}^{t,\left(m\right)}-\eta\left(\nabla
f\big{(}\bm{U}^{t}\big{)}-\nabla
f\big{(}\bm{U}^{t,\left(m\right)}\big{)}\right)-\eta\left(\nabla
f\big{(}\bm{U}^{t,\left(m\right)}\big{)}-\nabla
f^{\left(m\right)}\big{(}\bm{U}^{t,\left(m\right)}\big{)}\right)$
$\displaystyle\quad=\underbrace{\bm{U}^{t}-\bm{U}^{t,\left(m\right)}-\eta\left(\nabla
f_{\mathsf{clean}}\big{(}\bm{U}^{t}\big{)}-\nabla
f_{\mathsf{clean}}\big{(}\bm{U}^{t,\left(m\right)}\big{)}\right)}_{=:\,\alpha_{1}}$
$\displaystyle\quad\quad-\underbrace{\eta\,\Big{(}\left(p^{-1}\mathcal{P}_{\Omega_{m}}-\mathcal{P}_{m}\right)\Big{(}\sum\nolimits_{s\in[r]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}^{\otimes
3}-\bm{T}^{\star}\Big{)}\Big{)}\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}}_{=:\,\alpha_{2}}$
$\displaystyle\qquad+\underbrace{\eta\,p^{-1}\mathcal{P}_{\Omega_{m}}\left(\bm{E}\right)\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}}_{=:\,\alpha_{3}}+\underbrace{\eta
p^{-1}\,\big{\\{}\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}^{\mathsf{seq}}\bm{U}^{t}\times_{2}^{\mathsf{seq}}\bm{U}^{t}-\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\big{\\}}}_{=:\,\alpha_{4}}.$
(123)

Before proceeding to bounding these terms, we pause to define

$\displaystyle\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}:=\sum_{s\in[r]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}^{\otimes
3}-\bm{T}^{\star}.$ (124)

From (119) and hypothesis (47d), one can applying a similar argument as in
(107) to find that

$\displaystyle\big{\|}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{\|}_{\infty}\lesssim\max_{s\in[r]}\big{\|}\bm{u}^{\star}_{s}\big{\|}_{\infty}\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{2,\infty}\lesssim\frac{\mu\sqrt{r}\,\lambda_{\max}^{\star
2/3}}{d}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{2,\infty}.$
(125)

Now we begin to bound the terms in (123) separately.

(1) We start with $\alpha_{1}$. For any $0\leq\tau\leq 1$, define

$\displaystyle\bm{U}^{t,\left(m\right)}(\tau):=\tau\,\bm{U}^{t}+\left(1-\tau\right)\bm{U}^{t,\left(m\right)}.$

The fundamental theorem of calculus yields

$\displaystyle\bm{U}^{t}-\bm{U}^{t,\left(m\right)}-\eta\left(\nabla
f_{\mathsf{clean}}\big{(}\bm{U}^{t}\big{)}-\nabla
f_{\mathsf{clean}}\big{(}\bm{U}^{t,\left(m\right)}\big{)}\right)=\underbrace{\Big{(}\bm{I}_{dr}-\eta\int_{0}^{1}\nabla^{2}f_{\mathsf{clean}}\big{(}\bm{U}^{t,\left(m\right)}\left(\tau\right)\big{)}\,\mathrm{d}\tau\Big{)}}_{=:\bm{\Gamma}}\big{(}\bm{U}^{t}-\bm{U}^{t,\left(m\right)}\big{)}.$

By Lemma 5.2 and our assumptions on the noise, we know that
$\bm{U}^{t,\left(m\right)}(\tau)$ ($0\leq\tau\leq 1$) satisfies the conditions
in Lemma 5.1 for any $\tau\in[0,1]$. Applying the same argument as the one
used to bound $\left\|\bm{U}^{t}-\eta\nabla
f_{\mathsf{clean}}\left(\bm{U}^{t}\right)-\bm{U}^{\star}\right\|_{\mathrm{F}}$
in Lemma 5.3, we show that

$\displaystyle\Big{\|}\bm{U}^{t}-\bm{U}^{t,\left(m\right)}-\eta\Big{(}\nabla
f\big{(}\bm{U}^{t}\big{)}-\nabla
f\big{(}\bm{U}^{t,\left(m\right)}\big{)}\Big{)}\Big{\|}_{2}$
$\displaystyle\leq\big{(}1-\frac{1}{4}\lambda_{\min}^{\star
4/3}\eta\big{)}\big{\|}\bm{U}^{t}-\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}},$
(126)

provided that $0<\eta\leq\lambda_{\min}^{\star
4/3}/\big{(}32\lambda_{\max}^{\star 8/3}\big{)}$.

In what follows, we shall assume that $\\{E_{i,j,k}\\}_{i,j,k\in[d]}$ (resp.
$\\{\chi_{i,j,k}\\}_{i,j,k\in[d]}$) are independent random variables in order
to simplify presentation.

(2) The next step is to bound $\alpha_{2}$. For notational simplicity, define

$\displaystyle\bm{V}^{t,\left(m\right)}$
$\displaystyle:=\Big{(}\left(p^{-1}\mathcal{P}_{\Omega_{m}}-\mathcal{P}_{m}\right)\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}\Big{)}\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)};$
$\displaystyle\bm{v}^{t,\left(m\right)}_{s}$
$\displaystyle:=\Big{(}\left(p^{-1}\mathcal{P}_{\Omega_{m}}-\mathcal{P}_{m}\right)\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}\Big{)}\times_{1}\bm{u}^{t,\left(m\right)}_{s}\times_{2}\bm{u}^{t,\left(m\right)}_{s},\qquad
s\in[r].$

In order to control the Frobenius norm of $\bm{V}^{t,\left(m\right)}$, we
shall start by considering the $m$-th row of $\bm{V}^{t,\left(m\right)}$. In
view of the definitions of $\mathcal{P}_{\Omega_{m}}$ and $\mathcal{P}_{m}$
(cf. Appendix 5.1.3), we can expand

$\displaystyle\bm{V}^{t,\left(m\right)}_{m,:}$
$\displaystyle=\sum_{i,j\in[d]}\sum_{s\in[r]}\left(p^{-1}\chi_{i,j,m}-1\right)\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}_{i,j,m}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}\bm{e}_{s}^{\top}.$

We recognize that $\big{\\{}\bm{u}_{s}^{t,\left(m\right)}\big{\\}}_{s=1}^{r}$
is independent of $\Omega_{m}$, making it convenient for us to upper bound
$\big{\|}\bm{V}^{t,\left(m\right)}_{m,:}\big{\|}_{2}$. Specifically, for any
$i,j\in[d]$, from (119) and (125) we have

$\displaystyle\Big{\|}\sum_{s\in[r]}\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}_{i,j,m}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}\left(p^{-1}\chi_{i,j,m}-1\right)\bm{e}_{s}^{\top}\Big{\|}_{2}$
$\displaystyle\leq\frac{1}{p}\,\big{\|}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{\|}_{\infty}\max_{s\in[r]}\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{\infty}\big{\|}\bm{U}^{t,\left(m\right)}\big{\|}_{2,\infty}$
$\displaystyle\lesssim\frac{\mu^{2}r\lambda_{\max}^{\star
4/3}}{d^{2}p}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{2,\infty}=:L_{1}.$

In addition, it is easy to verify that
$\mathbb{E}\big{[}\bm{V}^{t,\left(m\right)}_{m,:}\big{]}=\bm{0}$ and

$\displaystyle\sum_{i,j\in[d]}\mathbb{E}$
$\displaystyle\Bigg{[}\Big{\|}\sum\nolimits_{s\in[r]}\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}_{i,j,m}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}(p^{-1}\chi_{i,j,m}-1)\,\bm{e}_{s}^{\top}\Big{\|}_{2}^{2}\Bigg{]}$
$\displaystyle=\sum_{i,j\in[d]}\sum_{s\in[r]}\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}^{2}_{i,j,m}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}^{2}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}^{2}\,\mathbb{E}\big{[}(p^{-1}{\chi}_{i,j,m}-1)^{2}\big{]}$
$\displaystyle\leq\frac{1}{p}\,\big{\|}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{\|}_{\infty}^{2}\max_{s\in[r]}\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}^{2}\big{\|}\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}^{2}\lesssim\frac{\mu^{2}r^{2}\lambda_{\max}^{\star
8/3}}{d^{2}p}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{2,\infty}^{2}=:V_{1},$

where the last inequality holds due to (119) and (125). We then apply the
matrix Bernstein inequality to yield that: with probability exceeding
$1-O(d^{-20})$,

$\displaystyle\big{\|}\bm{V}^{t,\left(m\right)}_{m,:}\big{\|}_{2}$
$\displaystyle\lesssim L_{1}\log d+\sqrt{V_{1}\log
d}\lesssim\Bigg{\\{}\frac{\mu^{2}r\lambda_{\max}^{\star 4/3}\log
d}{d^{2}p}+\frac{\mu r\lambda_{\max}^{\star 4/3}\sqrt{\log
d}}{d\sqrt{p}}\Bigg{\\}}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\infty}$
$\displaystyle\asymp\frac{\mu r\lambda_{\max}^{\star 4/3}\sqrt{\log
d}}{d\sqrt{p}}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\infty},$
(127)

where the last step holds as long as $p\gg\mu^{2}d^{-2}\log d$.

Next, we turn to the $k$-th row of $\bm{V}^{t,\left(m\right)}$ for any $k\neq
m$. For each $s\in[r]$, we have

$\displaystyle\big{(}\bm{v}^{t,\left(m\right)}_{s}\big{)}_{k}$
$\displaystyle=\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{m}\sum_{j\in[d]}\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}_{m,j,k}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}(p^{-1}\chi_{m,j,k}-1)$
$\displaystyle\quad+\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{m}\sum_{i:i\neq
m}\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}_{i,m,k}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}(p^{-1}\chi_{i,m,k}-1).$

Similar to the proof of Lemma D.9, we can show that with probability at least
$1-O(d^{-20})$,

$\displaystyle\sum_{s\in[r]}\sum_{k:k\neq m}$
$\displaystyle\Big{(}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{m}\sum\nolimits_{j\in[d]}\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}_{m,j,k}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}(p^{-1}\chi_{m,j,k}-1)\Big{)}^{2}$
$\displaystyle\lesssim\sum_{s\in[r]}\sum_{k:k\neq
m}\mathbb{E}\Big{[}\Big{(}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{m}\sum\nolimits_{j\in[d]}\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}_{m,j,k}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}(p^{-1}\chi_{m,j,k}-1)\Big{)}^{2}\Big{]}$
$\displaystyle\lesssim\frac{1}{p}\sum_{s\in[r]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{m}^{2}\sum_{j,k\in[d]}\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}_{m,j,k}^{2}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}^{2}$
$\displaystyle\leq\frac{d}{p}\max_{s\in[r]}\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{\infty}^{2}\big{\|}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{\|}_{\infty}^{2}\big{\|}\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}^{2}\lesssim\frac{\mu^{3}r^{2}\lambda_{\max}^{\star
8/3}}{d^{2}p}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{2,\infty}^{2},$

where the last inequality follows from (119), and (125). It is easily seen
that the bound also holds for the summation over $i\neq m$. We can then use
Cauchy-Schwartz to arrive at

$\displaystyle\sum_{k:k\neq
m}\big{\|}\bm{V}^{t,\left(m\right)}_{k,:}\big{\|}_{2}^{2}=\sum_{s\in[r]}\sum_{k:k\neq
m}\big{(}\bm{v}^{t,\left(m\right)}_{s}\big{)}_{k}^{2}\lesssim\frac{\mu^{3}r^{2}\lambda_{\max}^{\star
8/3}}{d^{2}p}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{2,\infty}^{2}.$
(128)

Combining (128) with (127) and invoking the union bound, we conclude that:
with probability exceeding $1-O(d^{-20})$,

$\displaystyle\begin{split}\Big{\|}\Big{(}\big{(}p^{-1}\mathcal{P}_{\Omega_{m}}-\mathcal{P}_{m}\big{)}\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}\Big{)}\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\Big{\|}_{\mathrm{F}}=\big{\|}\bm{V}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}\leq
C\frac{\mu^{3/2}r\lambda_{\min}^{\star 4/3}\sqrt{\log
d}}{d\sqrt{p}}\,\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{2,\infty}.\end{split}$
(129)

for some absolute constant $C>0$, where we use the assumption that
$\kappa\asymp 1$.

(3) For $\alpha_{3}$, following a similar argument for $\alpha_{2}$, we define

$\displaystyle\bm{W}^{t,\left(m\right)}$
$\displaystyle:=\mathcal{P}_{\Omega_{m}}\left(\bm{E}\right)\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}_{s}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}_{s}$
$\displaystyle\bm{w}^{t,\left(m\right)}_{s}$
$\displaystyle:=\mathcal{P}_{\Omega_{m}}\left(\bm{E}\right)\times_{1}\bm{u}^{t,\left(m\right)}_{s}\times_{2}\bm{u}^{t,\left(m\right)}_{s}$

for each $s\in[r]$. The $m$-th row of $\bm{W}^{t,\left(m\right)}$ is a sum of
independent zero-mean random vectors:

$\displaystyle\bm{W}^{t,\left(m\right)}_{m,:}$
$\displaystyle=\sum_{i,j\in[d]}\sum_{s\in[r]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}E_{i,j,m}\chi_{i,j,m}\bm{e}_{s}^{\top}.$

With (119) in place, it is easy to verify that

$\displaystyle\max_{i,j\in[d]}\Big{\|}\sum\nolimits_{s\in[r]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}E_{i,j,m}\chi_{i,j,m}\bm{e}_{s}^{\top}\Big{\|}_{\psi_{1}}$
$\displaystyle\leq\sigma\max_{s\in[r]}\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{\infty}\big{\|}\bm{U}^{t,\left(m\right)}\big{\|}_{2,\infty}$
$\displaystyle\lesssim\sigma\sqrt{\frac{\mu}{d}}\,\lambda_{\max}^{\star
1/3}\left\|\bm{U}^{\star}\right\|_{2,\infty}=:L_{2}$

and

$\displaystyle\sum_{i,j\in[d]}\mathbb{E}\Bigg{[}\Big{\|}\sum\nolimits_{s\in[r]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}E_{i,j,m}\chi_{i,j,m}\bm{e}_{s}^{\top}\Big{\|}_{2}^{2}\Bigg{]}$
$\displaystyle=\sum_{i,j\in[d]}\sum_{s\in[r]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}^{2}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}^{2}\mathbb{E}\big{[}\left(E_{i,j,m}\chi_{i,j,m}\right)^{2}\big{]}$
$\displaystyle\leq\sigma^{2}p\max_{s\in[r]}\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}^{2}\big{\|}\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}^{2}$
$\displaystyle\lesssim\sigma^{2}dp\lambda_{\max}^{\star
2/3}\left\|\bm{U}^{\star}\right\|_{2,\infty}^{2}=:V_{2},$

where we have used (119) and the fact that
$\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}\leq\sqrt{d}\left\|\bm{U}^{\star}\right\|_{2,\infty}$.
Apply the matrix Bernstein inequality to reveal that: with probability at
least $1-O(d^{-20})$,

$\displaystyle\left\|\bm{W}^{t,\left(m\right)}_{m,:}\right\|_{2}$
$\displaystyle=\Big{\|}\sum_{i,j\in[d]}\sum_{s\in[r]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}E_{i,j,m}\chi_{i,j,m}\bm{e}_{s}^{\top}\Big{\|}_{2}$
$\displaystyle\lesssim L_{2}\log^{2}d+\sqrt{V_{2}\log
d}\asymp\sigma\lambda_{\max}^{\star 1/3}\sqrt{dp\log
d}\left\|\bm{U}^{\star}\right\|_{2,\infty},$ (130)

where the last inequality holds as long as $p\gg\mu d^{-2}\log^{3}d$.

As for the other rows, we have

$\displaystyle\big{(}\bm{w}^{t,\left(m\right)}_{s}\big{)}_{k}$
$\displaystyle=\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{m}\sum_{j\in[d]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}E_{m,j,k}\chi_{m,j,k}+\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{m}\sum_{i:i\neq
m}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{i}E_{i,m,k}\chi_{i,m,k}$

for each $s\in[r]$. Arguing similarly as in the proof of Lemma D.10, we have
with probability at least $1-O(d^{-20})$,

$\displaystyle\sum_{s\in[r]}\sum_{k:k\neq m}$
$\displaystyle\Big{(}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{m}\sum\nolimits_{j\in[d]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}E_{m,j,k}\chi_{m,j,k}\Big{)}^{2}$
$\displaystyle\lesssim\sum_{s\in[r]}\sum_{k:k\neq
m}\mathbb{E}\Big{[}\Big{(}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{m}\sum_{j\in[d]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}\left(E_{m,j,k}\chi_{m,j,k}\right)\Big{)}^{2}\Big{]}$
$\displaystyle\leq\sigma^{2}dp\sum_{s\in[r]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{m}^{2}\sum_{j\in[d]}\big{(}\bm{u}^{t,\left(m\right)}_{s}\big{)}_{j}^{2}$
$\displaystyle\leq\sigma^{2}dp\max_{s\in[r]}\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}^{2}\big{\|}\bm{U}^{t,\left(m\right)}\big{\|}_{2,\infty}^{2}\lesssim\sigma^{2}\lambda_{\max}^{\star
2/3}dp\left\|\bm{U}^{\star}\right\|_{2,\infty}^{2},$

where the last inequality follows from (119). Additionally, the summation over
$\\{i:i\neq m\\}$ can be controlled using the same argument. Therefore, we use
Cauchy-Schwarz to find that

$\displaystyle\sum_{k:k\neq
m}\left\|\bm{W}^{t,\left(m\right)}_{k,:}\right\|_{2}^{2}\lesssim\sigma^{2}\lambda_{\max}^{\star
2/3}dp\left\|\bm{U}^{\star}\right\|_{2,\infty}^{2}.$ (131)

Combined with (130) and the assumption that $\kappa\asymp 1$, we obtain that

$\displaystyle\left\|p^{-1}\mathcal{P}_{\Omega_{m}}\left(\bm{E}\right)\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\right\|_{\mathrm{F}}=\big{\|}\bm{W}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}\leq\widetilde{C}\sigma\lambda_{\min}^{\star
1/3}\sqrt{dp\log d}\left\|\bm{U}^{\star}\right\|_{2,\infty},$ (132)

for some absolute constant $\widetilde{C}>0$.

(4) Regarding $\alpha_{4}$, we use the triangle inequality to show that for
each $s\in[r]$,

$\displaystyle\big{\|}\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}\bm{u}^{t}_{s}\times_{2}\bm{u}^{t}_{s}$
$\displaystyle-\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}\bm{u}^{t,\left(m\right)}_{s}\times_{2}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}$
$\displaystyle\leq\big{\|}\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}\big{(}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{)}\times_{2}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}+\big{\|}\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}\bm{u}^{t,\left(m\right)}_{s}\times_{2}\big{(}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{)}\big{\|}_{2}$
$\displaystyle\quad+\big{\|}\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}\big{(}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{)}\times_{2}\big{(}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{)}\big{\|}_{2}$
$\displaystyle\leq
2\left\|\mathcal{P}_{\Omega}\left(\bm{E}\right)\right\|\big{\|}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}+\left\|\mathcal{P}_{\Omega}\left(\bm{E}\right)\right\|\big{\|}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}^{2}$
$\displaystyle\lesssim\left\|\mathcal{P}_{\Omega}\left(\bm{E}\right)\right\|\big{\|}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2},$

where the last line follows from (119). From Corollary D.3, we can further
upper bound

$\displaystyle\big{\|}\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}\bm{u}^{t}_{s}\times_{2}\bm{u}^{t}_{s}-\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}\bm{u}^{t,\left(m\right)}_{s}\times_{2}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}$
$\displaystyle\leq\sigma\big{(}\sqrt{dp}+\log
d\big{)}\log^{5/2}d\,\big{\|}\bm{u}^{t}_{s}-\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}\big{\|}\bm{u}^{t,\left(m\right)}_{s}\big{\|}_{2}.$

As a result, we sum over $s\in[r]$ and use the Cauchy-Schwartz inequality to
derive

$\displaystyle\frac{1}{p}\big{\|}\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}^{\mathsf{seq}}\bm{U}^{t}\times_{2}^{\mathsf{seq}}\bm{U}^{t}$
$\displaystyle-\mathcal{P}_{\Omega}\left(\bm{E}\right)\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}$
$\displaystyle\lesssim\frac{\sigma}{p}\big{(}\sqrt{dp}+\log
d\big{)}\log^{5/2}d\,\big{\|}\bm{U}^{t}-\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}\big{\|}\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}$
$\displaystyle\lesssim\frac{\sigma}{p}\big{(}\sqrt{dp}+\log
d\big{)}\log^{5/2}d\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}^{2}$
$\displaystyle\ll\lambda_{\min}^{\star
4/3}\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty},$ (133)

where the last step arises from conditions that
$\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\ll\frac{1}{\mu^{3/2}r}$ and $\kappa\asymp 1$.

(5) Taking (126), (129), (132) and (133) together, we can invoke the sample
size assumption that $p\gg\mu^{3}r^{2}d^{-2}\log^{3}d$ and the union bound to
show that: with probability greater than $1-O(d^{-10})$ one has

$\displaystyle\big{\|}\bm{U}^{t+1}$
$\displaystyle-\bm{U}^{t+1,\left(m\right)}\big{\|}_{\mathrm{F}}$
$\displaystyle\leq\big{(}1-\frac{1}{4}\lambda_{\min}^{\star
4/3}\eta\big{)}\big{\|}\bm{U}^{t}-\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}+C\frac{\mu^{3/2}r\lambda_{\min}^{\star
4/3}\sqrt{\log
d}}{d\sqrt{p}}\,\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{2,\infty}$
$\displaystyle\quad+\widetilde{C}\eta\sigma\lambda_{\min}^{\star
1/3}\sqrt{\frac{\mu rd\log
d}{p}}\left\|\bm{U}^{\star}\right\|_{2,\infty}+o\left(1\right)\lambda_{\min}^{\star
4/3}\eta\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\leq\big{(}1-\frac{1}{4}\lambda_{\min}^{\star
4/3}\eta\big{)}\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}+\widetilde{C}\eta\sigma\lambda_{\min}^{\star
1/3}\sqrt{\frac{d\log d}{p}}\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\quad+C\eta\lambda_{\max}^{\star 4/3}\frac{\mu^{3/2}r\sqrt{\log
d}}{d\sqrt{p}}\left(2C_{3}\rho^{t}\mathcal{E}_{\mathsf{local}}+2C_{4}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\quad+o\left(1\right)\lambda_{\min}^{\star
4/3}\eta\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{\mu
rd\log d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\leq\big{(}1-\frac{1}{5}\lambda_{\min}^{\star
4/3}\eta\big{)}C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}\left\|\bm{U}^{\star}\right\|_{2,\infty}+\left(\big{(}1-\frac{1}{5}\lambda_{\min}^{\star
4/3}\eta\big{)}C_{6}+\widetilde{C}\lambda_{\min}^{\star
4/3}\eta\right)\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\leq\big{(}1-\frac{1}{5}\lambda_{\min}^{\star
4/3}\eta\big{)}C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}\left\|\bm{U}^{\star}\right\|_{2,\infty}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\leq\left(C_{5}\rho^{t+1}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty},$

provided $0<\eta\leq\lambda_{\min}^{\star 4/3}/\big{(}32\lambda_{\max}^{\star
8/3}\big{)}$, $1-\big{(}\lambda_{\min}^{\star 4/3}/5\big{)}\eta\leq\rho<1$ and
$C_{6}$ is sufficiently large.

###  A.5 Proof of Lemma 5.5

Fix an arbitrary $m\in[d]$. Recall our notation of
$\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}$ in (124). To simplify presentation,
we further define

$\displaystyle\widehat{\bm{U}}^{t+1,\left(m\right)}$
$\displaystyle:=\bm{U}^{t,\left(m\right)}-\eta\left(p^{-1}\mathcal{P}_{\Omega_{-m}}\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}-\bm{E}\big{)}\times_{1}^{\mathsf{seq}}\bm{U}^{\star}\times_{2}^{\mathsf{seq}}\bm{U}^{\star}+\mathcal{P}_{m}\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}\times_{1}^{\mathsf{seq}}\bm{U}^{\star}\times_{2}^{\mathsf{seq}}\bm{U}^{\star}\right),$
(134) $\displaystyle\bm{\Delta}^{t,\left(m\right)}_{s}$
$\displaystyle:=\bm{u}^{t,\left(m\right)}_{s}-\bm{u}^{\star}_{s},$ (135)

for each $s\in[r]$.

Apply the triangle inequality to yield

$\displaystyle\big{\|}\big{(}\bm{U}^{t+1,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}$
$\displaystyle\leq\underbrace{\big{\|}\big{(}\widehat{\bm{U}}^{t+1,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}}_{=:\,\alpha_{1}}+\underbrace{\big{\|}\big{(}\bm{U}^{t+1,\left(m\right)}-\widehat{\bm{U}}^{t+1,\left(m\right)}\big{)}_{m,:}\big{\|}_{2}}_{=:\,\alpha_{2}},$

leaving us with two terms to deal with. As it turns out, we will show that
$\alpha_{1}$ is the dominant term and $\alpha_{2}$ is negligible. To simplify
presentation, we shall assume that $\\{E_{i,j,k}\\}_{i,j,k\in[d]}$ (resp.
$\\{\chi_{i,j,k}\\}_{i,j,k\in[d]}$) are independent random variables.

  * •

Regarding $\alpha_{1}$, the definition of $\mathcal{P}_{\Omega_{-m}}$ allows
us to derive

$\displaystyle\big{(}\widehat{\bm{U}}^{t+1,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}$
$\displaystyle=\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}-\eta\,\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\bm{U}^{\star}\times_{2}^{\mathsf{seq}}\bm{U}^{\star}\big{)}_{m,:}$
$\displaystyle=\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}-\eta\,\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\bm{U}^{\star}\times_{2}^{\mathsf{seq}}\bm{U}^{\star}\big{)}_{m,:}.$

We can express
$\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}=\sum_{s\in[r]}\big{(}\bm{\Delta}_{s}^{t,\left(m\right)}+\bm{u}_{s}^{\star}\big{)}^{\otimes
3}-\bm{u}_{s}^{\star\otimes 3}$ and compute that

$\displaystyle\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}\bm{u}^{\star}_{s}\times_{2}\bm{u}^{\star}_{s}\big{)}_{m}$
$\displaystyle\qquad=\Big{(}\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}^{2}+\big{\langle}\bm{\Delta}^{t,(m)}_{s},\bm{u}^{\star}_{s}\big{\rangle}\Big{)}^{2}\big{(}\bm{\Delta}_{s}^{t,\left(m\right)}\big{)}_{m}+\Big{(}2\,\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}^{2}\big{\langle}\bm{\Delta}^{t,(m)}_{s},\bm{u}^{\star}_{s}\big{\rangle}+\big{\langle}\bm{\Delta}^{t,(m)}_{s},\bm{u}^{\star}_{s}\big{\rangle}^{2}\Big{)}\big{(}\bm{u}^{\star}_{s}\big{)}_{m}$
$\displaystyle\qquad\qquad+\sum_{i:i\neq
s}\Big{(}\big{\langle}\bm{u}^{\star}_{i},\bm{u}^{\star}_{s}\big{\rangle}+\big{\langle}\bm{\Delta}^{t,(m)}_{i},\bm{u}^{\star}_{s}\big{\rangle}\Big{)}^{2}\big{(}\bm{\Delta}_{i}^{t,\left(m\right)}\big{)}_{m}$
$\displaystyle\qquad\qquad+\sum_{i:i\neq
s}\Big{(}2\,\big{\langle}\bm{u}^{\star}_{i},\bm{u}^{\star}_{s}\big{\rangle}\big{\langle}\bm{\Delta}^{t,(m)}_{i},\bm{u}^{\star}_{s}\big{\rangle}+\big{\langle}\bm{\Delta}^{t,(m)}_{i},\bm{u}^{\star}_{s}\big{\rangle}^{2}\Big{)}\big{(}\bm{u}^{\star}_{i}\big{)}_{m}$
(136)

for each $s\in[r]$. This further indicates that

$\displaystyle\left\|\big{(}\widehat{\bm{U}}^{t+1,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\right\|_{2}$
$\displaystyle\leq\underbrace{\Big{\|}\sum\nolimits_{s\in[r]}\Big{(}1-\eta\left(\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}^{2}+\big{\langle}\bm{\Delta}^{t,(m)}_{s},\bm{u}^{\star}_{s}\big{\rangle}\right)^{2}\Big{)}\big{(}\bm{\Delta}_{s}^{t,\left(m\right)}\big{)}_{m}\bm{e}_{s}^{\top}\Big{\|}_{2}}_{=:\,\beta_{1}}$
$\displaystyle\quad+\underbrace{\eta\,\Big{\|}\sum\nolimits_{s\in[r]}\Big{(}2\,\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}^{2}\big{\langle}\bm{\Delta}^{t,(m)}_{s},\bm{u}^{\star}_{s}\big{\rangle}+\big{\langle}\bm{\Delta}^{t,(m)}_{s},\bm{u}^{\star}_{s}\big{\rangle}^{2}\Big{)}\big{(}\bm{u}^{\star}_{s}\big{)}_{m}\bm{e}_{s}^{\top}\Big{\|}_{2}}_{=:\,\beta_{2}}$
$\displaystyle\quad+\underbrace{\eta\,\Big{\|}\sum\nolimits_{s\in[r]}\sum\nolimits_{i:i\neq
s}\Big{(}\big{\langle}\bm{u}^{\star}_{i},\bm{u}^{\star}_{s}\big{\rangle}+\big{\langle}\bm{\Delta}^{t,(m)}_{i},\bm{u}^{\star}_{s}\big{\rangle}\Big{)}^{2}\big{(}\bm{\Delta}_{i}^{t,\left(m\right)}\big{)}_{m}\bm{e}_{s}^{\top}\Big{\|}_{2}}_{=:\,\beta_{3}}$
$\displaystyle\quad+\underbrace{\eta\,\Big{\|}\sum\nolimits_{s\in[r]}\sum\nolimits_{i:i\neq
s}\Big{(}2\,\big{\langle}\bm{u}^{\star}_{i},\bm{u}^{\star}_{s}\big{\rangle}\big{\langle}\bm{\Delta}^{t,(m)}_{i},\bm{u}^{\star}_{s}\big{\rangle}+\big{\langle}\bm{\Delta}^{t,(m)}_{i},\bm{u}^{\star}_{s}\big{\rangle}^{2}\Big{)}\left(\bm{u}^{\star}_{i}\right)_{m}\bm{e}_{s}^{\top}\Big{\|}_{2}}_{=:\,\beta_{4}}.$

In what follows, we will control the four terms separately.

    * –

For $\beta_{1}$, by (119), we use Cauchy-Schwarz to show that

$\displaystyle\Big{(}\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}^{2}+\big{\langle}\bm{\Delta}^{t,(m)}_{s},\bm{u}^{\star}_{s}\big{\rangle}\Big{)}^{2}\geq\left(\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}^{2}-\big{\|}\bm{\Delta}^{t,(m)}_{s}\big{\|}_{2}\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}\right)^{2}\geq\frac{2}{3}\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}^{4}\geq\frac{2}{3}\lambda_{\min}^{\star
4/3}$

for each $s\in[r]$. It follows that

$\displaystyle\beta_{1}\leq\big{(}1-\frac{2}{3}\lambda_{\min}^{\star
4/3}\eta\big{)}\left\|\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\right\|_{2}.$
(137)

    * –

Regarding $\beta_{2}$, by (119), we apply the Cauchy-Schwarz inequality again
to get that: for each $s\in[r]$,

$\displaystyle\Big{|}\Big{(}2\,\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}^{2}\big{\langle}\bm{\Delta}^{t,(m)}_{s},\bm{u}^{\star}_{s}\big{\rangle}+\big{\langle}\bm{\Delta}^{t,(m)}_{s},\bm{u}^{\star}_{s}\big{\rangle}^{2}\Big{)}\big{(}\bm{u}^{\star}_{s}\big{)}_{m}\Big{|}\leq
3\,\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}^{3}\big{\|}\bm{u}^{\star}_{s}\big{\|}_{\infty}\big{\|}\bm{\Delta}^{t,(m)}_{s}\big{\|}_{2}\leq
3\sqrt{\frac{\mu}{d}}\,\lambda_{\max}^{\star
4/3}\big{\|}\bm{\Delta}^{t,(m)}_{s}\big{\|}_{2},$

Together with the assumption that $\kappa\asymp 1$, this implies that

$\displaystyle\beta_{2}\leq 3\eta\lambda_{\min}^{\star
4/3}\sqrt{\frac{\mu}{d}}\,\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}.$
(138)

    * –

With regards to $\beta_{3}$, we show that for each $s\in[r]$:

$\displaystyle\Big{|}$ $\displaystyle\sum\nolimits_{i:i\neq
s}\Big{(}\big{\langle}\bm{u}^{\star}_{i},\bm{u}^{\star}_{s}\big{\rangle}+\big{\langle}\bm{\Delta}^{t,(m)}_{i},\bm{u}^{\star}_{s}\big{\rangle}\Big{)}^{2}\big{(}\bm{\Delta}_{i}^{t,\left(m\right)}\big{)}_{m}\Big{|}$
$\displaystyle\;\;\lesssim\max_{i:i\neq
s}\big{|}\big{\langle}\bm{u}^{\star}_{i},\bm{u}^{\star}_{s}\big{\rangle}\big{|}^{2}\sum_{i:i\neq
s}\left|\big{(}\bm{\Delta}_{i}^{t,\left(m\right)}\big{)}_{m}\right|+\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}^{2}\sum_{i:i\neq
s}\big{\|}\bm{\Delta}^{t,(m)}_{i}\big{\|}_{2}^{2}\left|\big{(}\bm{\Delta}_{i}^{t,\left(m\right)}\big{)}_{m}\right|$
$\displaystyle\;\;\leq\lambda_{\max}^{\star
4/3}\frac{\mu\sqrt{r}}{d}\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}+\lambda_{\max}^{\star
2/3}\max_{i:i\neq
s}\big{\|}\bm{\Delta}^{t,(m)}_{i}\big{\|}_{2}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}$
$\displaystyle\;\;\leq\lambda_{\max}^{\star
4/3}\Big{(}\frac{\mu\sqrt{r}}{d}+o\left(1/r\right)\Big{)}\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}\ll\frac{\lambda_{\max}^{\star
4/3}}{\sqrt{r}}\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2},$

where the last line follows from (119) that $\max_{i:i\neq
s}\big{\|}\bm{\Delta}^{t,(m)}_{i}\big{\|}_{2}\leq\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}\ll\lambda_{\max}^{\star
1/3}/\sqrt{r}$ and the low rank condition $r\ll\sqrt{d/\mu}$. Summing over
$s\in[r]$, we get

$\displaystyle\beta_{3}\ll\eta\lambda_{\min}^{\star
4/3}\left\|\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\right\|_{2}$
(139)

under the condition $\kappa\asymp 1$.

    * –

Turning attention to $\beta_{4}$, we observe that for each $s\in[r]$,

$\displaystyle\Big{|}\sum\nolimits_{i:i\neq
s}\Big{(}2\,\big{\langle}\bm{u}^{\star}_{i},\bm{u}^{\star}_{s}\big{\rangle}\big{\langle}\bm{\Delta}^{t,(m)}_{i},\bm{u}^{\star}_{s}\big{\rangle}+\big{\langle}\bm{\Delta}^{t,(m)}_{i},\bm{u}^{\star}_{s}\big{\rangle}^{2}\Big{)}\left(\bm{u}^{\star}_{i}\right)_{m}\Big{|}$
$\displaystyle\quad\lesssim\max_{i:i\neq
s}\big{|}\big{\langle}\bm{u}^{\star}_{i},\bm{u}^{\star}_{s}\big{\rangle}\big{|}\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}\sum\nolimits_{i:i\neq
s}\big{\|}\bm{\Delta}^{t,(m)}_{i}\big{\|}_{2}\left|\big{(}\bm{u}_{i}^{\star}\big{)}_{m}\right|+\big{\|}\bm{u}^{\star}_{s}\big{\|}_{2}^{2}\sum\nolimits_{i:i\neq
s}\big{\|}\bm{\Delta}^{t,(m)}_{i}\big{\|}_{2}^{2}\left|\big{(}\bm{u}_{i}^{\star}\big{)}_{m}\right|$
$\displaystyle\quad\leq\lambda_{\max}^{\star}\sqrt{\frac{\mu}{d}}\,\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}+\lambda_{\max}^{\star
2/3}\max_{i:i\neq
s}\big{\|}\bm{\Delta}^{t,(m)}_{i}\big{\|}_{2}\,\big{\|}\bm{U}^{\star}\big{\|}_{2,\infty}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}$
$\displaystyle\quad\lesssim\lambda_{\max}^{\star}\sqrt{\frac{\mu
r}{d}}\,\Big{(}\sqrt{\frac{\mu}{d}}\,\lambda_{\max}^{\star
1/3}+o(1/\sqrt{r})\Big{)}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}\ll\lambda_{\max}^{\star
4/3}\sqrt{\frac{\mu}{d}}\,\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}},$

where the last line follows from (119) and the rank assumption
$r\ll\sqrt{d/\mu}$. As a consequence,

$\displaystyle\beta_{4}\ll\eta\lambda_{\max}^{\star 4/3}\sqrt{\frac{\mu
r}{d}}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}.$
(140)

    * –

Therefore, we have

$\displaystyle\left\|\big{(}\widehat{\bm{U}}^{t+1,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\right\|_{2}$
$\displaystyle\leq\big{(}1-\frac{1}{3}\lambda_{\min}^{\star
4/3}\eta\big{)}\left\|\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\right\|_{2}+4\eta\lambda_{\max}^{\star
4/3}\sqrt{\frac{\mu
r}{d}}\,\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}.$
(141)

  * •

With regards to $\alpha_{2}$, it follows from the definition (46) and (134)
that

$\displaystyle\bm{U}^{t+1,\left(m\right)}-\widehat{\bm{U}}^{t+1,\left(m\right)}$
$\displaystyle=-\eta\left(\left(p^{-1}\mathcal{P}_{\Omega_{-m}}+\mathcal{P}_{m}\right)\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}-\left(p^{-1}\mathcal{P}_{\Omega_{-m}}+\mathcal{P}_{m}\right)\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\big{)}\times_{1}^{\mathsf{seq}}\bm{U}^{\star}\times_{2}^{\mathsf{seq}}\bm{U}^{\star}\right)$
$\displaystyle\quad+\frac{\eta}{p}\left(\mathcal{P}_{\Omega_{-m}}\left(\bm{E}\right)\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}-\mathcal{P}_{\Omega_{-m}}\left(\bm{E}\right)\times_{1}^{\mathsf{seq}}\bm{U}^{\star}\times_{2}^{\mathsf{seq}}\bm{U}^{\star}\right).$
(142)

Recall the definition of $\mathcal{P}_{\Omega_{-m}}$ and $\mathcal{P}_{m}$.
For the $m$-th row, we have

$\displaystyle\big{(}\bm{U}^{t+1,\left(m\right)}-\widehat{\bm{U}}^{t+1,\left(m\right)}\big{)}_{m,:}=-\eta\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}-\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\bm{U}^{\star}\times_{2}^{\mathsf{seq}}\bm{U}^{\star}\big{)}_{m,:}$

From the triangle inequality, we can further decompose

$\displaystyle\Big{\|}\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}-\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\bm{U}^{\star}\times_{2}^{\mathsf{seq}}\bm{U}^{\star}\big{)}_{m,:}\Big{\|}_{2}$
$\displaystyle\quad\leq\underbrace{\left\|\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}\times_{2}^{\mathsf{seq}}\bm{U}^{\star}\big{)}_{m,:}\right\|_{2}}_{=:\gamma_{1}}+\underbrace{\left\|\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\bm{U}^{\star}\times_{2}^{\mathsf{seq}}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}\big{)}_{m,:}\right\|_{2}}_{=:\gamma_{2}}$
$\displaystyle\quad\quad+\underbrace{\left\|\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}\times_{2}^{\mathsf{seq}}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}\big{)}_{m,:}\right\|_{2}}_{=:\gamma_{3}}.$

Let us consider $\gamma_{1}$ first. It is straightforward to calculate that

$\displaystyle\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}\bm{\Delta}^{t,\left(m\right)}_{s}\times_{2}\bm{u}^{\star}_{s}\big{)}_{m}=\sum_{i\in[r]}\big{\langle}\bm{u}_{i}^{t,\left(m\right)},\bm{\Delta}_{s}^{t,\left(m\right)}\big{\rangle}\big{\langle}\bm{u}_{i}^{t,\left(m\right)},\bm{u}_{s}^{\star}\big{\rangle}\big{(}\bm{\Delta}_{i}^{t,\left(m\right)}\big{)}_{m}$
$\displaystyle\quad+\sum_{i\in[r]}\Big{(}\big{\langle}\bm{\Delta}_{i}^{t,\left(m\right)},\bm{\Delta}_{s}^{t,\left(m\right)}\big{\rangle}\big{\langle}\bm{u}_{i}^{t,\left(m\right)},\bm{u}_{s}^{t,\left(m\right)}\big{\rangle}+\big{\langle}\bm{u}_{i}^{\star},\bm{\Delta}_{s}^{t,\left(m\right)}\big{\rangle}\big{\langle}\bm{\Delta}_{i}^{t,\left(m\right)},\bm{u}_{s}^{\star}\big{\rangle}+\big{\langle}\bm{\Delta}_{i}^{t,\left(m\right)},\bm{\Delta}_{s}^{t,\left(m\right)}\big{\rangle}\big{\langle}\bm{\Delta}_{i}^{t,\left(m\right)},\bm{u}_{s}^{t,\left(m\right)}\big{\rangle}\Big{)}\big{(}\bm{u}_{i}^{\star}\big{)}_{m}.$

for each $s\in[r]$. From (119), we use the triangle inequality and the Cauchy-
Schwarz inequality to upper bound

$\displaystyle\Big{|}\big{(}$
$\displaystyle\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}\bm{\Delta}^{t,\left(m\right)}_{s}\times_{2}\bm{u}^{\star}_{s}\big{)}_{m}\Big{|}\lesssim\big{\|}\bm{\Delta}_{s}^{t,\left(m\right)}\big{\|}_{2}\left\|\bm{u}_{s}^{\star}\right\|_{2}\sum_{i\in[r]}\big{\|}\bm{u}_{i}^{t,\left(m\right)}\big{\|}_{2}^{2}\left|\big{(}\bm{\Delta}_{i}^{t,\left(m\right)}\big{)}_{m}\right|$
$\displaystyle\quad+\big{\|}\bm{\Delta}_{s}^{t,\left(m\right)}\big{\|}_{2}\big{(}\left\|\bm{u}_{s}^{\star}\right\|_{2}+\big{\|}\bm{u}_{s}^{t,\left(m\right)}\big{\|}_{2}\big{)}\sum_{i\in[r]}\big{\|}\bm{\Delta}_{i}^{t,\left(m\right)}\big{\|}_{2}\big{(}\big{\|}\bm{u}_{i}^{t,\left(m\right)}\big{\|}_{2}+\left\|\bm{u}_{i}^{\star}\right\|_{2}+\big{\|}\bm{\Delta}_{i}^{t,\left(m\right)}\big{\|}_{2}\big{)}\left|\left(\bm{u}^{\star}_{i}\right)_{m}\right|$
$\displaystyle\lesssim\lambda_{\max}^{\star
2/3}\big{\|}\bm{\Delta}_{s}^{t,\left(m\right)}\big{\|}_{2}\sum_{i\in[r]}\big{\|}\bm{u}_{i}^{t,\left(m\right)}\big{\|}_{2}\left|\big{(}\bm{\Delta}_{i}^{t,\left(m\right)}\big{)}_{m}\right|+\lambda_{\max}^{\star
2/3}\sqrt{\frac{\mu}{d}}\,\big{\|}\bm{\Delta}_{s}^{t,\left(m\right)}\big{\|}_{2}\sum_{i\in[r]}\big{\|}\bm{\Delta}_{i}^{t,\left(m\right)}\big{\|}_{2}\big{\|}\bm{u}_{i}^{\star}\big{\|}_{2}$
$\displaystyle\lesssim\lambda_{\max}^{\star
2/3}\big{\|}\bm{\Delta}_{s}^{t,\left(m\right)}\big{\|}_{2}\big{\|}\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}+\lambda_{\max}^{\star
2/3}\sqrt{\frac{\mu}{d}}\,\big{\|}\bm{\Delta}_{s}^{t,\left(m\right)}\big{\|}_{2}\big{\|}\bm{U}^{\star}\big{\|}_{\mathrm{F}}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}$
$\displaystyle\lesssim\lambda_{\max}^{\star}\sqrt{r}\,\big{\|}\bm{\Delta}_{s}^{t,\left(m\right)}\big{\|}_{2}\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}+\lambda_{\max}^{\star}\sqrt{\frac{\mu
r}{d}}\,\big{\|}\bm{\Delta}_{s}^{t,\left(m\right)}\big{\|}_{2}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}$

We then sum over $s\in[r]$ to find that

$\displaystyle\left\|\left(\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}\times_{2}^{\mathsf{seq}}\bm{U}^{\star}\right)_{m,:}\right\|_{2}$
$\displaystyle\lesssim\lambda_{\max}^{\star}\sqrt{r}\,\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}$
$\displaystyle\quad+\lambda_{\max}^{\star}\sqrt{\frac{\mu
r}{d}}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}^{2},$
(143)

Moreover, it is easy to see that the upper bound also holds for $\gamma_{2}$.
As for $\gamma_{3}$, we can express

$\displaystyle\big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}\bm{\Delta}^{t,\left(m\right)}_{s}\times_{2}\bm{\Delta}^{t,\left(m\right)}_{s}\big{)}_{m}$
$\displaystyle=\sum_{i\in[r]}\Big{(}2\,\big{\langle}\bm{u}^{\star}_{i},\bm{\Delta}^{t,(m)}_{s}\big{\rangle}\big{\langle}\bm{\Delta}^{t,(m)}_{i},\bm{\Delta}^{t,(m)}_{s}\big{\rangle}+\big{\langle}\bm{\Delta}^{t,(m)}_{i},\bm{\Delta}^{t,(m)}_{s}\big{\rangle}^{2}\Big{)}\left(\bm{u}^{\star}_{i}\right)_{m}$
$\displaystyle\quad+\sum_{i\in[r]}\big{\langle}\bm{u}^{t,(m)}_{i},\bm{\Delta}^{t,(m)}_{s}\big{\rangle}^{2}\big{(}\bm{\Delta}_{i}^{t,\left(m\right)}\big{)}_{m}.$
(144)

Similarly, we combine (119) wtih the triangle inequality and the Cauchy-
Schwarz inequality to bound

$\displaystyle\Big{|}\Big{(}\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}\bm{\Delta}^{t,\left(m\right)}_{s}\times_{2}\bm{\Delta}^{t,\left(m\right)}_{s}\Big{)}_{m}\Big{|}$
$\displaystyle\quad\lesssim\big{\|}\bm{\Delta}^{t,(m)}_{s}\big{\|}_{2}^{2}\sum_{i\in[r]}\big{\|}\bm{\Delta}^{t,(m)}_{i}\big{\|}_{2}\left\|\bm{u}^{\star}_{i}\right\|_{2}\left|\left(\bm{u}^{\star}_{i}\right)_{m}\right|+\big{\|}\bm{\Delta}^{t,(m)}_{s}\big{\|}_{2}^{2}\sum_{i\in[r]}\big{\|}\bm{u}^{t,(m)}_{i}\big{\|}_{2}^{2}\left|\big{(}\bm{\Delta}_{i}^{t,\left(m\right)}\big{)}_{m}\right|$
$\displaystyle\quad\lesssim\lambda_{\max}^{\star
1/3}\big{\|}\bm{\Delta}^{t,(m)}_{s}\big{\|}_{2}^{2}\sum_{i\in[r]}\big{\|}\bm{\Delta}^{t,(m)}_{i}\big{\|}_{2}\left|\left(\bm{u}^{\star}_{i}\right)_{m}\right|+\lambda_{\max}^{\star
1/3}\big{\|}\bm{\Delta}^{t,(m)}_{s}\big{\|}_{2}^{2}\sum_{i\in[r]}\big{\|}\bm{u}^{t,(m)}_{i}\big{\|}_{2}\left|\big{(}\bm{\Delta}_{i}^{t,\left(m\right)}\big{)}_{m}\right|$
$\displaystyle\quad\leq\lambda_{\max}^{\star
1/3}\big{\|}\bm{\Delta}^{t,(m)}_{s}\big{\|}_{2}^{2}\left\|\bm{U}^{\star}\right\|_{2,\infty}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}+\lambda_{\max}^{\star
1/3}\big{\|}\bm{\Delta}^{t,(m)}_{s}\big{\|}_{2}^{2}\big{\|}\bm{U}^{t,\left(m\right)}\big{\|}_{\mathrm{F}}\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}$
$\displaystyle\quad\leq\lambda_{\max}^{\star
1/3}\left\|\bm{U}^{\star}\right\|_{2,\infty}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}^{2}\big{\|}\bm{\Delta}^{t,(m)}_{s}\big{\|}_{2}$
$\displaystyle\quad\quad+\lambda_{\max}^{\star
1/3}\left\|\bm{U}^{\star}\right\|_{\mathrm{F}}\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}\big{\|}\bm{\Delta}^{t,(m)}_{s}\big{\|}_{2}.$

Sum over $s\in[r]$ to obtain

$\displaystyle\left\|\left(\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}\times_{2}^{\mathsf{seq}}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}\right)_{m,:}\right\|_{2}$
$\displaystyle\qquad\leq\lambda_{\max}^{\star
1/3}\sqrt{r}\,\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}^{2}\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}+\lambda_{\max}^{\star
1/3}\sqrt{\frac{\mu
r}{d}}\,\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}^{3}.$

Since
$\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}\ll\lambda_{\max}^{\star
1/3}/\sqrt{r}\leq 1$ by (119), combined with (143), we find that

$\displaystyle\left\|\left(\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}\times_{2}^{\mathsf{seq}}\bm{U}^{t,\left(m\right)}-\bm{\Delta}^{t,\left(m\right)}_{\bm{T}}\times_{1}^{\mathsf{seq}}\bm{U}^{\star}\times_{2}^{\mathsf{seq}}\bm{U}^{\star}\right)_{m,:}\right\|_{2}$
$\displaystyle\qquad\lesssim\lambda_{\max}^{\star
1/3}\sqrt{r}\,\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}+\lambda_{\max}^{\star
1/3}\sqrt{\frac{\mu
r}{d}}\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}^{2}$
$\displaystyle\qquad\ll\lambda_{\min}^{\star
4/3}\big{\|}\big{(}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}+\lambda_{\min}^{\star
4/3}\sqrt{\frac{\mu
r}{d}}\,\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}.$
(145)

where the last inequality follows from the assumption that $\kappa\asymp 1$.

  * •

Putting (141) and (145) together, we reach the conclusion from (48) and the
condition $r\ll\sqrt{d/\mu}$ that,

$\displaystyle\Big{\|}\big{(}\bm{U}^{t+1,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\Big{\|}_{2}$
$\displaystyle\leq\big{(}1-\frac{1}{4}\lambda_{\min}^{\star
4/3}\eta\big{)}\,\big{\|}\big{(}\bm{U}^{t+1}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}+5\eta\lambda_{\min}^{\star
4/3}\sqrt{\frac{\mu
r}{d}}\,\big{\|}\bm{U}^{t,\left(m\right)}-\bm{U}^{\star}\big{\|}_{\mathrm{F}}$
$\displaystyle\leq\big{(}1-\frac{1}{4}\lambda_{\min}^{\star
4/3}\eta\big{)}\left(C_{7}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{8}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\quad+5\eta\lambda_{\min}^{\star
4/3}r\sqrt{\frac{\mu}{d}}\left(2C_{1}\rho^{t}\mathcal{E}_{\mathsf{local}}+2C_{2}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\leq\left(\big{(}1-\frac{1}{4}\lambda_{\min}^{\star
4/3}\eta\big{)}C_{7}+o\left(1\right)C_{1}\lambda_{\min}^{\star
4/3}\eta\right)\rho^{t}\mathcal{E}_{\mathsf{local}}\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\quad+\left(\big{(}1-\lambda_{\min}^{\star
4/3}\eta\big{)}C_{8}+o\left(1\right)C_{2}\lambda_{\min}^{\star
4/3}\eta\right)\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\leq\left(C_{7}\rho^{t+1}\mathcal{E}_{\mathsf{local}}+C_{8}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty},$

provided that $0<\eta\leq\lambda_{\min}^{\star
4/3}/\big{(}32\lambda_{\max}^{\star 8/3}\big{)}$, $1-\lambda_{\min}^{\star
4/3}\eta/5\leq\rho<1$, $C_{7},C_{8}$ are sufficiently large.

Recognizing that the above bound holds for any $1\leq m\leq d$, we conclude
the proof.

###  A.6 Proof of Lemma 5.6

It is easy to see that

$\displaystyle\begin{split}\big{\|}\big{(}\bm{U}^{t+1}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}&\leq\big{\|}\bm{U}^{t+1}-\bm{U}^{t+1,\left(m\right)}\big{\|}_{\mathrm{F}}+\big{\|}\big{(}\bm{U}^{t+1,\left(m\right)}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}.\end{split}$
(146)

Combining Lemma 5.4 and Lemma 5.5, we conclude that with probability at least
$1-O(d^{-10})$,

$\displaystyle\big{\|}\big{(}\bm{U}^{t+1}-\bm{U}^{\star}\big{)}_{m,:}\big{\|}_{2}$
$\displaystyle\leq\left(C_{5}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{6}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\quad\quad+\left(C_{7}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{8}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty}$
$\displaystyle\leq\left(C_{3}\rho^{t}\mathcal{E}_{\mathsf{local}}+C_{4}\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{d\log
d}{p}}\right)\left\|\bm{U}^{\star}\right\|_{2,\infty},$

with the proviso that $C_{3}/\left(C_{5}+C_{7}\right)$ and
$C_{4}/\left(C_{6}+C_{8}\right)$ are both sufficiently large.

##  Appendix B Proofs for retrieving tensor components

###  B.1 Proof of Lemma 5.12

We shall often operate upon the event where the claims in Lemma 5.7 hold,
which happens with very high probability (i.e. at least
$1-O\left(d^{-10}\right)$). Recall the definition of $\bm{\gamma}^{\star\tau}$
in (72). Since $\bm{\theta}^{\tau}=\bm{U}\bm{U}^{\top}\bm{g}^{\tau}$, this
allows us to write that: for each $1\leq i\leq r$,

$\displaystyle\gamma_{i}^{\star\tau}$
$\displaystyle=\lambda_{i}^{\star}\left\langle\bm{U}\bm{U}^{\top}\overline{\bm{u}}_{i}^{\star},\bm{g}^{\tau}\right\rangle,$

where we recall that $\lambda_{i}^{\star}=\|\bm{u}_{i}^{\star}\|_{2}^{3}$ and
$\overline{\bm{u}}_{i}^{\star}=\bm{u}_{i}^{\star}/\|\bm{u}_{i}^{\star}\|_{2}$.
Given that $\bm{g}^{\tau}$ is a Gaussian vector independent of $\bm{U}$, we
observe that $\bm{\gamma}^{\star\tau}$ is zero-mean Gaussian conditional on
$\Omega$ and $\bm{E}$. In order to understand the order statistics associated
with this vector, we first look at its covariance matrix.

Denote by $\bm{\Sigma}^{\tau}$ the covariance matrix of
$\bm{\gamma}^{\star\tau}$ (conditional on $\bm{U}$). Then we have

$\displaystyle\Sigma_{i,i}^{\tau}$ $\displaystyle=\lambda_{i}^{\star
2}\left\|\bm{U}\bm{U}^{\top}\overline{\bm{u}}_{i}^{\star}\right\|_{2}^{2}=\lambda_{i}^{\star
2}\left\|\mathcal{P}_{\bm{U}}\big{(}\overline{\bm{u}}_{i}^{\star}\big{)}\right\|_{2}^{2},$
(147a) $\displaystyle\Sigma_{i,j}^{\tau}$
$\displaystyle=\lambda_{i}^{\star}\lambda_{j}^{\star}\left\langle\bm{U}\bm{U}^{\top}\overline{\bm{u}}_{i}^{\star},\bm{U}\bm{U}^{\top}\overline{\bm{u}}_{j}^{\star}\right\rangle=\lambda_{i}^{\star}\lambda_{j}^{\star}\left\langle\overline{\bm{u}}_{i}^{\star},\mathcal{P}_{\bm{U}}\big{(}\overline{\bm{u}}_{j}^{\star}\big{)}\right\rangle$
$\displaystyle=\lambda_{i}^{\star}\lambda_{j}^{\star}\Big{(}\big{\langle}\overline{\bm{u}}_{i}^{\star},\overline{\bm{u}}_{j}^{\star}\big{\rangle}-\big{\langle}\overline{\bm{u}}_{i}^{\star},\mathcal{P}_{\bm{U}^{\perp}}\big{(}\overline{\bm{u}}_{j}^{\star}\big{)}\big{\rangle}\Big{)},$
(147b)

where we denote by $\mathcal{P}_{\bm{U}}(\bm{z})=\bm{U}\bm{U}^{\top}\bm{z}$
and
$\mathcal{P}_{\bm{U}^{\perp}}(\bm{z})=\left(\bm{I}-\bm{U}\bm{U}^{\top}\right)\bm{z}$.
In addition, since the unit vector $\overline{\bm{u}}_{i}^{\star}$ lies in the
span of the columns of $\bm{U}_{\mathsf{orth}}^{\star}$ (cf. (54)), it follows
from Lemma D.6 that

$\displaystyle\left\|\mathcal{P}_{\bm{U}}\big{(}\overline{\bm{u}}_{i}^{\star}\big{)}\right\|_{2}$
$\displaystyle=\big{\|}\bm{U}\bm{U}^{\top}\overline{\bm{u}}_{i}^{\star}\big{\|}_{2}=\big{\|}\bm{U}\bm{R}\left(\bm{U}\bm{R}\right)^{\top}\overline{\bm{u}}_{i}^{\star}\big{\|}_{2}\geq\sqrt{1-\left\|\bm{U}\bm{R}-\bm{U}_{\mathsf{orth}}^{\star}\right\|^{2}},$
(148a)
$\displaystyle\left\|\mathcal{P}_{\bm{U}^{\perp}}\big{(}\overline{\bm{u}}_{i}^{\star}\big{)}\right\|_{2}$
$\displaystyle=\big{\|}\big{(}\bm{I}-\bm{U}\bm{U}^{\top}\big{)}\overline{\bm{u}}_{i}^{\star}\big{\|}_{2}=\big{\|}\big{(}\bm{I}-\bm{U}\bm{R}\left(\bm{U}\bm{R}\right)^{\top}\big{)}\overline{\bm{u}}_{i}^{\star}\big{\|}_{2}\leq\left\|\bm{U}\bm{R}-\bm{U}_{\mathsf{orth}}^{\star}\right\|,$
(148b)

where $\bm{R}$ is a rotation matrix defined in (55). This together with (147a)
gives

$\displaystyle\lambda_{i}^{\star
2}\big{(}1-\left\|\bm{U}\bm{R}-\bm{U}_{\mathsf{orth}}^{\star}\right\|^{2}\big{)}\leq\Sigma_{i,i}^{\tau}\leq\lambda_{i}^{\star
2},$ (149)

where we have also used the fact that
$\left\|\mathcal{P}_{\bm{U}}\big{(}\overline{\bm{u}}_{i}^{\star}\big{)}\right\|_{2}\leq\left\|\overline{\bm{u}}_{i}^{\star}\right\|_{2}=1$.
Moreover, taking together (147a), (148b) and the incoherence condition, we see
that for any $1\leq i\neq j\leq r$,

$\displaystyle\left|\Sigma_{i,j}^{\tau}\right|$
$\displaystyle\leq\lambda_{i}^{\star}\lambda_{j}^{\star}\left\\{\left|\left\langle\overline{\bm{u}}_{i}^{\star},\overline{\bm{u}}_{j}^{\star}\right\rangle\right|+\left\|\overline{\bm{u}}_{i}^{\star}\right\|_{2}\left\|\mathcal{P}_{\bm{U}^{\perp}}\big{(}\overline{\bm{u}}_{j}^{\star}\big{)}\right\|_{2}\right\\}\leq\lambda_{i}^{\star}\lambda_{j}^{\star}\underbrace{\big{(}\sqrt{\mu/d}+\left\|\bm{U}\bm{R}-\bm{U}_{\mathsf{orth}}^{\star}\right\|\big{)}}_{=:\delta_{1}},$
(150)

which is expected to be small if $\delta_{1}$ is small.

From our assumptions on the sample size, the rank and the condition number, we
can invoke Lemma 5.7 to see that $\kappa r\delta_{1}\ll 1$, where $\delta_{1}$
is defined in (150) and
$\kappa=\lambda_{\max}^{\star}/\lambda_{\min}^{\star}$. Thus, we can decompose
$\bm{\Sigma}^{\tau}$ into two components as follows

$\displaystyle\bm{\Sigma}^{\tau}=\underbrace{\left(1-\kappa
r\delta_{1}\right)\bm{D}^{\star
2}}_{=:\,\widehat{\bm{\Sigma}}^{\tau}}+\underbrace{\bm{\Sigma}^{\tau}-\left(1-\kappa
r\delta_{1}\right)\bm{D}^{\star 2}}_{=:\,\breve{\bm{\Sigma}}^{\tau}},$

where

$\displaystyle\bm{D}^{\star}:=\mathsf{diag}\left(\lambda_{1}^{\star},\cdots,\lambda_{r}^{\star}\right)\in\mathbb{R}^{r\times
r}.$

As it turns out, both $\widehat{\bm{\Sigma}}^{\tau}$ and
$\breve{\bm{\Sigma}}^{\tau}$ are positive definite. Indeed, we first learn
from (149) and (150) that: the $i$-th digaonal entry of
$\breve{\bm{\Sigma}}^{\tau}$ obeys

$\displaystyle\breve{\Sigma}_{i,i}^{\tau}$
$\displaystyle\geq\lambda_{i}^{\star
2}\big{(}1-\left\|\bm{U}\bm{R}-\bm{U}_{\mathsf{orth}}^{\star}\right\|^{2}\big{)}-\left(1-\kappa
r\delta_{1}\right)\lambda_{i}^{\star 2}$ $\displaystyle=\lambda_{i}^{\star
2}\big{(}\kappa
r\delta_{1}-\left\|\bm{U}\bm{R}-\bm{U}_{\mathsf{orth}}^{\star}\right\|^{2}\big{)}\geq\lambda_{i}^{\star
2}\left(\kappa r\delta_{1}-\delta_{1}^{2}\right)$
$\displaystyle\overset{(\text{i})}{>}\kappa\lambda_{i}^{\star
2}\left(r-1\right)\delta_{1}\overset{\text{(ii)}}{\geq}\lambda_{i}^{\star}\lambda_{\max}^{\star}\left(r-1\right)\delta_{1}$
$\displaystyle\geq\sum_{j:j\neq i}\big{|}\breve{\Sigma}_{i,j}^{\tau}\big{|},$

where (i) holds since $\delta_{1}<1$ under our assumptions, (ii) follows since
$\kappa\lambda_{i}^{\star}\geq\kappa\lambda_{\min}^{\star}=\lambda_{\max}^{\star}$,
and the last line makes use of (150). This implies that
$\breve{\bm{\Sigma}}^{\tau}$ is diagonally dominant, and hence
$\breve{\bm{\Sigma}}^{\tau}\succeq\bm{0}$. In conclusion, both
$\widehat{\bm{\Sigma}}^{\tau}$ and $\breve{\bm{\Sigma}}^{\tau}$ are positive
definite.

Let $\widehat{\bm{\gamma}}^{\star\tau}$ and $\breve{\bm{\gamma}}^{\star\tau}$
be independent zero-mean Gaussian random vectors with covariance matrices
$\widehat{\bm{\Sigma}}^{\tau}$ and $\breve{\bm{\Sigma}}^{\tau}$, respectively.
Clearly, the distribution of $\bm{\gamma}^{\star\tau}$ is identical to that of
$\widehat{\bm{\gamma}}^{\star\tau}+\breve{\bm{\gamma}}^{\star\tau}$.
Consequently, it allows us to look at the distributions of these two random
vectors separately.

  * •

In view of (149) and the fact $\kappa r\delta_{1}<1$, one has

$\displaystyle\breve{\Sigma}_{i,i}^{\tau}\leq\lambda_{i}^{\star
2}-\left(1-\kappa r\delta_{1}\right)\lambda_{i}^{\star 2}=\kappa
r\delta_{1}\lambda_{i}^{\star 2}.$ (151)

Thus, with probability at least $1-O\left(d^{-10}\right)$, we have

$\displaystyle\left\|\breve{\bm{\gamma}}^{\star\tau}\right\|_{\infty}$
$\displaystyle\lesssim\mathbb{E}\Big{[}\max_{1\leq i\leq
r}\left|\breve{\gamma}_{i}^{\star\tau}\right|\Big{]}+\max_{1\leq i\leq
r}\sqrt{\mathsf{Var}\big{(}\breve{\gamma}_{i}^{\star\tau}\big{)}\log
d}\lesssim\lambda_{\max}^{\star}\sqrt{\kappa r\delta_{1}\log
d}\ll\lambda_{\min}^{\star}/\big{(}r\sqrt{\log d}\big{)},$ (152)

where the last step arises from $\kappa^{3}r^{3}\delta_{1}\log^{2}d\ll 1$
under our sample size, noise and rank conditions. By the condition that
$L\asymp r^{2\kappa^{2}}\log^{3/2}r$, $r\ll d$ and $\kappa\asymp 1$, we take a
union bound over $\tau\in\left[L\right]$ to find that each entry of
$\breve{\bm{\gamma}}^{\star\tau}$ is fairly small for all
$\tau\in\left[L\right]$. Another immediate consequence of (152) is that: for
any fixed vector $\bm{v}\in\mathbb{R}^{r}$, with probability at least
$1-O(d^{-10})$, for all $\tau\in\left[L\right]$,

$\displaystyle\left\|\breve{\bm{\gamma}}^{\star\tau}\right\|_{2}$
$\displaystyle\leq\sqrt{r}\left\|\breve{\bm{\gamma}}^{\star\tau}\right\|_{\infty}\ll\lambda_{\min}^{\star},$
(153a)
$\displaystyle\left|\left\langle\bm{v},\breve{\bm{\gamma}}^{\star\tau}\right\rangle\right|$
$\displaystyle\leq\left\|\bm{v}\right\|_{2}\left\|\breve{\bm{\gamma}}^{\star\tau}\right\|_{2}\ll\left\|\bm{v}\right\|_{2}\lambda_{\min}^{\star}.$
(153b)

  * •

We then turn attention to $\widehat{\bm{\gamma}}^{\star\tau}$, which is
composed of independent Gaussian random variables. Let us define
$\widehat{\Delta}^{\tau}:=\widehat{\gamma}_{1}^{\star\tau}-\max_{1<i\leq
r}\big{|}\widehat{\gamma}_{i}^{\star\tau}\big{|}$ for each $1\leq\tau\leq L$
and let
$\widehat{\Delta}_{1}^{\left(1\right)}\geq\widehat{\Delta}_{1}^{\left(2\right)}\geq\dots\geq\widehat{\Delta}_{1}^{\left(L\right)}$
denote the order statistics of
$\big{\\{}\widehat{\Delta}_{1}^{\tau}\big{\\}}_{\tau=1}^{L}$ in descending
order. Fix any small constant $\delta>0$. Invoke Lemma D.5 to demonstrate
that: with probability greater than $1-\delta/r$,

$\displaystyle\widehat{\Delta}_{1}^{\left(1\right)}$
$\displaystyle\gtrsim\lambda_{\min}^{\star},$ (154a)
$\displaystyle\widehat{\Delta}_{1}^{\left(1\right)}-\widehat{\Delta}_{1}^{\left(2\right)}$
$\displaystyle\gtrsim\frac{\lambda_{\min}^{\star}}{r\sqrt{\log d}},$ (154b)

where we use the conditions that $L\asymp r^{2\kappa^{2}}\log^{3/2}r$, $r\ll
d$ and $\kappa\asymp 1$. In addition, let
$\widehat{\bm{\gamma}}_{\smallsetminus
1}^{\star\tau}:=\big{[}\widehat{\gamma}_{2}^{\star\tau},\cdots,\widehat{\gamma}_{r}^{\star\tau}\big{]}^{\top}\in\mathbb{R}^{r-1}$.
We know from standard Gaussian concentration inequalities and union bounds
that for any fixed vector $\bm{v}\in\mathbb{R}^{r}$, with probability
$1-O(d^{-20})$, for all $\tau\in\left[L\right]$,

$\displaystyle\widehat{\gamma}_{1}^{\star\tau}$
$\displaystyle\lesssim\big{(}\sqrt{\log L}+\sqrt{\log
d}\big{)}\,\lambda_{\max}^{\star}\asymp\sqrt{\log d}\,\lambda_{\max}^{\star},$
(155a) $\displaystyle\big{\|}\widehat{\bm{\gamma}}^{\star\tau}\big{\|}_{2}$
$\displaystyle\leq\widehat{\gamma}_{1}^{\star\tau}+\big{\|}\widehat{\bm{\gamma}}_{\smallsetminus
1}^{\star\tau}\big{\|}_{2}\lesssim\big{(}\sqrt{\log d}+\sqrt{r\log
d}\big{)}\,\lambda_{\max}^{\star}\lesssim\sqrt{r\log
d}\,\lambda_{\max}^{\star},$ (155b)
$\displaystyle\big{|}\big{\langle}\bm{v},\widehat{\bm{\gamma}}^{\star\tau}\big{\rangle}\big{|}$
$\displaystyle\leq\widehat{\gamma}_{1}^{\star\tau}\left\|\bm{v}\right\|_{2}+\big{|}\big{\langle}\bm{v}_{\smallsetminus
1},\widehat{\bm{\gamma}}_{\smallsetminus
1}^{\star\tau}\big{\rangle}\big{|}\lesssim\left\|\bm{v}\right\|_{2}\sqrt{\log
d}\,\lambda_{\max}^{\star},$ (155c)

where $\bm{v}_{\smallsetminus
1}:=\left[v_{2},\cdots,\cdots,v_{r}\right]\in\mathbb{R}^{r-1}$.

  * •

Putting (152) and (154) together and invoking the triangle inequality
immediately establish (74a) and (74b). On the other hand, combining (152) with
(155a) proves (75a); (153a) and (155b) taken collectively establish (75b),
whereas (153b) and (155c) prove (75c).

###  B.2 Proof of Lemma 5.13

Recall that the vector of interest $\overline{\bm{u}}^{\tau}$ is the leading
singular vector of $\bm{M}^{\tau}$ (as constructed in (70c)), where
$\bm{M}^{\tau}$ satisfies

$\displaystyle\bm{M}^{\tau}$
$\displaystyle=p^{-1}\bm{T}\times_{3}\bm{\theta}^{\tau}=\bm{T}^{\star}\times_{3}\bm{\theta}^{\tau}+\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{3}\bm{\theta}^{\tau}$
$\displaystyle=\gamma_{1}^{\star\tau}\overline{\bm{u}}_{1}^{\star}\overline{\bm{u}}_{1}^{\star\top}+\sum_{s:s\neq
1}\gamma_{s}^{\star\tau}\overline{\bm{u}}_{s}^{\star}\overline{\bm{u}}_{s}^{\star\top}+\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{3}\bm{\theta}^{\tau}$
$\displaystyle=\underbrace{\gamma_{1}^{\star\tau}\overline{\bm{u}}_{1}^{\star}\overline{\bm{u}}_{1}^{\star\top}+\sum_{s:s\neq
1}\gamma_{s}^{\star\tau}\left(\bm{I}-\overline{\bm{u}}_{1}^{\star}\overline{\bm{u}}_{1}^{\star\top}\right)\overline{\bm{u}}_{s}^{\star}\overline{\bm{u}}_{s}^{\star\top}\left(\bm{I}-\overline{\bm{u}}_{1}^{\star}\overline{\bm{u}}_{1}^{\star\top}\right)}_{=:\,\bm{M}^{\star\tau}}$
$\displaystyle\qquad+\underbrace{\sum_{s:s\neq
1}\gamma_{s}^{\star\tau}\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle\left(\overline{\bm{u}}_{1}^{\star}\overline{\bm{u}}_{s}^{\star\top}+\overline{\bm{u}}_{s}^{\star}\overline{\bm{u}}_{1}^{\star\top}\right)-\sum_{s:s\neq
1}\gamma_{s}^{\star\tau}\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle^{2}\overline{\bm{u}}_{s}^{\star}\overline{\bm{u}}_{s}^{\star\top}}_{=:\,\bm{C}^{\tau}}+\underbrace{\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{3}\bm{\theta}^{\tau}}_{=:\,\bm{F}^{\tau}},$
(156)

and $\gamma_{i}^{\star\tau}\leavevmode\nobreak\ (1\leq i\leq r)$ is defined in
(72).

In what follows, we shall view $\bm{C}^{\tau}$ and $\bm{F}^{\tau}$ as
perturbation terms superimposed on $\bm{M}^{\star\tau}$. Lemma B.1 below
proves that their operator norms are all small under our sample size, noise
and rank conditions, which enables to apply Wedin’s theorem to justify the
$\ell_{2}$ proximity between $\overline{\bm{u}}^{\tau}$ and
$\overline{\bm{u}}_{1}^{\star}$.

######  Lemma B.1.

Instate the assumptions of Lemma 5.13. With probability at least
$1-O\left(d^{-10}\right)$, one has

$\displaystyle\big{\|}\bm{F}^{\tau}\big{\|}$
$\displaystyle\lesssim\frac{\sqrt{\mu
r}\,\lambda_{\max}^{\star}\log^{3}d}{d^{3/2}p}+\frac{\mu
r\lambda_{\max}^{\star}\log^{5/2}d}{d\sqrt{p}}+\frac{\sigma\log^{7/2}d}{p}+\sigma\sqrt{\frac{rd\log^{5}d}{p}},$
(157) $\displaystyle\big{\|}\bm{C}^{\tau}\big{\|}$
$\displaystyle\lesssim\sqrt{\frac{\mu r\log d}{d}}\,\lambda_{\max}^{\star},$
(158)
$\displaystyle\big{\|}\bm{F}^{\tau}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}$
$\displaystyle\lesssim\frac{\mu r\lambda_{\max}^{\star}\log
d}{d\sqrt{p}}+\sigma\sqrt{\frac{rd\log^{2}d}{p}},$ (159)
$\displaystyle\big{\|}\bm{C}^{\tau}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}$
$\displaystyle\lesssim\sqrt{\frac{\mu r\log d}{d}}\,\lambda_{\max}^{\star}.$
(160)

###### Proof.

See Appendix B.3.∎

As a consequence, recalling the definition of $\mathcal{E}_{\mathsf{op}}$ and
$\mathcal{E}_{\mathsf{proj}}$ in (81) and (79) respectively, one has

$\displaystyle\big{\|}\bm{M}^{\tau}-\bm{M}^{\star\tau}\big{\|}$
$\displaystyle\leq\big{\|}\bm{F}^{\tau}\big{\|}+\big{\|}\bm{C}^{\tau}\big{\|}$
$\displaystyle\lesssim\underbrace{\frac{\sqrt{\mu
r}\,\lambda_{\max}^{\star}\log^{3}d}{d^{3/2}p}+\frac{\mu
r\lambda_{\max}^{\star}\log^{5/2}d}{d\sqrt{p}}+\frac{\sigma\log^{7/2}d}{p}+\sigma\sqrt{\frac{rd\log^{5}d}{p}}+\sqrt{\frac{\mu
r\log
d}{d}}\,\lambda_{\max}^{\star}}_{=\,\mathcal{E}_{\mathsf{op}}\cdot\lambda_{\min}^{\star}},$
(161)

and

$\displaystyle\big{\|}\big{(}\bm{M}^{\tau}-\bm{M}^{\star\tau}\big{)}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}\leq\big{\|}\bm{F}^{\tau}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}+\big{\|}\bm{C}^{\tau}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}$
$\displaystyle\lesssim\underbrace{\frac{\mu r\lambda_{\max}^{\star}\log
d}{d\sqrt{p}}+\sigma\sqrt{\frac{rd\log^{2}d}{p}}+\sqrt{\frac{\mu r\log
d}{d}}\,\lambda_{\max}^{\star}}_{=\,\mathcal{E}_{\mathsf{proj}}\cdot\lambda_{\min}^{\star}}.$
(162)

It then follows from Weyl’s inequality that

$\displaystyle\max_{i\in\left[d\right]}$
$\displaystyle\left|\sigma_{i}\big{(}\bm{M}^{\tau}\big{)}-\sigma_{i}\big{(}\bm{M}^{\star\tau}\big{)}\right|\leq\big{\|}\bm{M}^{\tau}-\bm{M}^{\star\tau}\big{\|}\lesssim\mathcal{E}_{\mathsf{op}}\cdot\lambda_{\min}^{\star}\ll\lambda_{\min}^{\star}$
(163)

where $\sigma_{i}(\bm{Z})$ denotes the $i$-th largest singular value of a
matrix $\bm{Z}$ and we use the condition that $\mathcal{E}_{\mathsf{op}}\ll
1$. All in all, these arguments justify that the spectrum of $\bm{M}^{\tau}$
is fairly close to that of $\bm{M}^{\star\tau}$.

Next, we look at the gap between the two leading singular values of
$\bm{M}^{\star\tau}$. To begin with, it is self-evident from the definition of
$\bm{M}^{\star\tau}$ that: $\overline{\bm{u}}_{1}^{\star}$ is the singular
vector of $\bm{M}^{\star\tau}$. In fact, we claim one further result, that is,
$\overline{\bm{u}}_{1}^{\star}$ is indeed the leading singular vector of
$\bm{M}^{\star\tau}$ whose singular value is given by
$\sigma_{1}\big{(}\bm{M}^{\star\tau}\big{)}=\gamma_{1}^{\star\tau}$. Towards
this end, let us define

$\displaystyle\bm{U}_{\smallsetminus
1}^{\tau}:=\left(\bm{I}-\overline{\bm{u}}_{1}^{\star}\overline{\bm{u}}_{1}^{\star\top}\right)\overline{\bm{U}}^{\star}\in\mathbb{R}^{d\times\left(r-1\right)}\qquad\text{and}\qquad\bm{\gamma}_{\smallsetminus
1}^{\star\tau}:=\big{[}\gamma_{2}^{\star\tau},\cdots,\gamma_{r}^{\star\tau}\big{]}^{\top}\in\mathbb{R}^{r-1},$

allowing us to write

$\displaystyle\sum_{s:s\neq
1}\gamma_{s}^{\star\tau}\left(\bm{I}-\overline{\bm{u}}_{1}^{\star}\overline{\bm{u}}_{1}^{\star\top}\right)\overline{\bm{u}}_{s}^{\star}\overline{\bm{u}}_{s}^{\star\top}\left(\bm{I}-\overline{\bm{u}}_{1}^{\star}\overline{\bm{u}}_{1}^{\star\top}\right)=\bm{U}_{\smallsetminus
1}^{\tau}\mathsf{diag}\big{(}\bm{\gamma}_{\smallsetminus
1}^{\star\tau}\big{)}\bm{U}_{\smallsetminus
1}^{\tau\top}=:\,\bm{M}_{\smallsetminus 1}^{\star\tau}.$

We note that from Lemma D.1, one has

$\displaystyle\big{\|}\bm{U}_{\smallsetminus
1}^{\tau}\big{\|}=\big{\|}\left(\bm{I}-\overline{\bm{u}}_{1}^{\star}\overline{\bm{u}}_{1}^{\star\top}\right)\overline{\bm{U}}^{\star}\big{\|}\leq\big{\|}\overline{\bm{U}}^{\star}\big{\|}\leq\sqrt{1+r\sqrt{\mu/d}}.$

Let $|\gamma^{\star\tau}|_{(1)}\geq\dots\geq|\gamma^{\star\tau}|_{(r)}$ denote
the absolute values of $\\{\gamma_{i}^{\star\tau}\\}_{i=1}^{r}$ in descending
order. This together with Lemma 5.12 implies that

$\displaystyle\big{\|}\bm{M}_{\smallsetminus 1}^{\star\tau}\big{\|}$
$\displaystyle\leq\big{|}\gamma^{\star\tau}\big{|}_{(2)}\big{\|}\bm{U}_{\smallsetminus
1}^{\tau}\big{\|}^{2}\leq\big{|}\gamma^{\star\tau}\big{|}_{(2)}\big{(}1+r\sqrt{\mu/d}\big{)}$
$\displaystyle\leq\gamma_{1}^{\star\tau}-\big{(}\gamma_{1}^{\star\tau}-\big{|}\gamma^{\star\tau}\big{|}_{(2)}\big{)}+r\sqrt{\mu/d}\,\gamma_{1}^{\star\tau}<\gamma_{1}^{\star\tau},$

as long as $\kappa r\sqrt{(\mu\log d)/d}\ll 1$. Given that
$\overline{\bm{u}}_{1}^{\star}$ is the singular vector of $\bm{M}^{\star\tau}$
with singular value $\gamma_{1}^{\star\tau}$, we can conclude that
$\sigma_{1}\big{(}\bm{M}^{\star\tau}\big{)}=\gamma_{1}^{\star\tau}$. This also
allows us to lower bound the gap between the two largest singular values
$\bm{M}^{\star\tau}$ as follows

$\displaystyle\sigma_{1}\big{(}\bm{M}^{\star\tau}\big{)}-\sigma_{2}\big{(}\bm{M}^{\star\tau}\big{)}$
$\displaystyle\geq\gamma_{1}^{\star\tau}-\big{\|}\bm{M}_{\smallsetminus
1}^{\star\tau}\big{\|}\geq\gamma_{1}^{\star\tau}-\big{|}\gamma^{\star\tau}\big{|}_{(2)}\big{(}1+r\sqrt{\mu/d}\big{)}$
$\displaystyle\gtrsim\gamma_{1}^{\star\tau}-\big{|}\gamma^{\star\tau}\big{|}_{(2)}\gtrsim\lambda_{\min}^{\star},$
(164)

provided that $\kappa r\sqrt{(\mu\log d)/d}\ll 1$. We also know from (163) and
(164) that

$\displaystyle\sigma_{1}\big{(}\bm{M}^{\tau}\big{)}-\sigma_{2}\big{(}\bm{M}^{\tau}\big{)}\geq\sigma_{1}\big{(}\bm{M}^{\star\tau}\big{)}-\sigma_{2}\big{(}\bm{M}^{\star\tau}\big{)}-2\,\big{\|}\bm{M}^{\tau}-\bm{M}^{\star\tau}\big{\|}\gtrsim\lambda_{\min}^{\star}.$

Combined with (162) and Wedin’s theorem, we conclude that

$\displaystyle\big{\|}\overline{\bm{u}}^{\tau}-\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}$
$\displaystyle\leq\frac{\big{\|}\big{(}\bm{M}^{\tau}-\bm{M}^{\star\tau}\big{)}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}}{\sigma_{1}\big{(}\bm{M}^{\tau}\big{)}-\sigma_{2}\big{(}\bm{M}^{\tau}\big{)}-\big{\|}\bm{M}^{\tau}-\bm{M}^{\star\tau}\big{\|}}\lesssim\frac{\mu
r\log
d}{d\sqrt{p}}+\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{rd\log^{2}d}{p}}+\sqrt{\frac{\mu
r\log d}{d}}.$ (165)

Here, we have made use of the fact that $\overline{\bm{u}}^{\tau}$ is the
leading singular vector of $\bm{M}^{\tau}$ obeying
$\big{\langle}\overline{\bm{u}}^{\tau},\overline{\bm{u}}_{1}^{\star}\big{\rangle}\geq
0$.

###  B.3 Proof of Lemma B.1

####  B.3.1 Controlling $\bm{F}^{\tau}$

  * •

We first consider the spectral norm of $\bm{F}^{\tau}$. Recall the definition
that $\bm{\theta}^{\tau}=\bm{U}\bm{U}^{\top}\bm{g}^{\tau}$. Let us define

$\bm{\theta}^{\star\tau}:=\bm{U}_{\mathsf{orth}}^{\star}\bm{U}_{\mathsf{orth}}^{\star\top}\,\bm{g}^{\tau}$

and decompose

$\displaystyle\bm{F}^{\tau}=\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{3}\bm{\theta}^{\tau}=\underbrace{\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{3}\bm{\theta}^{\star\tau}}_{=:\,\bm{X}}+\underbrace{\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{3}\big{(}\bm{\theta}^{\tau}-\bm{\theta}^{\star\tau}\big{)}}_{=:\,\bm{Y}}.$

In the sequel, we shall control these two terms separately.

    * –

To bound $\left\|\bm{X}\right\|$, observe that $\bm{\theta}^{\star\tau}$ is
independent of $p^{-1}\bm{T}-\bm{T}^{\star}$. By Lemma D.4, one has

$\big{\|}\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{3}\bm{\theta}^{\star\tau}\big{\|}\lesssim\big{\|}\bm{\theta}^{\star\tau}\big{\|}_{\infty}\sqrt{\frac{\mu
r\log
d}{dp}}\,\lambda_{\max}^{\star}+\big{\|}\bm{\theta}^{\star\tau}\big{\|}_{\infty}\frac{\sigma\log^{5/2}d}{p}+\big{\|}\bm{\theta}^{\star\tau}\big{\|}_{2}\sigma\sqrt{\frac{d\log
d}{p}}.$ (166)

This suggests that we need to control the $\ell_{\infty}$ and $\ell_{2}$ norms
of $\bm{\theta}^{\star\tau}$. Using standard results on Gaussian random
vectors and Lemma D.1, we know that with probability at least
$1-O\left(d^{-20}\right)$,

$\displaystyle\big{\|}\bm{\theta}^{\star\tau}\big{\|}_{\infty}$
$\displaystyle=\big{\|}\bm{U}_{\mathsf{orth}}^{\star}\bm{U}_{\mathsf{orth}}^{\star\top}\,\bm{g}^{\tau}\big{\|}_{\infty}\lesssim\left\|\bm{U}_{\mathsf{orth}}^{\star}\right\|_{2,\infty}\sqrt{\log
d}\leq\sqrt{\frac{\mu r\log d}{d}},$ (167)
$\displaystyle\big{\|}\bm{\theta}^{\star\tau}\big{\|}_{2}$
$\displaystyle=\big{\|}\bm{U}_{\mathsf{orth}}^{\star}\bm{U}_{\mathsf{orth}}^{\star\top}\,\bm{g}^{\tau}\big{\|}_{2}\lesssim\left\|\bm{U}_{\mathsf{orth}}^{\star}\right\|_{\mathrm{F}}\sqrt{\log
d}=\sqrt{r\log d}.$ (168)

Combining (166) with (167) and (168) reveals that with probability exceeding
$1-O\left(d^{-20}\right)$,

$\displaystyle\big{\|}\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{3}\bm{\theta}^{\star\tau}\big{\|}$
$\displaystyle\lesssim\frac{\mu r\lambda_{\max}^{\star}\log
d}{d\sqrt{p}}+\frac{\sigma}{p}\sqrt{\frac{\mu
r\log^{6}d}{d}}+\sigma\sqrt{\frac{rd\log^{2}d}{p}}$
$\displaystyle\asymp\frac{\mu r\lambda_{\max}^{\star}\log
d}{d\sqrt{p}}+\sigma\sqrt{\frac{rd\log^{2}d}{p}},$ (169)

where the last inequality holds as long as $p\gtrsim\mu d^{-2}\log^{4}d$.

    * –

Turning to $\bm{Y}$, we can simply upper bound

$\displaystyle\big{\|}\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{3}\big{(}\bm{\theta}^{\tau}-\bm{\theta}^{\star\tau}\big{)}\big{\|}$
$\displaystyle\leq\left\|p^{-1}\bm{T}-\bm{T}^{\star}\right\|\big{\|}\bm{\theta}^{\tau}-\bm{\theta}^{\star\tau}\big{\|}_{2}.$

Since
$\mathsf{rank}\left(\bm{U}\bm{U}^{\top}-\bm{U}_{\mathsf{orth}}^{\star}\bm{U}_{\mathsf{orth}}^{\star\top}\right)\leq
2r$, Lemma 5.7 and the standard result of Gaussian random vectors yields that:
with probability at least $1-O\left(d^{-12}\right)$,

$\displaystyle\big{\|}\bm{\theta}^{\tau}-\bm{\theta}^{\star\tau}\big{\|}_{2}$
$\displaystyle=\left\|\left(\bm{U}\bm{U}^{\top}-\bm{U}_{\mathsf{orth}}^{\star}\bm{U}_{\mathsf{orth}}^{\star\top}\right)\bm{g}^{\tau}\right\|_{2}\lesssim\left\|\bm{U}\bm{U}^{\top}-\bm{U}_{\mathsf{orth}}^{\star}\bm{U}_{\mathsf{orth}}^{\star\top}\right\|_{\mathrm{F}}\sqrt{\log
d}$
$\displaystyle\leq\left\|\bm{U}\bm{U}^{\top}-\bm{U}_{\mathsf{orth}}^{\star}\bm{U}_{\mathsf{orth}}^{\star\top}\right\|\sqrt{2r\log
d}\lesssim\mathcal{E}_{\mathsf{se}}\sqrt{r\log d}\ll 1,$ (170)

where we recall the definition of $\mathcal{E}_{\mathsf{se}}$ in (57) and that
$\mathcal{E}_{\mathsf{se}}\ll 1/\sqrt{r\log d}$ by our conditions. Moreover,
by Lemma D.2, we know that with probability exceeding
$1-O\left(d^{-10}\right)$,

$\displaystyle\left\|p^{-1}\bm{T}-\bm{T}^{\star}\right\|$
$\displaystyle\leq\left\|p^{-1}\mathcal{P}_{\Omega}\left(\bm{T}^{\star}\right)-\bm{T}^{\star}\right\|+\left\|p^{-1}\mathcal{P}_{\Omega}\left(\bm{E}\right)\right\|$
$\displaystyle\lesssim\frac{\sqrt{\mu
r}\,\lambda_{\max}^{\star}\log^{3}d}{d^{3/2}p}+\frac{\mu\sqrt{r}\,\lambda_{\max}^{\star}\log^{5/2}d}{d\sqrt{p}}+\frac{\sigma\log^{7/2}d}{p}+\sigma\sqrt{\frac{d\log^{5}d}{p}}.$
(171)

Combining (170) and (171), we find that

$\displaystyle\big{\|}\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{3}\big{(}\bm{\theta}^{\tau}-\bm{\theta}^{\star\tau}\big{)}\big{\|}$
$\displaystyle\lesssim\frac{\sqrt{\mu
r}\,\lambda_{\max}^{\star}\log^{3}d}{d^{3/2}p}+\frac{\mu\sqrt{r}\,\lambda_{\max}^{\star}\log^{5/2}d}{d\sqrt{p}}+\frac{\sigma\log^{7/2}d}{p}+\sigma\sqrt{\frac{d\log^{5}d}{p}}.$
(172)

Putting (169) and (172) together shows that

$\displaystyle\big{\|}\bm{F}^{\tau}\big{\|}\lesssim\frac{\sqrt{\mu
r}\,\lambda_{\max}^{\star}\log^{3}d}{d^{3/2}p}+\frac{\mu
r\lambda_{\max}^{\star}\log^{5/2}d}{d\sqrt{p}}+\frac{\sigma\log^{7/2}d}{p}+\sigma\sqrt{\frac{rd\log^{5}d}{p}}.$

  * •

Next, we turn to
$\big{\|}\bm{F}^{\tau}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}$. By the
definition of the operator norm, we know that

$\displaystyle\big{\|}\bm{F}^{\tau}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}$
$\displaystyle=\left\|\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{2}\overline{\bm{u}}_{1}^{\star}\times_{3}\bm{\theta}^{\tau}\right\|_{2}\leq\left\|\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{2}\overline{\bm{u}}_{1}^{\star}\right\|\big{\|}\bm{\theta}^{\tau}\big{\|}_{2}.$

Applying Lemma D.4 again reveals that with probability at least
$1-O\left(d^{-12}\right)$,

$\displaystyle\left\|\left(p^{-1}\bm{T}-\bm{T}^{\star}\right)\times_{2}\overline{\bm{u}}_{1}^{\star}\right\|$
$\displaystyle\lesssim\left\|\overline{\bm{u}}_{1}^{\star}\right\|_{\infty}\sqrt{\frac{\mu
r\log
d}{dp}}\,\lambda_{\max}^{\star}+\left\|\overline{\bm{u}}_{1}^{\star}\right\|_{\infty}\frac{\sigma\log^{5/2}d}{p}+\left\|\overline{\bm{u}}_{1}^{\star}\right\|_{2}\sigma\sqrt{\frac{d\log
d}{p}}$
$\displaystyle\lesssim\frac{\mu\sqrt{r}\,\lambda_{\max}^{\star}\sqrt{\log
d}}{d\sqrt{p}}+\frac{\sigma\sqrt{\mu\log^{5}d}}{\sqrt{d}\,p}+\sigma\sqrt{\frac{d\log
d}{p}}$
$\displaystyle\asymp\frac{\mu\sqrt{r}\,\lambda_{\max}^{\star}\sqrt{\log
d}}{d\sqrt{p}}+\sigma\sqrt{\frac{d\log d}{p}},$ (173)

where the last step arises from the condition that $p\gtrsim\mu
d^{-2}\log^{4}d$. In addition, realizing that $\bm{U}$ consists of
eigenvectors, standard Gaussian random vectors results give that with
probability at least $1-O\left(d^{-12}\right)$,

$\left\|\bm{\theta}^{\tau}\right\|_{2}=\big{\|}\bm{U}\bm{U}^{\top}\bm{g}^{\tau}\big{\|}_{2}\lesssim\left\|\bm{U}\right\|_{\mathrm{F}}\sqrt{\log
d}=\sqrt{r\log d}.$ (174)

Combining (173) and (174) shows that with probability exceeding
$1-O\left(d^{-10}\right)$,

$\displaystyle\big{\|}\bm{F}^{\tau}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}\lesssim\frac{\mu
r\lambda_{\max}^{\star}\log d}{d\sqrt{p}}+\sigma\sqrt{\frac{rd\log^{2}d}{p}}.$

####  B.3.2 Controlling $\bm{C}^{\tau}$

Recall the definition of $\bm{C}^{\tau}$ in (156). We first consider the
spectral norm of $\bm{C}^{\tau}$. It is straightforward to compute that

$\displaystyle\big{\|}\bm{C}^{\tau}\big{\|}$ $\displaystyle\leq
2\,\Big{\|}\sum\nolimits_{s:s\neq
1}\gamma_{s}^{\star\tau}\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle\overline{\bm{u}}_{s}^{\star}\Big{\|}_{2}+\Big{|}\sum\nolimits_{s:s\neq
1}\gamma_{s}^{\star\tau}\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle^{2}\Big{|}$
$\displaystyle\lesssim\max_{s:s\neq
1}\left|\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle\right|\big{\|}\overline{\bm{U}}^{\star}\big{\|}\big{\|}\bm{\gamma}^{\star\tau}\big{\|}_{2}+\max_{s:s\neq
1}\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle^{2}\sqrt{r}\big{\|}\bm{\gamma}^{\star\tau}\big{\|}_{2}$
$\displaystyle\lesssim\Big{(}\sqrt{\frac{\mu}{d}}+\frac{\mu\sqrt{r}}{d}\Big{)}\sqrt{r\log
d}\,\lambda_{\max}^{\star}\asymp\sqrt{\frac{\mu r\log
d}{d}}\,\lambda_{\max}^{\star}$ (175)

if $\mu r/d\lesssim 1$, where we recall that
$\overline{\bm{U}}^{\star}=\left[\overline{\bm{u}}_{1}^{\star},\cdots,\overline{\bm{u}}_{r}^{\star}\right]$.
Here, the last line holds owing to (8c), Lemma D.1 (which justifies that
$\big{\|}\overline{\bm{U}}^{\star}\big{\|}\lesssim 1$ if $r\sqrt{\mu/d}\leq
1$) and Lemma 5.12.

The claim (160) arises from the definition of the spectral norm that
$\big{\|}\bm{C}^{\tau}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}\leq\big{\|}\bm{C}^{\tau}\big{\|}$.

###  B.4 Proof of Lemma 5.14

Let us fix an arbitrary $m\in\left[d\right]$. We remind the readers of several
definitions: (1) $\gamma_{1}^{\star\tau}$: see (72); (2) $\bm{M}^{\star\tau}$:
see (156); and (3) $\bm{M}^{\tau,\left(m\right)}$: see (70d).

Before continuing, we state two immediate facts. First, it has already been
observed in Appendix B.2 that $\overline{\bm{u}}_{1}^{\star}$ is a singular
vector of $\bm{M}^{\star\tau}$ with singular value $\gamma_{1}^{\star\tau}$,
and hence

$\displaystyle\big{(}\overline{\bm{u}}_{1}^{\star}\big{)}_{m}$
$\displaystyle=\big{(}\gamma_{1}^{\star\tau}\big{)}^{-1}\bm{M}_{m,:}^{\star\tau}\overline{\bm{u}}_{1}^{\star}.$
(176)

Here and throughout, $\bm{A}_{m,:}$ denotes the $m$-th row of a matrix
$\bm{A}$. Second, $\overline{\bm{u}}^{\tau,\left(m\right)}$ is the top
singular vector of $\bm{M}^{\tau,\left(m\right)}$ such that
$\langle\overline{\bm{u}}^{\tau,\left(m\right)},\overline{\bm{u}}_{1}^{\star}\rangle\geq
0$, and we denote by $\gamma_{\tau}^{(m)}$ the associated singular value.
Recall our definition of $\bm{\nu}^{\tau,\left(m\right)}$ in Algorithm 6.
Similar to the case of $\bm{\nu}^{\tau}$, we will show shortly in Lemma 5.16
that the global signs of $\bm{\nu}^{\tau,\left(m\right)}$ and
$\overline{\bm{u}}^{\tau,\left(m\right)}$ coincide, and hence

$\displaystyle\bm{\nu}^{\tau,\left(m\right)}=\overline{\bm{u}}^{\tau,\left(m\right)}.$
(177)

As a result, the proof of this lemma boils down to showing that
$\overline{\bm{u}}^{\tau,\left(m\right)}$ (and hence
$\bm{\nu}^{\tau,\left(m\right)}$) is sufficiently close to
$\overline{\bm{u}}_{1}^{\star}$ in the $m$-th entry. Towards this end, observe
that

$\displaystyle\big{(}\overline{\bm{u}}^{\tau,\left(m\right)}\big{)}_{m}$
$\displaystyle=\big{(}\gamma_{\tau}^{(m)}\big{)}^{-1}\bm{M}_{m,:}^{\tau,\left(m\right)}\overline{\bm{u}}^{\tau,\left(m\right)}.$
(178)

The above two facts (176) and (178) together with the triangle inequality lead
to

$\displaystyle\Big{|}\big{(}\overline{\bm{u}}^{\tau,\left(m\right)}-\overline{\bm{u}}_{1}^{\star}\big{)}_{m}\Big{|}$
$\displaystyle\leq\left|\Big{\\{}\big{(}\gamma_{\tau}^{(m)}\big{)}^{-1}-\big{(}\gamma_{1}^{\star\tau}\big{)}^{-1}\Big{\\}}\bm{M}_{m,:}^{\tau,\left(m\right)}\overline{\bm{u}}^{\tau,\left(m\right)}\right|$
$\displaystyle\quad+\big{(}\gamma_{1}^{\star\tau}\big{)}^{-1}\left|\big{(}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{)}_{m,:}\overline{\bm{u}}^{\tau,\left(m\right)}\right|$
$\displaystyle\quad+\big{(}\gamma_{1}^{\star\tau}\big{)}^{-1}\left|\bm{M}_{m,:}^{\star\tau}\big{(}\overline{\bm{u}}^{\tau,\left(m\right)}-\overline{\bm{u}}_{1}^{\star}\big{)}\right|$
$\displaystyle\leq\underbrace{\left|\big{(}\gamma_{\tau}^{(m)}\big{)}^{-1}-\big{(}\gamma_{1}^{\star\tau}\big{)}^{-1}\right|\big{\|}\bm{M}_{m,:}^{\tau,\left(m\right)}\big{\|}_{2}\big{\|}\overline{\bm{u}}^{\tau,\left(m\right)}\big{\|}_{2}}_{=:\,\alpha_{1}}$
$\displaystyle\quad+\underbrace{\big{(}\gamma_{1}^{\star\tau}\big{)}^{-1}\big{\|}\big{(}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{)}_{m,:}\big{\|}_{2}\big{\|}\overline{\bm{u}}^{\tau,\left(m\right)}\big{\|}_{2}}_{=:\,\alpha_{2}}$
$\displaystyle\quad+\underbrace{\big{(}\gamma_{1}^{\star\tau}\big{)}^{-1}\big{\|}\bm{M}_{m,:}^{\star\tau}\big{\|}_{2}\big{\|}\overline{\bm{u}}^{\tau,\left(m\right)}-\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}}_{=:\,\alpha_{3}}.$
(179)

Therefore, it suffices to upper bound the above three quantities separately.

####  B.4.1 Controlling $\alpha_{3}$

The first step to bound $\alpha_{3}$ (cf. (179)) is to control
$\big{\|}\bm{M}_{m,:}^{\star\tau}\big{\|}_{2}$. Towards this end, we first
observe from the incoherence conditions that

$\displaystyle\max_{s:s\neq
1}\big{|}\left(\overline{\bm{u}}_{s}^{\star}-\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle\overline{\bm{u}}_{1}^{\star}\right)_{m}\big{|}$
$\displaystyle\leq\max_{s:s\neq
1}\left\|\overline{\bm{u}}_{s}^{\star}\right\|_{\infty}+\max_{s:s\neq
1}\big{|}\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle\big{|}\left\|\overline{\bm{u}}_{1}^{\star}\right\|_{\infty}$
$\displaystyle\leq\max_{s:s\neq
1}\left\|\overline{\bm{u}}_{s}^{\star}\right\|_{\infty}+\max_{s:s\neq
1}\left\|\overline{\bm{u}}_{s}^{\star}\right\|_{2}\left\|\overline{\bm{u}}_{1}^{\star}\right\|_{2}\left\|\overline{\bm{u}}_{1}^{\star}\right\|_{\infty}\lesssim\sqrt{\frac{\mu}{d}}.$
(180)

When combined with the definition (156), this gives

$\displaystyle\big{\|}\bm{M}_{m,:}^{\star\tau}\big{\|}_{2}$
$\displaystyle=\Big{\|}\gamma_{1}^{\star\tau}\left(\overline{\bm{u}}_{1}^{\star}\right)_{m}\overline{\bm{u}}_{1}^{\star\top}+\sum\nolimits_{s:s\neq
1}\gamma_{s}^{\star\tau}\left(\overline{\bm{u}}_{s}^{\star}-\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle\overline{\bm{u}}_{1}^{\star}\right)_{m}\overline{\bm{u}}_{s}^{\star\top}\left(\bm{I}-\overline{\bm{u}}_{1}^{\star}\overline{\bm{u}}_{1}^{\star\top}\right)\Big{\|}_{2}$
$\displaystyle\leq\gamma_{1}^{\star\tau}\left\|\overline{\bm{u}}_{1}^{\star}\right\|_{\infty}\left\|\overline{\bm{u}}_{1}^{\star}\right\|_{2}+\Big{\|}\sum\nolimits_{s:s\neq
1}\gamma_{s}^{\star\tau}\left(\overline{\bm{u}}_{s}^{\star}-\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle\overline{\bm{u}}_{1}^{\star}\right)_{m}\overline{\bm{u}}_{s}^{\star\top}\Big{\|}_{2}$
$\displaystyle\leq\gamma_{1}^{\star\tau}\left\|\overline{\bm{u}}_{1}^{\star}\right\|_{\infty}+\max_{s:s\neq
1}\big{|}\left(\overline{\bm{u}}_{s}^{\star}-\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle\overline{\bm{u}}_{1}^{\star}\right)_{m}\big{|}\big{\|}\bm{\gamma}^{\star\tau}\big{\|}_{2}\big{\|}\overline{\bm{U}}^{\star}\big{\|}$
$\displaystyle\overset{(\text{i})}{\lesssim}\gamma_{1}^{\star\tau}\sqrt{\frac{\mu}{d}}+\big{\|}\bm{\gamma}^{\star\tau}\big{\|}_{2}\sqrt{\frac{\mu}{d}}\asymp\big{\|}\bm{\gamma}^{\star\tau}\big{\|}_{2}\sqrt{\frac{\mu}{d}}\lesssim\sqrt{\frac{\mu
r\log d}{d}}\,\lambda_{\max}^{\star},$ (181)

where (i) arises from (180) and
$\big{\|}\overline{\bm{U}}^{\star}\big{\|}\lesssim 1$ if $r\sqrt{\mu/d}\ll 1$,
and the last step comes from Lemma 5.12.

The second step is to upper bound
$\big{\|}\overline{\bm{u}}^{\tau,\left(m\right)}-\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}$.
Towards this, we resort to Wedin’s theorem as follows

$\displaystyle\big{\|}\overline{\bm{u}}^{\tau,\left(m\right)}-\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}\leq\frac{\big{\|}\big{(}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{)}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}}{\sigma_{1}\big{(}\bm{M}^{\star\tau}\big{)}-\sigma_{2}\big{(}\bm{M}^{\star\tau}\big{)}-\big{\|}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{\|}},$
(182)

where we rely on the fact that
$\big{\langle}\overline{\bm{u}}^{\tau,\left(m\right)},\overline{\bm{u}}_{1}^{\star}\big{\rangle}\geq
0$. To complete this bound, we need to control
$\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}$. Before we move on, we find
it helpful to introduce

$\displaystyle\widehat{\bm{M}}^{\tau,\left(m\right)}:=p^{-1}\bm{T}\times_{3}\bm{\theta}^{\tau,\left(m\right)}.$
(183)

Let $\widehat{\bm{u}}^{\tau,\left(m\right)}$ denote the top left singular
vector of $\widehat{\bm{M}}^{\tau,\left(m\right)}$ such that

$\displaystyle\big{\langle}\widehat{\bm{u}}^{\tau,\left(m\right)},\overline{\bm{u}}_{1}^{\star}\big{\rangle}\geq
0.$ (184)

Since we have already bounded
$\big{\|}\bm{M}^{\tau}-\bm{M}^{\star\tau}\big{\|}$ in Lemma B.1, we can
decompose

$\displaystyle\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}=\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\tau}+\bm{M}^{\tau}-\bm{M}^{\star\tau}=\bm{M}^{\tau,\left(m\right)}-\widehat{\bm{M}}^{\tau,\left(m\right)}+\widehat{\bm{M}}^{\tau,\left(m\right)}-\bm{M}^{\tau}+\bm{M}^{\tau}-\bm{M}^{\star\tau}.$

With these definitions in place, Lemma B.2 below provides the desired bounds.

######  Lemma B.2.

Instate the assumptions of Lemma 5.14. With probability at least
$1-O\left(d^{-10}\right)$, the following holds simultaneously for all $1\leq
m\leq d$:

$\displaystyle\big{\|}\widehat{\bm{M}}^{\tau,\left(m\right)}-\bm{M}^{\tau,\left(m\right)}\big{\|}$
$\displaystyle\lesssim\frac{\mu r\lambda_{\max}^{\star}\sqrt{\log
d}}{d\sqrt{p}}+\sigma\sqrt{\frac{rd\log d}{p}},$ (185)
$\displaystyle\big{\|}\widehat{\bm{M}}^{\tau,\left(m\right)}-\bm{M}^{\tau}\big{\|}$
$\displaystyle\lesssim\mathcal{E}_{\mathsf{loo}}\sqrt{\frac{\mu r\log
d}{d}}\lambda_{\max}^{\star},$ (186)

where $\mathcal{E}_{\mathsf{loo}}$ is defined in (65). As a result, one has

$\displaystyle\big{\|}\big{(}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{)}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}\leq\big{\|}\bm{M}^{\tau}-\bm{M}^{\tau,\left(m\right)}\big{\|}\lesssim\frac{\mu
r\lambda_{\max}^{\star}\sqrt{\log d}}{d\sqrt{p}}+\sigma\sqrt{\frac{rd\log
d}{p}}.$ (187)

###### Proof.

See Appendix B.5.∎

We then can further combine (161) and (162) to deduce that

$\displaystyle\begin{split}\big{\|}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{\|}&\leq\big{\|}\bm{M}^{\tau}-\bm{M}^{\tau,\left(m\right)}\big{\|}+\big{\|}\bm{M}^{\tau}-\bm{M}^{\star\tau}\big{\|}\\\
&\lesssim\underbrace{\frac{\sqrt{\mu
r}\,\lambda_{\max}^{\star}\log^{3}d}{d^{3/2}p}+\frac{\mu
r\lambda_{\max}^{\star}\log^{5/2}d}{d\sqrt{p}}+\frac{\sigma\log^{7/2}d}{p}+\sigma\sqrt{\frac{rd\log^{5}d}{p}}+\sqrt{\frac{\mu
r\log
d}{d}}\,\lambda_{\max}^{\star}}_{=\,\mathcal{E}_{\mathsf{op}}\cdot\lambda_{\min}^{\star}},\end{split}$
(188)

and

$\displaystyle\big{\|}\big{(}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{)}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}\lesssim\underbrace{\frac{\mu
r\lambda_{\max}^{\star}\log
d}{d\sqrt{p}}+\sigma\sqrt{\frac{rd\log^{2}d}{p}}+\sqrt{\frac{\mu r\log
d}{d}}\,\lambda_{\max}^{\star}}_{=\,\mathcal{E}_{\mathsf{proj}}\cdot\lambda_{\min}^{\star}}.$
(189)

In particular, we have
$\big{\|}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{\|}\ll\lambda_{\min}^{\star}$
under our conditions, and it follows from (164) that

$\displaystyle\sigma_{1}\big{(}\bm{M}^{\star\tau}\big{)}-\sigma_{2}\big{(}\bm{M}^{\star\tau}\big{)}-\big{\|}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{\|}\gtrsim\lambda_{\min}^{\star}.$

Invoke the bound (182) to obtain

$\displaystyle\big{\|}\overline{\bm{u}}^{\tau,\left(m\right)}-\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}\lesssim\frac{1}{\lambda_{\min}^{\star}}\big{\|}\big{(}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{)}\overline{\bm{u}}_{1}^{\star}\big{\|}_{2}\lesssim\underbrace{\frac{\mu
r\log
d}{d\sqrt{p}}+\frac{\sigma}{\lambda_{\min}^{\star}}\sqrt{\frac{rd\log^{2}d}{p}}+\sqrt{\frac{\mu
r\log d}{d}}}_{=\,\mathcal{E}_{\mathsf{proj}}}.$ (190)

To finish up, combine this with (181) and the spectral condition to arrive at

$\displaystyle\alpha_{3}\lesssim\mathcal{E}_{\mathsf{proj}}\sqrt{\frac{\mu
r\log d}{d}}\lesssim\mathcal{E}_{\mathsf{op}}\sqrt{\frac{\mu r\log d}{d}},$
(191)

which results from the fact that
$\mathcal{E}_{\mathsf{proj}}\leq\mathcal{E}_{\mathsf{op}}$ (cf. (81)).

####  B.4.2 Controlling $\alpha_{2}$

We then turn to $\alpha_{2}$ (cf. (179)). Recall the definition of
$\bm{M}^{\tau,\left(m\right)}$ in (70c). It is straightforward to verify that

$\displaystyle\big{(}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{)}_{m,:}$
$\displaystyle=\big{(}p^{-1}\bm{T}^{\tau,\left(m\right)}\times_{3}\bm{\theta}^{\tau,\left(m\right)}-\bm{T}^{\star}\times_{3}\bm{\theta}^{\tau}\big{)}_{m,:}+\big{(}\bm{T}^{\star}\times_{3}\bm{\theta}^{\tau}-\bm{M}^{\star\tau}\big{)}_{m,:}$
$\displaystyle=\big{(}p^{-1}\bm{T}^{\tau,\left(m\right)}\times_{3}\bm{\theta}^{\tau,\left(m\right)}-\bm{T}^{\star}\times_{3}\bm{\theta}^{\tau}\big{)}_{m,:}+\bm{C}_{m,:}^{\tau}$
$\displaystyle=\bm{T}_{m,:,:}^{\star}\times_{3}\big{(}\bm{\theta}^{\tau,\left(m\right)}-\bm{\theta}^{\tau}\big{)}+\bm{C}_{m,:}^{\tau},$

where $\bm{C}^{\tau}$ is defined in (156).

From the incoherence conditions, we can upper bound

$\displaystyle\big{\|}\bm{C}_{m,:}^{\tau}\big{\|}_{2}$
$\displaystyle=\Big{\|}\sum\nolimits_{s:s\neq
1}\gamma_{s}^{\star\tau}\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle\left(\left(\overline{\bm{u}}_{1}^{\star}\right)_{m}\overline{\bm{u}}_{s}^{\star\top}+\left(\overline{\bm{u}}_{s}^{\star}\right)_{m}\overline{\bm{u}}_{1}^{\star\top}\right)-\sum\nolimits_{s:s\neq
1}\gamma_{s}^{\star\tau}\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle^{2}\left(\overline{\bm{u}}_{1}^{\star}\right)_{m}\overline{\bm{u}}_{1}^{\star\top}\Big{\|}_{2}$
$\displaystyle\leq\Big{\|}\sum\nolimits_{s:s\neq
1}\gamma_{s}^{\star\tau}\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle\left(\overline{\bm{u}}_{1}^{\star}\right)_{m}\overline{\bm{u}}_{s}^{\star\top}\Big{\|}_{2}+\Big{|}\sum\nolimits_{s:s\neq
1}\gamma_{s}^{\star\tau}\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle\left(\overline{\bm{u}}_{s}^{\star}\right)_{m}\Big{|}+\Big{|}\sum\nolimits_{s:s\neq
1}\gamma_{s}^{\star\tau}\left\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\right\rangle^{2}\left(\overline{\bm{u}}_{1}^{\star}\right)_{m}\Big{|}$
$\displaystyle\lesssim\big{\|}\bm{\gamma}^{\star\tau}\big{\|}_{2}\Big{(}\max_{s:s\neq
1}\left|\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\rangle\right|\left\|\overline{\bm{u}}_{1}^{\star}\right\|_{\infty}\big{\|}\overline{\bm{U}}^{\star}\big{\|}+\max_{s:s\neq
1}\left|\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\rangle\right|\big{\|}\overline{\bm{U}}^{\star}\big{\|}_{2,\infty}+\max_{s:s\neq
1}\left|\langle\overline{\bm{u}}_{s}^{\star},\overline{\bm{u}}_{1}^{\star}\rangle\right|^{2}\left\|\overline{\bm{u}}_{1}^{\star}\right\|_{\infty}\sqrt{r}\Big{)}$
$\displaystyle\lesssim\big{\|}\bm{\gamma}^{\star\tau}\big{\|}_{2}\left(\sqrt{\frac{\mu}{d}}\sqrt{\frac{\mu}{d}}+\sqrt{\frac{\mu}{d}}\sqrt{\frac{\mu
r}{d}}+\sqrt{\frac{\mu}{d}}\sqrt{\frac{\mu
r}{d}}\right)\lesssim\sqrt{\frac{\mu r}{d}}\sqrt{\frac{\mu r\log
d}{d}}\,\lambda_{\max}^{\star},$ (192)

where we use the fact that
$\big{\|}\bm{\gamma}^{\star\tau}\big{\|}_{2}\lesssim\sqrt{r\log
d}\,\lambda_{\max}^{\star}$ from Lemma 5.12 and
$\big{\|}\overline{\bm{U}}^{\star}\big{\|}\lesssim 1$ from Lemma D.1.

In addition, we can express

$\displaystyle\bm{T}_{m,:,:}^{\star}\times_{3}\big{(}\bm{\theta}^{\tau,\left(m\right)}-\bm{\theta}^{\tau}\big{)}=\sum_{s\in\left[r\right]}\lambda_{s}^{\star}\big{(}\overline{\bm{u}}_{s}^{\star}\big{)}_{m}\big{\langle}\overline{\bm{u}}_{s}^{\star},\bm{\theta}^{\tau,\left(m\right)}-\bm{\theta}^{\tau}\big{\rangle}\overline{\bm{u}}_{s}^{\star}.$

By construction, we know that

$\displaystyle\bm{\theta}^{\tau}-\bm{\theta}^{\tau,\left(m\right)}$
$\displaystyle=\big{(}\bm{U}\bm{U}^{\top}-\bm{U}^{(m)}\bm{U}^{\left(m\right)\top}\big{)}\,\bm{g}^{\tau}$

is a zero-mean Gaussian random vector conditional on
$\mathcal{P}_{\Omega}\left(\bm{E}\right)$. Using standard results on Gaussian
random vectors, one has: with probability at least $1-O\left(d^{-11}\right)$,
for each $s\in\left[r\right]$ and $m\in\left[d\right]$,

$\displaystyle\left|\big{\langle}\overline{\bm{u}}_{s}^{\star},\bm{\theta}^{\tau}-\bm{\theta}^{\tau,\left(m\right)}\big{\rangle}\right|$
$\displaystyle=\left|\big{\langle}\bm{g}^{\tau},\big{(}\bm{U}\bm{U}^{\top}-\bm{U}^{(m)}\bm{U}^{\left(m\right)\top}\big{)}\,\overline{\bm{u}}_{s}^{\star}\big{\rangle}\right|\lesssim\big{\|}\big{(}\bm{U}\bm{U}^{\top}-\bm{U}^{(m)}\bm{U}^{\left(m\right)\top}\big{)}\,\overline{\bm{u}}_{s}^{\star}\big{\|}_{2}\sqrt{\log
d}$
$\displaystyle\leq\big{\|}\bm{U}\bm{U}^{\top}-\bm{U}^{(m)}\bm{U}^{\left(m\right)\top}\big{\|}\sqrt{\log
d}$ (193)

and

$\big{\|}\bm{\theta}^{\tau}-\bm{\theta}^{\tau,\left(m\right)}\big{\|}_{2}\lesssim\big{\|}\bm{U}\bm{U}^{\top}-\bm{U}^{(m)}\bm{U}^{\left(m\right)\top}\big{\|}_{\mathrm{F}}\sqrt{\log
d}.$ (194)

Therefore, we have

$\displaystyle\big{\|}\bm{T}_{m,:,:}^{\star}\times_{3}\big{(}\bm{\theta}^{\tau,\left(m\right)}-\bm{\theta}^{\tau}\big{)}\big{\|}_{2}$
$\displaystyle\leq\max_{s\in\left[r\right]}\big{|}\lambda_{s}^{\star}\big{\langle}\overline{\bm{u}}_{s}^{\star},\bm{\theta}^{\tau,\left(m\right)}-\bm{\theta}^{\tau}\big{\rangle}\big{|}\big{\|}\overline{\bm{U}}^{\star}\big{\|}_{2,\infty}\big{\|}\overline{\bm{U}}^{\star}\big{\|}$
$\displaystyle\lesssim\lambda_{\max}^{\star}\big{\|}\overline{\bm{U}}^{\star}\big{\|}_{2,\infty}\big{\|}\bm{U}\bm{U}^{\top}-\bm{U}^{(m)}\bm{U}^{\left(m\right)\top}\big{\|}\sqrt{\log
d}$ $\displaystyle\lesssim\mathcal{E}_{\mathsf{loo}}\sqrt{\frac{\mu
r}{d}}\sqrt{\frac{\mu r\log d}{d}}\,\lambda_{\max}^{\star}\ll\sqrt{\frac{\mu
r}{d}}\sqrt{\frac{\mu r\log d}{d}}\,\lambda_{\max}^{\star}$

where we have used Lemma 5.8 as well as the conditions that
$\mathcal{E}_{\mathsf{loo}}\ll 1$,
$\big{\|}\overline{\bm{U}}^{\star}\big{\|}\lesssim 1$ and
$\big{\|}\overline{\bm{U}}^{\star}\big{\|}_{2,\infty}\lesssim\sqrt{\mu r/d}$.

Putting the above bounds together, we arrive at

$\displaystyle\left\|\big{(}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{)}_{m,:}\right\|_{2}$
$\displaystyle\leq\big{\|}\bm{T}_{m,:,:}^{\star}\times_{3}\big{(}\bm{\theta}^{\tau,\left(m\right)}-\bm{\theta}^{\tau}\big{)}\big{\|}_{2}+\big{\|}\bm{C}_{m,:}^{\tau}\big{\|}_{2}\lesssim\sqrt{\frac{\mu
r}{d}}\sqrt{\frac{\mu r\log d}{d}}\,\lambda_{\max}^{\star}.$ (195)

We therefore conclude that

$\displaystyle\alpha_{2}\lesssim\sqrt{\frac{\mu r}{d}}\sqrt{\frac{\mu r\log
d}{d}}\,\lambda_{\max}^{\star}\lesssim\mathcal{E}_{\mathsf{op}}\sqrt{\frac{\mu
r\log d}{d}}\,\lambda_{\max}^{\star}$

where we remind the reader of the definition of $\mathcal{E}_{\mathsf{op}}$ in
(81).

####  B.4.3 Controlling $\alpha_{1}$

The remaining quantity to control is $\alpha_{1}$ (see (179)). Invoke Weyl’s
inequality to show that

$\displaystyle\big{|}\gamma_{1}^{\star\tau}-\gamma_{\tau}^{(m)}\big{|}$
$\displaystyle\leq\big{\|}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{\|}\lesssim\mathcal{E}_{\mathsf{op}}\lambda_{\min}^{\star}\ll\gamma_{1}^{\star\tau},$

where the last inequality arises from (188) and Lemma 5.12. Under our sample
size, rank and noise conditions, we have

$\displaystyle\frac{1}{2}\gamma_{1}^{\star\tau}\leq\gamma_{1}^{\star\tau}-\big{|}\gamma_{1}^{\star\tau}-\gamma_{\tau}^{(m)}\big{|}\leq\gamma_{\tau}^{(m)}\leq\big{|}\gamma_{1}^{\star\tau}-\gamma_{\tau}^{(m)}\big{|}+\gamma_{1}^{\star\tau}\leq
2\gamma_{1}^{\star\tau}.$

This indicates that

$\displaystyle\frac{\big{|}\gamma_{1}^{\star\tau}-\gamma_{\tau}^{(m)}\big{|}}{\gamma_{1}^{\star\tau}\gamma_{\tau}^{(m)}}\lesssim\frac{1}{\big{(}\gamma_{1}^{\star\tau}\big{)}^{2}}$
$\displaystyle\big{\|}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{\|}\lesssim\frac{1}{\lambda_{\min}^{\star}}\mathcal{E}_{\mathsf{op}}.$

Moreover, we learn from (195) and (181) that

$\displaystyle\big{\|}\bm{M}_{m,:}^{\tau,\left(m\right)}\big{\|}_{2}$
$\displaystyle\leq\big{\|}\big{(}\bm{M}^{\tau,\left(m\right)}-\bm{M}^{\star\tau}\big{)}_{m,:}\big{\|}_{2}+\big{\|}\bm{M}_{m,:}^{\star\tau}\big{\|}_{2}$
$\displaystyle\lesssim\frac{\mu r\sqrt{\log
d}}{d}\,\lambda_{\max}^{\star}+\sqrt{\frac{\mu r\log
d}{d}}\,\lambda_{\max}^{\star}\asymp\sqrt{\frac{\mu r\log
d}{d}}\,\lambda_{\min}^{\star},$

where the last step follows from the fact that $\mu r\leq d$ and $\kappa\asymp
1$. Hence, we reach the conclusion that

$\displaystyle\alpha_{1}$
$\displaystyle\lesssim\frac{\big{|}\gamma_{1}^{\star\tau}-\gamma_{\tau}^{(m)}\big{|}}{\gamma_{1}^{\star\tau}\gamma_{\tau}^{(m)}}\big{\|}\bm{M}_{m,:}^{\tau,\left(m\right)}\big{\|}_{2}\lesssim\mathcal{E}_{\mathsf{op}}\sqrt{\frac{\mu
r\log d}{d}}.$

####  B.4.4 Combining $\alpha_{1}$, $\alpha_{2}$ and $\alpha_{3}$

Putting together all of the preceding bounds on $\alpha_{1}$, $\alpha_{2}$ and
$\alpha_{3}$ immediately establishes the lemma.

###  B.5 Proof of Lemma B.2

First of all, if the claims (185) and (186) can be established, then putting
them together yields

$\displaystyle\big{\|}\bm{M}^{\tau}-\bm{M}^{\tau,\left(m\right)}\big{\|}$
$\displaystyle\leq\big{\|}\bm{M}^{\tau}-\widehat{\bm{M}}^{\tau,\left(m\right)}\big{\|}+\big{\|}\widehat{\bm{M}}^{\tau,\left(m\right)}-\bm{M}^{\tau,\left(m\right)}\big{\|}\lesssim\frac{\mu
r\lambda_{\max}^{\star}\sqrt{\log d}}{d\sqrt{p}}+\sigma\sqrt{\frac{rd\log
d}{p}},$ (196)

where we recall the definition of $\mathcal{E}_{\mathsf{loo}}$ in (65) and use
the sample size, noise and rank conditions. The rest of the proof is thus
dedicated to establishing (185) and (186). In what follows, we shall assume
$\\{E_{i,j,k}\\}_{i,j,k\in[d]}$ (resp. $\\{\chi_{i,j,k}\\}_{i,j,k\in[d]}$) are
independent random variables to simplify presentation.

####  B.5.1 Proximity of $\bm{M}^{\tau,\left(m\right)}$ and
$\widehat{\bm{M}}^{\tau,\left(m\right)}$

Recall the definition of
$\bm{M}^{\tau,\left(m\right)}=p^{-1}\bm{T}^{(m)}\times_{3}\bm{\theta}^{\tau,\left(m\right)}$
in (70c). Comparing this with the definition of
$\widehat{\bm{M}}^{\tau,\left(m\right)}$ in (183), we see that

$\displaystyle\big{(}\widehat{\bm{M}}^{\tau,\left(m\right)}-\bm{M}^{\tau,\left(m\right)}\big{)}_{i,j}$
$\displaystyle=\theta_{m}^{\tau,\left(m\right)}\big{(}T_{i,j,m}^{\star}(p^{-1}\chi_{i,j,m}-1)+p^{-1}E_{i,j,m}\chi_{i,j,m}\big{)},\;i\neq