$\displaystyle\bigg{\|}\mathbf{Z}_{k}^{j-m}\mathcal{\widetilde{P}}_{k}^{t,j-m}\bigg{\|}^{2}$
$\displaystyle=\bigg{\|}\mathcal{\widetilde{P}}_{k}^{t,j-m}(\mathbf{Z}_{k}^{j-m})^{\top}\mathbf{Z}_{k}^{j-m}\mathcal{\widetilde{P}}_{k}^{t,j-m}\bigg{\|}$
$\displaystyle\leq\bigg{\|}\mathcal{\widetilde{P}}_{k}^{t,j-m}\mathbf{Z}_{k}^{\top}\mathbf{Z}_{k}\mathcal{\widetilde{P}}_{k}^{t,j-m}\bigg{\|}^{2}$
$\displaystyle=\bigg{\|}\mathbf{Z}_{k}\mathcal{\widetilde{P}}_{k}^{t,j-m}\bigg{\|}$
$\displaystyle\leq\tau_{k}^{2},$

where we took the supremum in the final inequality. Therefore,
$\|\mathbf{Z}_{k}^{j-m}\mathcal{\widetilde{P}}_{k}^{t,j-m}\|\leq\tau_{k}$.
Therefore, by Weyl’s inequality, it holds that

$\displaystyle\bigg{|}\lambda_{r_{k}}\bigg{(}\mathbf{T}_{k}\mathcal{\widehat{P}}_{k}^{(t)}+\mathbf{Z}_{k}^{j-m}\mathcal{\widetilde{P}}_{k}^{t,j-m}\mathcal{\widehat{P}}_{k}^{(t)}\bigg{)}-\lambda_{r_{k}}(\mathbf{T}_{k}\mathcal{\widehat{P}}_{k}^{(t)})\bigg{|}$
$\displaystyle\leq\|\mathbf{Z}_{k}^{j-m}\mathcal{\widetilde{P}}_{k}^{t,j-m}\mathcal{\widehat{P}}_{k}^{(t)}\|$
$\displaystyle\leq\|\mathbf{Z}_{k}^{j-m}\mathcal{\widetilde{P}}_{k}^{t,j-m}\|$
$\displaystyle\leq\tau_{k}$ $\displaystyle\leq\frac{\lambda}{4}.$ (10)

Next, when $\eta_{k}^{(t)}\leq\frac{1}{4}$, this implies that

$\displaystyle\max\bigg{(}\|\sin\Theta(\mathbf{\widehat{U}}_{k+1}^{(t-1)},{\mathbf{U}}_{k+1})\|,\|\sin\Theta(\mathbf{\widehat{U}}_{k+2}^{(t-1)},{\mathbf{U}}_{k+2})\|\bigg{)}\leq\frac{1}{4},$

and hence that

$\displaystyle\lambda_{\min}(\mathbf{T}_{k}\mathcal{\widehat{P}}_{k}^{(t)})$
$\displaystyle=\lambda_{\min}\bigg{(}\mathbf{T}_{k}{\mathbf{U}}_{k+1}\otimes{\mathbf{U}}_{k+2}({\mathbf{U}}_{k+1}\otimes{\mathbf{U}}_{k+2})^{\top}\mathcal{\widehat{P}}_{k}^{(t)}\bigg{)}$
$\displaystyle\geq\lambda\lambda_{\min}\bigg{(}({\mathbf{U}}_{k+1}\otimes{\mathbf{U}}_{k+2})^{\top}\mathcal{\widehat{P}}_{k}^{(t)}\bigg{)}$
$\displaystyle\geq\lambda\lambda_{\min}({\mathbf{U}}_{k+1}^{\top}\mathbf{\widehat{U}}_{k+1}^{(t-1)})\lambda_{\min}({\mathbf{U}}_{k+2}^{\top}\mathbf{\widehat{U}}_{k+2}^{(t-1)})$
$\displaystyle\geq\lambda(1-\frac{1}{16})$
$\displaystyle\geq\frac{15}{16}\lambda.$ (11)

Combining (11) and (10) gives the first claim.

For the second claim, we simply note that by Weyl’s inequality,

$\displaystyle\bigg{|}\lambda_{r_{k}+1}\bigg{(}\mathbf{T}_{k}\mathcal{\widehat{P}}_{k}^{(t)}+\mathbf{Z}_{k}\mathcal{\widehat{P}}_{k}^{(t)}\bigg{)}-\lambda_{r_{k}+1}\bigg{(}\mathbf{T}_{k}\mathcal{\widehat{P}}_{k}^{(t)}\bigg{)}\bigg{|}$
$\displaystyle\leq\|\mathbf{Z}_{k}\mathcal{\widehat{P}}_{k}^{(t)}\|$
$\displaystyle\leq\tau_{k}\leq\frac{\lambda}{4}.$

Since $\mathbf{T}_{k}$ is rank $r_{k}$, it holds that

$\displaystyle\lambda_{r_{k}+1}\bigg{(}\mathbf{T}_{k}\mathcal{\widehat{P}}_{k}^{(t)}\bigg{)}=0,$

which proves the second assertion. This completes the proof. ∎

######  Lemma 7 (Deterministic Bound for Leave-One-Out Sequence).

Suppose that $\tau_{k}\leq\frac{\lambda}{4}$ and that
$\eta_{k}^{(t)}\leq\frac{1}{4}$. Then it holds that

$\displaystyle\|\sin\Theta(\mathbf{\widehat{U}}_{k}^{(t)},\mathbf{\widetilde{U}}_{k}^{t,j-m})\|$
$\displaystyle\leq\frac{16\kappa}{\lambda}\tau_{k}\bigg{(}\eta_{k}^{(t,j-m)}\bigg{)}+\frac{16\kappa}{\lambda}\xi_{k}^{t,j-m}\bigg{(}\eta_{k}^{(t,j-m)}\bigg{)}$
$\displaystyle\qquad+\frac{8\kappa}{\lambda}\widetilde{\xi}_{k}^{t,j-m}+\frac{16}{\lambda^{2}}\tau_{k}^{2}\bigg{(}\eta_{k}^{(t,j-m)}\bigg{)}+\frac{8}{\lambda^{2}}\tau_{k}\xi_{k}^{t,j-m}+\frac{4}{\lambda^{2}}(\xi_{k}^{t,j-m})^{2},$

###### Proof.

We prove the result for $k=1$; the result for $k=2$ and $k=3$ are similar by
modifying the index on $t$.

Recall that $\mathbf{\widehat{U}}_{1}^{(t)}$ are the singular vectors of the
matrix

$\displaystyle\mathbf{T}_{1}\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}+\mathbf{Z}_{1}\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}$

and $\mathbf{\widetilde{U}}_{1}^{t,j-m}$ are the singular vectors of the
matrix

$\displaystyle\mathbf{T}_{1}+\mathbf{Z}_{1}^{j-m}\mathcal{\widetilde{P}}_{1}^{t,j-m}$

Consequently, the projection
$\mathbf{\widetilde{U}}_{1}^{t,j-m}(\mathbf{\widetilde{U}}_{1}^{t,j-m})^{\top}$
is also the projection onto the dominant left singular space of the matrix

$\displaystyle\bigg{(}\mathbf{T}_{1}+\mathbf{Z}_{1}^{j-m}\mathcal{\widetilde{P}}_{1}^{t,j-m}\bigg{)}\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)},$

Therefore, both projections are projections onto the dominant eigenspaces of
the matrices defined via

$\displaystyle\mathbf{\widehat{A}}$
$\displaystyle\coloneqq\mathbf{T}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{T}_{1}^{\top}+\bigg{[}\mathbf{Z}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{T}_{1}^{\top}+\mathbf{T}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{Z}_{1}^{\top}+\mathbf{Z}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{Z}_{1}^{\top}\bigg{]};$
$\displaystyle\mathbf{\widetilde{A}}$
$\displaystyle\coloneqq\mathbf{T}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{T}_{1}^{\top}+\bigg{[}\mathbf{Z}_{1}^{j-m}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{T}_{1}^{\top}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\mathbf{T}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}(\mathbf{Z}_{1}^{j-m})^{\top}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\mathbf{Z}_{1}^{j-m}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\mathbf{Z}_{1}^{j-m})^{\top}\bigg{]}.$

Therefore, the perturbation $\mathbf{\widehat{A}-\widetilde{A}}$ is equal to
the sum of three terms, defined via

$\displaystyle\mathbf{P}_{1}$
$\displaystyle\coloneqq\mathbf{Z}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{T}_{1}^{\top}-\mathbf{Z}_{1}^{j-m}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{T}_{1}^{\top}$
$\displaystyle=\bigg{[}\mathbf{Z}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}-\mathbf{Z}_{1}^{j-m}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\bigg{]}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{T}_{1}^{\top}$
$\displaystyle\mathbf{P}_{2}$
$\displaystyle\coloneqq\mathbf{T}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{Z}_{1}^{\top}-\mathbf{T}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}(\mathbf{Z}_{1}^{j-m})^{\top}$
$\displaystyle=\mathbf{T}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\bigg{(}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{Z}_{1}^{\top}-\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}(\mathbf{Z}_{1}^{j-m})^{\top}\bigg{)}$
$\displaystyle\mathbf{P}_{3}$
$\displaystyle\coloneqq\mathbf{Z}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{Z}_{1}^{\top}-\mathbf{Z}_{1}^{j-m}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\mathbf{Z}_{1}^{j-m})^{\top}$

where we have used the fact that
$\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}$
is a projection matrix and hence equal to its square. We now bound each term
successively.

The term $\|\mathbf{P}_{1}\|$: Observe that

$\displaystyle\mathbf{P}_{1}$
$\displaystyle=\bigg{[}\mathbf{Z}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}-\mathbf{Z}_{1}^{j-m}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\bigg{]}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{T}_{1}^{\top}$
$\displaystyle=\left[\mathbf{Z}_{1}\left(\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}-\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\right)\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\right]\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{T}_{1}^{\top}$
$\displaystyle\qquad+\left[\mathbf{Z}_{1}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\left(\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}-\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\right)\right]\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{T}_{1}^{\top}$
$\displaystyle\qquad+\left[\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m}\right]\bigg{(}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\bigg{)}\left[\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}-\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\right]\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{T}_{1}^{\top}$
$\displaystyle\qquad+\left[\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m}\right]\bigg{(}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\bigg{)}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\left[\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}-\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\right]\mathbf{T}_{1}^{\top}$
$\displaystyle\qquad+\left[\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m}\right]\bigg{(}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\bigg{)}\mathbf{T}_{1}^{\top}.$

Taking norms yields

$\displaystyle\|\mathbf{P}_{1}\|$ $\displaystyle\leq
2\lambda_{1}\tau_{1}\bigg{(}\|\sin\Theta(\mathbf{\widehat{U}}_{2}^{(t-1)},\mathbf{\widetilde{U}}_{2}^{t-1,j-m})\|+\|\sin\Theta(\mathbf{\widehat{U}}_{3}^{(t-1)},\mathbf{\widetilde{U}}_{3}^{t-1,j-m})\|\bigg{)}$
$\displaystyle\qquad+2\lambda_{1}\|\left[\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m}\right]\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\|\|\sin\Theta(\mathbf{\widehat{U}}_{2}^{(t-1)},\mathbf{\widetilde{U}}_{2}^{t-1,j-m})\|$
$\displaystyle\qquad+2\lambda_{1}\|\left[\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m}\right]\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\|\|\sin\Theta(\mathbf{\widehat{U}}_{3}^{(t-1)},\mathbf{\widetilde{U}}_{3}^{t-1,j-m})\|$
$\displaystyle\qquad+\lambda_{1}\|\left[\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m}\right]\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\mathbf{V}_{1}\|$
$\displaystyle\leq
2\lambda_{1}\tau_{1}\bigg{(}\eta_{1}^{(t,j-m)}\bigg{)}+2\lambda_{1}\xi_{1}^{t,j-m}\bigg{(}\eta_{1}^{(t,j-m)}\bigg{)}+\lambda_{1}\widetilde{\xi}_{1}^{t,j-m}.$

For $\mathbf{P}_{2}$ we proceed similarly. It holds that

$\displaystyle\mathbf{P}_{2}$
$\displaystyle=\mathbf{T}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\bigg{(}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{Z}_{1}^{\top}-\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}(\mathbf{Z}_{1}^{j-m})^{\top}\bigg{)}$
$\displaystyle=\mathbf{T}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\bigg{(}\left[\mathcal{P}_{\mathbf{\widehat{U}}^{(t)}_{k+1}}-\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\right]\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{Z}_{1}^{\top}\bigg{)}$
$\displaystyle\qquad+\mathbf{T}_{1}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\bigg{(}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\left[\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}-\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\right]\mathbf{Z}_{1}^{\top}\bigg{)}$
$\displaystyle\qquad+\mathbf{T}_{1}\bigg{(}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}-\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\bigg{)}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\bigg{(}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}(\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m})^{\top}\bigg{)}$
$\displaystyle\qquad+\mathbf{T}_{1}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\bigg{(}\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\bigg{)}\bigg{(}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}(\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m})^{\top}\bigg{)}$
$\displaystyle\qquad+\mathbf{T}_{1}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}(\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m})^{\top}.$

Taking norms yields the same upper bound as for $\|\mathbf{P}_{1}\|$.

For the the term $\mathbf{P}_{3}$, we note that since
$\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}$
is a projection matrix and hence equal to its cube, it holds that

$\displaystyle\|\mathbf{P}_{3}\|$
$\displaystyle\leq\bigg{\|}\mathbf{Z}_{1}\left[\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}-\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\right]\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{Z}_{1}\bigg{\|}$
$\displaystyle\qquad+\bigg{\|}\mathbf{Z}_{1}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\left[\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\right]\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{Z}_{1}\bigg{\|}$
$\displaystyle\qquad+\bigg{\|}\mathbf{Z}_{1}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\left[\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}}-\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\right]\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathbf{Z}_{1}\bigg{\|}$
$\displaystyle\qquad+\bigg{\|}\mathbf{Z}_{1}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\left[\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t-1)}}\right]\mathbf{Z}_{1}\bigg{\|}$
$\displaystyle\qquad+\bigg{\|}\mathbf{Z}_{1}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\left[\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m}\right]^{\top}\bigg{\|}$
$\displaystyle\qquad+\bigg{\|}\left[\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m}\right]\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t-1)}\otimes\mathbf{\widehat{U}}_{3}^{(t-1)}}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\mathbf{Z}_{1}^{j-m}\bigg{\|}$
$\displaystyle\leq
2\tau_{1}^{2}\bigg{(}\|\sin\Theta(\mathbf{\widehat{U}}_{2}^{(t-1)},\mathbf{\widetilde{U}}_{2}^{t-1,j-m})\|+\|\sin\Theta(\mathbf{\widehat{U}}_{3}^{(t-1)},\mathbf{\widetilde{U}}_{3}^{t-1,j-m})\|\bigg{)}$
$\displaystyle\qquad+\tau_{1}\bigg{\|}\left[\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m}\right]\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\bigg{\|}$
$\displaystyle\qquad+\bigg{\|}\mathbf{Z}_{1}^{j-m}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\bigg{\|}\bigg{\|}\left[\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m}\right]\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\bigg{\|}$
$\displaystyle\leq
4\tau_{1}^{2}\bigg{(}\eta_{1}^{(t,j-m)}\bigg{)}+\tau_{1}\xi_{1}^{t,j-m}+\bigg{\|}\mathbf{Z}_{1}^{j-m}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\bigg{\|}\xi_{1}^{t,j-m}$
$\displaystyle\leq
4\tau_{1}^{2}\bigg{(}\eta_{1}^{(t,j-m)}\bigg{)}+2\tau_{1}\xi_{1}^{t,j-m}+\bigg{\|}\bigg{(}\mathbf{Z}_{1}-\mathbf{Z}_{1}^{j-m}\bigg{)}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{t-1,j-m}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{t-1,j-m}}\bigg{\|}\xi_{1}^{t,j-m}$
$\displaystyle\leq
4\tau_{1}^{2}\bigg{(}\eta_{1}^{(t,j-m)}\bigg{)}+2\tau_{1}\xi_{1}^{t,j-m}+\big{(}\xi_{1}^{t,j-m}\big{)}^{2}.$

We note that by Lemma 6, it holds that

$\displaystyle\lambda_{r_{1}}\big{(}\mathbf{\widetilde{A}}\big{)}-\lambda_{r_{1}+1}\big{(}\mathbf{\widehat{A}}\big{)}$
$\displaystyle=\lambda_{r_{1}}^{2}\bigg{(}\mathbf{T}_{1}\mathcal{\widehat{P}}_{1}^{(t)}+\mathbf{Z}_{1}^{j-m}\mathcal{\widetilde{P}}_{1}^{t,j-m}\bigg{)}-\lambda_{r_{1}+1}^{2}\bigg{(}\mathbf{T}_{1}\mathcal{\widehat{P}}_{1}^{(t)}+\mathbf{Z}_{k}\mathcal{\widehat{P}}_{1}^{(t)}\bigg{)}$
$\displaystyle\geq\bigg{(}\frac{3}{4}\lambda\bigg{)}^{2}-\bigg{(}\frac{\lambda}{4}\bigg{)}^{2}$
$\displaystyle\geq\frac{\lambda^{2}}{4}.$

Consequently, by the Davis-Kahan Theorem, it holds that

$\displaystyle\|\sin\Theta(\mathbf{\widehat{U}}_{1}^{(t)},\mathbf{\widetilde{U}}_{1}^{t,j-m})\|$
$\displaystyle\leq\frac{4}{\lambda^{2}}\bigg{(}\|\mathbf{P}_{1}\|+\|\mathbf{P}_{2}\|+\|\mathbf{P}_{3}\|\bigg{)},$

which holds under the eigengap condition by Lemma 6 and the assumption
$\tau_{k}\leq\frac{\lambda}{4}$. Therefore,

$\displaystyle\|\sin\Theta(\mathbf{\widehat{U}}_{1}^{(t)},\mathbf{\widetilde{U}}_{1}^{t,j-m})\|$
$\displaystyle\leq\frac{4}{\lambda^{2}}\bigg{(}\|\mathbf{P}_{1}\|+\|\mathbf{P}_{2}\|+\|\mathbf{P}_{3}\|\bigg{)}$
$\displaystyle\leq\frac{8}{\lambda^{2}}\bigg{(}2\lambda_{1}\tau_{1}\bigg{(}\eta_{1}^{(t,j-m)}\bigg{)}+2\lambda_{1}\xi_{1}^{t,j-m}\bigg{(}\eta_{1}^{(t,j-m)}\bigg{)}+\lambda_{1}\widetilde{\xi}_{1}^{t,j-m}\bigg{)}$
$\displaystyle\qquad+\frac{4}{\lambda^{2}}\bigg{(}4\tau_{1}^{2}\bigg{(}\eta_{1}^{(t,j-m)}\bigg{)}+2\tau_{1}\xi_{1}^{t,j-m}+\big{(}\xi_{1}^{t,j-m}\big{)}^{2}\bigg{)}$
$\displaystyle\leq\frac{16\kappa}{\lambda}\tau_{1}\bigg{(}\eta_{1}^{(t,j-m)}\bigg{)}+\frac{16\kappa}{\lambda}\xi_{1}^{t,j-m}\bigg{(}\eta_{1}^{(t,j-m)}\bigg{)}$
$\displaystyle\qquad+\frac{8\kappa}{\lambda}\widetilde{\xi}_{1}^{t,j-m}+\frac{16}{\lambda^{2}}\tau_{1}^{2}\bigg{(}\eta_{1}^{(t,j-m)}\bigg{)}+\frac{8}{\lambda^{2}}\tau_{1}\xi_{1}^{t,j-m}+\frac{4}{\lambda^{2}}(\xi_{1}^{t,j-m})^{2}$

as desired. ∎

###  A.3 Probabilistic Bounds on Good Events

This section contains high-probability bounds for the terms considered in the
previous subsection. Let $r=\max r_{k}$, $p=\max p_{k}$. In what follows, we
denote

$\displaystyle\delta_{\mathrm{L}}^{(k)}$ $\displaystyle\coloneqq
C_{0}\kappa\sqrt{p_{k}\log(p)},$

where $C_{0}$ is taken to be some fixed constant.

We will also recall the notation from the previous section:

$\displaystyle\mathcal{\widehat{P}}_{k}^{(t)}$
$\displaystyle\coloneqq\begin{cases}\mathcal{P}_{\mathbf{\widehat{U}}_{k+1}^{(t-1)}\otimes\mathbf{\widehat{U}}_{k+2}^{(t-1)}}&k=1;\\\
\mathcal{P}_{\mathbf{\widehat{U}}_{k+1}^{(t-1)}\otimes\mathbf{\widehat{U}}_{k+2}^{(t)}}&k=2;\\\
\mathcal{P}_{\mathbf{\widehat{U}}_{k+1}^{(t)}\otimes\mathbf{\widehat{U}}_{k+2}^{(t)}}&k=3.\end{cases}$
$\displaystyle\mathcal{\widetilde{P}}_{k}^{t,j-m}$
$\displaystyle\coloneqq\begin{cases}\mathcal{P}_{\mathbf{\widetilde{U}}_{k+1}^{(t-1,j-m)}\otimes\mathbf{\widetilde{U}}_{k+2}^{(t-1,j-m)}}&k=1;\\\
\mathcal{P}_{\mathbf{\widetilde{U}}_{k+1}^{(t-1,j-m)}\otimes\mathbf{\widetilde{U}}_{k+2}^{(t,j-m)}}&k=2;\\\
\mathcal{P}_{\mathbf{\widetilde{U}}_{k+1}^{(t,j-m)}\otimes\mathbf{\widetilde{U}}_{k+2}^{(t,j-m)}}&k=3.\end{cases}$
$\displaystyle\mathbf{L}_{k}^{(t)}$
$\displaystyle\coloneqq{\mathbf{U}}_{k\perp}{\mathbf{U}}_{k\perp}^{\top}\mathbf{Z}_{k}\mathcal{\widehat{P}}_{k}^{(t)}\mathbf{T}_{k}^{\top}\mathbf{\widehat{U}}^{(t-1)}_{k}(\mathbf{\widehat{\Lambda}}_{k}^{(t-1)})^{-2};$
$\displaystyle\mathbf{Q}_{k}^{(t)}$
$\displaystyle\coloneqq{\mathbf{U}}_{k\perp}{\mathbf{U}}_{k\perp}^{\top}\mathbf{Z}_{k}\mathcal{\widehat{P}}_{k}^{(t)}\mathbf{Z}_{k}^{\top}\widehat{{\mathbf{U}}}_{k}^{(t-1)}(\mathbf{\widehat{\Lambda}}_{k}^{(t-1)})^{-2}$
$\displaystyle\tau_{k}$
$\displaystyle\coloneqq\sup_{\begin{subarray}{c}\|\mathbf{U}_{1}\|=1,\mathrm{rank}({\mathbf{U}}_{1})\leq
2r_{k+1}\\\ \|\mathbf{U}_{2}\|=1,\mathrm{rank}({\mathbf{U}}_{2})\leq
2r_{k+2}\end{subarray}}\|\mathbf{Z}_{k}\bigg{(}\mathcal{P}_{\mathbf{U}_{1}}\otimes\mathcal{P}_{\mathbf{U}_{2}}\bigg{)}\|;$
$\displaystyle\xi_{k}^{(t,j-m)}$
$\displaystyle\coloneqq\bigg{\|}\bigg{(}\mathbf{Z}_{k}^{j-m}-\mathbf{Z}_{k}\bigg{)}\mathcal{\widetilde{P}}_{k}^{t,j-m}\bigg{\|}$
$\displaystyle\widetilde{\xi}_{k}^{(t,j-m)}$
$\displaystyle\coloneqq\bigg{\|}\bigg{(}\mathbf{Z}_{k}^{j-m}-\mathbf{Z}_{k}\bigg{)}\mathcal{\widetilde{P}}_{k}^{t,j-m}\mathbf{V}_{k}\bigg{\|}$
$\displaystyle\eta_{k}^{(t,j-m)}$
$\displaystyle\coloneqq\begin{cases}\|\sin\Theta(\mathbf{\widetilde{U}}_{k+1}^{(t-1,j-m)},\mathbf{\widehat{U}}_{k+1}^{(t-1)})\|+\|\sin\Theta(\mathbf{\widetilde{U}}_{k+2}^{(t-1,j-m)},\mathbf{\widehat{U}}_{k+2}^{(t-1)})\|&k=1\\\
\|\sin\Theta(\mathbf{\widetilde{U}}_{k+1}^{(t-1,j-m)},\mathbf{\widehat{U}}_{k+1}^{(t-1)})\|+\|\sin\Theta(\mathbf{\widetilde{U}}_{k+2}^{(t,j-m)},\mathbf{\widehat{U}}_{k+2}^{(t)})\|&k=2\\\
\|\sin\Theta(\mathbf{\widetilde{U}}_{k+1}^{(t,j-m)},\mathbf{\widehat{U}}_{k+1}^{(t)})\|+\|\sin\Theta(\mathbf{\widetilde{U}}_{k+2}^{(t,j-m)},\mathbf{\widehat{U}}_{k+2}^{(t)})\|&k=3\end{cases}$
$\displaystyle\eta_{k}^{(t)}$
$\displaystyle\coloneqq\begin{cases}\|\sin\Theta({\mathbf{U}}_{k+1},\mathbf{\widehat{U}}_{k+1}^{(t-1)})\|+\|\sin\Theta({\mathbf{U}}_{k+2},\mathbf{\widehat{U}}_{k+2}^{(t-1)})\|&k=1\\\
\|\sin\Theta({\mathbf{U}}_{k+1},\mathbf{\widehat{U}}_{k+1}^{(t-1)})\|+\|\sin\Theta({\mathbf{U}}_{k+2},\mathbf{\widehat{U}}_{k+2}^{(t)})\|&k=2\\\
\|\sin\Theta({\mathbf{U}}_{k+1},\mathbf{\widehat{U}}_{k+1}^{(t)})\|+\|\sin\Theta({\mathbf{U}}_{k+2},\mathbf{\widehat{U}}_{k+2}^{(t)})\|&k=3\end{cases}.$

We will also need to define several probabilistic events. The first event
$\mathcal{E}_{\mathrm{Good}}$ collects several probabilistic bounds that hold
independently of $t$, provided $t_{\max}\leq C\log(p)$ for some constant $C$:

$\displaystyle\mathcal{E}_{\mathrm{Good}}$
$\displaystyle\coloneqq\bigg{\\{}\max_{k}\tau_{k}\leq
C\sqrt{pr}\bigg{\\}}\bigcap\bigg{\\{}\|\sin\Theta(\mathbf{\widehat{U}}_{k}^{(t)},{\mathbf{U}}_{k})\|\leq\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}+\frac{1}{2^{t}}\text{
for all $t\leq t_{\max}$ and $1\leq k\leq 3$ }\bigg{\\}}$
$\displaystyle\qquad\bigcap\bigg{\\{}\max_{k}\bigg{\|}{\mathbf{U}}_{k}^{\top}\mathbf{Z}_{k}\mathbf{V}_{k}\bigg{\|}\leq
C\left(\sqrt{r}+\sqrt{\log(p)}\right)\bigg{\\}};$
$\displaystyle\qquad\bigcap\bigg{\\{}\max_{k}\bigg{\|}{\mathbf{U}}_{k}^{\top}\mathbf{Z}_{k}\mathcal{P}_{{\mathbf{U}}_{k+1}}\otimes\mathcal{P}_{{\mathbf{U}}_{k+2}}\bigg{\|}\leq
C\left(r+\sqrt{\log(p)}\right)\bigg{\\}};$
$\displaystyle\qquad\bigcap\bigg{\\{}\max_{k}\bigg{\|}\mathbf{Z}_{k}\mathbf{V}_{k}\bigg{\|}\leq
C\sqrt{p_{k}}\bigg{\\}}.$

By Lemma 18, the proof in Zhang and Xia (2018), and a standard
$\varepsilon$-net argument, it is straightforward to show that

$\displaystyle\mathbb{P}\left(\mathcal{E}_{\mathrm{Good}}\right)\geq
1-O(p^{-30}).$

Note that Zhang and Xia (2018) assumes homoskedastic entries, but their proof
of Theorem 1 goes through in precisely the same way under the conditions of
Theorem 2, since their induction argument only requires a suitably warm
initialization. Alternatively, one can apply Theorem 1 of Luo et al. (2021),
where the $\sin\Theta$ bounds hold by the assumption
$\lambda\gtrsim\kappa\sqrt{\log(p)}p/p_{\min}^{1/4}$.

We now define several events we use in our induction argument. Set

$\displaystyle\mathcal{E}_{2,\infty}^{t,k}$
$\displaystyle\coloneqq\bigg{\\{}\|\mathbf{\widehat{U}}_{k}^{(t)}-{\mathbf{U}}_{k}\mathbf{W}_{k}^{(t)}\|_{2,\infty}\leq\bigg{(}\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}+\frac{1}{2^{t}}\bigg{)}\mu_{0}\sqrt{\frac{r_{k}}{p_{k}}}\bigg{\\}};$
$\displaystyle\mathcal{E}_{j-m}^{t,k}$
$\displaystyle\coloneqq\bigg{\\{}\|\sin\Theta(\mathbf{\widetilde{U}}_{k}^{t,j-m},\mathbf{\widehat{U}}_{k}^{(t)})\|\leq\bigg{(}\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}+\frac{1}{2^{t}}\bigg{)}\mu_{0}\sqrt{\frac{r_{k}}{p_{j}}}\bigg{\\}};$
$\displaystyle\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}$
$\displaystyle\coloneqq\bigcap_{t=1}^{t_{0}-1}\Bigg{\\{}\bigcap_{k=1}^{3}\mathcal{E}^{t,k}_{2,\infty}\cap\bigcap_{j=1}^{3}\bigcap_{m=1}^{p_{j}}\mathcal{E}_{k-m}^{t,j}\Bigg{\\}};$
$\displaystyle\mathcal{E}_{\mathrm{main}}^{t_{0}-1,2}$
$\displaystyle\coloneqq\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\cap\bigg{\\{}\bigcap_{k=1}^{3}\bigcap_{m=1}^{p_{k}}\mathcal{E}_{k-m}^{t_{0},1}\bigg{\\}}\cap\mathcal{E}_{2,\infty}^{t_{0},1}$
$\displaystyle\mathcal{E}_{\mathrm{main}}^{t_{0}-1,3}$
$\displaystyle\coloneqq\mathcal{E}_{\mathrm{main}}^{t_{0}-1,2}\cap\bigg{\\{}\bigcap_{k=1}^{3}\bigcap_{m=1}^{p_{k}}\mathcal{E}_{k-m}^{t_{0},2}\bigg{\\}}\cap\mathcal{E}_{2,\infty}^{t_{0},2}.$

The event $\mathcal{E}^{t,k}_{2,\infty}$ concerns the desired bound, the event
$\mathcal{E}^{t,k}_{j-m}$ controls the leave one out sequences, and the other
events $\mathcal{E}_{\mathrm{main}}^{t_{0}-1,k}$ are simply the intersection
of these events, mainly introduced for convenience.

Finally, the following event concerns the incoherence of our leave-one-out
sequences:

$\displaystyle\mathcal{\widetilde{E}}_{j-m}^{t,k}$
$\displaystyle\coloneqq\Bigg{\\{}\|\mathcal{\widetilde{P}}_{k}^{t_{0},j-m}\mathbf{V}_{k}\|_{2,\infty}\leq
c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{p_{j}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+1)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{j}p_{k+2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+1)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{j}p_{k+1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{-k}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+1)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{-k}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+c\mu_{0}\sqrt{\frac{r_{k}}{p_{-k}}}.\Bigg{\\}}$
$\displaystyle\bigcap\Bigg{\\{}\|\mathcal{\widetilde{P}}_{k}^{t_{0},j-m}\|_{2,\infty}\leq
c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{p_{j}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+1)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{j}p_{k+2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+1)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{j}p_{k+1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{-k}}}.\Bigg{\\}},$

where $c$ is some deterministic constant. While the precise definition of the
event $\mathcal{\widetilde{E}}_{j-m}^{t,k}$ is complicated, it is useful to
keep in mind that the event will be used as an event independent of the
nonzero elements in the matrices $\mathbf{Z}_{k}-\mathbf{Z}_{k}^{j-m}$, and it
simply controls the incoherence of the leave-one-out sequences.

The following lemma shows that the leave-one-out sequences are incoherent
whenever there are bounds on the previous iterates in $\ell_{2,\infty}$ norm.

######  Lemma 8.

For any fixed $t_{0}$, $j$, $k$, and $m$ with $1\leq t_{0}\leq t_{\max}$,
$1\leq j\leq 3$, $1\leq k\leq 3$, and $1\leq m\leq p_{j}$, it holds that the
set

$\displaystyle\mathcal{E}_{\mathrm{Good}}\cap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,k}\cap\left(\mathcal{\widetilde{E}}_{j-m}^{t_{0},k}\right)^{c}$

is empty.

###### Proof.

Without loss of generality, we prove the result for $k=1$; the cases $k=2$ and
$k=3$ are similar (in fact, the result can be made slightly sharper, but this
is not needed for our purposes).

Note that when $t_{0}\geq 1$, it holds that on the event
$\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}$.

$\displaystyle\|\mathbf{\widehat{U}}_{1}^{(t_{0}-1)}\|_{2,\infty}$
$\displaystyle\leq\|\mathbf{\widehat{U}}_{1}^{(t_{0}-1)}-{\mathbf{U}}_{1}\mathbf{W}_{1}^{(t_{0}-1)}\|_{2,\infty}+\|{\mathbf{U}}_{1}\|_{2,\infty}\leq
2\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}.$

Similarly,

$\displaystyle\|\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}\|_{2,\infty}$
$\displaystyle\leq 2\mu_{0}\sqrt{\frac{r_{2}}{p_{2}}};$
$\displaystyle\|\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}\|_{2,\infty}$
$\displaystyle\leq 2\mu_{0}\sqrt{\frac{r_{3}}{p_{3}}}.$

In addition, on this event it holds that

$\displaystyle\|\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\|$
$\displaystyle\leq
2\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}};$
$\displaystyle\|\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\|$
$\displaystyle\leq
2\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}.$
(12)

Next, observe that on the events listed,

$\displaystyle\|\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}\mathbf{V}_{1}\|_{2,\infty}$
$\displaystyle\leq\bigg{\|}\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{]}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle+\bigg{\|}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle\leq\bigg{\|}\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{]}\otimes\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{]}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle+\bigg{\|}\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{]}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle+\bigg{\|}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\otimes\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{]}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle+\bigg{\|}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle\leq\bigg{\|}\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{]}\otimes\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{]}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle+\bigg{\|}\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{]}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle+\bigg{\|}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\otimes\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{]}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle+\bigg{\|}\bigg{[}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}-\mathcal{P}_{{\mathbf{U}}_{2}}\bigg{]}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle+\bigg{\|}\mathcal{P}_{{\mathbf{U}}_{2}}\otimes\bigg{[}\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}-\mathcal{P}_{{\mathbf{U}}_{3}}\bigg{]}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle+\bigg{\|}\mathcal{P}_{{\mathbf{U}}_{2}}\otimes\mathcal{P}_{{\mathbf{U}}_{3}}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle\eqqcolon(I)+(II)+(III)+(IV)+(V)+(VI),$

where

$\displaystyle(I)$
$\displaystyle\coloneqq\bigg{\|}\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{]}\otimes\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{]}\mathbf{V}_{1}\bigg{\|}_{2,\infty};$
$\displaystyle(II):$
$\displaystyle=\bigg{\|}\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{]}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\mathbf{V}_{1}\bigg{\|}_{2,\infty};$
$\displaystyle(III)$
$\displaystyle\coloneqq\bigg{\|}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\otimes\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{]}\mathbf{V}_{1}\bigg{\|}_{2,\infty};$
$\displaystyle(IV)$
$\displaystyle\coloneqq\bigg{\|}\bigg{[}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}-\mathcal{P}_{{\mathbf{U}}_{2}}\bigg{]}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\mathbf{V}_{1}\bigg{\|}_{2,\infty};$
$\displaystyle(V)$
$\displaystyle\coloneqq\bigg{\|}\mathcal{P}_{{\mathbf{U}}_{2}}\otimes\bigg{[}\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}-\mathcal{P}_{{\mathbf{U}}_{3}}\bigg{]}\mathbf{V}_{1}\bigg{\|}_{2,\infty};$
$\displaystyle(VI)$
$\displaystyle\coloneqq\bigg{\|}\mathcal{P}_{{\mathbf{U}}_{2}}\otimes\mathcal{P}_{{\mathbf{U}}_{3}}\mathbf{V}_{1}\bigg{\|}_{2,\infty}.$

We now bound each term in turn, where we will use (12) repeatedly. We have
that

$\displaystyle(I)$
$\displaystyle\leq\bigg{\|}\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{]}\otimes\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{]}\bigg{\|}_{2,\infty}$
$\displaystyle\leq\bigg{\|}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{\|}\bigg{\|}\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{\|}$
$\displaystyle\leq
4\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{p_{j}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}.$
(13)

Similarly,

$\displaystyle(II)$
$\displaystyle\leq\bigg{\|}\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{]}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{\|}_{2,\infty}$
$\displaystyle\leq\bigg{\|}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{\|}\bigg{\|}\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{\|}_{2,\infty}$
$\displaystyle\leq
4\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\mu_{0}^{2}\sqrt{\frac{r_{2}}{p_{j}}}\sqrt{\frac{r_{3}}{p_{3}}}.$

Next,

$\displaystyle(III)$
$\displaystyle\leq\bigg{\|}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\otimes\bigg{[}\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{]}\bigg{\|}_{2,\infty}$
$\displaystyle\leq
4\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\mu_{0}^{2}\sqrt{\frac{r_{3}}{p_{j}}}\sqrt{\frac{r_{2}}{p_{2}}}.$

For the next two terms, we note that for any orthogonal matrix
$\mathbf{W}\in\mathbb{O}(r_{k})$,

$\displaystyle\|\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}\mathbf{\widehat{U}}_{2}^{t_{0}-1\top}-{\mathbf{U}}_{2}{\mathbf{U}}_{2}^{\top}\|_{2,\infty}$
$\displaystyle=\|\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}\mathbf{W}\mathbf{W}^{\top}\mathbf{\widehat{U}}_{2}^{t_{0}-1\top}-{\mathbf{U}}_{2}{\mathbf{U}}_{2}^{\top}\|_{2,\infty}$
$\displaystyle\leq\|(\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}\mathbf{W}-{\mathbf{U}}_{2})(\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}\mathbf{W})^{\top}\|_{2,\infty}$
$\displaystyle\qquad+\|{\mathbf{U}}_{2}(\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}\mathbf{W}-{\mathbf{U}}_{2})\|_{2,\infty}$
$\displaystyle\leq\|\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}\mathbf{W}-{\mathbf{U}}_{2}\|_{2,\infty}$
$\displaystyle\qquad+\|{\mathbf{U}}_{2}\|_{2,\infty}\|\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}\mathbf{W}-{\mathbf{U}}_{2}\|.$

By taking the infimum over $\mathbb{O}(r_{2})$, we note that by Proposition 1
of Cai and Zhang (2018)

$\displaystyle\inf_{\mathbf{W}\in\mathbb{O}(r_{2})}\|\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}\mathbf{W}-{\mathbf{U}}_{2}\|$
$\displaystyle\leq\sqrt{2}\|\sin\Theta(\mathbf{\widehat{U}}_{2}^{(t_{0}-1)},{\mathbf{U}}_{2})\|$
$\displaystyle\leq\sqrt{2}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)},$

where the final inequality is on the event $\mathcal{E}_{\mathrm{Good}}$ since
$t_{0}\leq t_{\max}$. We also note that on the event
$\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}$ and the right-invariance of
$\|\cdot\|_{2,\infty}$ to orthogonal matrices,

$\displaystyle\inf_{\mathbf{W}\in\mathbb{O}(r_{2})}\|\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}\mathbf{W}-{\mathbf{U}}_{2}\|_{2,\infty}$
$\displaystyle\leq\inf_{\mathbf{W}\in\mathbb{O}(r_{2})}\|\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}-{\mathbf{U}}_{2}\mathbf{W}\|_{2,\infty}$
$\displaystyle\leq\|\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}-{\mathbf{U}}_{2}\mathbf{W}_{2}^{(t_{0}-1)}\|_{2,\infty}$
$\displaystyle\leq\mu_{0}\sqrt{\frac{r_{2}}{p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{((2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}.$

Therefore,

$\displaystyle\|\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}-\mathcal{P}_{{\mathbf{U}}_{2}}\|_{2,\infty}$
$\displaystyle\leq
3\mu_{0}\sqrt{\frac{r_{2}}{p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}.$

Similarly,

$\displaystyle\|\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}-\mathcal{P}_{{\mathbf{U}}_{3}}\|_{2,\infty}$
$\displaystyle\leq
3\mu_{0}\sqrt{\frac{r_{3}}{p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}.$

Therefore,

$\displaystyle(IV)$
$\displaystyle\leq\bigg{\|}\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}-\mathcal{P}_{{\mathbf{U}}_{2}}\bigg{\|}_{2,\infty}\|\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\|_{2,\infty};$
$\displaystyle\leq
6\mu_{0}^{2}\sqrt{\frac{r_{3}}{p_{3}}}\sqrt{\frac{r_{2}}{p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)};$
$\displaystyle(V)$
$\displaystyle\leq\bigg{\|}\mathcal{P}_{{\mathbf{U}}_{2}}\otimes\bigg{[}\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}-\mathcal{P}_{{\mathbf{U}}_{3}}\bigg{]}\bigg{\|}_{2,\infty}$
$\displaystyle\leq
3\mu_{0}^{2}\sqrt{\frac{r_{2}}{p_{2}}}\sqrt{\frac{r_{3}}{p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}.$

Finally,

$\displaystyle(VI)$
$\displaystyle\coloneqq\bigg{\|}\mathcal{P}_{{\mathbf{U}}_{2}}\otimes\mathcal{P}_{{\mathbf{U}}_{3}}\mathbf{V}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle=\|\mathbf{V}_{1}\|_{2,\infty}$
$\displaystyle\leq\mu_{0}\sqrt{\frac{r_{1}}{p_{-1}}}.$

Plugging all of these bounds in we obtain (with $c=6$)

$\displaystyle\|\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}\mathbf{V}_{1}\|_{2,\infty}$
$\displaystyle\leq
c\Bigg{\\{}\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{p_{j}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)};$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}\sqrt{\frac{r_{1}}{p_{-1}}}\Bigg{\\}}.$

This shows that the first part of the event in
$\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}$ must hold. For the second part of
the event, we note that

$\displaystyle\|\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}\otimes\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}\|_{2,\infty}$
$\displaystyle\leq\|\bigg{(}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{)}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}\|_{2,\infty}$
$\displaystyle\qquad+\|\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\otimes\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}\|_{2,\infty}$
$\displaystyle\leq\|\bigg{(}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{)}\otimes\bigg{(}\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{)}\|_{2,\infty}$
$\displaystyle\qquad+\|\bigg{(}\mathcal{P}_{\mathbf{\widetilde{U}}_{2}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\bigg{)}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\|_{2,\infty}$
$\displaystyle\qquad+\|\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\otimes\bigg{(}\mathcal{P}_{\mathbf{\widetilde{U}}_{3}^{(t_{0}-1,j-m)}}-\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\bigg{)}\|_{2,\infty}$
$\displaystyle\qquad+\|\mathcal{P}_{\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}}\otimes\mathcal{P}_{\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}}\|_{2,\infty}$
$\displaystyle\leq
4\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{p_{j}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+4\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+4\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+4\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}.$

where we used the fact that
$\|\mathbf{\widehat{U}}_{3}^{(t_{0}-1)}\|_{2,\infty}\leq
2\mu_{0}\sqrt{\frac{r_{3}}{p_{3}}}$ on the events in question, and similarly
for $\mathbf{\widehat{U}}_{2}^{(t_{0}-1)}$. This shows the second part of the
event must hold, which completes the proof. ∎

######  Lemma 9 (Proximity of the Leave-one-out Sequence on a good event).

Let $1\leq j\leq 3$ and $1\leq m\leq p_{j}$ be fixed. Then

$\displaystyle\mathbb{P}\Bigg{\\{}\bigg{\\{}\|\sin\Theta(\mathbf{\widehat{U}}_{k}^{t_{0}},\mathbf{\widetilde{U}}_{k}^{t_{0},j-m})\|\geq\bigg{(}\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{k}}{p_{j}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,k}\Bigg{\\}}$
$\displaystyle\leq p^{-29}.$

###### Proof.

On the event $\mathcal{E}_{\mathrm{Good}}$ it holds that $\tau_{k}\leq
C\sqrt{pr}\ll\lambda$ by assumption, since $r\leq Cp_{\min}^{1/2}$ and
$\lambda\gtrsim\kappa p/p_{\min}^{1/4}\sqrt{\log(p)}$. Therefore, the eigengap
assumption in Lemma 7 is met, so on the event $\mathcal{E}_{\mathrm{Good}}$ it
holds that

$\displaystyle\|\sin\Theta(\mathbf{\widehat{U}}_{k}^{(t)},\mathbf{\widetilde{U}}_{k}^{t,j-m})\|$
$\displaystyle\leq\frac{16\kappa}{\lambda}\tau_{k}\bigg{(}\eta_{k}^{(t_{0},j-m)}\bigg{)}+\frac{16\kappa}{\lambda}\xi_{k}^{t_{0},j-m}\bigg{(}\eta_{k}^{(t_{0},j-m)}\bigg{)}$
$\displaystyle\qquad+\frac{8\kappa}{\lambda}\widetilde{\xi}_{k}^{t_{0},j-m}+\frac{16}{\lambda^{2}}\tau_{k}^{2}\bigg{(}\eta_{k}^{(t_{0},j-m)}\bigg{)}+\frac{8}{\lambda^{2}}\tau_{k}\xi_{k}^{t_{0},j-m}+\frac{4}{\lambda^{2}}(\xi_{k}^{t_{0},j-m})^{2},$

where we recall the notation

$\displaystyle\eta_{k}^{(t,j-m)}$
$\displaystyle\coloneqq\begin{cases}\left\|\sin\Theta\left(\widetilde{\mathbf{U}}_{k+1}^{t-1,j-m},\widehat{\mathbf{U}}_{k+1}^{(t-1)}\right)\right\|+\left\|\sin\Theta\left(\widetilde{\mathbf{U}}_{k+2}^{t-1,j-m},\widehat{\mathbf{U}}_{k+2}^{(t-1)}\right)\right\|&k=1;\\\
\left\|\sin\Theta\left(\widetilde{\mathbf{U}}_{k+1}^{t-1,j-m},\widehat{\mathbf{U}}_{k+1}^{(t-1)}\right)\right\|+\left\|\sin\Theta\left(\widetilde{\mathbf{U}}_{k+2}^{t,j-m},\widehat{\mathbf{U}}_{k+2}^{(t)}\right)\right\|&k=2\\\
\left\|\sin\Theta\left(\widetilde{\mathbf{U}}_{k+1}^{t,j-m},\widehat{\mathbf{U}}_{k+1}^{(t)}\right)\right\|+\left\|\sin\Theta\left(\widetilde{\mathbf{U}}_{k+2}^{t,j-m},\widehat{\mathbf{U}}_{k+2}^{(t)}\right)\right\|&k=3;\end{cases};$
$\displaystyle\xi_{k}^{(t,j-m)}$
$\displaystyle\coloneqq\left\|\left(\mathbf{Z}_{k}^{j-m}-\mathbf{Z}_{k}\right)\widetilde{\mathcal{P}}_{k}^{t,j-m}\right\|;$
$\displaystyle\widetilde{\xi}_{k}^{(t,j-m)}$
$\displaystyle\coloneqq\left\|\left(\mathbf{Z}_{k}^{j-m}-\mathbf{Z}_{k}\right)\widetilde{\mathcal{P}}_{k}^{t,j-m}\mathbf{V}_{k}\right\|.$

Similar to Lemma 8 we now complete the proof for $k=1$ without loss of
generality (if $k=2$ or $3$, the proof is similar since slightly stronger
bounds hold, but this again is not needed for our analysis). On the event
$\mathcal{E}_{\mathrm{Good}}\cap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}$, we
have the additional bounds

$\displaystyle\tau_{1}$ $\displaystyle\leq C_{1}\sqrt{pr};$
$\displaystyle\eta_{1}^{(t_{0},j-m)}$
$\displaystyle\leq\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}.$

Plugging this in to the deterministic bound for
$\|\sin\Theta(\mathbf{\widehat{U}}_{k}^{(t)},\mathbf{\widetilde{U}}_{k}^{t,j-m})\|$
above yields

$\displaystyle\|\sin\Theta(\mathbf{\widehat{U}}_{1}^{(t)},\mathbf{\widetilde{U}}_{1}^{t,j-m})\|$
$\displaystyle\leq\frac{16C_{1}\kappa}{\lambda}\sqrt{pr}\bigg{(}\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{)}$
$\displaystyle\quad+\frac{16\kappa}{\lambda}\xi_{k}^{t_{0},j-m}\bigg{(}\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{)}$
$\displaystyle\qquad+\frac{8\kappa}{\lambda}\widetilde{\xi}_{k}^{t_{0},j-m}+\frac{16C_{1}^{2}pr}{\lambda^{2}}\bigg{(}\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{)}$
$\displaystyle\quad+\frac{8C_{1}\sqrt{pr}}{\lambda^{2}}\xi_{k}^{t_{0},j-m}+\frac{4}{\lambda^{2}}(\xi_{k}^{t_{0},j-m})^{2}.$

Observe that

$\displaystyle\frac{16C_{1}\kappa}{\lambda}$
$\displaystyle\sqrt{pr}\bigg{(}\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{)}$
$\displaystyle=\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\frac{16C_{1}\kappa\sqrt{pr}}{\lambda}\frac{C_{0}\kappa\sqrt{p_{2}\log(p)}}{\lambda}+\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}\frac{16C_{1}\kappa\sqrt{pr}}{\lambda}\frac{C_{0}\kappa\sqrt{p_{3}\log(p)}}{\lambda}$
$\displaystyle\quad+\frac{16C_{1}\kappa\sqrt{pr}}{\lambda}\bigg{(}\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}+\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\bigg{)}\frac{1}{2^{t_{0}-1}}$
$\displaystyle=\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\frac{C_{0}\kappa\sqrt{p_{1}\log(p)}}{\lambda}\bigg{(}\frac{16C_{1}\kappa\sqrt{pr}\sqrt{\frac{p_{2}}{p_{1}}}\sqrt{\frac{r_{2}}{r_{1}}}}{\lambda}+\frac{16C_{1}\kappa\sqrt{pr}\sqrt{\frac{p_{3}}{p_{1}}}\sqrt{\frac{r_{3}}{r_{1}}}}{\lambda}\bigg{)}$
$\displaystyle\quad+\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\frac{1}{2^{t_{0}-1}}\bigg{(}\frac{16C_{1}\kappa\sqrt{pr}\sqrt{\frac{r_{3}}{r_{1}}}}{\lambda}+\frac{16C_{1}\kappa\sqrt{pr}\sqrt{\frac{r_{2}}{r_{1}}}}{\lambda}\bigg{)}$
$\displaystyle\leq\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}\bigg{(}\frac{32C_{1}\kappa\sqrt{pr}\sqrt{\frac{p}{p_{\min}}}}{\lambda}\max\bigg{\\{}\sqrt{\frac{r_{3}}{r_{1}}},\sqrt{\frac{r_{2}}{r_{1}}}\bigg{\\}}\bigg{)}$
$\displaystyle\quad+\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\frac{1}{2^{t_{0}-1}}\bigg{(}\frac{32C_{1}\kappa\sqrt{pr}}{\lambda}\max\bigg{\\{}\sqrt{\frac{r_{3}}{r_{1}}},\sqrt{\frac{r_{2}}{r_{1}}}\bigg{\\}}\bigg{)}$
$\displaystyle\leq\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}\bigg{(}\frac{32C_{1}C_{2}\kappa
p/p_{\min}^{1/4}}{\lambda}\bigg{\\}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\frac{1}{2^{t_{0}-1}}\bigg{(}\frac{32C_{1}C_{2}\kappa\sqrt{pr}}{\lambda}\bigg{)}$
$\displaystyle\leq\frac{1}{8}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)},$

which holds under the assumption
$\lambda\gtrsim\kappa\sqrt{\log(p)}p/p_{\min}^{1/4}$, $r_{k}/r_{j}\leq C$, and
$\mu_{0}^{2}r\lesssim p_{\min}^{1/2}$. By a similar argument,

$\displaystyle\frac{16C_{1}^{2}pr}{\lambda^{2}}\bigg{(}\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\leq\frac{1}{8}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}.$

Therefore,

$\displaystyle\|\sin\Theta(\mathbf{\widehat{U}}_{1}^{(t)},\mathbf{\widetilde{U}}_{1}^{t,j-m})\|$
$\displaystyle\leq\frac{1}{8}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}+\frac{8\kappa}{\lambda}\widetilde{\xi}_{1}^{t_{0},j-m}$
$\displaystyle\quad+\xi_{1}^{t_{0},j-m}\frac{16\kappa}{\lambda}\bigg{(}\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{)}$
$\displaystyle\quad+\frac{8C_{1}\sqrt{pr}}{\lambda^{2}}\xi_{1}^{t_{0},j-m}+\frac{4}{\lambda^{2}}(\xi_{1}^{t_{0},j-m})^{2}.$

The bound above depends only on $\xi_{1}^{t_{0},j-m}$ and
$\widetilde{\xi}_{1}^{t_{0},j-m}$. Define

$\displaystyle(I)$
$\displaystyle\coloneqq\xi_{1}^{t_{0},j-m}\bigg{\\{}\frac{16\kappa}{\lambda}\bigg{(}\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{)}+\frac{8C_{1}\sqrt{pr}}{\lambda^{2}}\bigg{\\}};$
$\displaystyle(II)$
$\displaystyle\coloneqq\frac{4}{\lambda^{2}}(\xi_{1}^{t_{0},j-m})^{2};$
$\displaystyle(III)$
$\displaystyle\coloneqq\frac{8\kappa}{\lambda}\widetilde{\xi}_{1}^{t_{0},j-m}.$

Then

$\displaystyle\mathbb{P}\Bigg{\\{}\bigg{\\{}\|$
$\displaystyle\sin\Theta(\mathbf{\widehat{U}}_{1}^{t_{0}},\mathbf{\widetilde{U}}_{1}^{t_{0},j-m})\|\geq\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\Bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}(I)\geq\frac{1}{4}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\Bigg{\\}}$
$\displaystyle\quad+\mathbb{P}\Bigg{\\{}\bigg{\\{}(II)\geq\frac{1}{4}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\Bigg{\\}}$
$\displaystyle\quad+\mathbb{P}\Bigg{\\{}\bigg{\\{}(III)\geq\frac{1}{4}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\Bigg{\\}}.$

We now will derive probabilistic bounds for each of the terms above on the
event
$\mathcal{E}_{\mathrm{Good}}\cap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}$. We
will consider each term separately, though the strategy for each will remain
the same: since there is nontrivial dependence between the events above and
the random variable $\xi_{1}^{j-m}$, we use the auxiliary event
$\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}$, which is independent of the nonzero
entries in the random matrix $\mathbf{Z}_{1}^{j-m}-\mathbf{Z}_{1}$. We then
use Lemma 8 to show that the intersection of this event with other events is
empty.

The term $(I)$: We note that

$\displaystyle\mathbb{P}\Bigg{\\{}$
$\displaystyle\bigg{\\{}(I)\geq\frac{1}{4}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\Bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}(I)\geq\frac{1}{4}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\bigcap\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}\Bigg{\\}}$
$\displaystyle\qquad+\mathbb{P}\Bigg{\\{}\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\bigcap\big{(}\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}\big{)}^{c}\Bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}(I)\geq\frac{1}{4}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{\\}}\bigcap\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}\Bigg{\\}},$

where we have used Lemma 8 to show that the intesection of the complement
$\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}$ with the other events is zero.

Now we simply observe that $\mathcal{\widetilde{E}}_{j-m}^{t_{0},k}$ does not
depend on any of the random variables in the matrix
$\mathbf{Z}_{k}^{j-m}-\mathbf{Z}_{k}$, so we are free to condition on this
event. Recall that

$\displaystyle\xi_{k}^{t_{0},j-m}$
$\displaystyle=\bigg{\|}\bigg{(}\mathbf{Z}_{k}-\mathbf{Z}_{k}^{j-m}\bigg{)}\mathcal{\widetilde{P}}_{1}^{t_{0},j-m}\bigg{\|}.$

By Lemma 17, it holds that

$\displaystyle\xi_{1}^{t_{0},j-m}$ $\displaystyle\leq
C\sqrt{p_{-j}\log(p)}\bigg{\|}\mathcal{\widetilde{P}}_{1}^{t_{0},j-m}\bigg{\|}_{2,\infty}$

with probability at least $1-O(p^{-30})$. On the event
$\mathcal{\widetilde{E}}_{j-m}^{t_{0},k}$ we have that

$\displaystyle\bigg{\|}\mathcal{\widetilde{P}}_{1}^{t_{0},j-m}\bigg{\|}_{2,\infty}$
$\displaystyle\leq
c\Bigg{\\{}\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{p_{j}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{\\}}.$

Therefore,

$\displaystyle\xi_{1}^{t_{0},j-m}$ $\displaystyle\leq
C^{\prime}\sqrt{p_{-j}\log(p)}\bigg{(}\frac{\mu_{0}^{2}\sqrt{r_{2}r_{3}}}{p_{j}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\mu_{0}^{2}\sqrt{r_{2}r_{3}}}{p_{j}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+2\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{)}$
$\displaystyle\quad+C^{\prime}\sqrt{p_{-j}\log(p)}\bigg{(}\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{p_{j}}\frac{1}{2^{t_{0}-1}}\frac{1}{2^{t_{0}-1}}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}}}\frac{1}{2^{t_{0}-1}}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}}}\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\leq
C^{\prime\prime}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\sqrt{p_{1}\log(p)}\sqrt{p_{-1}}\Bigg{\\{}\frac{\mu_{0}\sqrt{r_{2}r_{3}}}{p_{j}\sqrt{r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{)}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\Bigg{\\}}$
$\displaystyle\quad+C^{\prime\prime}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\sqrt{p_{1}\log(p)}\sqrt{p_{-1}}\Bigg{\\{}\frac{\mu_{0}\sqrt{r_{2}r_{3}}}{p_{j}\sqrt{r_{1}}}\frac{1}{2^{t_{0}-1}}+2\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}r_{1}}}\frac{1}{2^{t_{0}-1}}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}r_{1}}}\frac{1}{2^{t_{0}-1}}\Bigg{\\}},$

where we have absorbed the constants in each term. Therefore, with probability
at least $1-O(p^{-30})$ it holds that

$\displaystyle(I)$ $\displaystyle\leq
C^{\prime\prime}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\sqrt{p_{1}\log(p)}\sqrt{p_{-1}}\Bigg{\\{}\frac{\mu_{0}\sqrt{r_{2}r_{3}}}{p_{j}\sqrt{r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{)}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\Bigg{\\}}$
$\displaystyle\quad\quad\times\bigg{\\{}\frac{16\kappa}{\lambda}\bigg{(}\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{)}+\frac{8C_{1}\sqrt{pr}}{\lambda^{2}}\bigg{\\}}$
$\displaystyle\quad+C^{\prime\prime}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\sqrt{p_{1}\log(p)}\sqrt{p_{-1}}\Bigg{\\{}\frac{\mu_{0}\sqrt{r_{2}r_{3}}}{p_{j}\sqrt{r_{1}}}\frac{1}{2^{t_{0}-1}}+2\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}r_{1}}}\frac{1}{2^{t_{0}-1}}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}r_{1}}}\frac{1}{2^{t_{0}-1}}\Bigg{\\}}$
$\displaystyle\quad\quad\times\bigg{\\{}\frac{16\kappa}{\lambda}\bigg{(}\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{)}+\frac{8C_{1}\sqrt{pr}}{\lambda^{2}}\bigg{\\}}.$

We now show the first term is less than
$\frac{1}{8}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}$
and the second term is less than
$\frac{1}{8}\frac{1}{2^{t_{0}}}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}$. The first
term will be less than this provided that

$\displaystyle\frac{8}{C_{0}C^{\prime\prime}}\sqrt{p_{-1}}$
$\displaystyle\Bigg{\\{}\frac{\mu_{0}\sqrt{r_{2}r_{3}}}{p_{j}\sqrt{r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{)}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\Bigg{\\}}$
$\displaystyle\quad\quad\times\bigg{\\{}16\bigg{(}\mu_{0}\sqrt{\frac{r_{2}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{3}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{)}+\frac{8C_{1}\sqrt{pr}}{\lambda\kappa}\bigg{\\}}$

is less than one. This follows from basic algebra and the assumptions
$\lambda\gtrsim\kappa\sqrt{\log(p)}p/p_{\min}^{1/4}$, that
$\mu_{0}^{2}r\lesssim p_{\min}^{1/2}$, and that $r_{k}\asymp r$. A similar
argument shows that the second term is smaller than
$\frac{1}{8}\frac{1}{2^{t_{0}}}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}$. Therefore,
on the event $\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}$, with probability at
least $1-O(p^{-30})$ it holds that

$\displaystyle(I)$
$\displaystyle\leq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}.$

The term (II): By a similar argument, we note that

$\displaystyle\mathbb{P}$
$\displaystyle\Bigg{\\{}\left\\{(II)\geq\frac{1}{4}\left(\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\right)\mu_{0}\sqrt{\frac{r_{k}}{p_{j}}}\right\\}\bigcap\mathcal{E}_{\text{Good
}}\bigcap\mathcal{E}_{\text{main }}^{t_{0}-1,1}\Bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}(II)\geq\frac{1}{4}\left(\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\right)\mu_{0}\sqrt{\frac{r_{k}}{p_{j}}}\bigg{\\}}\bigcap\mathcal{E}_{\text{Good
}}\bigcap\mathcal{E}_{\text{main
}}^{t_{0}-1,1}\bigcap\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}\Bigg{\\}}$
$\displaystyle\qquad+\mathbb{P}\bigg{\\{}\mathcal{E}_{\text{Good
}}\bigcap\mathcal{E}_{\text{main
}}^{t_{0}-1,1}\bigcap(\mathcal{\widetilde{E}}_{j-m}^{t_{0},1})^{c}\bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}(II)\geq\frac{1}{4}\left(\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\right)\mu_{0}\sqrt{\frac{r_{k}}{p_{j}}}\bigg{\\}}\bigcap\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}\Bigg{\\}},$

where again we used Lemma 8. Conditioning on the event
$\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}$, by the same argument as in Term
$(I)$, with probability at least $1-O(p^{-30})$ one has

$\displaystyle\xi_{1}^{j-m}$
$\displaystyle\leq\widetilde{C}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\sqrt{p_{1}\log(p)}\sqrt{p_{-1}}\Bigg{\\{}\frac{\mu_{0}\sqrt{r_{2}r_{3}}}{p_{j}\sqrt{r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{)}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\Bigg{\\}}$
$\displaystyle\quad+\widetilde{C}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\sqrt{p_{1}\log(p)}\sqrt{p_{-1}}\Bigg{\\{}\frac{\mu_{0}\sqrt{r_{2}r_{3}}}{p_{j}\sqrt{r_{1}}}\frac{1}{2^{t_{0}-1}}+2\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}r_{1}}}\frac{1}{2^{t_{0}-1}}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}r_{1}}}\frac{1}{2^{t_{0}-1}}\Bigg{\\}},$

where we have once again absorbed the constant. Therefore, with probability at
least $1-O(p^{-30})$,

$\displaystyle(II)$
$\displaystyle=\frac{4}{\lambda^{2}}\big{(}\xi_{1}^{j-m}\big{)}^{2}$
$\displaystyle\leq\frac{4}{\lambda^{2}}\widetilde{C}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\sqrt{p_{1}\log(p)}\sqrt{p_{-1}}\Bigg{\\{}\frac{\mu_{0}\sqrt{r_{2}r_{3}}}{p_{j}\sqrt{r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{)}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\Bigg{\\}}$
$\displaystyle\quad+\frac{4}{\lambda^{2}}\widetilde{C}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\sqrt{p_{1}\log(p)}\sqrt{p_{-1}}\Bigg{\\{}\frac{\mu_{0}\sqrt{r_{2}r_{3}}}{p_{j}\sqrt{r_{1}}}\frac{1}{2^{t_{0}-1}}+2\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}r_{1}}}\frac{1}{2^{t_{0}-1}}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}r_{1}}}\frac{1}{2^{t_{0}-1}}\Bigg{\\}},$
$\displaystyle=\frac{1}{8}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{(}\frac{4\widetilde{C}\sqrt{p_{-1}}}{C_{0}\lambda}\bigg{)}\times\Bigg{\\{}\frac{\mu_{0}\sqrt{r_{2}r_{3}}}{p_{j}\sqrt{r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{)}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\Bigg{\\}}$
$\displaystyle\quad+\frac{1}{8}\frac{1}{2^{t_{0}}}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{(}\frac{4\widetilde{C}\sqrt{p_{-1}}}{C_{0}\lambda}\bigg{)}\Bigg{\\{}\frac{\mu_{0}\sqrt{r_{2}r_{3}}}{p_{j}\sqrt{r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{)}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\Bigg{\\}}$
$\displaystyle\leq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}},$

where the final inequality holds when the additional terms are smaller than
one, which holds via basic algebra as long as $C_{0}\geq 4C\widetilde{C}$,
$\lambda\gtrsim\kappa\sqrt{\log(p)}p/p_{\min}^{1/4}$, $r_{k}\asymp r$ and
$\mu_{0}^{2}r\lesssim p_{\min}^{1/2}$.

The term (III): Proceeding similarly again,

$\displaystyle\mathbb{P}$
$\displaystyle\Bigg{\\{}\left\\{(III)\geq\frac{1}{4}\left(\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\right)\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\right\\}\bigcap\mathcal{E}_{\text{Good
}}\bigcap\mathcal{E}_{\text{main }}^{t_{0}-1,1}\Bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}(III)\geq\frac{1}{4}\left(\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\right)\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{\\}}\bigcap\mathcal{E}_{\text{Good
}}\bigcap\mathcal{E}_{\text{main
}}^{t_{0}-1,1}\bigcap\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}\Bigg{\\}}$
$\displaystyle\qquad+\mathbb{P}\bigg{\\{}\mathcal{E}_{\text{Good
}}\bigcap\mathcal{E}_{\text{main
}}^{t_{0}-1,1}\bigcap(\mathcal{\widetilde{E}}_{j-m}^{t_{0},1})^{c}\bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}(III)\geq\frac{1}{4}\left(\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\right)\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{\\}}\bigcap\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}\Bigg{\\}},$

where again we used Lemma 8. Conditioning on the event
$\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}$, by Lemma 17, with probability at
least $1-O(p^{-30})$ one has

$\displaystyle\widetilde{\xi}_{1}^{j-m}$
$\displaystyle=\bigg{\|}\bigg{(}\mathbf{Z}_{1}^{j-m}-\mathbf{Z}_{1}\bigg{)}\mathcal{\widetilde{P}}_{1}^{t_{0},j-m}\mathbf{V}_{1}\bigg{\|}$
$\displaystyle\leq
C\sqrt{p_{-j}\log(p)}\bigg{\|}\mathcal{\widetilde{P}}_{1}^{t_{0},j-m}\mathbf{V}_{k}\bigg{\|}_{2,\infty}.$

On the event $\mathcal{\widetilde{E}}_{j-m}^{t_{0},1}$ it holds that

$\displaystyle\|\mathcal{\widetilde{P}}_{k}^{t_{0},j-m}\mathbf{V}_{1}\|_{2,\infty}$
$\displaystyle\leq
c\Bigg{\\{}\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{p_{j}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)};$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}\sqrt{\frac{r_{1}}{p_{-1}}}\Bigg{\\}}.$

Therefore, with probability at least $1-O(p^{-30})$,

$\displaystyle(III)$
$\displaystyle\coloneqq\frac{8\kappa}{\lambda}\widetilde{\xi}_{1}^{t_{0},j-m}$
$\displaystyle\leq\frac{8C\kappa}{\lambda}\sqrt{p_{-j}\log(p)}$
$\displaystyle\quad\quad\times
c\Bigg{\\{}\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{p_{j}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad\quad\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad\quad\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{1}}{p_{-1}}}\Bigg{\\}}$
$\displaystyle=\frac{1}{8}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{(}\frac{64C^{\prime}}{C_{0}}\sqrt{p_{-1}}\bigg{)}$
$\displaystyle\quad\quad\times\Bigg{\\{}\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{p_{j}\sqrt{r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad\quad\quad+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{3}r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{j}p_{2}r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad\quad\quad+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\sqrt{\frac{1}{p_{-1}}}\Bigg{\\}}$
$\displaystyle\leq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}},$

where the final inequality holds by basic algebra as long as $C_{0}\geq
64CC^{\prime}$ for some other constant $C^{\prime}$, as well as the
assumptions $\lambda\gtrsim\kappa\sqrt{\log(p)}p/p_{\min}^{1/4}$, $r_{k}\asymp
r$ and $\mu_{0}^{2}r\lesssim p_{\min}^{1/2}$.

Consequently, we have shown that the desired bounds on the terms $(I)$,
$(II)$, and $(III)$ hold with probability at most $O(p^{-30})\leq p^{-29}$ as
desired. ∎

######  Lemma 10 (Bounding the linear term on a good event).

Let $t_{0}$ and $k$ be fixed, and let $m$ be such that $1\leq m\leq p_{k}$.
Then

$\displaystyle\mathbb{P}\Bigg{\\{}\bigg{\\{}\|e_{m}^{\top}\mathbf{L}_{k}^{t_{0}}\|\geq\frac{1}{4}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{k}}{p_{k}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,k}\Bigg{\\}}\leq
p^{-29}.$

###### Proof of Lemma 10.

The proof of this is similar to the proof of Lemma 9, only using the
deterministic bound in Lemma 4 instead of the deterministic bound in Lemma 7.
Once again without loss of generality we prove the result for $k=1$; the
bounds for $k=2$ and $k=3$ are similar.

First, on the event $\mathcal{E}_{\mathrm{Good}}$, it holds that
$\lambda/2\leq\lambda_{r_{1}}(\mathbf{\widehat{\Lambda}}_{k}^{(t_{0}-1)})$ for
$t_{0}\geq 1$. By Lemma 4, it holds that

$\displaystyle\|e_{m}^{\top}\mathbf{L}_{k}^{t_{0}}\|$
$\displaystyle\leq\frac{8\kappa}{\lambda}\|{\mathbf{U}}_{1}\|_{2,\infty}\bigg{(}\tau_{1}\eta_{1}^{(t)}+\|{\mathbf{U}}_{1}^{\top}\mathbf{Z}_{k}\mathbf{V}_{1}\|\bigg{)}+\frac{8\kappa}{\lambda}\bigg{(}\tau_{k}\eta_{k}^{(t,k-m)}\bigg{)}+\frac{4\kappa}{\lambda}\widetilde{\xi}_{k}^{t_{0},k-m}.$

On the event
$\mathcal{E}_{\mathrm{main}}^{t_{0}-1,k}\cap\mathcal{E}_{\mathrm{Good}}$, we
have the following bounds:

$\displaystyle\tau_{1}$ $\displaystyle\leq C_{1}\sqrt{pr};$
$\displaystyle\|{\mathbf{U}}_{1}^{\top}\mathbf{Z}_{1}\mathbf{V}_{1}\|$
$\displaystyle\leq C_{1}\big{(}\sqrt{r}+\sqrt{\log(p)}\big{)};$
$\displaystyle\eta_{1}^{(t)}$
$\displaystyle\leq\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{2}{2^{t_{0}-1}};$
$\displaystyle\eta_{1}^{(t,1-m)}$
$\displaystyle\leq\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\mu_{0}\sqrt{\frac{r_{2}}{p_{1}}}+\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\mu_{0}\sqrt{\frac{r_{3}}{p_{1}}}.$

Plugging in these bounds yields

$\displaystyle\|e_{m}^{\top}\mathbf{L}_{k}^{t_{0}}\|$
$\displaystyle\leq\frac{8C\kappa}{\lambda}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\sqrt{pr}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{2}{2^{t_{0}-1}}\bigg{)}+\sqrt{r}+\sqrt{\log(p)}\bigg{)}$
$\displaystyle\quad+\frac{8C\sqrt{pr}\kappa}{\lambda}\bigg{(}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\mu_{0}\sqrt{\frac{r_{2}}{p_{1}}}+\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\mu_{0}\sqrt{\frac{r_{3}}{p_{1}}}\bigg{)}+\frac{4\kappa}{\lambda}\widetilde{\xi}_{k}^{t_{0},k-m}$
$\displaystyle\leq\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\frac{8C\kappa}{\lambda}\Bigg{[}\sqrt{pr}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{)}+\sqrt{r}+\sqrt{\log(p)}\Bigg{]}+\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\frac{8C\kappa\sqrt{pr}}{\lambda}\frac{2}{2^{t_{0}-1}}$
$\displaystyle\quad+\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\frac{8C\sqrt{pr}\kappa}{\lambda}\sqrt{\frac{r_{2}}{r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\frac{8C\sqrt{pr}\kappa}{\lambda}\sqrt{\frac{r_{3}}{r_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\frac{4\kappa}{\lambda}\widetilde{\xi}_{k}^{t_{0},k-m}$
$\displaystyle\leq\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}\bigg{(}\frac{8C}{C_{0}\sqrt{p_{1}\log(p)}}\bigg{)}\Bigg{[}\sqrt{pr}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{)}+\sqrt{r}+\sqrt{\log(p)}+\sqrt{\frac{r_{2}}{r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\sqrt{\frac{r_{3}}{r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\Bigg{]}$
$\displaystyle\quad+\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\frac{1}{2^{t_{0}}}\frac{32C\kappa\sqrt{pr}}{\lambda}+\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\frac{1}{2^{t_{0}}}\frac{32C\sqrt{pr}{\kappa}}{\lambda}\sqrt{\frac{r}{r_{1}}}$
$\displaystyle\quad+\frac{4\kappa}{\lambda}\widetilde{\xi}_{1}^{t_{0},1-m}$
$\displaystyle\leq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}+\frac{4\kappa}{\lambda}\widetilde{\xi}_{1}^{t_{0},1-m},$

where the final inequality holds as long as

$\displaystyle\bigg{(}\frac{8C}{C_{0}\sqrt{p_{1}\log(p)}}\bigg{)}\Bigg{[}\sqrt{pr}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{)}+\sqrt{r}+\sqrt{\log(p)}+\sqrt{\frac{r_{2}}{r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\sqrt{\frac{r_{3}}{r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\Bigg{]}\leq\frac{1}{8}$

and

$\displaystyle\frac{32C\kappa\sqrt{pr}}{\lambda}+\frac{32C\sqrt{pr}{\kappa}}{\lambda}\sqrt{\frac{r}{r_{1}}}\leq\frac{1}{8}.$

These two inequalities hold as long as $C_{0}$ is larger than some fixed
constant and the assumptions
$\lambda\gtrsim\kappa\sqrt{\log(p)}p/p_{\min}^{1/4}$, $r_{k}\asymp r$ and
$\mu_{0}^{2}r\lesssim p_{\min}^{1/2}$. Consequently,

$\displaystyle\mathbb{P}\Bigg{\\{}$
$\displaystyle\bigg{\\{}\|e_{m}^{\top}\mathbf{L}_{1}^{t_{0}}\|\geq\frac{1}{4}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0},1}\Bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}\frac{4\kappa}{\lambda}\widetilde{\xi}_{1}^{t_{0},1-m}\geq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0},1}\Bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}\frac{4\kappa}{\lambda}\widetilde{\xi}_{1}^{t_{0},1-m}\geq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0},1}\bigcap\mathcal{\widetilde{E}}_{1-m}^{t_{0},1}\Bigg{\\}}$
$\displaystyle\qquad+\mathbb{P}\bigg{\\{}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0},1}\bigcap(\mathcal{\widetilde{E}}_{1-m}^{t_{0},1})^{c}\bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}\frac{4\kappa}{\lambda}\widetilde{\xi}_{1}^{t_{0},1-m}\geq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{\\}}\bigcap\mathcal{\widetilde{E}}_{1-m}^{t_{0},1}\Bigg{\\}}$

where we have used Lemma 8 to conclude that the event in the penultimate line
is empty. Therefore, it suffices to bound $\widetilde{\xi}_{1}^{t_{0},1-m}$ on
the event $\mathcal{\widetilde{E}}_{1-m}^{t_{0},1}$. Since this event is
independent from the random variables belonging to
$e_{m}^{\top}\mathbf{Z}_{1}$, by Lemma 16, it holds that with probability at
least $1-O(p^{-30})$ that

$\displaystyle\widetilde{\xi}_{1}^{t_{0},1-m}$
$\displaystyle=\bigg{\|}\bigg{(}\mathbf{Z}_{1}^{1-m}-\mathbf{Z}_{1}\bigg{)}\mathcal{\widetilde{P}}_{1}^{t_{0},1-m}\mathbf{V}_{1}\bigg{\|}$
$\displaystyle\leq
C\sqrt{p_{-1}\log(p)}\bigg{\|}\mathcal{\widetilde{P}}_{1}^{t_{0},j-m}\mathbf{V}_{1}\bigg{\|}_{2,\infty}.$

On the event $\mathcal{\widetilde{E}}_{1-m}^{t_{0},1}$ it holds that

$\displaystyle\|\mathcal{\widetilde{P}}_{1}^{t_{0},1-m}\mathbf{V}_{1}\|_{2,\infty}$
$\displaystyle\leq
c\Bigg{\\{}\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{p_{1}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)};$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}\sqrt{\frac{r_{1}}{p_{-1}}}\Bigg{\\}}.$

Therefore with probability at least $1-O(p^{-30})$, one has

$\displaystyle\frac{4\kappa}{\lambda}\widetilde{\xi}_{1}^{t_{0},1-m}$
$\displaystyle\leq\frac{4C\kappa\sqrt{\log(p)}}{\lambda}\sqrt{p_{-1}}$
$\displaystyle\times\Bigg{\\{}\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{p_{1}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)};$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{1}}{p_{-1}}}\Bigg{\\}}$
$\displaystyle\leq\frac{C_{0}\kappa\sqrt{p_{1}\log(p)}}{\lambda}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{4C\sqrt{p_{-1}}}{C_{0}}\bigg{)}$
$\displaystyle\times\Bigg{\\{}\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{r_{1}}p_{1}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)};$
$\displaystyle\quad+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{r_{1}p_{1}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{r_{1}p_{1}p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{r_{1}p_{2}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{r_{1}p_{2}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\sqrt{\frac{1}{p_{-1}}}\Bigg{\\}}$
$\displaystyle\leq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}},$

where the final inequality holds by similar algebraic manipulations as in the
previous part of this proof provided that $C_{0}$ is larger than some fixed
constant together with the assumptions
$\lambda\gtrsim\kappa\sqrt{\log(p)}p/p_{\min}^{1/4}$, $r_{k}\asymp r$ and
$\mu_{0}^{2}r\lesssim p_{\min}^{1/2}$. This completes the proof. ∎

######  Lemma 11 (Bounding the quadratic term on a good event).

The quadratic term satisfies

$\displaystyle\mathbb{P}\Bigg{\\{}\bigg{\\{}\|e_{m}^{\top}\mathbf{Q}_{k}^{(t)}\|\geq\frac{1}{4}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}+\frac{1}{2^{t}}\bigg{)}\mu_{0}\sqrt{\frac{r_{k}}{p_{k}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\bigcap\mathcal{E}_{\mathrm{Good}}\Bigg{\\}}\leq
p^{-29}.$

###### Proof.

Again without loss of generality we prove the result for $k=1$; the bounds for
$k=2$ and $3$ are similar. First, on the event $\mathcal{E}_{\mathrm{Good}}$
it holds that
$\lambda/2\leq\lambda_{r_{1}}(\mathbf{\widehat{\Lambda}}^{(t_{0}-1)})$, and
hence by Lemma 5 it holds that

$\displaystyle\|e_{m}^{\top}\mathbf{Q}_{1}^{t_{0}}\|$
$\displaystyle\leq\frac{4}{\lambda^{2}}\|{\mathbf{U}}_{1}\|_{2,\infty}\bigg{(}\tau_{1}\eta_{1}^{(t)}+\bigg{\|}{\mathbf{U}}_{1}^{\top}\mathbf{Z}_{1}\bigg{[}\mathcal{P}_{{\mathbf{U}}_{2}}\otimes\mathcal{P}_{{\mathbf{U}}_{3}}\bigg{]}\bigg{\|}\bigg{)}+\frac{16}{\lambda^{2}}\tau_{1}^{2}\bigg{(}\eta_{1}^{(t,1-m)}\bigg{)}$
$\displaystyle+\frac{4}{\lambda^{2}}\xi_{1}^{t,1-m}\bigg{(}\tau_{1}\|\sin\Theta(\mathbf{\widehat{U}}_{1}^{(t)},{\mathbf{U}}_{1})\|+\tau_{1}\eta^{(t-1)}_{1}+\bigg{\|}{\mathbf{U}}_{1}{\mathbf{U}}_{1}^{\top}\mathbf{Z}_{1}\mathcal{P}_{{\mathbf{U}}_{2}}\otimes\mathcal{P}_{{\mathbf{U}}_{3}}\bigg{\|}\bigg{)}.$

On the event
$\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\cap\mathcal{E}_{\mathrm{Good}}$, one
has the following bounds:

$\displaystyle\tau_{1}$ $\displaystyle\leq C\sqrt{pr};$
$\displaystyle\eta_{1}^{(t_{0},1-m)}$
$\displaystyle\leq\mu_{0}\sqrt{\frac{r_{2}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{3}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)};$
$\displaystyle\eta_{1}^{(t_{0})}$
$\displaystyle\leq\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{2}{2^{t_{0}-1}};$
$\displaystyle\|\sin\Theta(\mathbf{\widehat{U}}_{1}^{(t_{0}-1)},{\mathbf{U}}_{1}^{(t_{0}-1)})\|$
$\displaystyle\leq\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}-1}};$
$\displaystyle\|{\mathbf{U}}_{1}^{\top}\mathbf{Z}_{1}\mathcal{P}_{{\mathbf{U}}_{2}}\otimes\mathcal{P}_{{\mathbf{U}}_{3}}\|$
$\displaystyle\leq C(r+\sqrt{\log(p)}).$

Plugging these in yields

$\displaystyle\|e_{m}^{\top}\mathbf{Q}_{1}^{t_{0}}\|$
$\displaystyle\leq\frac{4C}{\lambda^{2}}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{[}\sqrt{pr}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{2}{2^{t_{0}-1}}\bigg{)}+r+\sqrt{\log(p)}\bigg{]}$
$\displaystyle\quad+\frac{16C^{2}pr}{\lambda^{2}}\bigg{[}\mu_{0}\sqrt{\frac{r_{2}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{3}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{]}$
$\displaystyle+\frac{4C}{\lambda^{2}}\xi_{1}^{t,1-m}\bigg{[}\sqrt{pr}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{3}{2^{t_{0}-1}}\bigg{)}+r+\sqrt{\log(p)}\bigg{]}$
$\displaystyle\leq\frac{C_{0}\sqrt{p_{1}\log(p)}}{\lambda}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{4C}{C_{0}}\frac{1}{\lambda\sqrt{p_{1}\log(p)}}\bigg{)}\bigg{[}\sqrt{pr}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{)}+r+\sqrt{\log(p)}\bigg{]}$
$\displaystyle\quad+\frac{C_{0}\sqrt{p_{1}\log(p)}}{\lambda}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{16C^{2}pr}{C_{0}\lambda\sqrt{p_{1}\log(p)}}\bigg{)}\bigg{[}\sqrt{\frac{r_{2}}{r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\sqrt{\frac{r_{3}}{r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{]}$
$\displaystyle\quad+\frac{1}{2^{t_{0}}}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{[}\frac{32C\sqrt{pr}}{\lambda}+\sqrt{\frac{r_{2}}{r_{1}}}\frac{32C^{2}pr}{\lambda^{2}}+\sqrt{\frac{r_{3}}{r_{1}}}\frac{32C^{2}pr}{\lambda^{2}}\bigg{]}$
$\displaystyle\quad+\xi_{1}^{t_{0},1-m}\frac{4C}{\lambda^{2}}\bigg{[}\sqrt{pr}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{3}{2^{t_{0}-1}}\bigg{)}+r+\sqrt{\log(p)}\bigg{]}$
$\displaystyle\leq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}$
$\displaystyle\quad+\xi_{1}^{t_{0},1-m}\frac{4C}{\lambda^{2}}\bigg{[}\sqrt{pr}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{3}{2^{t_{0}-1}}\bigg{)}+r+\sqrt{\log(p)}\bigg{]},$

where the final inequality holds as long as

$\displaystyle\bigg{(}\frac{4C}{C_{0}}\frac{1}{\lambda\sqrt{p_{1}\log(p)}}\bigg{)}\bigg{[}\sqrt{pr}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{)}+r+\sqrt{\log(p)}\bigg{]}+\bigg{(}\frac{16C^{2}pr}{C_{0}\lambda\sqrt{p_{1}\log(p)}}\bigg{)}\bigg{[}\sqrt{\frac{r_{2}}{r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\sqrt{\frac{r_{3}}{r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}\bigg{]}\leq\frac{1}{8}$

and

$\displaystyle\frac{32C\sqrt{pr}}{\lambda}+\sqrt{\frac{r_{2}}{r_{1}}}\frac{32C^{2}pr}{\lambda^{2}}+\sqrt{\frac{r_{3}}{r_{1}}}\frac{32C^{2}pr}{\lambda^{2}}\leq\frac{1}{8}.$

Both of these conditions hold when
$\lambda\gtrsim\kappa\sqrt{\log(p)}p/p_{\min}^{1/4}$, $r_{k}\asymp r$ and
$r\leq Cp_{\min}^{1/2}$ provided the constant $C_{0}$ is larger than some
fixed constant. Finally, we note that

$\displaystyle\xi_{1}^{t_{0},1-m}$
$\displaystyle\frac{4C}{\lambda^{2}}\bigg{[}\sqrt{pr}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{3}{2^{t_{0}-1}}\bigg{)}+r+\sqrt{\log(p)}\bigg{]}$
$\displaystyle\leq\frac{\xi_{1}^{t_{0},1-m}}{\lambda}\bigg{(}\frac{4C}{\lambda}\bigg{)}\bigg{[}\sqrt{pr}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{3}{2^{t_{0}-1}}\bigg{)}+r+\sqrt{\log(p)}\bigg{]}$
$\displaystyle\leq\frac{\xi_{1}^{t_{0},1-m}}{\lambda}\bigg{(}\frac{\widetilde{C}\big{(}\sqrt{pr}+r+\sqrt{\log(p)}\big{)}}{\lambda}\bigg{)}.$

Define

$\displaystyle B_{1}$
$\displaystyle\coloneqq\frac{\xi_{1}^{t_{0},1-m}}{\lambda}\bigg{(}\frac{\widetilde{C}\big{(}\sqrt{pr}+r+\sqrt{\log(p)}\big{)}}{\lambda}\bigg{)}.$

Then

$\displaystyle\mathbb{P}\Bigg{\\{}$
$\displaystyle\bigg{\\{}\|e_{m}^{\top}\mathbf{Q}_{1}^{t_{0}}\|\geq\frac{1}{4}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{\\}}\bigcap\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\bigcap\mathcal{E}_{\mathrm{Good}}\Bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}B_{1}\geq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{\\}}\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\bigcap\mathcal{E}_{\mathrm{Good}}\Bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}B_{1}\geq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{\\}}\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap\mathcal{\widetilde{E}}_{1-m}^{t_{0},1}\Bigg{\\}}$
$\displaystyle\qquad+\mathbb{P}\bigg{\\{}\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\bigcap\mathcal{E}_{\mathrm{Good}}\bigcap(\mathcal{\widetilde{E}}_{1-m}^{t_{0},1})^{c}\bigg{\\}}$
$\displaystyle\leq\mathbb{P}\Bigg{\\{}\bigg{\\{}B_{1}\geq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{\\}}\bigcap\mathcal{\widetilde{E}}_{1-m}^{t_{0},1}\Bigg{\\}},$

where we have used Lemma 8 to conclude that the event in the penultimate line
is empty. Since the event $\mathcal{\widetilde{E}}_{1-m}^{t_{0},1}$ is
independent from the random variables belonging to
$e_{m}^{\top}\mathbf{Z}_{1}$, by Lemma 16, it holds that with probability at
least $1-O(p^{-30})$ that

$\displaystyle\xi_{1}^{t_{0},1-m}$
$\displaystyle\coloneqq\bigg{\|}\bigg{(}\mathbf{Z}_{1}^{1-m}-\mathbf{Z}_{1}\bigg{)}\mathcal{\widetilde{P}}^{t_{0},1-m}_{1}\bigg{\|}$
$\displaystyle\leq
C\sqrt{p_{-1}\log(p)}\bigg{\|}\mathcal{\widetilde{P}}^{t_{0},1-m}_{1}\bigg{\|}_{2,\infty}.$

On the event $\mathcal{\widetilde{E}}_{1-m}^{t_{0},1}$, we have that

$\displaystyle\bigg{\|}\mathcal{\widetilde{P}}^{t_{0},1-m}_{1}\bigg{\|}_{2,\infty}$
$\displaystyle\leq
c\Bigg{\\{}\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{p_{1}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\Bigg{\\}}.$

Therefore, with probability at least $1-O(p^{-30})$, it holds that

$\displaystyle B_{1}$
$\displaystyle=\frac{\xi_{1}^{t_{0},1-m}}{\lambda}\bigg{(}\frac{\widetilde{C}\big{(}\sqrt{pr}+r+\sqrt{\log(p)}\big{)}}{\lambda}\bigg{)}$
$\displaystyle\leq\frac{C^{\prime}\sqrt{p_{-1}\log(p)}}{\lambda}\bigg{(}\frac{\sqrt{pr}+r+\sqrt{\log(p)}}{\lambda}\bigg{)}$
$\displaystyle\quad\quad\times\bigg{\\{}\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{p_{1}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad\quad\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{\\}}$
$\displaystyle\leq\frac{C^{\prime}\sqrt{p_{-1}\log(p)}}{\lambda}\bigg{(}\frac{\sqrt{pr}+r+\sqrt{\log(p)}}{\lambda}\bigg{)}$
$\displaystyle\quad\quad\times\bigg{\\{}\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{p_{1}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{3}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad\quad\quad+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}}}\bigg{\\}}$
$\displaystyle\leq\frac{C_{0}\sqrt{p_{1}\log(p)}}{\lambda}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\sqrt{p_{-1}}\frac{C_{0}}{C^{\prime}}\frac{\sqrt{pr}}{\lambda}\bigg{)}\bigg{(}\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{p_{1}\sqrt{r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+2\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{3}r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{2}r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}r_{1}}}\bigg{)}$
$\displaystyle\quad+\frac{1}{2^{t_{0}}}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{C^{\prime\prime}\sqrt{p_{1}}\sqrt{p_{-1}\log(p)}}{\lambda}\frac{\sqrt{pr}}{\lambda}\bigg{)}\bigg{[}\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{p_{1}\sqrt{r_{1}}}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{3}r_{1}}}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{2}r_{1}}}\bigg{]}$
$\displaystyle\leq\frac{1}{8}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}},$

where the final inequality holds as long as

$\displaystyle\bigg{(}\sqrt{p_{-1}}\frac{C_{0}}{C^{\prime}}\frac{\sqrt{pr}}{\lambda}\bigg{)}\bigg{(}\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{p_{1}\sqrt{r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+2\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{3}r_{1}}}\frac{\delta_{\mathrm{L}}^{(2)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{2}r_{1}}}\frac{\delta_{\mathrm{L}}^{(3)}}{\lambda}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{2}p_{3}r_{1}}}\bigg{)}\leq\frac{1}{8}$

and

$\displaystyle\bigg{(}\frac{C^{\prime\prime}\sqrt{p_{1}}\sqrt{p_{-1}\log(p)}}{\lambda}\frac{\sqrt{pr}}{\lambda}\bigg{)}\bigg{[}\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{p_{1}\sqrt{r_{1}}}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{3}r_{1}}}+\mu_{0}\frac{\sqrt{r_{2}r_{3}}}{\sqrt{p_{1}p_{2}r_{1}}}\bigg{]}\leq\frac{1}{8},$

both of which hold when $C_{0}$ is larger than some fixed constant and
$\lambda\gtrsim\kappa\sqrt{\log(p)}p/p_{\min}^{1/4}$, $r_{k}\asymp r$ and
$r\leq Cp_{\min}^{1/2}$. This completes the proof. ∎

###  A.4 Putting it all together: Proof of Theorem 2

Recall we define

$\displaystyle\mathcal{E}_{\mathrm{Good}}$
$\displaystyle\coloneqq\bigg{\\{}\max_{k}\tau_{k}\leq
C\sqrt{pr}\bigg{\\}}\bigcap\bigg{\\{}\|\sin\Theta(\mathbf{\widehat{U}}_{k}^{(t)},{\mathbf{U}}_{k})\|\leq\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}+\frac{1}{2^{t}}\text{
for all $t\leq t_{\max}$ and $1\leq k\leq 3$ }\bigg{\\}}$
$\displaystyle\qquad\bigcap\bigg{\\{}\max_{k}\bigg{\|}{\mathbf{U}}_{k}^{\top}\mathbf{Z}_{k}\mathbf{V}_{k}\bigg{\|}\leq
C\left(\sqrt{r}+\sqrt{\log(p)}\right)\bigg{\\}};$
$\displaystyle\qquad\bigcap\bigg{\\{}\max_{k}\bigg{\|}{\mathbf{U}}_{k}^{\top}\mathbf{Z}_{k}\mathcal{P}_{{\mathbf{U}}_{k+1}}\otimes\mathcal{P}_{{\mathbf{U}}_{k+2}}\bigg{\|}\leq
C\left(r+\sqrt{\log(p)}\right)\bigg{\\}};$
$\displaystyle\qquad\bigcap\bigg{\\{}\max_{k}\bigg{\|}\mathbf{Z}_{k}\mathbf{V}_{k}\bigg{\|}\leq
C\sqrt{p_{k}}\bigg{\\}};$ $\displaystyle\mathcal{E}_{2,\infty}^{t,k}$
$\displaystyle\coloneqq\bigg{\\{}\|\mathbf{\widehat{U}}_{k}^{(t)}-{\mathbf{U}}_{k}\mathbf{W}_{k}^{(t)}\|_{2,\infty}\leq\bigg{(}\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}+\frac{1}{2^{t}}\bigg{)}\mu_{0}\sqrt{\frac{r_{k}}{p_{k}}}\bigg{\\}};$
$\displaystyle\mathcal{E}_{j-m}^{t,k}$
$\displaystyle\coloneqq\bigg{\\{}\|\sin\Theta(\mathbf{\widetilde{U}}_{k}^{t,j-m},\mathbf{\widehat{U}}_{k}^{(t)})\|\leq\bigg{(}\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}+\frac{1}{2^{t}}\bigg{)}\mu_{0}\sqrt{\frac{r_{k}}{p_{j}}}\bigg{\\}};$
$\displaystyle\mathcal{\widetilde{E}}_{j-m}^{t,k}$
$\displaystyle\coloneqq\Bigg{\\{}\|\mathcal{\widetilde{P}}_{k}^{t_{0},j-m}\mathbf{V}_{k}\|_{2,\infty}\leq
c\Bigg{[}\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{p_{j}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+1)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)};$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{j}p_{k+2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+1)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{j}p_{k+1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{-k}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+1)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{-k}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+\mu_{0}\sqrt{\frac{r_{k}}{p_{-k}}}\Bigg{]}.\Bigg{\\}}$
$\displaystyle\bigcap\Bigg{\\{}\|\mathcal{\widetilde{P}}_{k}^{t_{0},j-m}\|_{2,\infty}\leq
c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{p_{j}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+1)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}$
$\displaystyle\quad+c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{j}p_{k+2}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+1)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{j}p_{k+1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(k+2)}}{\lambda}+\frac{1}{2^{t_{0}-1}}\bigg{)}+c\mu_{0}^{2}\frac{\sqrt{r_{-k}}}{\sqrt{p_{-k}}}.\Bigg{\\}};$
$\displaystyle\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}$
$\displaystyle\coloneqq\bigcap_{t=1}^{(t_{0}-1)}\Bigg{\\{}\bigcap_{k=1}^{3}\mathcal{E}^{t,k}_{2,\infty}\cap\bigcap_{j=1}^{3}\bigcap_{m=1}^{p_{j}}\mathcal{E}_{k-m}^{t,j}\Bigg{\\}};$
$\displaystyle\mathcal{E}_{\mathrm{main}}^{t_{0}-1,2}$
$\displaystyle\coloneqq\mathcal{E}_{\mathrm{main}}^{t_{0}-1,1}\cap\bigg{\\{}\bigcap_{k=1}^{3}\bigcap_{m=1}^{p_{k}}\mathcal{E}_{k-m}^{t_{0},1}\bigg{\\}}\cap\mathcal{E}_{2,\infty}^{t_{0},1}$
$\displaystyle\mathcal{E}_{\mathrm{main}}^{t_{0}-1,3}$
$\displaystyle\coloneqq\mathcal{E}_{\mathrm{main}}^{t_{0}-1,2}\cap\bigg{\\{}\bigcap_{k=1}^{3}\bigcap_{m=1}^{p_{k}}\mathcal{E}_{k-m}^{t_{0},2}\bigg{\\}}\cap\mathcal{E}_{2,\infty}^{t_{0},2}.$

###### Proof of Theorem 2.

We will show that by induction that with probability at least
$1-3(t_{0}+1)p^{-15}$ that simultaneously for all $t\leq t_{0}$ and each $k$

$\displaystyle\|\mathbf{\widehat{U}}_{k}^{t_{0}}-{\mathbf{U}}_{k}\mathbf{W}_{k}^{t_{0}}\|_{2,\infty}\leq\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}\mu_{0}\sqrt{\frac{r_{k}}{p_{k}}}+\frac{1}{2^{t}}\mu_{0}\sqrt{\frac{r_{k}}{p_{k}}};$
$\displaystyle\max_{1\leq m\leq p_{k}}\max_{1\leq j\leq
3}\|\sin\Theta(\mathbf{\widehat{U}}_{j}^{t_{0}},\mathbf{\widetilde{U}}_{j}^{t_{0},k-m})\|\leq\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}\mu_{0}\sqrt{\frac{r_{k}}{p_{j}}}+\frac{1}{2^{t}}\mu_{0}\sqrt{\frac{r_{k}}{p_{j}}}.$

Assuming that for the moment, suppose the algorithm is run for at most
$C\log(\kappa p/\lambda)$ iterations. Then since $\lambda\gtrsim\kappa
p\sqrt{\log(p)}/p_{\min}^{1/4}$ it holds that

$\displaystyle t$ $\displaystyle\geq\max\\{C\log(p),1\\}$

and hence that

$\displaystyle\frac{1}{2^{t}}$ $\displaystyle\leq\frac{1}{2^{C\log(\kappa
p/\lambda)}}$ $\displaystyle\leq\frac{C_{0}\sqrt{p_{k}\log(p)}}{\lambda}$
$\displaystyle\leq\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}.$

Moreover, the probability holds with at least

$\displaystyle 1-(t-1)p^{-15}\geq 1-C(\log(p)-1)p^{-15}\geq 1-p^{-10}.$

Therefore, it remains to show that the result holds by induction.

Step 1: Base Case
By Theorem 4 it holds that with probability at least $1-O(p^{-20})$ that

$\displaystyle\|\mathbf{\widehat{U}}_{k}^{S}-{\mathbf{U}}_{k}\mathbf{W}_{k}^{S}\|_{2,\infty}$
$\displaystyle\lesssim\frac{\kappa\mu_{0}\sqrt{r_{1}\log(p)}}{\lambda}+\frac{\mu_{0}\sqrt{r_{k}p_{-k}}\log(p)}{\lambda^{2}}+\kappa^{2}\mu_{0}^{2}\frac{r_{k}}{p_{k}}$
$\displaystyle\leq\bigg{(}\frac{C\kappa\sqrt{p_{k}\log(p)}}{\lambda}+\frac{1}{2}\bigg{)}\mu_{0}\sqrt{\frac{r_{k}}{p_{k}}},$

where the final inequality holds since $\lambda\gtrsim\kappa
p\sqrt{\log(p)}p_{\min}^{1/4}$ and $\mu_{0}^{2}r\leq Cp_{\min}^{1/2}$ and that
$\kappa^{2}\leq cp_{\min}^{1/4}$ as long as $c\times\sqrt{C}\leq\frac{1}{4}$.
In addition, by Lemma 2 we have the initial bound for each $k$ via

$\displaystyle\max_{j}\max_{m}\|\sin\Theta(\mathbf{\widehat{U}}_{k}^{S},\mathbf{\widetilde{U}}_{k}^{j-m})\|$
$\displaystyle\lesssim\frac{\kappa\sqrt{p_{k}\log(p)}}{\lambda}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}+\frac{(p_{1}p_{2}p_{3})^{1/2}\log(p)}{\lambda^{2}}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}$
$\displaystyle\leq\bigg{(}\frac{C\kappa\sqrt{p_{k}\log(p)}}{\lambda}+\frac{1}{2}\bigg{)}\mu_{0}\sqrt{\frac{r_{k}}{p_{j}}},$

which holds with probability at least $1-O(p^{-19})$. Therefore, we have
established the base case, which holds with probability $1-O(p^{-19})\geq
1-3p^{-15}$, as long as $C_{0}$ in the definition of $\delta_{\mathrm{L}}$
satisfies $C_{0}\geq C$, with $C$ as above.

Step 2: Induction Step
Suppose that for all $t\leq t_{0}-1$ it holds that with probability at least
$1-3t_{0}p^{-15}$ that

$\displaystyle\max_{k}\|\mathbf{\widehat{U}}_{k}^{(t)}-{\mathbf{U}}_{k}\mathbf{W}_{k}^{(t)}\|_{2,\infty}\leq\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}\mu_{0}\sqrt{\frac{r_{k}}{p_{k}}}+\frac{1}{2^{t}}\mu_{0}\sqrt{\frac{r_{k}}{p_{k}}};$
$\displaystyle\max_{k}\max_{m}\max_{j}\|\sin\Theta(\mathbf{\widehat{U}}_{j}^{(t)},\mathbf{\widetilde{U}}_{j}^{t,k-m})\|\leq\frac{\delta_{\mathrm{L}}^{(k)}}{\lambda}\mu_{0}\sqrt{\frac{r_{k}}{p_{j}}}+\frac{1}{2^{t}}\mu_{0}\sqrt{\frac{r_{k}}{p_{j}}}.$

Observe that the induction hypothesis is equivalent to stating that
$\mathcal{E}_{1,\mathrm{main}}^{(t_{0}-1)}$ holds with probability at least
$1-3t_{0}p^{-15}$. We will now show that with probability at least
$1-3t_{0}p^{-15}-p^{-15}$ that $\mathcal{E}_{2,\mathrm{main}}^{(t_{0}-1)}$
holds, which is equivalent to showing that

$\displaystyle\|\mathbf{\widehat{U}}_{1}^{t_{0}}-{\mathbf{U}}_{1}\mathbf{W}_{1}^{t_{0}}\|_{2,\infty}$
$\displaystyle\leq\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}+\frac{1}{2^{t_{0}}}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}};$
$\displaystyle\max_{m}\max_{j}\|\sin\Theta(\mathbf{\widehat{U}}^{t_{0}}_{j},\mathbf{\widetilde{U}}_{j}^{t_{0},1-m})\|$
$\displaystyle\leq\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}+\frac{1}{2^{t_{0}}}\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}.$

In other words, we will show that all of the bounds for the first mode hold.
Note that

$\displaystyle\widehat{{\mathbf{U}}}_{1}^{t_{0}}-{\mathbf{U}}_{1}{\mathbf{U}}_{1}^{\top}\widehat{{\mathbf{U}}}_{1}^{t_{0}}$
$\displaystyle={\mathbf{U}}_{1\perp}{\mathbf{U}}_{1\perp}^{\top}\mathbf{Z}_{1}\bigg{[}\mathcal{P}_{\widehat{{\mathbf{U}}}_{2}^{(t_{0}-1)}}\otimes\mathcal{P}_{\widehat{{\mathbf{U}}}_{3}^{(t_{0}-1)}}\bigg{]}\mathbf{Z}_{1}^{\top}\widehat{{\mathbf{U}}}_{1}^{t_{0}}(\mathbf{\widehat{\Lambda}}_{1}^{(t_{0})})^{-2}$
$\displaystyle\qquad+{\mathbf{U}}_{1\perp}{\mathbf{U}}_{1\perp}^{\top}\mathbf{Z}_{1}\bigg{[}\mathcal{P}_{\widehat{{\mathbf{U}}}_{2}^{(t_{0}-1)}}\otimes\mathcal{P}_{\widehat{{\mathbf{U}}}_{3}^{(t_{0}-1)}}\bigg{]}\mathbf{T}_{1}^{\top}\widehat{{\mathbf{U}}}_{1}^{t_{0}}(\mathbf{\widehat{\Lambda}}_{1}^{(t_{0})})^{-2}$
$\displaystyle=\mathbf{Q}_{1}^{t_{0}}+\mathbf{L}_{1}^{t_{0}}.$

Therefore,

$\displaystyle\mathbf{\widehat{U}}_{1}^{t_{0}}-{\mathbf{U}}_{1}\mathbf{W}_{1}^{t_{0}}$
$\displaystyle=\mathbf{\widehat{U}}_{1}^{t_{0}}-{\mathbf{U}}_{1}{\mathbf{U}}_{1}\mathbf{\widehat{U}}_{1}^{t_{0}}+{\mathbf{U}}_{1}({\mathbf{U}}_{1}\mathbf{\widehat{U}}_{1}^{t_{0}}-\mathbf{W}_{1}^{t_{0}})$
$\displaystyle=\mathbf{Q}_{1}^{t_{0}}+\mathbf{L}_{1}^{t_{0}}+{\mathbf{U}}_{1}({\mathbf{U}}_{1}\mathbf{\widehat{U}}_{1}^{t_{0}}-\mathbf{W}_{1}^{t_{0}}).$

Consequently,

$\displaystyle
e_{m}^{\top}\bigg{(}\mathbf{\widehat{U}}_{1}^{t_{0}}-{\mathbf{U}}_{1}\mathbf{W}_{1}^{t_{0}}\bigg{)}$
$\displaystyle=e_{m}^{\top}\mathbf{Q}_{1}^{t_{0}}+e_{m}^{\top}\mathbf{L}_{1}^{t_{0}}+e_{m}^{\top}{\mathbf{U}}_{1}({\mathbf{U}}_{1}\mathbf{\widehat{U}}_{1}^{t_{0}}-\mathbf{W}_{1}^{t_{0}}).$

We now proceed by bounding probabilistically. Observe that

$\displaystyle\mathbb{P}\bigg{\\{}$
$\displaystyle\|\mathbf{\widehat{U}}_{1}^{t_{0}}-{\mathbf{U}}_{1}\mathbf{W}_{1}^{t_{0}}\|_{2,\infty}\geq\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}$
$\displaystyle\qquad\bigcup\max_{m}\max_{j}\|\sin\Theta(\mathbf{\widehat{U}}_{j}^{t_{0}},\mathbf{\widetilde{U}}_{j}^{t_{0},1-m}\|\geq\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\bigg{\\}}$
$\displaystyle\leq\mathbb{P}\bigg{\\{}\|\mathbf{\widehat{U}}_{1}^{t_{0}}-{\mathbf{U}}_{1}\mathbf{W}_{1}^{t_{0}}\|_{2,\infty}\geq\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}$
$\displaystyle\qquad\bigcup\max_{m}\max_{j}\|\sin\Theta(\mathbf{\widehat{U}}_{j}^{t_{0}},\mathbf{\widetilde{U}}_{j}^{t_{0},1-m}\|\geq\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\bigcap\mathcal{E}_{\mathrm{1,main}}^{(t_{0}-1)}\bigg{\\}}+3t_{0}p^{-15}$
$\displaystyle\leq\mathbb{P}\bigg{\\{}\|\mathbf{\widehat{U}}_{1}^{t_{0}}-{\mathbf{U}}_{1}\mathbf{W}_{1}^{t_{0}}\|_{2,\infty}\geq\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\bigcap\mathcal{E}_{\mathrm{1,main}}^{(t_{0}-1)}\bigg{\\}}$
$\displaystyle\qquad+\mathbb{P}\bigg{\\{}\max_{m}\max_{j}\|\sin\Theta(\mathbf{\widehat{U}}_{j}^{t_{0}},\mathbf{\widetilde{U}}_{j}^{t_{0},1-m}\|\geq\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\bigcap\mathcal{E}_{\mathrm{1,main}}^{(t_{0}-1)}\bigg{\\}}+3t_{0}p^{-15}$
$\displaystyle\leq\mathbb{P}\bigg{\\{}\|\mathbf{\widehat{U}}_{1}^{t_{0}}-{\mathbf{U}}_{1}\mathbf{W}_{1}^{t_{0}}\|_{2,\infty}\geq\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\bigcap\mathcal{E}_{\mathrm{1,main}}^{(t_{0}-1)}\bigcap\mathcal{E}_{\mathrm{Good}}\bigg{\\}}$
$\displaystyle\qquad+\mathbb{P}\bigg{\\{}\max_{m}\max_{j}\|\sin\Theta(\mathbf{\widehat{U}}_{j}^{t_{0}},\mathbf{\widetilde{U}}_{j}^{t_{0},1-m}\|\geq\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\bigcap\mathcal{E}_{\mathrm{1,main}}^{(t_{0}-1)}\bigcap\mathcal{E}_{\mathrm{Good}}\bigg{\\}}$
$\displaystyle\qquad+O(p^{-30})+3t_{0}p^{-15}$ $\displaystyle\leq
p\max_{m}\mathbb{P}\bigg{\\{}\|e_{m}^{\top}\big{(}\mathbf{\widehat{U}}_{1}^{t_{0}}-{\mathbf{U}}_{1}\mathbf{W}_{1}^{t_{0}}\big{)}\|\geq\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\bigcap\mathcal{E}_{\mathrm{1,main}}^{(t_{0}-1)}\bigcap\mathcal{E}_{\mathrm{Good}}\bigg{\\}}$
$\displaystyle\qquad+p\max_{m}\mathbb{P}\bigg{\\{}\max_{j}\|\sin\Theta(\mathbf{\widehat{U}}_{j}^{t_{0}},\mathbf{\widetilde{U}}_{j}^{t_{0},1-m}\|\geq\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\bigcap\mathcal{E}_{\mathrm{1,main}}^{(t_{0}-1)}\bigcap\mathcal{E}_{\mathrm{Good}}\bigg{\\}}$
$\displaystyle\qquad+O(p^{-30})+3t_{0}p^{-15}$ $\displaystyle\leq
p\max_{m}\Bigg{[}\mathbb{P}\bigg{\\{}\|e_{m}^{\top}\mathbf{L}_{1}^{t_{0}}\|\geq\frac{1}{4}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\bigcap\mathcal{E}_{\mathrm{1,main}}^{(t_{0}-1)}\bigcap\mathcal{E}_{\mathrm{Good}}\bigg{\\}}$
$\displaystyle\qquad+\mathbb{P}\bigg{\\{}\|e_{m}^{\top}\mathbf{Q}_{1}^{t_{0}}\|\geq\frac{1}{4}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\bigcap\mathcal{E}_{\mathrm{1,main}}^{(t_{0}-1)}\bigcap\mathcal{E}_{\mathrm{Good}}\bigg{\\}}$
$\displaystyle\qquad+\mathbb{P}\bigg{\\{}\|e_{m}^{\top}{\mathbf{U}}_{1}\big{(}{\mathbf{U}}_{1}^{\top}\mathbf{\widehat{U}}_{1}^{t_{0}}-\mathbf{W}_{1}^{t_{0}}\big{)}\|\geq\frac{1}{4}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\bigcap\mathcal{E}_{\mathrm{1,main}}^{(t_{0}-1)}\bigcap\mathcal{E}_{\mathrm{Good}}\bigg{\\}}\Bigg{]}$
$\displaystyle\qquad+p\max_{m}\mathbb{P}\bigg{\\{}\max_{j}\|\sin\Theta(\mathbf{\widehat{U}}_{j}^{t_{0}},\mathbf{\widetilde{U}}_{j}^{t_{0},k-m}\|\geq\mu_{0}\sqrt{\frac{r_{1}}{p_{j}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}\bigcap\mathcal{E}_{\mathrm{1,main}}^{(t_{0}-1)}\bigcap\mathcal{E}_{\mathrm{Good}}\bigg{\\}}$
$\displaystyle\qquad+O(p^{-30})+3t_{0}p^{-15}$ $\displaystyle\leq
3p^{-28}+p^{-28}+O(p^{-30})+3t_{0}p^{-15}$
$\displaystyle\leq(3t_{0}+1)p^{-15},$

for $p$ sufficiently large, where the penultimate inequality holds by Lemmas
9, 10, and 11, and the fact that on $\mathcal{E}_{\mathrm{Good}}$,

$\displaystyle\|e_{m}^{\top}{\mathbf{U}}_{1}\left({\mathbf{U}}_{1}^{\top}\mathbf{\widehat{U}}_{1}^{t_{0}}-\mathbf{W}_{1}^{t_{0}}\right)\|\leq\frac{1}{4}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\frac{\delta_{\mathrm{L}}^{(1)}}{\lambda}+\frac{1}{2^{t_{0}}}\bigg{)}$

by Lemma 3 since $t_{0}\leq C\log(p)$ by assumption. Therefore, we have shown
that the bound holds for $k=1$. For $k=2$, we proceed similarly, only now on
the hypothesis that $\mathcal{E}_{\mathrm{main}}^{t_{0}-1,2}$ holds with
probability at least $1-3t_{0}p^{-15}-p^{-15}$. The exact same argument goes
through,accumulating an additional factor of $p^{-15}$. Finally, for $k=3$, we
proceed again, only now assuming that
$\mathcal{E}^{t_{0}-1,3}_{\mathrm{main}}$ holds with probability at least
$1-3t_{0}p^{-15}-2p^{-15}$. This accumulates a final factor of $p^{-15}$.
Therefore, since this accumulates three factors of $p^{-15}$, it holds that
$\mathcal{E}_{\mathrm{main}}^{t_{0},1}$ holds with probability at least
$1-3(t_{0}+1)p^{-15}$ as desired, which completes the proof. ∎

###  A.5 Initialization Bounds

This section contains the proof the initialization bounds. Section A.5.1
contains preliminary lemmas and their proofs, Section A.5.2 contains the proof
of Theorem 4, and Section A.5.3 contains the proof of Lemma 2.

####  A.5.1 Preliminary Lemmas

The following result establishes concentration inequalities for the spectral
norm of the noise matrices, needed in order to establish sufficient eigengap
conditions.

######  Lemma 12.

The following bounds hold simultaneously with probability at least
$1-O(p^{-30}):$

  1. 1.

$\|{\rm
diag}(\mathbf{Z}_{1}\mathbf{T}_{1}^{\top})\|\lesssim\lambda_{1}\mu_{0}^{2}r\sqrt{\frac{\log(p)}{p_{1}}}$;

  2. 2.

$\|\Gamma(\mathbf{Z}_{1}\mathbf{Z}_{1}^{\top})\|\lesssim(p_{1}p_{2}p_{3})^{1/2}$

  3. 3.

$\|\Gamma(\mathbf{T}_{1}\mathbf{Z}_{1}^{\top})\|\lesssim\lambda_{1}\sqrt{p_{1}}$;

  4. 4.

$\|{\mathbf{U}}_{1}\mathbf{Z}_{1}\mathbf{V}_{1}\|\lesssim\sqrt{r}$.

###### Proof.

Part one follows since

$\displaystyle\|{\rm diag}(\mathbf{Z}_{1}\mathbf{T}_{1}^{\top})\|$
$\displaystyle=\max_{i}\big{|}e_{i}^{\top}\mathbf{Z}_{1}\mathbf{T}_{1}^{\top}e_{i}\big{|}$
$\displaystyle\leq\max_{i}\|e_{i}^{\top}\mathbf{Z}_{1}\mathbf{V}_{1}\|\|e_{i}^{\top}{\mathbf{U}}_{1}\mathbf{\Lambda}_{1}\|$
$\displaystyle\leq\|\mathbf{Z}_{1}\mathbf{V}_{1}\|_{2,\infty}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\lambda_{1}$
$\displaystyle\leq
C\sqrt{p_{-1}\log(p)}\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\lambda_{1}\|\mathbf{V}_{1}\|_{2,\infty}$
$\displaystyle\lesssim\lambda_{1}\mu_{0}^{2}r\sqrt{\frac{\log(p)}{p_{1}}},$

where the final inequality holds with probability at least $1-O(p^{-30})$ by
Lemma 17.

Part two follows by a slight modification of Lemma 1 of Agterberg et al.
(2022b) (with $M$ in the statement therein taken to be 0), where the higher
probability holds by adjusting the constant in the definition of $\delta$ in
the proof therein. We omit the detailed proof for brevity.

Part three follows since

$\displaystyle\|\Gamma(\mathbf{Z}_{1}\mathbf{T}_{1}^{\top})\|$
$\displaystyle\leq\|\mathbf{Z}_{1}\mathbf{T}_{1}^{\top}\|+\|{\rm
diag}(\mathbf{Z}_{1}\mathbf{T}_{1}^{\top})\|$
$\displaystyle\lesssim\|\mathbf{Z}_{1}\mathbf{V}_{1}\|\lambda_{1}+\lambda_{1}\mu_{0}^{2}r\sqrt{\frac{\log(p)}{p_{1}}}$
$\displaystyle\lesssim\sqrt{p_{1}}\lambda_{1}+\lambda_{1}\mu_{0}^{2}r\sqrt{\frac{\log(p)}{p_{1}}}$
$\displaystyle\lesssim\sqrt{p_{1}}\lambda_{1},$

where the penultimate inequality
$\|\mathbf{Z}_{1}\mathbf{V}_{1}\|\lesssim\sqrt{p_{1}}$ holds by a standard
$\varepsilon-$net argument, and the final inequality holds since
$\mu_{0}^{2}r\lesssim\sqrt{p_{\min}}$ by assumption.

Part four follows via a standard $\varepsilon$-net argument. ∎

We also have the following result, needed in establishing the concentration of
the leave-one-out sequences.

######  Lemma 13.

The following bounds hold with probability at least $1-O(p^{-30})$:

  1. 1.

$\|\Gamma(\mathbf{T}_{1}(\mathbf{Z}_{1}-\mathbf{Z}_{1}^{1-m})^{\top})\|\lesssim\lambda_{1}\mu_{0}\sqrt{r\log(p)}$;

  2. 2.

$\|\Gamma(\mathbf{Z}_{1}\mathbf{Z}_{1}^{\top}-\mathbf{Z}_{1}^{1-m}(\mathbf{Z}_{1}^{1-m})^{\top})\|\lesssim(p_{1}p_{2}p_{3})^{1/2}$

  3. 3.

$\|\Gamma(\mathbf{T}_{1}(\mathbf{Z}_{1}^{1-m}-\mathbf{Z}_{1}^{1-m,1-l})^{\top})\|\lesssim\mu_{0}\lambda_{1}\sqrt{r\log(p)}\sqrt{\frac{p_{1}}{p_{-1}}}$;

  4. 4.

$\|\Gamma(\mathbf{Z}_{1}^{1-m}(\mathbf{Z}_{1}^{1-m})^{\top}-\mathbf{Z}_{1}^{1-m,1-l}(\mathbf{Z}_{1}^{1-m,1-l})^{\top})\|\lesssim
p$.

  5. 5.

$\|\Gamma(\mathbf{Z}_{1}^{1-m}(\mathbf{Z}_{1}^{1-m})-\mathbf{Z}_{1}^{1-m,1-l}(\mathbf{Z}_{1}^{1-m,1-l})^{\top})\mathbf{\widetilde{U}}_{1}^{S,1-m,1-l}\|\lesssim\sqrt{p_{1}}\log(p)\|\mathbf{\widetilde{U}}_{1}^{S,1-m,1-l}\|_{2,\infty}$

Here $\mathbf{Z}_{1}^{1-m,1-l}$ is the matrix $\mathbf{Z}_{1}$ with its $m$’th
row and $l$’th column removed, and $\mathbf{\widetilde{U}}_{1}^{S,1-m,1-l}$ is
matrix of leading eigenvectors obtained by initializing with the noise matrix
$\mathbf{Z}_{1}$ replaced with $\mathbf{Z}_{1}^{1-m,1-l}$.

###### Proof of Lemma 13.

For part one, we observe that $\mathbf{Z}_{1}-\mathbf{Z}_{1}^{1-m}$ is a zero
matrix with only its $m$’th row nonzero. Therefore,

$\displaystyle\|\Gamma\big{(}\mathbf{Z}_{1}-\mathbf{Z}_{1}^{1-m})\mathbf{T}_{1}^{\top}\big{)}\|$
$\displaystyle\leq\|(\mathbf{Z}_{1}-\mathbf{Z}_{1}^{1-m})\mathbf{T}_{1}^{\top}\|+\|{\rm
diag}\big{(}(\mathbf{Z}_{1}-\mathbf{Z}_{1}^{1-m})\mathbf{T}_{1}^{\top}\big{)}\|$
$\displaystyle=\|e_{m}^{\top}\mathbf{Z}_{1}\mathbf{T}_{1}^{\top}\|+\max_{i}|e_{i}^{\top}\big{(}\mathbf{Z}_{1}-\mathbf{Z}_{1}^{1-m}\big{)}\mathbf{T}_{1}^{\top}e_{i}|$
$\displaystyle\leq\|\mathbf{Z}_{1}\mathbf{V}_{1}\|_{2,\infty}\lambda_{1}+\|\mathbf{Z}_{1}\mathbf{V}_{1}\|_{2,\infty}\lambda_{1}\mu_{0}\sqrt{\frac{r}{p_{1}}}$
$\displaystyle\lesssim\|\mathbf{Z}_{1}\mathbf{V}_{1}\|_{2,\infty}\lambda_{1}$
$\displaystyle\lesssim\lambda_{1}\sqrt{p_{-1}\log(p)}\|\mathbf{V}_{1}\|_{2,\infty}$
$\displaystyle\lesssim\lambda_{1}\mu_{0}\sqrt{r\log(p)},$

with probability at least $1-O(p^{-30})$, where the penultimate line follows
from Lemma 16.

For part 2, we first observe that
$\Gamma\big{(}\mathbf{Z}_{1}\mathbf{Z}_{1}^{\top}-\mathbf{Z}_{1}^{1-m}(\mathbf{Z}_{1}^{1-m})^{\top}\big{)}$
is a matrix with $i,j$ entry equal to

$\displaystyle\Gamma\big{(}\mathbf{Z}_{1}\mathbf{Z}_{1}^{\top}-\mathbf{Z}_{1}^{1-m}(\mathbf{Z}_{1}^{1-m})^{\top}\big{)}_{ij}$
$\displaystyle=\begin{cases}\langle
e_{m}^{\top}\mathbf{Z}_{1},e_{j}^{\top}\mathbf{Z}_{1}\rangle&i=m,j\neq m\\\
\langle e_{m}^{\top}\mathbf{Z}_{1},e_{i}^{\top}\mathbf{Z}_{1}\rangle&j=m,i\neq
m\\\ 0&\text{else}.\end{cases}$

Therefore, we can decompose this matrix via

$\displaystyle\Gamma\big{(}\mathbf{Z}_{1}\mathbf{Z}_{1}^{\top}-\mathbf{Z}_{1}^{1-m}(\mathbf{Z}_{1}^{1-m})^{\top}\big{)}$
$\displaystyle=\mathbf{G}_{\mathrm{row}}+\mathbf{G}_{\mathrm{col}},$

where $\mathbf{G}_{\mathrm{row}}$ is the matrix whose only nonzero row is its
$m$’th row, in which case it the $m,j$ entry is $\langle
e_{m}^{\top}\mathbf{Z}_{1},e_{j}^{\top}\mathbf{Z}_{1}\rangle$ for $j\neq m$,
and $\mathbf{G}_{\mathrm{col}}$ is defined as the transpose of this matrix. We
then observe that with high probability

$\displaystyle\|\Gamma\big{(}\mathbf{Z}_{1}\mathbf{Z}_{1}^{\top}-\mathbf{Z}_{1}^{1-m}(\mathbf{Z}_{1}^{1-m})^{\top}\big{)}\|$
$\displaystyle\leq\|\mathbf{G}_{\mathrm{row}}\|+\|\mathbf{G}_{\mathrm{col}}\|$
$\displaystyle\leq 2\|\mathbf{G}_{\mathrm{row}}\|$
$\displaystyle=2\|e_{m}^{\top}\Gamma(\mathbf{Z}_{1}\mathbf{Z}_{1}^{\top})\|$
$\displaystyle\leq 2\|\Gamma(\mathbf{Z}_{1}\mathbf{Z}_{1}^{\top})\|$
$\displaystyle\lesssim(p_{1}p_{2}p_{3})^{1/2},$

where the final inequality follows from Lemma 12.

For part three, we first observe that
$\mathbf{Z}_{1}^{1-m}-\mathbf{Z}_{1}^{1-m,1-l}$ is a matrix with only its
$l$’th column nonzero. Then we note

$\displaystyle\|\Gamma\big{(}\big{(}\mathbf{Z}_{1}^{1-m}-\mathbf{Z}_{1}^{1-m,1-l}\big{)}\mathbf{T}_{1}^{\top}\big{)}\|$
$\displaystyle\leq\sqrt{p_{1}}\|\Gamma\big{(}\big{(}\mathbf{Z}_{1}^{1-m}-\mathbf{Z}_{1}^{1-m,1-l}\big{)}\mathbf{T}_{1}^{\top}\big{)}\|_{2,\infty}$
$\displaystyle\leq\sqrt{p_{1}}\bigg{[}\|\big{(}\mathbf{Z}_{1}^{1-m}-\mathbf{Z}_{1}^{1-m,1-l}\big{)}\mathbf{T}_{1}^{\top}\|_{2,\infty}$
$\displaystyle\qquad+\|{\rm
diag}\bigg{(}\big{(}\mathbf{Z}_{1}^{1-m}-\mathbf{Z}_{1}^{1-m,1-l}\big{)}\mathbf{T}_{1}^{\top}\bigg{)}\|_{2,\infty}\bigg{]}$
$\displaystyle\leq\sqrt{p_{1}}\bigg{[}\max_{i}\|\big{(}\mathbf{Z}_{1}\big{)}_{il}\big{(}\mathbf{T}_{1}^{\top}\big{)}_{l\cdot}\|+\max_{i}|(\mathbf{Z}_{1})_{il}(\mathbf{T}_{1}^{\top})_{li}|\bigg{]}$
$\displaystyle\lesssim\sqrt{p_{1}}\bigg{[}\sqrt{\log(p)}\|\mathbf{T}_{1}^{\top}\|_{2,\infty}+\sqrt{\log(p)}\|\mathbf{T}_{1}^{\top}\|_{\max}\bigg{]}$
$\displaystyle\lesssim\sqrt{p_{1}\log(p)}\|\mathbf{T}_{1}^{\top}\|_{2,\infty}$
$\displaystyle\lesssim\sqrt{p_{1}\log(p)}\|\mathbf{V}_{1}\|_{2,\infty}\lambda_{1}$
$\displaystyle\lesssim\mu_{0}\lambda_{1}\sqrt{r\log(p)}\sqrt{\frac{p_{1}}{p_{-1}}},$

where we used the fact that
$\max_{i,l}|(\mathbf{Z}_{1})_{il}|\lesssim\sqrt{\log(p)}$ with probability at
least $1-O(p^{-30})$.

We next note that
$\Gamma\big{(}\mathbf{Z}_{1}^{1-m}(\mathbf{Z}_{1}^{1-m})^{\top}-\mathbf{Z}_{1}^{1-m,1-l}(\mathbf{Z}_{1}^{1-m,1-l})^{\top}\big{)}$
is a matrix with entries equal to $(\mathbf{Z}_{1})_{il}(\mathbf{Z}_{1})_{jl}$
for $i\neq j$ and $i,j\neq m$. In particular, it is a the $p_{1}-1\times
p_{1}-1$ dimensional submatrix of the matrix whose entries are simply
$(\mathbf{Z}_{1})_{il}(\mathbf{Z}_{1})_{jl}$ for $i\neq j$. This is a sample
Gram matrix, so by Lemma 1 of Agterberg et al. (2022b), it holds that

$\displaystyle\|\Gamma\big{(}\mathbf{Z}_{1}^{1-m}(\mathbf{Z}_{1}^{1-m})^{\top}-\mathbf{Z}_{1}^{1-m,1-l}(\mathbf{Z}_{1}^{1-m,1-l})^{\top}\big{)}\|$
$\displaystyle\lesssim p_{1}$

with probability at least $1-O(p^{-30})$ (where as in the proof of Lemma 12
the result holds by taking $M=0$, $d=1$, and modifying the constant on
$\delta$ in the proof of Lemma 1 of Agterberg et al. (2022b)).

For the final term, we note that

$\displaystyle\|$
$\displaystyle\Gamma(\mathbf{Z}_{1}^{1-m}(\mathbf{Z}_{1}^{1-m})-\mathbf{Z}_{1}^{1-m,1-l}(\mathbf{Z}_{1}^{1-m,1-l})^{\top})\mathbf{\widetilde{U}}_{1}^{S,1-m,1-l}\|_{2,\infty}$
$\displaystyle=\max_{a}\big{\|}\sum_{j\neq
a}(\mathbf{Z}_{1})_{al}(\mathbf{Z}_{1})_{jl}\big{(}\mathbf{\widetilde{U}}^{S,1-m,1-l}_{1}\big{)}_{j\cdot}\big{\|}$
$\displaystyle\leq\max_{a}|(\mathbf{Z}_{1})|_{al}\|\sum_{j\neq
a}(\mathbf{Z}_{1})_{jl}\big{(}\mathbf{\widetilde{U}}^{S,1-m,1-l}_{1}\big{)}_{j\cdot}\big{\|}$
$\displaystyle\lesssim\sqrt{\log(p)}\max_{a}\|\sum_{j\neq
a}(\mathbf{Z}_{1})_{jl}\big{(}\mathbf{\widetilde{U}}^{S,1-m,1-l}_{1}\big{)}_{j\cdot}\big{\|}$
$\displaystyle\lesssim\sqrt{p_{1}}\log(p)\|\mathbf{\widetilde{U}}_{1}^{S,1-m,1-l}\|_{2,\infty},$

where the final inequality follows from Lemma 16 applied to
$\mathbf{Z}_{1}^{\top}$. ∎

The following result verifies the eigengap conditions that we use repeatedly
throughout the proof. We adopt similar notation to Cai et al. (2021).

######  Lemma 14.

Define the matrices

$\displaystyle\mathbf{G}$
$\displaystyle\coloneqq\Gamma\big{(}\mathbf{T}_{1}\mathbf{T}_{1}^{\top}+\mathbf{T}_{1}\mathbf{Z}_{1}^{\top}+\mathbf{Z}_{1}\mathbf{T}_{1}^{\top}+\mathbf{Z}_{1}\mathbf{Z}_{1}^{\top}\big{)};$
$\displaystyle\mathbf{G}^{(m)}$
$\displaystyle\coloneqq\Gamma\big{(}\mathbf{T}_{1}\mathbf{T}_{1}^{\top}+\mathbf{T}_{1}(\mathbf{Z}_{1}^{-m})^{\top}+\mathbf{Z}_{1}^{-m}\mathbf{T}_{1}^{\top}+\mathbf{Z}_{1}^{-m}(\mathbf{Z}_{1}^{-m})^{\top})\big{)};$
$\displaystyle\mathbf{G}^{(m,l)}$
$\displaystyle\coloneqq\Gamma\big{(}\mathbf{T}_{1}\mathbf{T}_{1}^{\top}+\mathbf{T}_{1}(\mathbf{Z}_{1}^{-m-l})^{\top}+\mathbf{Z}_{1}^{-m-l}\mathbf{T}_{1}^{\top}+\mathbf{Z}_{1}^{-m-l}(\mathbf{Z}_{1}^{-m-l})^{\top})\big{)}.$

Then on the events in Lemma 12 and Lemma 13, it holds that

$\displaystyle\lambda_{r}^{2}-\|\mathbf{G}-\mathbf{T}_{1}\mathbf{T}_{1}^{\top}\|\gtrsim\lambda^{2};$
$\displaystyle\lambda_{r}\big{(}\mathbf{G}\big{)}-\lambda_{r+1}\big{(}\mathbf{G}\big{)}-\|\mathbf{G}-\mathbf{G}^{-m}\|\gtrsim\lambda^{2};$
$\displaystyle\lambda_{r}\big{(}\mathbf{G}^{-m}\big{)}-\lambda_{r+1}\big{(}\mathbf{G}^{-m}\big{)}-\|\mathbf{G}^{-m}-\mathbf{G}^{-m-l}\|\gtrsim\lambda^{2};$
$\displaystyle\lambda_{r}\big{(}\mathbf{G}\big{)}\gtrsim\lambda^{2}.$

###### Proof of Lemma 14.

First, we note that on the event in Lemma 12,

$\displaystyle\|\mathbf{G}-\mathbf{T}_{1}\mathbf{T}_{1}^{\top}\|$
$\displaystyle\leq\|{\rm
diag}(\mathbf{T}_{1}\mathbf{T}_{1}^{\top})\|+2\|\Gamma(\mathbf{T}_{1}\mathbf{Z}_{1}^{\top})\|+\|\Gamma(\mathbf{Z}_{1}\mathbf{Z}_{1}^{\top})\|$
$\displaystyle\lesssim\lambda_{1}^{2}\mu_{0}^{2}\frac{r}{p_{1}}+\lambda_{1}\sqrt{p_{1}}+(p_{1}p_{2}p_{3})^{1/2}$
$\displaystyle\ll\lambda^{2};$ $\displaystyle\|\mathbf{G}-\mathbf{G}^{-m}\|$
$\displaystyle\leq
2\|\Gamma(\mathbf{T}_{1}(\mathbf{Z}_{1}-\mathbf{Z}_{1}^{1-m})^{\top})\|+\|\Gamma(\mathbf{Z}_{1}\mathbf{Z}_{1}^{\top}-\mathbf{Z}_{1}^{1-m}(\mathbf{Z}_{1}^{1-m})^{\top}\|$
$\displaystyle\lesssim\lambda_{1}\mu_{0}\sqrt{r\log(p)}+(p_{1}p_{2}p_{3})^{1/2}$
$\displaystyle\ll\lambda^{2};$
$\displaystyle\|\mathbf{G}^{-m}-\mathbf{G}^{-m-l}\|$
$\displaystyle\leq\|\Gamma\big{(}\mathbf{T}_{1}(\mathbf{Z}_{1}^{1-m}-\mathbf{Z}_{1}^{1-m,1-l})^{\top}\big{)}\|+\left\|\Gamma\left(\mathbf{Z}_{1}^{1-m}\left(\mathbf{Z}_{1}^{1-m}\right)^{\top}-\mathbf{Z}_{1}^{1-m,1-l}\left(\mathbf{Z}_{1}^{1-m,1-l}\right)^{\top}\right)\right\|$
$\displaystyle\lesssim\mu_{0}\lambda_{1}\sqrt{r\log(p)}\sqrt{\frac{p_{1}}{p_{-1}}}+p_{1}$
$\displaystyle\ll\lambda^{2}.$

Therefore, by Weyl’s inequality,

$\displaystyle\lambda_{r}\big{(}\mathbf{G}\big{)}-\lambda_{r+1}\big{(}\mathbf{G}\big{)}-\|\mathbf{G}-\mathbf{T}_{1}\mathbf{T}_{1}^{\top}\|$
$\displaystyle\geq\lambda_{r}^{2}-3\|\mathbf{G}-\mathbf{T}_{1}\mathbf{T}_{1}^{\top}\|$
$\displaystyle\gtrsim\lambda^{2}.$

Similarly,

$\displaystyle\lambda_{r}\big{(}\mathbf{G}^{-m}\big{)}-\lambda_{r+1}\big{(}\mathbf{G}^{-m}\big{)}-\|\mathbf{G}-\mathbf{G}^{-m}\|$
$\displaystyle\gtrsim\lambda_{r}\big{(}\mathbf{G}\big{)}-\lambda_{r+1}\big{(}\mathbf{G}\big{)}-2\|\mathbf{G}-\mathbf{G}^{-m}\|$
$\displaystyle\gtrsim\lambda^{2}.$

Finally, we note that

$\displaystyle\lambda_{r}\big{(}\mathbf{G}\big{)}\geq\lambda_{r}^{2}-\|\mathbf{G}-\mathbf{T}_{1}\mathbf{T}_{1}^{\top}\|$
$\displaystyle\geq\lambda^{2}-\|\mathbf{G}-\mathbf{T}_{1}\mathbf{T}_{1}^{\top}\|$
$\displaystyle\gtrsim\lambda^{2}.$

This completes the proof. ∎

With these spectral norm concentration and eigengap conditions fixed, we now
consider the $\ell_{2,\infty}$ analysis. The first step is to show that
several terms are negligible with respect to the main bound. For the remainder
of the analysis, we implicitly use the eigenvalue bounds in Lemma 14, which
hold under the events in Lemma 12 and Lemma 13.

######  Lemma 15.

The following bounds hold with probability at least $1-O(p^{-30})$:

  1. 1.

$\|{\mathbf{U}}_{1}{\mathbf{U}}_{1}^{\top}\mathbf{Z}_{1}\mathbf{T}_{1}^{\top}\mathbf{\widehat{U}}_{1}^{S}\mathbf{\widehat{\Lambda}}_{1}^{-2}\|_{2,\infty}\lesssim\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\frac{\sqrt{r}\kappa}{\lambda}$

  2. 2.

$\|{\mathbf{U}}_{1}{\mathbf{U}}_{1}^{\top}\Gamma(\mathbf{Z}_{1}\mathbf{Z}_{1}^{\top})\mathbf{\widehat{U}}_{1}^{S}\mathbf{\widehat{\Lambda}}^{-2}_{1}\|_{2,\infty}\lesssim\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\frac{(p_{1}p_{2}p_{3})^{1/2}}{\lambda^{2}}$

  3. 3.

$\|{\mathbf{U}}_{1}{\mathbf{U}}_{1}^{\top}{\rm
diag}\bigg{(}\mathbf{T}_{1}\mathbf{T}_{1}^{\top}+\mathbf{T}_{1}\mathbf{Z}_{1}^{\top}+\mathbf{Z}_{1}\mathbf{T}_{1}^{\top}\bigg{)}\mathbf{\widehat{U}}_{1}^{S}\mathbf{\widehat{\Lambda}}^{-2}_{1}\|_{2,\infty}\lesssim\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\kappa^{2}\mu_{0}^{2}\frac{r}{p_{1}}+\frac{\kappa\mu_{0}^{2}r\sqrt{\log(p)}}{\lambda\sqrt{p_{1}}}\bigg{)}$

  4. 4.

$\|{\rm
diag}(\mathbf{T}_{1}\mathbf{T}_{1}^{\top}+\mathbf{T}_{1}\mathbf{Z}_{1}^{\top}+\mathbf{Z}_{1}\mathbf{T}_{1}^{\top})\mathbf{\widehat{U}}_{1}^{S}\mathbf{\widehat{\Lambda}}^{-2}_{1}\|_{2,\infty}\lesssim\kappa^{2}\mu_{0}^{2}\frac{r_{1}}{p_{1}}+\frac{\kappa\mu_{0}^{2}r\sqrt{\log(p)}}{\lambda\sqrt{p_{1}}}$

  5. 5.

$\|{\mathbf{U}}_{1}(\mathbf{W}_{1}^{S}-{\mathbf{U}}_{1}^{\top}\mathbf{\widehat{U}}_{1}^{S})\|_{2,\infty}\lesssim\mu_{0}\sqrt{\frac{r_{1}}{p_{1}}}\bigg{(}\kappa^{2}\mu_{0}^{2}\frac{r}{p_{1}}+\frac{\kappa\sqrt{p_{1}}}{\lambda}+\frac{(p_{1}p_{2}p_{3})^{1/2}}{\lambda^{2}}\bigg{)}^{2}$.

Moreover, all of these terms are upper bounded by the quantity

$\displaystyle\bigg{(}\frac{\kappa\sqrt{p_{1}\log(p)}}{\lambda}+\frac{(p_{1}p_{2}p_{3})^{1/2}\log(p)}{\lambda^{2}}+\kappa^{2}\mu_{0}\sqrt{\frac{r}{p_{1}}}\bigg{)}\mu_{0}\sqrt{\frac{r}{p_{1}}}.$