that $\left\lVert\Delta_{t}\right\rVert\leq 0.02\sigma_{r}$; this marks the
end of Phase 1. Without loss of generality, we may assume that
$\left\lVert\Delta_{t}\right\rVert\geq 0.02\sigma_{r}$ for every $t\leq
T_{1}$. To see this, suppose that $\left\lVert\Delta_{t}\right\rVert\leq
0.02\sigma_{r}$ for some $t\leq T_{1}$. This implies that $\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert\leq\left\lVert\Delta_{t}\right\rVert\leq
0.02\sigma_{r}$, which in turn leads to $\lambda_{\min}(S_{t}S_{t}^{\top})\geq
0.98\sigma_{r}$. On the other hand, $\left\lVert\Delta_{t}\right\rVert\geq
0.02\sigma_{r}$ together with Lemma 9 implies that the one-step dynamic in
Proposition 7 holds and we have

$\displaystyle\lambda_{\min}\left(S_{t+1}S_{t+1}^{\top}\right)\geq$
$\displaystyle\left(\left(1+\frac{\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\sigma_{r}\right)^{2}-\frac{2\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\left\lVert
E_{t}E_{t}^{\top}\right\rVert-384\sqrt{r}\eta\rho^{t}\delta\right)\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)$
$\displaystyle-2\frac{\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\left(1+\frac{\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\sigma_{r}\right)\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)^{2}.$
$\displaystyle\geq$
$\displaystyle\left(1+\frac{2\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\left(\sigma_{r}-\mathcal{O}(\sqrt{r}\sigma_{1}\delta)\right)\right)\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)-\frac{2.01\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)^{2}$
$\displaystyle\geq$
$\displaystyle\left(1+\frac{1.99\eta\rho^{t}\sigma_{r}}{\left\lVert\Delta_{t}\right\rVert}\right)\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)-\frac{2.01\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)^{2}$
(62)

where the second inequality follows from
$\left\lVert\Delta_{t}\right\rVert\geq 0.02\sigma_{r}$ and $\eta\lesssim 1$,
and the last inequality follows from $\delta\lesssim 1/(\sqrt{r}\sigma_{1})$.
The rest of the proof for the eigenvalue learning phase is similar to the
arguments made after (37) in the proof of Theorem 6. Suppose that
$T^{\prime}_{1}$ is the largest iteration such that
$\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\leq\sigma_{r}/2.01$ for every
$t\leq T_{1}^{\prime}$. We show that
$T_{1}^{\prime}=\mathcal{O}((\kappa/\eta)\log(1/\alpha))$. To see this, note
that for every $t\leq T_{1}^{\prime}$, the above inequality can be simplified
as

$\displaystyle\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)$
$\displaystyle\geq\left(1+\frac{0.99\eta\rho^{t}\sigma_{r}}{\left\lVert\Delta_{t}\right\rVert}\right)\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)$
$\displaystyle\geq\lambda_{\min}\left(S_{0}S_{0}^{\top}\right)\prod_{s=0}^{t}\left(1+\frac{\eta\rho^{s}}{6\kappa}\right),$
(63)

where we used the assumption $\delta\lesssim 1/(\sqrt{r}\kappa)$ and
$\left\lVert\Delta_{t}\right\rVert\leq 5\sigma_{1}$. To proceed with the
proof, we need the following technical lemma.

######  Lemma 10.

For any $\alpha>0,0<\rho<1$ and $T\in\mathbb{N}_{+}$, we have

$\exp\left(\frac{\alpha
T\rho^{T}}{1+\alpha}\right)\leq\prod_{t=0}^{T}\left(1+\alpha\rho^{t}\right)\leq\exp\left(\frac{\alpha}{1-\rho}\right).$
(64)

The proof of Lemma 10 can be found in Appendix F.5. Lemma 10 together with
Lemma 6 and (63) leads to

$\displaystyle\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)$
$\displaystyle\geq\exp\left(\frac{\eta
t\rho^{t}}{6\kappa+\eta}\right)\alpha^{2}\varphi(X^{\star})\left(\frac{\sigma_{r}}{\left\lVert
X^{\star}\right\rVert_{F}}-\delta\right)$
$\displaystyle\geq\exp\left(\frac{\eta
t\rho^{t}}{6\kappa+\eta}\right)\alpha^{2}\varphi(X^{\star})\left(\frac{\sigma_{r}}{\sqrt{r}\sigma_{1}}-\delta\right)$
$\displaystyle\geq\exp\left(\frac{\eta
t\rho^{t}}{6\kappa+\eta}\right)\frac{\alpha^{2}\varphi(X^{\star})}{2\sqrt{r}\kappa}.$

Due to our assumption $\rho=1-\Theta(\eta/(\kappa\log(1/\alpha)))$, we have
$\rho^{t}\geq 1-\mathcal{O}(\eta t/(\kappa\log(1/\alpha)))$. This together
with the assumption $t\leq\mathcal{O}((\kappa/\eta)\log(1/\alpha))$ leads to
$\rho^{t}\geq 1-\mathcal{O}(1)\geq\Omega(1)$. Therefore, one can write

$\displaystyle\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\geq\exp\left(\Omega(1)\frac{\eta
t}{\kappa}\right)\frac{\alpha^{2}\varphi(X^{\star})}{2\sqrt{r}\kappa}.$

Given the above equation, it is easy to verify that after
$\mathcal{O}((\kappa/\eta)\log(1/\alpha))$ iterations, we have
$\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\geq\sigma_{r}/2.01$. This
implies that $T_{1}^{\prime}=\mathcal{O}((\kappa/\eta)\log(1/\alpha))$.

For $t>T_{1}^{\prime}$, define
$x_{t}=\sigma_{r}-\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)$. Then,
arguments analogous to the proof of Theorem 6 can be used to write

$\displaystyle x_{t+1}-0.0196\sigma_{r}$
$\displaystyle\leq\left(1-1.02\frac{\eta\rho^{t}\sigma_{r}}{\left\lVert\Delta_{t}\right\rVert}\right)(x_{t}-0.0196\sigma_{r})$
$\displaystyle\leq\left(1-\frac{\eta\rho^{t}}{5\kappa}\right)(x_{t}-0.0196\sigma_{r})$
$\displaystyle\leq(x_{T_{1}^{\prime}}-0.0196\sigma_{r})\prod_{s=T_{1}^{\prime}}^{t}\left(1-\frac{\eta\rho^{t}}{5\kappa}\right).$

Recall that $\rho^{t}=\Omega(1)$ for every
$t\leq\mathcal{O}((\kappa/\eta)\log(1/\alpha))$. Therefore, for every
$T_{1}^{\prime}<t\leq\mathcal{O}((\kappa/\eta)\log(1/\alpha))$, we have

$\displaystyle x_{t+1}-0.0196\sigma_{r}$
$\displaystyle\leq(x_{T_{1}^{\prime}}-0.0196\sigma_{r})\left(1-\Omega(1)\frac{\eta\sigma_{r}}{\kappa}\right)^{t-T_{1}^{\prime}+1}.$

This in turn implies that after additional
$T_{1}^{\prime\prime}=\mathcal{O}(\kappa/\eta)$ iterations, we have
$x_{t+1}\leq 0.02\sigma_{r}$. Therefore, we have
$\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\geq 0.98\sigma_{r}$ after
$T_{1}=T_{1}^{\prime}+T_{1}^{\prime\prime}=\mathcal{O}((\kappa/\eta)\log(1/\alpha))$
iterations. Now, it suffices to show that, after additional
$T_{2}=\mathcal{O}((\kappa/\eta)\log(\kappa))$ iterations, we have
$\left\lVert\Delta_{t}\right\rVert\leq 0.02\sigma_{r}$. To this goal, suppose
that $\left\lVert\Delta_{t}\right\rVert\geq 0.02\sigma_{r}$ for every
$T_{1}\leq t\leq T_{1}+T_{2}$. Recalling the signal-residual decomposition
(21), one can write

$\displaystyle\left\lVert\Delta_{t}\right\rVert$
$\displaystyle\leq\left\lVert\Sigma-S_{t}S_{t}^{\top}\right\rVert+2\left\lVert
S_{t}E_{t}^{\top}\right\rVert+\left\lVert F_{t}\right\rVert^{2}+\left\lVert
G_{t}\right\rVert^{2}$ $\displaystyle\leq\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert+0.01\sigma_{r},$

where the second inequality follows from Lemma 9. Given the above inequality,
$\left\lVert\Delta_{t}\right\rVert\geq 0.02\sigma_{r}$ implies that
$\left\lVert\Sigma-S_{t}S_{t}^{\top}\right\rVert\geq 0.01\sigma_{r}$ for every
$T_{1}\leq t\leq T_{1}+T_{2}$. Combined with the one-step dynamic for the
signal term, we have

$\displaystyle\left\lVert\Sigma-S_{t+1}S_{t+1}^{\top}\right\rVert$
$\displaystyle\leq\left(1-\frac{\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\right)\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert+5\frac{\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\left\lVert
S_{t}E_{t}^{\top}\right\rVert^{2}+193\sqrt{r}\eta\rho^{t}\delta\sigma_{1}$
(65)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left(1-\frac{0.98\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\sigma_{r}\right)\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert+\mathcal{O}\left(\sqrt{r}\eta\rho^{t}\delta\sigma_{1}\right)$
$\displaystyle\leq\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert-0.98\eta\rho^{t}\sigma_{r}\frac{\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert}{\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert+0.01\sigma_{r}}+\mathcal{O}\left(\sqrt{r}\eta\rho^{t}\delta\sigma_{1}\right)$
$\displaystyle\leq\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert-0.49\eta\rho^{t}\sigma_{r}+\mathcal{O}\left(\sqrt{r}\eta\rho^{t}\delta\sigma_{1}\right)$
$\displaystyle\leq\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert-\Omega\left(\eta\rho^{t}\sigma_{r}\right),$

where in (a) we used the fact that $\left\lVert
S_{t}E_{t}^{\top}\right\rVert\lesssim\sqrt{\sigma_{1}}\left\lVert
F_{t}\right\rVert\lesssim\sigma_{1}\sqrt{r}\eta_{0}\rho^{t}\delta t$,
$\delta\lesssim{1}/\left({\sqrt{r}\kappa^{2}\bar{\varphi}^{4}\log^{2}\left(1/\alpha\right)}\right)$,
and $t\lesssim({\kappa}/{\eta})\log\left({1}/{\alpha}\right)$. The above
inequality leads to

$\displaystyle\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert\leq\left\lVert\Sigma-
S_{T_{1}}S_{T_{1}}^{\top}\right\rVert-\Omega\left(\sum_{s=T_{1}}^{t-1}\eta\rho^{t}\sigma_{r}\right).$

Therefore, after $T_{3}=T_{1}+\mathcal{O}((\kappa/\eta)\log\kappa)$
iterations, we have $\left\lVert\Sigma-S_{t}S_{t}^{\top}\right\rVert\leq
0.01\sigma_{r}$. This completes the proof of the first phase.

#### Phase 2: Global Convergence.

In the second phase, we show that, once $\left\lVert\Delta_{t}\right\rVert\leq
0.02\sigma_{r}$, $\left\lVert\Delta_{t}\right\rVert$ starts to decay linearly
until it is dominated by $\sqrt{d}\left\lVert G_{t}\right\rVert^{2}$. Similar
to before, we define $\gamma_{t}=\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert+2\left\lVert
S_{t}E_{t}^{\top}\right\rVert+\left\lVert F_{t}\right\rVert^{2}+\left\lVert
G_{t}\right\rVert^{2}$. Our next lemma plays a central role in our subsequent
arguments:

######  Lemma 11.

Suppose that $T_{3}\leq t\leq T_{end}$ is chosen such that $\gamma_{s}\leq
0.1\sigma_{r}$ and $\left\lVert\Delta_{s}\right\rVert\geq\sqrt{d}\left\lVert
G_{s}\right\rVert^{2}$, for every $T_{3}\leq s\leq t$. Then, we have

  * -

$\gamma_{t+1}\leq 0.1\sigma_{r}$.

Moreover, at least one of the following statements are satisfied:

  * -

$\left\lVert\Delta_{t+1}\right\rVert\geq\sqrt{d}\left\lVert
G_{t+1}\right\rVert^{2}$,

  * -

$\left\lVert\Delta_{t+1}\right\rVert\lesssim\sqrt{d}\alpha^{2-\mathcal{O}(\sqrt{r}\kappa\delta)}$.

To streamline the presentation, we defer the proof of the above lemma to
Appendix F.6. According to the above lemma, we may assume that $\gamma_{t}\leq
0.1\sigma_{r}$ and $\left\lVert\Delta_{t}\right\rVert\geq\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}$ for all iterations $T_{3}\leq t\leq T_{end}$;
otherwise, we have
$\left\lVert\Delta_{t}\right\rVert\lesssim\sqrt{d}\alpha^{2-\mathcal{O}(\sqrt{r}\kappa\delta)}$
for some $T_{3}\leq t\leq T_{end}$, which readily completes the proof. On the
other hand, the assumptions $\gamma_{t}\leq 0.1\sigma_{r}$ and
$\left\lVert\Delta_{t}\right\rVert\geq\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}$ lead to

$\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\geq
0.9\sigma_{r},\quad\left\lVert S_{t}S_{t}^{\top}\right\rVert\leq
1.1\sigma_{1},\quad\left\lVert E_{t}E_{t}^{\top}\right\rVert\leq
0.1\sigma_{r},\quad\left\lVert
E_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}\right\rVert\leq 0.2.$

Together with our analysis in Phase 1, this implies that the one-step dynamic
of $G_{t}$ holds for every $0\leq t\leq T_{end}$, and we have $\left\lVert
G_{t}\right\rVert\leq
2\sqrt{2}\alpha^{1-\mathcal{O}\left(\sqrt{r}\kappa\delta\right)}\sqrt{\bar{\varphi}\delta}$,
for every $0\leq t\leq T_{end}$.

Under the assumption $\left\lVert\Delta_{t}\right\rVert\geq\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}$, our next lemma shows that, if
$\left\lVert\Delta_{t+T_{3}}\right\rVert\geq 0.02\sigma_{r}\rho^{t}$ for some
$t\geq 0$, then there exists $t^{\prime}$ satisfying
$t^{\prime}-t=\mathcal{O}(1/\eta)$ such that
$\left\lVert\Delta_{t^{\prime}+T_{3}}\right\rVert\leq
0.02\sigma_{r}\rho^{t^{\prime}}$. This in turn ensures that the generalization
error decays by a constant factor every $\mathcal{O}(1/\eta)$ iterations until
it reaches the same order as $\sqrt{d}\left\lVert G_{t}\right\rVert^{2}$. In
particular, we have the following lemma:

######  Lemma 12.

Suppose that $\left\lVert\Delta_{t}\right\rVert\geq\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}$ for every $T_{3}\leq t\leq T_{end}$. Suppose that
$t_{0}\geq 1$ satisfies $\left\lVert\Delta_{t_{0}+T_{3}-1}\right\rVert\leq
0.02\sigma_{r}\rho^{t_{0}-1}$ and
$\left\lVert\Delta_{t_{0}+T_{3}}\right\rVert>0.02\sigma_{r}\rho^{t_{0}}$.
Then, after at most $\Delta t=\mathcal{O}\left(1/\eta\right)$ iterations, we
have $\left\lVert\Delta_{t_{0}+\Delta t+T_{3}}\right\rVert\leq
0.02\sigma_{r}\rho^{t_{0}+\Delta t}$.

The proof of the above lemma is presented in Appendix F.7. We show how Lemma
12 can be used to finish the proof of Theorem 8. Recall that
$\rho=1-\Theta\left(\eta/(\kappa\log(1/\alpha))\right)$. Let us pick
$T_{4}=\mathcal{O}((\kappa/\eta)\log^{2}(1/\alpha))$. Simple calculation
reveals that $0.02\sigma_{r}\rho^{T_{4}}\lesssim\alpha^{2}$. According to
Lemma 12, if
$\left\lVert\Delta_{T_{4}+T_{3}}\right\rVert>0.02\sigma_{r}\rho^{T_{4}}$, then
there exists $\Delta t=\mathcal{O}\left(1/\eta\right)$ such that
$\left\lVert\Delta_{T_{4}+T_{3}+\Delta t}\right\rVert\leq
0.02\sigma_{r}\rho^{T_{4}+\Delta t}\lesssim\alpha^{2}$. Combined with Lemma
11, we have
$\left\lVert\Delta_{t}\right\rVert_{F}\leq\sqrt{d}\left\lVert\Delta_{t}\right\rVert\lesssim
d\left\lVert G_{t}\right\rVert^{2}\vee\zeta\lesssim
d\alpha^{2-\mathcal{O}\left(\sqrt{r}\kappa\delta\right)}\vee\zeta$ after at
most $T_{end}=T_{3}+T_{4}+\Delta
t=\mathcal{O}((\kappa/\eta)\log^{2}(1/\alpha))$ iterations. This completes the
proof of Theorem 8.$\hfill\square$

##  Appendix B Proofs of Sign-RIP

###  B.1 Preliminary

We first provide the preliminary probability tools for proving Theorems 4 and
5.

######  Definition 6 (Sub-Gaussian random variable).

We say a random variable $X\in\mathbb{R}$ with expectation $\mathbb{E}[X]=\mu$
is $\sigma^{2}$-sub-Gaussian if for all $\lambda\in\mathbb{R}$, we have
$\mathbb{E}\left[e^{\lambda(X-\mu)}\right]\leq
e^{\frac{\lambda^{2}\sigma^{2}}{2}}$. Moreover, the sub-Gaussian norm of $X$
is defined as $\left\lVert
X\right\rVert_{\psi_{2}}:=\sup_{p\in\mathbb{N}_{+}}\left\\{p^{-1/2}(\mathbb{E}[|X|^{p}])^{1/p}\right\\}$.

According to [36], the following statements are equivalent:

  * •

$X$ is $\sigma^{2}$-sub-Gaussian.

  * •

(Tail bound) For any $t>0$, we have $\mathbb{P}(|X-\mu|\geq t)\leq
2e^{-\frac{t^{2}}{2\sigma^{2}}}$.

  * •

(Moment bound) We have $\left\lVert X\right\rVert_{\psi_{2}}\lesssim\sigma$.

Next, we provide the definitions of the sub-Gaussian process, $\xi$-net, and
covering number.

######  Definition 7 (Sub-Gaussian process).

A zero mean stochastic process
$\\{\mathcal{X}_{\theta},\theta\in\mathbb{T}\\}$ is a $\sigma^{2}$-sub-
Gaussian process with respect to a metric $d$ on a set $\mathbb{T}$, if for
every $\theta,\theta^{\prime}\in\mathbb{T}$, the random variable
$\mathcal{X}_{\theta}-\mathcal{X}_{\theta^{\prime}}$ is $\left(\sigma
d(\theta,\theta^{\prime})\right)^{2}$-sub-Gaussian.

######  Definition 8 ($\xi$-net and covering number).

A set $\mathcal{N}$ is called an $\xi$-net on $(\mathbb{T},d)$ if for every
$t\in\mathbb{T}$, there exists $\pi(t)\in\mathcal{N}$ such that
$d(t,\pi(t))\leq\xi$. The covering number $N(\mathbb{T},d,\xi)$ is defined as
the smallest cardinality of an $\xi$-net for $(\mathbb{T},d)$:

$N(\mathbb{T},d,\xi):=\inf\\{|\mathcal{N}|:\mathcal{N}\text{ is an
}\xi\text{-net for }(\mathbb{T},d)\\}.$

Next, we introduce some additional notations which will be used throughout our
arguments. Define the rank-$k$ and $\varepsilon$-approximate rank-$k$ unit
balls as:

$\displaystyle\mathbb{S}_{k}$ $\displaystyle=\\{X\in\mathbb{R}^{d\times
d}:\mathrm{rank}(X)\leq k,\left\lVert X\right\rVert_{F}=1\\},$
$\displaystyle\mathbb{S}_{k,\varepsilon}$
$\displaystyle=\\{X\in\mathbb{R}^{d\times d}:\left\lVert
X\right\rVert_{F}=1\text{ and }\exists X^{\prime}\text{ such that
}\mathrm{rank}(X^{\prime})\leq k,\left\lVert
X-X^{\prime}\right\rVert_{F}\leq\varepsilon\\}.$

For simplicity of notation, we use $N_{k,\xi}$ to denote
$N(\mathbb{S}_{k},\left\lVert\cdot\right\rVert_{F},\xi)$. Moreover, we define
$\mathcal{S}_{k,\varepsilon}$ as the restriction of the set $\mathcal{S}$ to
the set of $\varepsilon$-approximate rank-$k$ matrices, i.e.,
$\mathcal{S}_{k,\varepsilon}=\\{X:X\in\mathcal{S},X\text{ is
}\varepsilon\text{-approximate rank-}k\\}$. The following lemma characterizes
the covering number of the set of low-rank matrices with unit norm.

######  Lemma 13 (Li et al. [20]).

We have
$N_{k,\xi}=N(\mathbb{S}_{k},\left\lVert\cdot\right\rVert_{F},\xi)\leq\left(\frac{9}{\xi}\right)^{(2d+1)k}$.

The following well-known result characterizes a concentration bound on the
supremum of a sub-Gaussian process.

######  Theorem 9 (Corollary 5.25 and Theorem 5.29 in [35]).

Let $\\{X_{t}\\}_{t\in\mathbb{T}}$ be a separable sub-Gaussian process on
$(\mathbb{T},d)$. Then, the following statements hold:

  * •

We have

$\mathbb{E}\left[\sup_{t\in\mathbb{T}}X_{t}\right]\leq
12\int_{0}^{\infty}\sqrt{\log N(\mathbb{T},d,\xi)}d\xi.$

  * •

For all $t_{0}\in\mathbb{T}$ and $x\geq 0$, we have

$\mathbb{P}\left(\sup_{t\in\mathbb{T}}\left\\{X_{t}-X_{t_{0}}\right\\}\geq
C\int_{0}^{\infty}\sqrt{\log N(\mathbb{T},d,\xi)}d\xi+x\right)\leq
Ce^{-x^{2}/C\operatorname{diam}(\mathbb{T})^{2}},$

where $C<\infty$ is a universal constant, and
$\operatorname{diam}(\mathbb{T})=\sup_{t,t^{\prime}\in\mathbb{T}}\\{d(t,t^{\prime})\\}$
is the diameter of $\mathbb{T}$.

Equipped with these preliminary results, we proceed with the proof of Theorem
4.

###  B.2 Proof of Theorem 4

To provide the proof of Theorem 4, we first define the following stochastic
process:

$\mathcal{H}_{X,Y}=\sup\left\\{\frac{1}{m}\sum_{i=1}^{m}\mathrm{Sign}(\left\langle
A_{i},X\right\rangle-s_{i})\left\langle
A_{i},Y\right\rangle-\varphi(X)\left\langle\frac{X}{\left\lVert
X\right\rVert_{F}},Y\right\rangle\right\\},$

where
$\varphi(X):=\sqrt{\frac{2}{\pi}}\left(1-p+p\mathbb{E}\left[e^{-s^{2}/(2\left\lVert
X\right\rVert_{F}^{2})}\right]\right)$, and the supremum is taken over the
set-valued function $\mathrm{Sign}(\cdot)$. Moreover, to streamline the
presentation and whenever there is no ambiguity, we drop the supremum when it
is taken with respect to the set-valued function $\mathrm{Sign}(\cdot)$. Our
next lemma provides a sufficient condition for Sign-RIP.

######  Lemma 14.

Sign-RIP holds with parameters delineated in Theorem 4, if

$\sup_{X\in\mathcal{S}_{k,\varepsilon},Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\mathcal{H}_{X,Y}\lesssim\inf_{X\in\mathcal{S}_{k,\varepsilon}}\varphi(X)\delta.$
(66)

###### Proof.

According to the definition, Sign-RIP is satisfied if, for every
$X,Y\in\mathcal{S}_{k,\varepsilon}$ and $Q\in\mathcal{Q}(X)$, we have

$\displaystyle\left\langle
Q-\varphi(X)\frac{X}{\|X\|_{F}},\frac{Y}{\left\lVert
Y\right\rVert_{F}}\right\rangle\leq\varphi(X)\delta.$ (67)

Recall that $\mathcal{S}_{k,\varepsilon}=\\{X:\zeta\leq\left\lVert
X\right\rVert_{F}\leq R,X\text{ is }\varepsilon\text{-approximate rank-}k\\}$.
This implies that $Y\in\mathcal{S}_{k,\varepsilon}$ if $Y/\left\lVert
Y\right\rVert_{F}\in\mathbb{S}_{k,\varepsilon/\zeta}$. Hence, it suffices to
restrict $Y\in\mathbb{S}_{k,\varepsilon/\zeta}$. Therefore, Sign-RIP is
satisfied if

$\mathcal{H}_{X,Y}\leq\varphi(X)\delta,\quad\forall
X\in\mathcal{S}_{k,\varepsilon},Y\in\mathbb{S}_{k,\varepsilon/\zeta}.$

Hence, to guarantee Sign-RIP, it suffices to have

$\sup_{X\in\mathcal{S}_{k,\varepsilon},Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\mathcal{H}_{X,Y}\leq\inf_{X\in\mathcal{S}_{k,\varepsilon}}\varphi(X)\delta.$

∎

Relying on the above lemma, we instead focus on analyzing the stochastic
process
$\\{\mathcal{H}_{X,Y}\\}_{X\in\mathcal{S}_{k,\varepsilon},Y\in\mathbb{S}_{k,\varepsilon/\zeta}}$.
As a first step towards this goal, we show that the scaling function can be
used to characterize $\mathbb{E}[\left\langle Q,Y\right\rangle]$, for every
$Q\in\mathcal{Q}(X)$.

######  Lemma 15.

Suppose that the matrix $A$ has i.i.d. standard Gaussian entries and the noise
satisfies Assumption 4. Then, for every $Q\in\mathcal{Q}(X)$, we have

$\mathbb{E}\left[\left\langle
Q,Y\right\rangle\right]=\sqrt{\frac{2}{\pi}}\left(1-p+p\mathbb{E}\left[e^{-s^{2}/\left(2\left\|X\right\|_{F}\right)}\right]\right)\left\langle\frac{X}{\left\lVert
X\right\rVert_{F}},Y\right\rangle.$

###### Proof.

Without loss of generality, we assume $\left\lVert
X\right\rVert_{F}=\left\lVert Y\right\rVert_{F}=1$. Let us denote
$u:=\left\langle A,X\right\rangle,v:=\left\langle
A,Y\right\rangle,\rho:=\operatorname{Cov}(u,v)=\left\langle X,Y\right\rangle$.
Then, we have

$\displaystyle\mathbb{E}\left[\mathrm{Sign}\left(\left\langle
A,X\right\rangle-s\right)\left\langle A,Y\right\rangle|s\not=0\right]$
$\displaystyle=\mathbb{E}\left[\mathrm{Sign}\left(u-s\right)v|s\not=0\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\rho\mathbb{E}\left[\mathrm{Sign}(u-s)u|s\not=0\right]$
$\displaystyle=\rho\mathbb{E}_{s\sim\mathbb{P}}\left[\int_{s}^{\infty}u\frac{1}{\sqrt{2\pi}}e^{-u^{2}/2}du-\int_{-\infty}^{s}u\frac{1}{\sqrt{2\pi}}e^{-u^{2}/2}du\right]$
$\displaystyle=\rho\mathbb{E}_{s\sim\mathbb{P}}\left[\int_{s}^{\infty}u\frac{1}{\sqrt{2\pi}}e^{-u^{2}/2}du+\int_{-s}^{\infty}u\frac{1}{\sqrt{2\pi}}e^{-u^{2}/2}du\right]$
$\displaystyle=2\rho\mathbb{E}_{s\sim\mathbb{P}}\left[\int_{|s|}^{\infty}u\frac{1}{\sqrt{2\pi}}e^{-u^{2}/2}du\right]$
$\displaystyle=\sqrt{\frac{2}{\pi}}\mathbb{E}_{s\sim\mathbb{P}}\left[\int_{|s|}^{\infty}d\left(-e^{-u^{2}/2}\right)\right]\left\langle
X,Y\right\rangle$
$\displaystyle=\sqrt{\frac{2}{\pi}}\mathbb{E}_{s\sim\mathbb{P}}\left[e^{-s^{2}/2}\right]\left\langle
X,Y\right\rangle,$

where, in (a), we used the fact that $v|u,s\sim\mathcal{N}(\rho u,1-\rho^{2})$
since $s$ is independent of $u,v$. Similarly, one can show that
$\mathbb{E}\left[\mathrm{Sign}\left(\left\langle
A,X\right\rangle\right)\left\langle
A,Y\right\rangle\right]=\sqrt{\frac{2}{\pi}}\left\langle X,Y\right\rangle$.
The proof is completed by noting that

$\displaystyle\mathbb{E}\left[\mathrm{Sign}\left(s+\left\langle
A,X\right\rangle\right)\left\langle A,Y\right\rangle\right]=$ $\displaystyle
p\mathbb{E}\left[\mathrm{Sign}\left(\left\langle
A,X\right\rangle-s\right)\left\langle
A,Y\right\rangle|s\not=0\right]+(1-p)\mathbb{E}\left[\mathrm{Sign}\left(\left\langle
A,X\right\rangle\right)\left\langle A,Y\right\rangle\right].$

This completes the proof. ∎

Now, we provide an overview of our proof technique for Theorem 4. Let
$\mathcal{G}_{Y}=\sup_{X\in\mathcal{S}_{k,\varepsilon}}\mathcal{H}_{X,Y}$ and
$\bar{\mathcal{G}}_{Y}=\mathcal{G}_{Y}-\mathbb{E}[\mathcal{G}_{Y}]$ be
stochastic processes indexed by $Y$. According to Lemma 14, it suffices to
control $\sup_{Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\mathcal{G}_{Y}$. We
consider the following decomposition:

$\displaystyle\sup_{Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\mathcal{G}_{Y}$
$\displaystyle\leq\sup_{Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\bar{\mathcal{G}}_{Y}+\sup_{Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\mathbb{E}[{\mathcal{G}_{Y}}]$
$\displaystyle\leq\sup_{Y\in\mathbb{S}_{k}}\bar{\mathcal{G}}_{Y}+\frac{\varepsilon}{\zeta}\sup_{Y\in\mathbb{S}}\bar{\mathcal{G}}_{Y}+\sup_{Y\in\mathbb{S}_{k}}\mathbb{E}[\mathcal{G}_{Y}]+\frac{\varepsilon}{\zeta}\sup_{Y\in\mathbb{S}}\mathbb{E}[\mathcal{G}_{Y}],$
(68)

where the second inequality follows from
$\mathbb{S}_{k,\varepsilon/\zeta}\subset\mathbb{S}_{k}+\frac{\varepsilon}{\zeta}\mathbb{S}$,
and the fact that both $\bar{\mathcal{G}}_{Y}$ and
$\mathbb{E}[\mathcal{G}_{Y}]$ are linear functions of $Y$. We control the
individual terms in the above decomposition separately. To provide an upper
bound for $\sup_{Y\in\mathbb{S}_{k}}\bar{\mathcal{G}}_{Y}$ and
$\sup_{Y\in\mathbb{S}}\bar{\mathcal{G}}_{Y}$, we rely on the following key
lemma.

######  Lemma 16.

The stochastic processes $\\{\bar{\mathcal{G}}_{Y}\\}_{Y\in\mathbb{S}_{k}}$
and $\\{\bar{\mathcal{G}}_{Y}\\}_{Y\in\mathbb{S}}$ are
$\mathcal{O}\left({1}/{m}\right)$-sub-Gaussian processes.

###### Proof.

Since $\mathbb{S}_{k}\subset\mathbb{S}$, it suffices to show that
$\\{\bar{\mathcal{G}}_{Y}\\}_{Y\in\mathbb{S}}$ is
$\mathcal{O}\left({1}/{m}\right)$-sub-Gaussian. According to Definition 7, the
stochastic process $\left\\{\bar{\mathcal{G}}_{Y}\right\\}_{Y\in\mathbb{S}}$
is sub-Gaussian if for any arbitrary $Y,Y^{\prime}\in\mathbb{S}$,
$\bar{\mathcal{G}}_{Y}-\bar{\mathcal{G}}_{Y^{\prime}}$ is
$\mathcal{O}\left(\left\lVert Y-Y^{\prime}\right\rVert_{F}^{2}/m\right)$-sub-
Gaussian. Note that $\bar{\mathcal{G}}_{Y}-\bar{\mathcal{G}}_{Y^{\prime}}$ is
sub-Gaussian if and only if $\mathcal{G}_{Y}-\mathcal{G}_{Y^{\prime}}$ is sub-
Gaussian with the same parameter. The latter will be proven by checking the
moment bound condition in Definition 6. For arbitrary
$Y,Y^{\prime}\in\mathbb{S}$, denote $\Delta Y=Y-Y^{\prime}$. Then, for any
$p\in\mathbb{N}_{+}$, we have

$\displaystyle\mathbb{E}\left[|\mathcal{G}_{Y}-\mathcal{G}_{Y^{\prime}}|^{2p}\right]$
$\displaystyle\leq\mathbb{E}\left[\left|\sup_{X\in\mathcal{S}_{k,\varepsilon}}\frac{1}{m}\sum_{i=1}^{m}\mathrm{Sign}\left(\left\langle
A_{i},X\right\rangle-s_{i}\right)\left\langle A_{i},\Delta
Y\right\rangle-\varphi(X)\left\langle\frac{X}{\left\lVert
X\right\rVert_{F}},\Delta Y\right\rangle\right|^{2p}\right]$
$\displaystyle\leq\\!\mathbb{E}\left[\left(\sup_{X\in\mathcal{S}_{k,\varepsilon}}\\!\left|\frac{1}{m}\sum_{i=1}^{m}\mathrm{Sign}\left(\left\langle
A_{i},X\right\rangle\\!-\\!s_{i}\right)\left\langle A_{i},\Delta
Y\right\rangle\right|\\!+\\!\\!\\!\sup_{X\in\mathcal{S}_{k,\varepsilon}}\\!\left|\varphi(X)\left\langle\frac{X}{\left\lVert
X\right\rVert_{F}},\Delta Y\right\rangle\right|\right)^{2p}\right]$
$\displaystyle\leq\mathbb{E}\left[\left(\frac{1}{m}\sum_{i=1}^{m}|\left\langle
A_{i},\Delta Y\right\rangle|+\sqrt[]{\frac{2}{\pi}}\left\lVert\Delta
Y\right\rVert_{F}\right)^{2p}\right]$ $\displaystyle\leq
2^{2p}\left(\mathbb{E}\left[\left(\frac{1}{m}\sum_{i=1}^{m}|\left\langle
A_{i},\Delta
Y\right\rangle|\right)^{2p}\right]+\left(\frac{2}{\pi}\right)^{p}\left\lVert\Delta
Y\right\rVert_{F}^{2p}\right),$

where in the third inequality, we used $\varphi(X)\leq\sqrt{2/\pi}$, which
holds for every $X\in\mathbb{R}^{d\times d}$. According to [20, Appendix A.2],
the random variable $({1}/{m})\sum_{i=1}^{m}|\left\langle A_{i},\Delta
Y\right\rangle|$ is $\mathcal{O}\left({\left\lVert\Delta
Y\right\rVert_{F}^{2}}/{m}\right)$-sub-Gaussian with mean
$\sqrt[]{{2}/{\pi}}\left\lVert\Delta Y\right\rVert_{F}$. Therefore, we have

$\displaystyle\mathbb{E}\left[\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
A_{i},\Delta Y\right\rangle\right|\right)^{2p}\right]$
$\displaystyle=\mathbb{E}\left[\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
A_{i},\Delta Y\right\rangle\right|-\sqrt[]{\frac{2}{\pi}}\|\Delta
Y\|_{F}+\sqrt[]{\frac{2}{\pi}}\|\Delta Y\|_{F}\right)^{2p}\right]$
$\displaystyle\leq
2^{2p}\left(\mathbb{E}\left[\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
A_{i},\Delta Y\right\rangle\right|-\sqrt[]{\frac{2}{\pi}}\|\Delta
Y\|_{F}\right)^{2p}\right]+\left(\frac{2}{\pi}\right)^{p}\|\Delta
Y\|_{F}^{2p}\right)$ $\displaystyle\leq
2^{2p}\left((2p-1)!!\frac{1}{m^{p}}\|\Delta
Y\|_{F}^{2p}+\left(\frac{2}{\pi}\right)^{p}\|\Delta Y\|_{F}^{2p}\right).$

Combining the above inequalities leads to

$\mathbb{E}\left[|\mathcal{G}_{Y}-\mathcal{G}_{Y^{\prime}}|^{2p}\right]^{1/2p}\leq
4\left((2p-1)!!\frac{1}{m^{p}}\|\Delta
Y\|_{F}^{2p}+\left(\frac{2}{\pi}\right)^{p}\|\Delta
Y\|_{F}^{2p}\right)^{1/2p}\lesssim\sqrt[]{\frac{p}{m}}\left\lVert\Delta
Y\right\rVert_{F},$

given that $p>m$. Therefore, $\\{\mathcal{G}_{Y}\\}_{Y\in\mathbb{S}}$ is a
$\mathcal{O}\left({1}/{m}\right)$-sub-Gaussian process, which implies that
$\\{\mathcal{G}_{Y}\\}_{Y\in\mathbb{S}_{k}}$ is also a
$\mathcal{O}\left({1}/{m}\right)$-sub-Gaussian process. ∎

Given that both $\\{\bar{\mathcal{G}}_{Y}\\}_{Y\in\mathbb{S}_{k}}$ and
$\\{\bar{\mathcal{G}}_{Y}\\}_{Y\in\mathbb{S}}$ are sub-Gaussian processes, we
can readily obtain sharp concentration bounds on their suprema.

######  Lemma 17.

The following statements hold:

$\displaystyle\mathbb{E}\left[\sup_{Y\in\mathbb{S}_{k}}\bar{\mathcal{G}}_{Y}\right]\lesssim\sqrt[]{\frac{dk}{m}},$
$\displaystyle\mathbb{P}\left(\sup_{Y\in\mathbb{S}_{k}}\bar{\mathcal{G}}_{Y}\geq\mathbb{E}\left[\sup_{Y\in\mathbb{S}_{k}}\bar{\mathcal{G}}_{Y}\right]+\gamma\right)\lesssim
e^{-cm\gamma^{2}};$ (69)
$\displaystyle\mathbb{E}\left[\sup_{Y\in\mathbb{S}}\bar{\mathcal{G}}_{Y}\right]\lesssim\sqrt[]{\frac{d^{2}}{m}},$
$\displaystyle\mathbb{P}\left(\sup_{Y\in\mathbb{S}}\bar{\mathcal{G}}_{Y}\geq\mathbb{E}\left[\sup_{Y\in\mathbb{S}}\bar{\mathcal{G}}_{Y}\right]+\gamma\right)\lesssim
e^{-cm\gamma^{2}}.$ (70)

###### Proof.

The proof follows directly from Theorem 9. The details are omitted for
brevity. ∎

Equipped with the above lemma, we provide a concentration bound on
$\sup_{Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\bar{\mathcal{G}}_{Y}$.

######  Lemma 18.

Assume that $m\gtrsim\sqrt{dk/\gamma^{2}}$ and
$\varepsilon/\zeta\lesssim\sqrt{k/d}$. Then, the following inequality holds
with probability of at least $1-Ce^{-cm\gamma^{2}}$:

$\displaystyle\sup_{Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\bar{\mathcal{G}}_{Y}\leq\left(3+\sqrt{\frac{k}{d}}\right)\gamma.$

###### Proof.

Based on (69), we have, with probability of at least $1-Ce^{-cm\gamma^{2}}$

$\displaystyle\sup_{Y\in\mathbb{S}_{k}}\bar{\mathcal{G}}_{Y}\leq\mathbb{E}\left[\sup_{Y\in\mathbb{S}_{k}}\bar{\mathcal{G}}_{Y}\right]+\gamma\lesssim\sqrt{\frac{dk}{m}}+\gamma\leq
2\gamma,$

where the last inequality follows from the assumption
$m\gtrsim\sqrt{dk/\gamma^{2}}$. Similarly, based on (70), the following
inequalities hold with a probability of at least $1-Ce^{-cm\gamma^{2}}$:

$\displaystyle\frac{\varepsilon}{\zeta}\sup_{Y\in\mathbb{S}}\bar{\mathcal{G}}_{Y}\leq\frac{\varepsilon}{\zeta}\left(\mathbb{E}\left[\sup_{Y\in\mathbb{S}}\bar{\mathcal{G}}_{Y}\right]+\gamma\right)\lesssim\sqrt{\frac{\varepsilon^{2}d^{2}}{\zeta^{2}m}}+\frac{\varepsilon\gamma}{\zeta}\leq\left(1+\sqrt{\frac{k}{d}}\right)\gamma,$

where the last inequality follows from $m\gtrsim\sqrt{dk/\gamma^{2}}$ and
$\varepsilon/\zeta\lesssim\sqrt{k/d}$. Finally, a simple union bound implies
that

$\displaystyle\sup_{Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\bar{\mathcal{G}}_{Y}\leq\sup_{Y\in\mathbb{S}_{k}}\bar{\mathcal{G}}_{Y}+\frac{\varepsilon}{\zeta}\sup_{Y\in\mathbb{S}}\bar{\mathcal{G}}_{Y}\leq\left(3+\sqrt{\frac{k}{d}}\right)\gamma,$

with probability of at least $1-Ce^{-cm\gamma^{2}}$, thereby completing the
proof. ∎

Recalling (B.2), it remains to control the terms
$\sup_{Y\in\mathbb{S}_{k}}\mathbb{E}[\mathcal{G}_{Y}]$ and
$\sup_{Y\in\mathbb{S}}\mathbb{E}[\mathcal{G}_{Y}]$.

######  Lemma 19.

The following inequality holds:

$\displaystyle\sup_{Y\in\mathbb{S}_{k}}\mathbb{E}[\mathcal{G}_{Y}]\leq\sup_{Y\in\mathbb{S}}\mathbb{E}[\mathcal{G}_{Y}]\lesssim\sqrt{\frac{dk}{m}\log^{2}(m)\log\left(\frac{R}{\zeta}\right)}.$
(71)

Due to its length, we defer the proof of Lemma 19 to Appendix F.1. Equipped
with Lemmas 18 and 19, we are ready to present the proof of Theorem 4.

Proof of Theorem 4. The inequality (B.2) combined with Lemmas 18 and 19
implies that the following inequality holds with probability of at least
$1-Ce^{-cm\gamma^{2}}$:

$\displaystyle\sup_{Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\mathcal{G}_{Y}\lesssim\sqrt{\frac{dk}{m}\log^{2}(m)\log\left(\frac{R}{\zeta}\right)}+\gamma.$

On the other hand, one can write

$\inf_{X\in\mathcal{S}_{k,\varepsilon}}\varphi(X)=\inf_{X\in\mathcal{S}_{k,\varepsilon}}\left\\{\sqrt{\frac{2}{\pi}}\left(1-p+p\mathbb{E}\left[e^{-s^{2}/(2\left\lVert
X\right\rVert_{F}^{2})}\right]\right)\right\\}\geq\sqrt{\frac{2}{\pi}}(1-p).$
(72)

Therefore, upon choosing

$\displaystyle
m\gtrsim\frac{dk\log^{2}(m)\log\left(R/\zeta\right)}{(1-p)^{2}\delta^{2}},\quad\text{and}\quad\gamma\lesssim(1-p)\delta,$

we have

$\displaystyle\sup_{Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\mathcal{G}_{Y}=\sup_{\begin{subarray}{c}X\in\mathcal{S}_{k,\varepsilon}\\\
Y\in\mathbb{S}_{k,\varepsilon/\zeta}\end{subarray}}\mathcal{H}_{X,Y}\leq\inf_{X\in\mathcal{S}_{k,\varepsilon}}\varphi(X)\delta$

with probability of at least $1-Ce^{-cm(1-p)^{2}\delta^{2}}$. This completes
the proof of Theorem 4. $\hfill\square$

###  B.3 Proof of Theorem 5

Recall that, with outlier noise model, the scaling function takes the form
$\varphi(X)=\sqrt{\frac{2}{\pi}}\left(1-p+p\mathbb{E}\left[e^{-s^{2}/(2\|X\|_{F}^{2})}\right]\right)$.
Setting $p=1$, and $s_{i}\sim\mathcal{N}(0,\nu_{g}^{2})$ immediately implies
$\varphi(X)=\mathbb{E}_{s\sim\mathcal{N}(0,\nu_{g}^{2})}\left[e^{-s^{2}/(2\|X\|_{F}^{2})}\right]=\sqrt{\frac{2}{\pi}}\frac{\left\lVert
X\right\rVert_{F}}{\sqrt{\left\lVert X\right\rVert_{F}^{2}+\nu_{g}^{2}}}$. On
the other hand, using the same method in the proof of Theorem 4, we can show
that the following inequality holds with probability at least
$1-Ce^{-cm\gamma^{2}}$:

$\displaystyle\sup_{Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\mathcal{G}_{Y}\lesssim\sqrt{\frac{dk}{m}\log^{2}(m)\log\left(\frac{R}{\zeta}\right)}+\gamma,$

where $\mathcal{G}_{Y}$ is defined in the proof of Theorem 4. It remains to
bound $\inf_{X\in\mathcal{S}_{k,\varepsilon}}\varphi(X)$. To this goal, note
that $\left\lVert X\right\rVert_{F}\geq\zeta,\forall
X\in\mathcal{S}_{k,\varepsilon}$. Hence, we have the following lower bound for
the scaling function

$\inf_{X\in\mathcal{S}_{k,\varepsilon}}\varphi(X)=\inf_{X\in\mathcal{S}_{k,\varepsilon}}\sqrt{\frac{2}{\pi}}\frac{\left\lVert
X\right\rVert_{F}}{\sqrt{\left\lVert
X\right\rVert_{F}^{2}+\nu_{g}^{2}}}\geq\sqrt{\frac{2}{\pi}}\frac{\zeta}{\sqrt{\zeta^{2}+\nu_{g}^{2}}}\gtrsim\frac{\zeta}{\nu_{g}},$
(73)

provided that $\zeta\lesssim\nu_{g}$. Therefore, upon choosing
$m\gtrsim\frac{\nu_{g}^{2}dk\log^{2}(m)\log\left(R/\zeta\right)}{\zeta^{2}\delta^{2}}$
and $\gamma\lesssim\frac{\zeta}{\nu_{g}}\delta$, we have

$\sup_{Y\in\mathbb{S}_{k,\varepsilon/\zeta}}\mathcal{G}_{Y}=\sup_{\begin{subarray}{c}X\in\mathcal{S}_{k,\varepsilon}\\\
Y\in\mathbb{S}_{k,\varepsilon/\zeta}\end{subarray}}\mathcal{H}_{X,Y}\leq\inf_{X\in\mathcal{S}_{k,\varepsilon}}\varphi(X)\delta,$
(74)

with probability at least $1-C_{1}e^{-C_{2}m\zeta^{2}\delta^{2}/\nu_{g}^{2}}$,
which completes the proof. $\hfill\square$

###  B.4 Proof of Lemma 1

Lemma 20 is a direct consequence of the following more general result:

######  Lemma 20.

Suppose that the measurements are noiseless, and satisfy
$(k,\delta,\varepsilon,\mathcal{S})$-Sign-RIP for any $\varepsilon\geq 0$,
$\mathcal{S}$, and scaling function $\varphi(\cdot)$. Then, for any
$\varepsilon$-approximate rank-$k$ matrix $X\in\mathcal{S}$, we have

$\left|\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
A_{i},X\right\rangle\right|-\varphi(X)\left\lVert
X\right\rVert_{F}\right|\leq\delta\varphi(X)\left\lVert X\right\rVert_{F}.$

###### Proof.

According to the definition of Sign-RIP, for every $\varepsilon$-approximate
rank-$k$ matrices $X,Y\in\mathcal{S}$, and every $Q\in\mathcal{Q}(X)$, we have
$\left|\left\langle Q-\varphi(X)\frac{X}{\left\lVert
X\right\rVert_{F}},\frac{Y}{\|Y\|_{F}}\right\rangle\right|\leq\varphi(X)\delta$.
In particular, upon choosing $Y=X$, we have

$\left|\left\langle Q-\varphi(X)\frac{X}{\left\lVert
X\right\rVert_{F}},X\right\rangle\right|=\left|\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
A_{i},X\right\rangle\right|-\varphi(X)\left\lVert
X\right\rVert_{F}\right|\leq\varphi(X)\delta\left\lVert X\right\rVert_{F}.$

This completes the proof. ∎

Evidently, the result of Lemma 20 can be readily recovered from the above
lemma after substituting $X$ with $\Delta_{t}$. Moreover, it is worth noting
that the above lemma recovers the so-called $\ell_{1}/\ell_{2}$-RIP introduced
in [20] with $\varepsilon=0$ and $\varphi(X)=\sqrt{2/\pi}$.

###  B.5 Proof of Lemma 2

Due to Sign-RIP, we have

$\displaystyle\left\lVert
Q_{t}\right\rVert\leq\varphi(\Delta_{t})\left(\frac{\left\lVert\Delta_{t}\right\rVert}{\left\lVert\Delta_{t}\right\rVert_{F}}+\delta\right)$
$\displaystyle\implies$ $\displaystyle\frac{1}{\left\lVert
Q_{t}\right\rVert}\geq\frac{1}{\varphi(\Delta_{t})}\frac{1}{\delta+\frac{\left\lVert\Delta_{t}\right\rVert}{\left\lVert\Delta_{t}\right\rVert_{F}}}$
$\displaystyle\implies$ $\displaystyle\frac{1}{\left\lVert
Q_{t}\right\rVert}\geq\frac{1}{\varphi(\Delta_{t})}\frac{\left\lVert\Delta_{t}\right\rVert_{F}}{\left\lVert\Delta_{t}\right\rVert}\left(1-\delta\frac{\left\lVert\Delta_{t}\right\rVert_{F}}{\left\lVert\Delta_{t}\right\rVert}\right)$
(75)

By our assumption, $\Delta_{t}$ is $\varepsilon$-approximate rank-$k$. This
implies that, there exists a rank-$k$ matrix $X^{\prime}$ such that
$\left\lVert\Delta_{t}-X^{\prime}\right\rVert_{F}\leq\varepsilon$. This in
turn implies that

$\displaystyle\left\lVert\Delta_{t}\right\rVert_{F}$
$\displaystyle\leq\left\lVert\Delta_{t}-X^{\prime}\right\rVert_{F}+\left\lVert
X^{\prime}\right\rVert_{F}\leq\varepsilon+\left\lVert
X^{\prime}\right\rVert_{F}\leq\varepsilon+\sqrt{k}\left\lVert
X^{\prime}\right\rVert\leq(1+\sqrt{k})\varepsilon+\sqrt{k}\left\lVert\Delta_{t}\right\rVert$
$\displaystyle\left\lVert\Delta_{t}\right\rVert$ $\displaystyle\geq\left\lVert
X^{\prime}\right\rVert-\left\lVert\Delta_{t}-X^{\prime}\right\rVert\geq\left\lVert
X^{\prime}\right\rVert-\varepsilon\geq\left\lVert\Delta_{t}\right\rVert-2\varepsilon\geq\left\lVert\Delta_{t}\right\rVert/2$

where in the last inequality we used the assumption
$\left\lVert\Delta_{t}\right\rVert\geq 4\varepsilon$. Combining the above
inequalities implies that

$\displaystyle\frac{\left\lVert\Delta_{t}\right\rVert_{F}}{\left\lVert\Delta_{t}\right\rVert}\leq\frac{2(1+\sqrt{k})\varepsilon}{\left\lVert\Delta_{t}\right\rVert}+2\sqrt{k}\leq\frac{1+5\sqrt{k}}{2}.$

Combining the above inequality with (75) leads to

$\displaystyle\eta_{t}=\frac{\eta\rho^{t}}{\left\lVert
Q_{t}\right\rVert}\geq\left(1-\left(\frac{1+5\sqrt{k}}{2}\right)\delta\right)\frac{\eta\rho^{t}}{\varphi(\Delta_{t})}\frac{\left\lVert\Delta_{t}\right\rVert_{F}}{\left\lVert\Delta_{t}\right\rVert}.$

The upper bound can be derived in a similar fashion.$\hfill\square$

##  Appendix C Proofs of the Expected Loss

###  C.1 Proof of Proposition 2

According to the update rule
$U_{t+1}=U_{t}-\eta\left(U_{t}U_{t}^{\top}-X^{\star}\right)U_{t}$, we have

$\displaystyle S_{t+1}$
$\displaystyle=V^{\top}U_{t+1}=S_{t}-\eta\left(\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}+S_{t}E_{t}^{\top}E_{t}\right).$

Define an auxiliary matrix $M$ as

$M:=\left(I-\Xi\right)\left(S_{t}-\eta\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}\right)\left(S_{t}^{\top}-\eta
S_{t}^{\top}\left(S_{t}S_{t}^{\top}-\Sigma\right)\right)\left(I-\Xi^{\top}\right),$
(76)

where $\Xi=\eta
S_{t}E_{t}^{\top}E_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}\left(I-\eta\left(S_{t}S_{t}^{\top}-\Sigma\right)\right)^{-1}$.
Note that, due to our assumptions and the choice of $\eta$, we have
$S_{t}S_{t}^{\top}\succ 0$ and $\eta\left\lVert
S_{t}S_{t}^{\top}-\Sigma\right\rVert<1$. Therefore, both matrices
$S_{t}S_{t}^{\top}$ and $I-\eta\left(S_{t}S_{t}^{\top}-\Sigma\right)$ are
invertible and the matrix $\Xi$ is well-defined. Our goal is to first show
that $\lambda_{\min}(S_{t+1}S_{t+1}^{\top})\geq\lambda_{\min}(M)$, and then
derive a lower bound for $\lambda_{\min}(M)$. Based on the definition of
$\Xi$, it is easy to verify that
$\Xi\left(S_{t}-\eta\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}\right)=S_{t}E_{t}^{\top}E_{t}\mathsf{P}_{S_{t}}.$
Combining this with (76) reveals that

$\displaystyle S_{t+1}S_{t+1}^{\top}-M$
$\displaystyle=\eta^{2}S_{t}E_{t}^{\top}E_{t}\mathsf{P}_{S_{t}}^{\perp}E_{t}^{\top}E_{t}S_{t}^{\top}\succeq
0.$

Therefore, instead of obtaining a lower bound for
$\lambda_{\min}(S_{t+1}S_{t+1}^{\top})$, it suffices to obtain a lower bound
for $\lambda_{\min}(M)$. One can write

$\displaystyle\left\lVert\Xi\right\rVert$ $\displaystyle\leq\eta\left\lVert
S_{t}E_{t}^{\top}E_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}\right\rVert\left\lVert\left(I-\eta\left(S_{t}S_{t}^{\top}-\Sigma\right)\right)^{-1}\right\rVert$
(77) $\displaystyle\lesssim\eta\left\lVert
S_{t}E_{t}^{\top}E_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}\right\rVert$
$\displaystyle=\eta\left\lVert\left(S_{t}S_{t}^{\top}\right)^{-1/2}S_{t}E_{t}^{\top}E_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1/2}\right\rVert$
$\displaystyle\leq\eta\left\lVert
E_{t}E_{t}^{\top}\right\rVert\left\lVert\left(S_{t}S_{t}^{\top}\right)^{-1/2}S_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1/2}\right\rVert$
$\displaystyle=\eta\left\lVert E_{t}E_{t}^{\top}\right\rVert.$
$\displaystyle<1,$

where the last inequality is due to the assumption $\left\lVert
E_{t}E_{t}^{\top}\right\rVert\leq\sigma_{1}$ and the choice of $\eta$.
Therefore, we have

$\displaystyle\lambda_{\min}\left(S_{t+1}S_{t+1}^{\top}\right)$
$\displaystyle\geq\lambda_{\min}\left(M\right)$ (78)
$\displaystyle\geq\left(1-\left\lVert\Xi\right\rVert\right)^{2}\lambda_{\min}\left(\left(S_{t}-\eta\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}\right)\left(S_{t}^{\top}-\eta
S_{t}^{\top}\left(S_{t}S_{t}^{\top}-\Sigma\right)\right)\right).$

Now it suffices to bound
$\lambda_{\min}\left(\left(S_{t}-\eta\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}\right)\left(S_{t}^{\top}-\eta
S_{t}^{\top}\left(S_{t}S_{t}^{\top}-\Sigma\right)\right)\right)$. First note
that

$S_{t}-\eta\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}=\left(I+\eta\Sigma\left(I-\eta
S_{t}S_{t}^{\top}\right)^{-1}\right)\left(S_{t}-\eta
S_{t}S_{t}^{\top}S_{t}\right).$

Based on the above equality, one can write

$\displaystyle\lambda_{\min}\left(\left(S_{t}-\eta\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}\right)\left(S_{t}^{\top}-\eta
S_{t}^{\top}\left(S_{t}S_{t}^{\top}-\Sigma\right)\right)\right)$ (79)
$\displaystyle=\lambda_{\min}\left(\left(I+\eta\Sigma\left(I-\eta
S_{t}S_{t}^{\top}\right)^{-1}\right)\left(S_{t}-\eta
S_{t}S_{t}^{\top}S_{t}\right)\left(S_{t}^{\top}-\eta
S_{t}^{\top}S_{t}S_{t}^{\top}\right)\left(I+\eta\Sigma\left(I-\eta
S_{t}S_{t}^{\top}\right)^{-1}\right)\right)$
$\displaystyle\geq\lambda_{\min}\left(\left(I+\eta\Sigma\left(I-\eta
S_{t}S_{t}^{\top}\right)^{-1}\right)\right)^{2}\lambda_{\min}\left(\left(S_{t}-\eta
S_{t}S_{t}^{\top}S_{t}\right)\left(S_{t}^{\top}-\eta
S_{t}^{\top}S_{t}S_{t}^{\top}\right)\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\left(1+\eta\sigma_{r}\left(1-\eta\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\right)^{-1}\right)^{2}\lambda_{\min}\left(S_{t}S_{t}^{\top}-2\eta\left(S_{t}S_{t}^{\top}\right)^{2}+\eta^{2}\left(S_{t}S_{t}^{\top}\right)^{3}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\left(1+\eta\sigma_{r}\left(1-\eta\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\right)^{-1}\right)^{2}\left(\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)-2\eta\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)^{2}+\eta^{2}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)^{3}\right)$
$\displaystyle\geq\left(1+\eta\sigma_{r}\left(1-\eta\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\right)^{-1}\right)^{2}\left(\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)-2\eta\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)^{2}\right)$
$\displaystyle=\left(1+\eta\sigma_{r}\right)^{2}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)-2\eta\left(1+\eta\sigma_{r}\right)\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)^{2},$

where in (a), we used the fact that

$\displaystyle\lambda_{\min}\left(I+\eta\Sigma\left(I-\eta
S_{t}S_{t}^{\top}\right)^{-1}\right)$
$\displaystyle=1+\lambda_{\min}\left(\eta\Sigma\left(I-\eta
S_{t}S_{t}^{\top}\right)^{-1}\right)$
$\displaystyle=1+\eta\lambda_{\min}\left(\Sigma^{1/2}\left(I-\eta
S_{t}S_{t}^{\top}\right)^{-1}\Sigma^{1/2}\right)$ $\displaystyle\geq
1+\eta\sigma_{r}\lambda_{\min}\left(\left(I-\eta
S_{t}S_{t}^{\top}\right)^{-1}\right)$
$\displaystyle=1+\eta\sigma_{r}\left(1-\eta\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\right)^{-1},$

and in (b) we used the fact that the matrices $S_{t}S_{t}^{\top}$,
$(S_{t}S_{t}^{\top})^{2}$, and $(S_{t}S_{t}^{\top})^{3}$ share the same
eigenvectors. Combining (79) with (77) and (78) completes the proof.
$\hfill\square$

###  C.2 Proof of Proposition 3

Before delving into the details, we provide the update rule for $S_{t}$ and
$E_{t}$, which will be used frequently throughout our proof. Applying the
signal-residual decomposition to
$U_{t+1}=U_{t}-\eta\left(U_{t}U_{t}^{\top}-X^{\star}\right)U_{t}$ leads to

$S_{t+1}=V^{\top}U_{t+1}=S_{t}-\eta\left(\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}+S_{t}E_{t}^{\top}E_{t}\right),$
(80) $E_{t+1}=V_{\perp}^{\top}U_{t+1}=E_{t}-\eta
E_{t}\left(S_{t}^{\top}S_{t}+E_{t}^{\top}E_{t}\right).$ (81)

#### Bounding $\left\lVert\Sigma-S_{t+1}S_{t+1}^{\top}\right\rVert$:

The update rule for $S_{t+1}$ leads to

$\displaystyle\Sigma\\!-\\!S_{t+1}S_{t+1}^{\top}$
$\displaystyle\\!=\\!\underbrace{\Sigma\\!-\\!S_{t}S_{t}^{\top}\\!+\\!\eta
S_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\\!-\\!\Sigma\right)\\!+\\!\eta\left(S_{t}S_{t}^{\top}\\!-\\!\Sigma\right)S_{t}S_{t}^{\top}\\!-\\!\eta^{2}\left(S_{t}S_{t}^{\top}\\!-\\!\Sigma\right)S_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\\!-\\!\Sigma\right)}_{(A)}$
(82) $\displaystyle\underbrace{+2\eta
S_{t}E_{t}^{\top}E_{t}S_{t}^{\top}-\eta^{2}\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}E_{t}^{\top}E_{t}S_{t}^{\top}-{\eta^{2}S_{t}E_{t}^{\top}E_{t}S^{\top}_{t}\left(S_{t}S_{t}^{\top}-\Sigma\right)}}_{(B)}$
$\displaystyle-\underbrace{\eta^{2}S_{t}E_{t}^{\top}E_{t}E_{t}^{\top}E_{t}S_{t}^{\top}}_{(C)}.$

First, we provide an upper bound for (B). Recall that
$\eta=\mathcal{O}\left({1}/{\sigma_{1}}\right)$. Moreover, we have
$\left\lVert S_{t}S_{t}^{\top}-\Sigma\right\rVert\leq 2.01\sigma_{1}$ due to
the assumption $\left\lVert S_{t}S_{t}^{\top}\right\rVert\leq 1.01\sigma_{1}$.
Therefore, one can write

$\left\lVert(B)\right\rVert\leq 2\eta\left\lVert
S_{t}E_{t}^{\top}E_{t}S_{t}^{\top}\right\rVert+2\eta^{2}\left\lVert
S_{t}S_{t}^{\top}-\Sigma\right\rVert\left\lVert
S_{t}E_{t}^{\top}E_{t}S_{t}^{\top}\right\rVert\leq 4\eta\left\lVert
S_{t}E_{t}^{\top}\right\rVert^{2}.$

Similarly, due to our assumption on $\left\lVert
E_{t}E_{t}^{\top}\right\rVert$ and $\eta$, we have $\left\lVert
E_{t}E_{t}^{\top}\right\rVert\leq 1/\eta$, which in turn implies

$\left\lVert(C)\right\rVert\leq\eta^{2}\left\lVert
E_{t}E_{t}^{\top}\right\rVert\left\lVert
S_{t}E_{t}^{\top}\right\rVert^{2}\leq\eta\left\lVert
S_{t}E_{t}^{\top}\right\rVert^{2}.$

Finally, we provide an upper bound for (A). First, one can verify that

$\displaystyle(A)=\underbrace{\left(\Sigma-
S_{t}S_{t}^{\top}\right)\left(0.5I-\eta
S_{t}S_{t}^{\top}\right)}_{(A_{1})}+\underbrace{\left(0.5I-\eta
S_{t}S_{t}^{\top}+\eta^{2}\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}S_{t}^{\top}\right)\left(\Sigma-
S_{t}S_{t}^{\top}\right)}_{(A_{2})}.$

For the first term, we have

$\displaystyle\left\lVert(A_{1})\right\rVert$ $\displaystyle\leq\left\lVert
0.5I-\eta S_{t}S_{t}^{\top}\right\rVert\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert\leq\left(0.5-\eta\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\right)\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert.$

To provide a bound for $(A_{2})$, observe that

$0.5I-\eta
S_{t}S_{t}^{\top}+\eta^{2}\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}S_{t}^{\top}=0.5I-\eta\left(I+\eta\left(\Sigma-
S_{t}S_{t}^{\top}\right)\right)S_{t}S_{t}^{\top}.$

The next step in our proof is to show that, with the choice of $\eta\lesssim
1/\sigma_{1}$, the eigenvalues of $\left(I+\eta\left(\Sigma-
S_{t}S_{t}^{\top}\right)\right)S_{t}S_{t}^{\top}$ are nonnegative. We prove
this by showing that the eigenvalues of $\left(I+\eta\left(\Sigma-
S_{t}S_{t}^{\top}\right)\right)S_{t}S_{t}^{\top}$ are close to those of
$S_{t}S_{t}^{\top}$. First, note that $I+\eta\left(\Sigma-
S_{t}S_{t}^{\top}\right)$ is positive definite due to our choice of step-size.
Therefore, the matrix $D=\left(I+\eta\left(\Sigma-
S_{t}S_{t}^{\top}\right)\right)^{1/2}$ is well-defined and invertable. Hence,
for any $1\leq i\leq r$, we have

$\lambda_{i}\left(\left(I+\eta\left(\Sigma-
S_{t}S_{t}^{\top}\right)\right)S_{t}S_{t}^{\top}\right)=\lambda_{i}\left(D^{-1}\left(I+\eta\left(\Sigma-
S_{t}S_{t}^{\top}\right)\right)S_{t}S_{t}^{\top}D\right)=\lambda_{i}\left(DS_{t}S_{t}^{\top}D\right).$

To proceed with our argument, we first present a relative perturbation bound
for symmetric matrices.

######  Lemma 21 (Relative Perturbation Bound, Eisenstat and Ipsen [11]).

Let $X\in\mathbb{R}^{d\times d}$ be a symmetric matrix with eigenvalues
$\lambda_{1}\geq\dots\geq\lambda_{d}$. Moreover, suppose $R$ is a non-singular
matrix. Let $\hat{\lambda}_{1}\geq\dots\geq\hat{\lambda}_{d}$ be the
eigenvalues of $Y=R^{\top}XR$. Then, we have

$\left|\lambda_{i}-\hat{\lambda}_{i}\right|\leq|\lambda_{i}|\left\lVert
I-R^{\top}R\right\rVert,\quad\text{for all }i.$

Invoking Lemma 21 with $X=S_{t}S_{t}$ and $Y=DS_{t}S_{t}D$ results in

$\displaystyle{\left|\lambda_{i}\left(\left(I+\eta\left(\Sigma-
S_{t}S_{t}^{\top}\right)\right)S_{t}S_{t}^{\top}\right)-\lambda_{i}\left(S_{t}S_{t}^{\top}\right)\right|}$
$\displaystyle\leq\left|\lambda_{i}(S_{t}S_{t}^{\top})\right|\left\lVert
I-D^{2}\right\rVert$
$\displaystyle=\left|\lambda_{i}(S_{t}S_{t}^{\top})\right|\left\lVert
I-\left(I+\eta\left(\Sigma-S_{t}S_{t}^{\top}\right)\right)\right\rVert$
$\displaystyle=\eta\left|\lambda_{i}(S_{t}S_{t}^{\top})\right|\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert$ $\displaystyle\leq
0.5\left|\lambda_{i}(S_{t}S_{t}^{\top})\right|.$

for every $i=1,2,\dots,r$. The above inequality implies that
$\lambda_{\min}\left(\left(I+\eta\left(\Sigma-
S_{t}S_{t}^{\top}\right)\right)S_{t}S_{t}^{\top}\right)\asymp\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)$,
and therefore, $\lambda_{\min}\left(\left(I+\eta\left(\Sigma-
S_{t}S_{t}^{\top}\right)\right)S_{t}S_{t}^{\top}\right)\geq 0$. This leads to

$\displaystyle\left\lVert 0.5I-\eta
S_{t}S_{t}^{\top}+\eta^{2}\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}S_{t}^{\top}\right\rVert$
$\displaystyle=\left\lVert 0.5I-\eta
S_{t}S_{t}^{\top}+\eta^{2}\left(S_{t}S_{t}^{\top}\right)^{1/2}\left(S_{t}S_{t}^{\top}-\Sigma\right)\left(S_{t}S_{t}^{\top}\right)^{1/2}\right\rVert$
$\displaystyle\leq 0.5-\lambda_{\min}\left(\eta
S_{t}S_{t}^{\top}-\eta^{2}\left(S_{t}S_{t}^{\top}\right)^{1/2}\left(S_{t}S_{t}^{\top}-\Sigma\right)\left(S_{t}S_{t}^{\top}\right)^{1/2}\right)$
$\displaystyle=0.5-\lambda_{\min}\left(\eta
S_{t}S_{t}^{\top}-\eta^{2}\left(S_{t}S_{t}^{\top}-\Sigma\right)\left(S_{t}S_{t}^{\top}\right)\right)$
$\displaystyle=0.5-\eta\lambda_{\min}\left(\left(I+\eta\left(\Sigma-
S_{t}S_{t}^{\top}\right)\right)S_{t}S_{t}^{\top}\right)\leq 0.5,$

where in the last inequality, we used the fact that
$\lambda_{\min}\left(\left(I+\eta\left(\Sigma-
S_{t}S_{t}^{\top}\right)\right)S_{t}S_{t}^{\top}\right)\geq 0$. Combined with
the definition of $(A_{2})$, we have

$\displaystyle\left\lVert(A_{2})\right\rVert\leq\left\lVert 0.5I-\eta
S_{t}S_{t}^{\top}+\eta^{2}\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}S_{t}^{\top}\right\rVert\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert\leq 0.5\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert,$

which in turn implies

$\displaystyle\left\lVert(A)\right\rVert\leq\left(1-\eta\lambda_{\min}(S_{t}S_{t}^{\top})\right)\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert.$

Combining the derived upper bounds for $(A)$, $(B)$, and $(C)$ completes the
proof for the signal dynamics.$\hfill\square$

#### Bounding $\left\lVert S_{t+1}E_{t+1}^{\top}\right\rVert$:

Recalling the update rules (80) and (81), we have

$\displaystyle S_{t+1}E_{t+1}^{\top}$
$\displaystyle=\underbrace{S_{t}E_{t}^{\top}+\eta(\Sigma-
S_{t}S_{t}^{\top})S_{t}E_{t}^{\top}-\eta
S_{t}(S_{t}^{\top}S_{t}+E_{t}^{\top}E_{t})E_{t}^{\top}}_{(A)}$
$\displaystyle+\underbrace{\eta^{2}\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}(S_{t}^{\top}S_{t}+E_{t}^{\top}E_{t})E_{t}^{\top}}_{(B)}-\underbrace{\eta
S_{t}E_{t}^{\top}E_{t}E^{\top}_{t}}_{(C)}+\underbrace{\eta^{2}S_{t}E^{\top}_{t}E_{t}\left(S_{t}^{\top}S_{t}+E_{t}^{\top}E_{t}\right)E_{t}^{\top}}_{(D)}.$

We provide separate bounds for the individual terms in the above equality.
First, observe that $\left\lVert(C)\right\rVert\leq\eta\left\lVert
E_{t}E_{t}^{\top}\right\rVert\left\lVert S_{t}E_{t}^{\top}\right\rVert$.
Moreover, one can write

$\displaystyle\left\lVert(B)\right\rVert$
$\displaystyle\leq\eta^{2}\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert\left\lVert
S_{t}(S_{t}^{\top}S_{t}+E_{t}^{\top}E_{t})E_{t}^{\top}\right\rVert$
$\displaystyle\leq\eta^{2}\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert\left(\left\lVert
S_{t}S_{t}^{\top}\right\rVert+\left\lVert
E_{t}E_{t}^{\top}\right\rVert\right)\left\lVert S_{t}E_{t}^{\top}\right\rVert$
$\displaystyle\leq\eta\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert\left\lVert S_{t}E_{t}^{\top}\right\rVert,$

where, in the last inequality, we used the assumption that $\left\lVert
E_{t}E_{t}^{\top}\right\rVert\lesssim\sigma_{1}$ and $\left\lVert
S_{t}S_{t}^{\top}\right\rVert\lesssim\sigma_{1}$. Similarly, we have

$\displaystyle\left\lVert(D)\right\rVert$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\eta^{2}\left\lVert
S_{t}E_{t}^{\top}\right\rVert\left(\left\lVert
S_{t}S_{t}^{\top}\right\rVert+\left\lVert
E_{t}E_{t}^{\top}\right\rVert\right)\left\lVert E_{t}E_{t}^{\top}\right\rVert$
$\displaystyle\leq\eta\left\lVert E_{t}E_{t}^{\top}\right\rVert\left\lVert
S_{t}E_{t}^{\top}\right\rVert,$

where, in (a), we used $\left\lVert S_{t}S_{t}^{\top}\right\rVert
E_{t}E_{t}^{\top}\succeq E_{t}S_{t}^{\top}S_{t}E_{t}^{\top}\succeq 0$.
Finally, we provide an upper bound for $(A)$.

$\displaystyle\left\lVert(A)\right\rVert$
$\displaystyle\leq\left(\eta\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert+\left\lVert I-\eta
S_{t}S_{t}^{\top}\right\rVert\right)\left\lVert S_{t}E_{t}^{\top}\right\rVert$
$\displaystyle\leq\left(\eta\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert+1-\eta\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\right)\left\lVert
S_{t}E_{t}^{\top}\right\rVert.$

Combining the derived bounds for (A), (B), (C), and (D) concludes the
proof.$\hfill\square$

#### Bounding $\left\lVert E_{t+1}E_{t+1}^{\top}\right\rVert$:

Due to the update rule for $E_{t+1}$, one can write

$\displaystyle E_{t+1}E_{t+1}^{\top}$ $\displaystyle=E_{t}E_{t}^{\top}-2\eta
E_{t}\left(E^{\top}_{t}E_{t}+S^{\top}_{t}S_{t}\right)E_{t}^{\top}+\eta^{2}E_{t}\left(E^{\top}_{t}E_{t}+S^{\top}_{t}S_{t}\right)^{2}E_{t}^{\top}$
(83)
$\displaystyle=E_{t}\left(I-2\eta\left(E^{\top}_{t}E_{t}+S^{\top}_{t}S_{t}\right)+\eta^{2}\left(E^{\top}_{t}E_{t}+S^{\top}_{t}S_{t}\right)^{2}\right)E_{t}^{\top}.$

On the other hand, $\eta\lesssim 1/\sigma_{1}$, $\left\lVert
E_{t}E_{t}\right\rVert\lesssim\sigma_{1}$, and $\left\lVert
S_{t}S_{t}\right\rVert\lesssim\sigma_{1}$ imply that

$I-\eta E^{\top}_{t}E_{t}\succ
I-2\eta\left(E^{\top}_{t}E_{t}+S^{\top}_{t}S_{t}\right)+\eta^{2}\left(E^{\top}_{t}E_{t}+S^{\top}_{t}S_{t}\right)^{2}\succ
0.$ (84)

Hence, we have

$\displaystyle\left\lVert E_{t}E_{t}^{\top}\right\rVert$
$\displaystyle=\left\lVert
E_{t}\left(I-2\eta\left(E^{\top}_{t}E_{t}+S^{\top}_{t}S_{t}\right)+\eta^{2}\left(E^{\top}_{t}E_{t}+S^{\top}_{t}S_{t}\right)^{2}\right)E_{t}^{\top}\right\rVert$
$\displaystyle\leq\left\lVert E_{t}\left(I-\eta
E_{t}^{\top}E_{t}\right)E_{t}^{\top}\right\rVert$ $\displaystyle=\left\lVert
E_{t}E_{t}^{\top}-\eta E_{t}E^{\top}_{t}E_{t}E_{t}^{\top}\right\rVert$
$\displaystyle=\left(1-\eta\left\lVert
E_{t}E_{t}^{\top}\right\rVert\right)\left\lVert
E_{t}E_{t}^{\top}\right\rVert,$

where in the last inequality, we used the fact that $\left\lVert
E_{t}E_{t}^{\top}\right\rVert\leq\sigma_{1}$.

#### Bounding $\left\lVert S_{t+1}S_{t+1}^{\top}\right\rVert$:

First, recall that

$\displaystyle S_{t+1}S_{t+1}^{\top}=$ $\displaystyle{S_{t}S_{t}^{\top}-2\eta
S_{t}S_{t}^{\top}S_{t}S_{t}^{\top}+\eta\Sigma S_{t}S_{t}^{\top}+\eta
S_{t}S_{t}^{\top}\Sigma+\eta^{2}\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}-\Sigma\right)}$
$\displaystyle{-2\eta
S_{t}E_{t}E_{t}^{\top}S_{t}^{\top}+\eta^{2}S_{t}E_{t}^{\top}E_{t}E_{t}^{\top}E_{t}S_{t}^{\top}}$
$\displaystyle{+\eta^{2}\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}E_{t}E_{t}^{\top}S_{t}^{\top}+\eta^{2}S_{t}E_{t}E_{t}^{\top}S_{t}^{\top}\left(S_{t}S_{t}^{\top}-\Sigma\right)}$
$\displaystyle\preceq$ $\displaystyle\underbrace{S_{t}S_{t}^{\top}-2\eta
S_{t}S_{t}^{\top}S_{t}S_{t}^{\top}+\eta\Sigma S_{t}S_{t}^{\top}+\eta
S_{t}S_{t}^{\top}\Sigma+\eta^{2}\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}-\Sigma\right)}_{(A)}$
$\displaystyle+\underbrace{\eta^{2}S_{t}E_{t}^{\top}E_{t}E_{t}^{\top}E_{t}S_{t}^{\top}+\eta^{2}\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}E_{t}E_{t}^{\top}S_{t}^{\top}+\eta^{2}S_{t}E_{t}E_{t}^{\top}S_{t}^{\top}\left(S_{t}S_{t}^{\top}-\Sigma\right)}_{(B)},$

where the last inequality follows by noting that ${-2\eta
S_{t}E_{t}E_{t}^{\top}S_{t}^{\top}}\preceq 0$. Now, it is easy to see that

$\displaystyle\left\lVert(B)\right\rVert$
$\displaystyle\leq\eta^{2}\left\lVert
E_{t}E_{t}^{\top}\right\rVert^{2}\left\lVert
S_{t}S_{t}^{\top}\right\rVert+2\eta^{2}\left\lVert
E_{t}E_{t}^{\top}\right\rVert\left\lVert
S_{t}S_{t}^{\top}\right\rVert\left(\sigma_{1}+\left\lVert
S_{t}S_{t}^{\top}\right\rVert\right)$ $\displaystyle\leq 3\eta^{2}\left\lVert
E_{t}E_{t}^{\top}\right\rVert\left\lVert
S_{t}S_{t}^{\top}\right\rVert\left(\sigma_{1}+\left\lVert
S_{t}S_{t}^{\top}\right\rVert\right).$

It remains to provide an upper bound for $(A)$. One can write

$\displaystyle(A)=$
$\displaystyle\underbrace{S_{t}S_{t}^{\top}-2\eta\left(S_{t}S_{t}^{\top}\right)^{2}+\eta^{2}\left(\left(S_{t}S_{t}^{\top}\right)^{3}+\Sigma
S_{t}S_{t}^{\top}\Sigma\right)}_{({A_{1}})}$
$\displaystyle+\underbrace{\eta\Sigma S_{t}S_{t}^{\top}\left(I-\eta
S_{t}S_{t}^{\top}\right)\eta S_{t}S_{t}^{\top}\left(I-\eta
S_{t}S_{t}^{\top}\right)\Sigma}_{(A_{2})}.$

For ($A_{1}$), we have

$\displaystyle\left\lVert(A_{1})\right\rVert$ $\displaystyle\leq\left\lVert
S_{t}S_{t}^{\top}-2\eta\left(S_{t}S_{t}^{\top}\right)^{2}+\eta^{2}\left(S_{t}S_{t}^{\top}\right)^{3}\right\rVert+\eta^{2}\left\lVert\Sigma
S_{t}S_{t}^{\top}\Sigma\right\rVert$ $\displaystyle\leq\left\lVert
S_{t}S_{t}^{\top}-2\eta\left(S_{t}S_{t}^{\top}\right)^{2}+\eta^{2}\left(S_{t}S_{t}^{\top}\right)^{3}\right\rVert+\eta^{2}\sigma_{1}^{2}\left\lVert
S_{t}S_{t}^{\top}\right\rVert$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left\lVert
S_{t}S_{t}^{\top}\right\rVert-2\eta\left\lVert
S_{t}S_{t}^{\top}\right\rVert^{2}+\eta^{2}\left\lVert
S_{t}S_{t}^{\top}\right\rVert^{3}+\eta^{2}\sigma_{1}^{2}\left\lVert
S_{t}S_{t}^{\top}\right\rVert,$

where (a) follows from the fact that $S_{t}S_{t}^{\top}$,
$\left(S_{t}S_{t}^{\top}\right)^{2}$, $\left(S_{t}S_{t}^{\top}\right)^{3}$
share the same eigenvectors, and the assumption $\eta\lesssim 1/\sigma_{1}$.
On the other hand, one can easily verify that

$\left\lVert(A_{2})\right\rVert\leq 2\eta\sigma_{1}\left\lVert
S_{t}S_{t}^{\top}\left(I-\eta S_{t}S_{t}^{\top}\right)\right\rVert\leq
2\eta\sigma_{1}\left(\left\lVert S_{t}S_{t}^{\top}\right\rVert-\eta\left\lVert
S_{t}S_{t}^{\top}\right\rVert^{2}\right).$

Combining the upper bounds for (A) and (B) leads to

$\displaystyle\left\lVert S_{t+1}S_{t+1}^{\top}\right\rVert$
$\displaystyle\leq\left((1+\eta\sigma_{1})^{2}+3\eta^{2}\sigma_{1}\left\lVert
E_{t}E_{t}^{\top}\right\rVert\right)\left\lVert
S_{t}S_{t}^{\top}\right\rVert-2\eta\left(1+\eta\sigma_{1}-1.5\eta\left\lVert
E_{t}E_{t}^{\top}\right\rVert\right)\left\lVert
S_{t}S_{t}^{\top}\right\rVert^{2}$ $\displaystyle\ \ +\eta^{2}\left\lVert
S_{t}S_{t}^{\top}\right\rVert^{3}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left((1+2.001\sigma_{1}\right)\left\lVert
S_{t}S_{t}^{\top}\right\rVert-2\eta\left\lVert
S_{t}S_{t}^{\top}\right\rVert^{2}+\eta^{2}\left\lVert
S_{t}S_{t}^{\top}\right\rVert^{3}=f\left(\left\lVert
S_{t}S_{t}^{\top}\right\rVert\right),$

where, in (a), we used the assumption $\left\lVert
E_{t}E_{t}^{\top}\right\rVert\lesssim\sigma_{1}$ and $\eta\lesssim
1/\sigma_{1}$. Now, let us define the function

$f(x):=\eta^{2}x^{3}-2\eta x^{2}+\left(1+2.001\sigma_{1}\right)x.$

It is easy to see that $f(x)$ is increasing within the interval
$x\leq{1}/{4\eta}$. On the other hand, we have $1.01\sigma_{1}\leq{1}/{4\eta}$
due to our choice of $\eta$. Therefore, we have

$\left\lVert S_{t+1}S_{t+1}^{\top}\right\rVert\leq f\left(\left\lVert
S_{t}S_{t}^{\top}\right\rVert\right)\leq f\left(1.01\sigma_{1}\right).$

On the other hand, simple calculation reveals that

$\displaystyle
f(1.01\sigma_{1})=\eta^{2}(1.01\sigma_{1})^{3}-2\eta(1.01\sigma_{1})^{2}+\left(1+2.001\sigma_{1}\right)(1.01\sigma_{1})\leq
1.01\sigma_{1}.$

for $\eta\leq{c}/{\sigma_{1}}$ with sufficiently small constant $c$. This
completes the proof.$\hfill\square$

###  C.3 Proof of Lemma 5

We prove this lemma by induction on $t$. First, due to our choice of the
initial point in Theorem 6, we have $\left\lVert
E_{0}E_{0}^{\top}\right\rVert\leq\alpha^{2}$, $\left\lVert
S_{0}S_{0}^{\top}\right\rVert\leq 1.01\sigma_{1}$ and $S_{0}S_{0}^{\top}\succ
0$. Now, suppose that (34), (35), and (36) hold for $t$. Then, it is easy to
see that

$\displaystyle\left\lVert E_{t}E_{t}^{\top}\right\rVert\leq\left\lVert
E_{0}E_{0}^{\top}\right\rVert\leq\alpha^{2},$ (85)

due to the decreasing nature of $\left\lVert E_{t}E_{t}^{\top}\right\rVert$.
Therefore, Proposition 3 can be invoked to show that $\left\lVert
S_{t+1}S_{t+1}^{\top}\right\rVert\leq 1.01\sigma_{1}$. Moreover, we have

$\displaystyle\left\lVert E_{t+1}E_{t+1}^{\top}\right\rVert$
$\displaystyle\leq\left\lVert E_{t}E_{t}^{\top}\right\rVert-\eta\left\lVert
E_{t}E_{t}^{\top}\right\rVert^{2}$ (86) $\displaystyle\leq\frac{1}{\eta
t+\frac{1}{\alpha^{2}}}-\frac{\eta}{\left(\eta
t+\frac{1}{\alpha^{2}}\right)^{2}}$
$\displaystyle\leq\frac{1}{\eta(t+1)+\frac{1}{\alpha^{2}}}.$

On the other hand, Proposition 2 can be used to show that

$\displaystyle\lambda_{\min}\left(S_{t+1}S_{t+1}^{\top}\right)$
$\displaystyle\geq\left(1+\eta^{2}\sigma_{r}^{2}\right)\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)-2\eta\left(1+\eta\sigma_{r}\right)\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)^{2}$
$\displaystyle\geq\left(1-2\eta\sigma_{1}\left(1+\eta\sigma_{r}\right)+\eta^{2}\sigma_{r}^{2}\right)\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)$
$\displaystyle>0,$

where in the first inequality, we used $\left\lVert
E_{t}E_{t}^{\top}\right\rVert\lesssim\sigma_{r}$, which follows from
$\left\lVert E_{t}E_{t}^{\top}\right\rVert\leq\alpha^{2}$ and our choice of
$\alpha$. Moreover, the last inequality follows from our choice of $\eta$.
$\hfill\square$

##  Appendix D Proofs of Empirical Loss with Noiseless Measurements

###  D.1 Preliminaries

For simplicity, we define $\Delta_{t}=U_{t}U_{t}^{\top}-X^{\star}$. Before
presenting the proofs for the empirical loss, we first introduce a key
decomposition. Recall the update rule

$U_{t+1}=U_{t}-2\eta_{t}Q_{t}U_{t}:=\tilde{U}_{t+1}+R_{t}U_{t},$ (87)

where $\eta_{t}=\frac{\eta}{2}\frac{1}{m}\sum_{i=1}^{m}|\left\langle
A_{i},\Delta_{t}\right\rangle|$ and $Q_{t}\in\mathcal{Q}(\Delta_{t})$.
Moreover, denote $\tilde{U}_{t+1}=U_{t}-\bar{\eta}_{t}\Delta_{t}U_{t}$, where
$\bar{\eta}_{t}=\eta\varphi(\Delta_{t})^{2}$ is the update rule obtained from
the expected loss, and $R_{t}U_{t}$ with
$R_{t}=\bar{\eta}_{t}\Delta_{t}-2\eta_{t}Q_{t}$ is the residual caused by the
deviation of the empirical loss from its expectation. Finally, we define
$\tilde{S}_{t}=V^{\top}\tilde{U}_{t}$, and
$\tilde{E}_{t}=V_{\perp}^{\top}\tilde{U}_{t}$.

######  Lemma 22.

Suppose that the measurements satisfy Sign-RIP with parameters
$\left(4r,\delta,\sqrt{d}\left\lVert G_{t}\right\rVert^{2}\right)$. Then, we
have $\left\lVert R_{t}\right\rVert\leq
3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}$.

###### Proof.

One can write

$\Delta_{t}=\underbrace{V\left(S_{t}S_{t}^{\top}-\Sigma\right)V^{\top}+VS_{t}E_{t}^{\top}V_{\perp}^{\top}+V_{\perp}E_{t}S_{t}^{\top}V^{\top}+V_{\perp}G_{t}G_{t}^{\top}V_{\perp}^{\top}}_{\text{rank-$4r$}}+\underbrace{V_{\perp}G_{t}G_{t}^{\top}V_{\perp}^{\top}}_{\text{small
perturbation}}.$

Note that $\left\lVert
V_{\perp}G_{t}G_{t}^{\top}V_{\perp}^{\top}\right\rVert_{F}\leq\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}$. Therefore, $\Delta_{t}$ is an $\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}$-approximate rank-$4r$ matrix. One can write

$\displaystyle R_{t}=$
$\displaystyle\eta\varphi(\Delta_{t})^{2}\Delta_{t}-2\eta_{t}Q_{t}$
$\displaystyle=$
$\displaystyle\left(\frac{\eta}{2}\varphi(\Delta)\left\lVert\Delta_{t}\right\rVert_{F}-\eta_{t}\right)Q_{t}+\left(\frac{\eta}{2}\varphi(\Delta)\left\lVert\Delta_{t}\right\rVert_{F}-\eta_{t}\right)Q_{t}^{\top}$
$\displaystyle+\frac{\eta}{2}\varphi(\Delta_{t})\left\lVert\Delta_{t}\right\rVert_{F}\left(\varphi(\Delta_{t})\frac{\Delta_{t}}{\left\lVert\Delta_{t}\right\rVert_{F}}-Q_{t}\right)+\frac{\eta}{2}\varphi(\Delta_{t})\left\lVert\Delta_{t}\right\rVert_{F}\left(\varphi(\Delta_{t})\frac{\Delta_{t}}{\left\lVert\Delta_{t}\right\rVert_{F}}-Q_{t}^{\top}\right)$

Due to the above decomposition, one can write

$\displaystyle\left\lVert
R_{t}\right\rVert\leq{2\left|{\frac{\eta}{2}\varphi(\Delta)\left\lVert\Delta_{t}\right\rVert_{F}-\eta_{t}}\right|\left\lVert
Q_{t}\right\rVert}+{\eta\varphi(\Delta_{t})\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert\varphi(X)\frac{\Delta_{t}}{\left\lVert\Delta_{t}\right\rVert_{F}}-Q_{t}\right\rVert}.$
(88)

First, note that
$\left|{(\eta/2)\varphi(\Delta)\left\lVert\Delta_{t}\right\rVert_{F}-\eta_{t}}\right|\leq\delta(\eta/2)\varphi(\Delta_{t})\left\lVert\Delta_{t}\right\rVert_{F}$
due to Lemma 20. Moreover, due to Sign-RIP, we have $\left\lVert
Q_{t}\right\rVert\leq(1+\delta)\varphi(\Delta_{t})$ and
$\left\lVert\varphi(X)\frac{\Delta_{t}}{\left\lVert\Delta_{t}\right\rVert_{F}}-Q_{t}\right\rVert\leq\delta\varphi(\Delta_{t})$.
Combining these upper bounds with (88) completes the proof. ∎

###  D.2 Proof of Proposition 4

Due to the proposed decomposition (87), one can write

$\displaystyle S_{t+1}$ $\displaystyle=\tilde{S}_{t+1}+V^{\top}R_{t}U_{t}.$
(89)

Our main goal is to show that the minimum eigenvalue of $S_{t}S_{t}^{\top}$
follows that of $\tilde{S}_{t}\tilde{S}_{t}^{\top}$—which has been
characterized in Lemma 2—plus an additional deviation caused by the term
$V^{\top}R_{t}U_{t}$. Similar to the proof of Proposition 2, we characterize
the growth rate of $\lambda_{\min}(S_{t+1}S_{t+1}^{\top})$ by first resorting
to a more tractable lower bound. Adopting the notation introduced in Appendix
D, consider the following auxiliary matrix

$\displaystyle M$
$\displaystyle:=\left(I+\Xi\right)\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\left(I+\Xi\right)^{\top}=\left(I+\Xi\right)V^{\top}\left(I-\bar{\eta}_{t}\Delta_{t}\right)U_{t}U_{t}^{\top}\left(I-\bar{\eta}_{t}\Delta_{t}\right)\left(I+\Xi\right)^{\top},$

where
$\Xi:=V^{\top}R_{t}U_{t}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}$.
Note that, according to Lemma 5, we have
$\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\succ 0$ due to our assumption
$S_{t}S_{t}^{\top}\succ 0$. Therefore, $\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}$
is invertible, and hence, the matrix $\Xi$ is well-defined. On the other hand,
it is easy to see that $\Xi$ satisfies

$V^{\top}R_{t}U_{t}\tilde{S}_{t+1}^{\top}=\Xi\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}.$
(90)

Based on the above equality, one can write

$\displaystyle S_{t+1}S_{t+1}^{\top}-M$
$\displaystyle=\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}+V^{\top}R_{t}U_{t}U_{t}^{\top}R_{t}^{\top}V+\tilde{S}_{t+1}U_{t}^{\top}R_{t}^{\top}V+V^{\top}R_{t}U_{t}\tilde{S}_{t+1}^{\top}\right)$
(91) $\displaystyle\ \ \
-\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}-\Xi\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\Xi^{\top}+\Xi\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}+\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\Xi^{\top}\right)$
$\displaystyle=V^{\top}R_{t}U_{t}U_{t}^{\top}R_{t}^{\top}V-V^{\top}R_{t}U_{t}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\tilde{S}_{t+1}U_{t}^{\top}R_{t}^{\top}V$
$\displaystyle=V^{\top}R_{t}U_{t}\left(I-\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\tilde{S}_{t+1}\right)U_{t}^{\top}R_{t}^{\top}V$
$\displaystyle=V^{\top}R_{t}U_{t}\mathsf{P}_{\tilde{S}+1}^{\perp}U_{t}^{\top}R_{t}^{\top}V$
$\displaystyle\succeq 0.$

Therefore, we have
$\lambda_{\min}(S_{t+1}S_{t+1}^{\top})\geq\lambda_{\min}(M)$. Our next goal is
to provide a lower bound for $\lambda_{\min}(M)$. To this goal, we will show
that the minimum eigenvalue of $M$ is close to that of
$\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}$. Combined with the minimum eigenvalue
dynamics of $\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}$ presented in Proposition
2, this completes the proof.

To show that
$\lambda_{\min}(M)\approx\lambda_{\min}(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top})$,
we will use the relative perturbation bound presented in Lemma 21. To this
goal, first we need to provide an upper bound for
$\left\lVert\Xi\right\rVert$.

#### Bounding $\left\lVert\Xi\right\rVert$.

One can write

$\displaystyle\left\lVert\Xi\right\rVert$ $\displaystyle\leq\left\lVert
R_{t}\right\rVert\left\lVert
U_{t}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\right\rVert$
(92) $\displaystyle=\left\lVert
R_{t}\right\rVert\left\lVert\left(I-\bar{\eta}_{t}\left(U_{t}U_{t}^{\top}-X^{\star}\right)\right)^{-1}\tilde{U}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\right\rVert$
$\displaystyle\leq\left\lVert
R_{t}\right\rVert\left\lVert\left(I-\bar{\eta}_{t}\left(U_{t}U_{t}^{\top}-X^{\star}\right)\right)^{-1}\right\rVert\left\lVert\tilde{U}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\right\rVert$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2\left\lVert
R_{t}\right\rVert\left\lVert\tilde{U}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\right\rVert$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}6\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert\tilde{U}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\right\rVert,$

where in (a), we used the fact that $\left\lVert
U_{t}U_{t}^{\top}-X^{\star}\right\rVert\lesssim\sigma_{1}$ due to our
assumptions on $\left\lVert S_{t}S_{t}^{\top}\right\rVert$ and $\left\lVert
E_{t}E_{t}^{\top}\right\rVert$, and our choice of $\eta$. Moreover, (b)
follows from Lemma 22. Now, note that

$\displaystyle\tilde{U}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}$
$\displaystyle=V\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}+V_{\perp}\tilde{E}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}$
(93)
$\displaystyle=V+V_{\perp}\tilde{E}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}.$

Therefore, we have

$\displaystyle\left\lVert\tilde{U}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\right\rVert\leq
1+\left\lVert\tilde{E}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\right\rVert.$

In order to provide an upper bound for $\left\lVert\Xi\right\rVert$, it
suffices to bound
$\left\lVert\tilde{E}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\right\rVert$.
To this goal, first we present the following technical lemma, the proof of
which can be found in Appendix F.2.

######  Lemma 23.

The following statements hold:

  * -

$\frac{1}{2}\leq\left\lVert
S_{t}S_{t}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\right\rVert\leq
2$ and $\frac{1}{3}\leq\left\lVert
S_{t}S_{t}^{\top}\left({S}_{t+1}{S}_{t+1}^{\top}\right)^{-1}\right\rVert\leq
3$;

  * -

$\left\lVert\tilde{E}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\right\rVert\leq
3\left\lVert
E_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}\right\rVert$.

The second statement of the above lemma connects
$\left\lVert\tilde{E}_{t+1}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}\right\rVert$
to $\left\lVert
E_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}\right\rVert$ which,
according to our assumption, is upper bounded by $1/3$. This upper bound,
together with (92) implies that

$\left\lVert\Xi\right\rVert\leq
12\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}.$

On the other hand, applying the relative perturbation bound to $M$ and
$\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}$ implies that

$\displaystyle\left|\lambda_{\min}(M)-\lambda_{\min}(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top})\right|\leq$
$\displaystyle\lambda_{\min}(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top})\left\lVert
I-(I+\Xi)(I+\Xi)^{\top}\right\rVert$ $\displaystyle\leq$ $\displaystyle
3\left\lVert\Xi\right\rVert\lambda_{\min}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)$
$\displaystyle\leq$ $\displaystyle
36\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\lambda_{\min}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right).$

This in turn implies that

$\displaystyle\lambda_{\min}({S}_{t+1}{S}_{t+1}^{\top})$
$\displaystyle\geq\lambda_{\min}(M)$
$\displaystyle\geq(1-36\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F})\lambda_{\min}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)$
$\displaystyle\geq\left(\left(1+\bar{\eta}_{t}\sigma_{r}\right)^{2}-2\bar{\eta}_{t}\left\lVert
E_{t}E_{t}^{\top}\right\rVert-72\bar{\eta}_{t}\delta\left\lVert
U_{t}U_{t}^{\top}-X^{\star}\right\rVert_{F}\right)\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)$
$\displaystyle-2\bar{\eta}_{t}\left(1+\bar{\eta}_{t}\sigma_{r}\right)\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)^{2},$

which completes the proof.$\hfill\square$

###  D.3 Proof of Proposition 5

#### Bounding $\left\lVert\Sigma-S_{t+1}S_{t+1}^{\top}\right\rVert$:

Recall that $S_{t+1}=\tilde{S}_{t+1}+V^{\top}R_{t}U_{t}$. Therefore, we have

$\displaystyle\Sigma-
S_{t+1}S_{t+1}^{\top}=\Sigma-\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\underbrace{-V^{\top}R_{t}U_{t}\tilde{S}_{t+1}^{\top}-\tilde{S}_{t+1}U_{t}^{\top}R_{t}^{\top}V-V^{\top}R_{t}U_{t}U_{t}^{\top}R_{t}^{\top}V}_{\text{deviation}}.$
(94)

The main idea behind our proof is to first control the norm of the deviation
term, and then invoke Proposition 3 for
$\Sigma-\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}$. One can write

$\displaystyle\left\lVert
V^{\top}R_{t}U_{t}\tilde{S}_{t+1}^{\top}\right\rVert\leq\left\lVert
R_{t}\right\rVert\left\lVert\tilde{S}_{t+1}U_{t}^{\top}\right\rVert\leq
3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert\tilde{S}_{t+1}U_{t}^{\top}\right\rVert,$

where in the last inequality, we used Lemma 22. Moreover,
$\tilde{S}_{t+1}U_{t}^{\top}$ can be rewritten as

$\displaystyle\tilde{S}_{t+1}U_{t}^{\top}$
$\displaystyle=\left(\left(I-\bar{\eta}_{t}\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}+S_{t}E_{t}^{\top}E_{t}\right)\right)\left(S^{\top}V^{\top}+E^{\top}V_{\perp}^{\top}\right)$
$\displaystyle=\left(I-\bar{\eta}_{t}\left(S_{t}S_{t}^{\top}-\Sigma\right)\right)S_{t}S_{t}^{\top}V^{\top}+\left(I-\bar{\eta}_{t}\left(S_{t}S_{t}^{\top}-\Sigma\right)\right)S_{t}E_{t}^{\top}V_{\perp}^{\top}$
$\displaystyle+S_{t}E_{t}^{\top}E_{t}S_{t}^{\top}V^{\top}+S_{t}E_{t}^{\top}E_{t}E_{t}^{\top}V_{\perp}^{\top}.$

Note that $\left\lVert
I-\bar{\eta}_{t}\left(S_{t}S_{t}^{\top}-\Sigma\right)\right\rVert\leq 2$ due
to our choice of $\eta$ and our assumption on $S_{t}S_{t}^{\top}$. Therefore,
we have

$\displaystyle\left\lVert\tilde{S}_{t+1}U_{t}^{\top}\right\rVert$
$\displaystyle\leq 2\left\lVert S_{t}S_{t}^{\top}\right\rVert+2\left\lVert
S_{t}E_{t}^{\top}\right\rVert+\left\lVert
S_{t}E_{t}^{\top}\right\rVert^{2}+\left\lVert
S_{t}E_{t}^{\top}\right\rVert\left\lVert E_{t}\right\rVert^{2}\leq
6\sigma_{1},$ (95)

where we used our assumptions on $\left\lVert S_{t}S_{t}^{\top}\right\rVert$
and $\left\lVert E_{t}E_{t}^{\top}\right\rVert$. Combining the above two
inequalities leads to

$\left\lVert\tilde{S}_{t+1}U_{t}^{\top}R_{t}^{\top}V\right\rVert=\left\lVert
V^{\top}R_{t}U_{t}\tilde{S}_{t+1}^{\top}\right\rVert\leq
18\bar{\eta}_{t}\delta\sigma_{1}\left\lVert\Delta_{t}\right\rVert_{F}.$ (96)

Using a similar technique, we have

$\left\lVert V^{\top}R_{t}U_{t}U_{t}^{\top}R_{t}^{\top}V\right\rVert\leq
9\bar{\eta}_{t}^{2}\delta^{2}\sigma_{1}\left\lVert\Delta_{t}\right\rVert_{F}^{2}\leq\bar{\eta}_{t}\delta\sigma_{1}\left\lVert\Delta_{t}\right\rVert_{F},$
(97)

where we used the assumed upper bounds on $\eta$ and $\delta$, and the fact
that $\left\lVert E_{t}E_{t}^{\top}\right\rVert\leq\sigma_{1}$, $\left\lVert
S_{t}S_{t}^{\top}\right\rVert\leq 1.01\sigma_{1}$, and $\left\lVert
E_{t}E_{t}^{\top}\right\rVert_{F}\leq\sqrt{r}\sigma_{1}$, which in turn
implies $\left\lVert\Delta_{t}\right\rVert_{F}\lesssim\sqrt{r}\sigma_{1}$ due
to Lemma 3. Moreover, we have already shown in Proposition 3 that

$\left\lVert\Sigma-\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right\rVert\leq\left(1-\bar{\eta}_{t}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\right)\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert+5\bar{\eta}_{t}\left\lVert
S_{t}E_{t}^{\top}\right\rVert^{2}.$

Hence, combining the above inequalities leads to

$\displaystyle\left\lVert\Sigma-S_{t+1}S_{t+1}^{\top}\right\rVert$
$\displaystyle\leq\left(1-\bar{\eta}_{t}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\right)\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert+5\bar{\eta}_{t}\left\lVert
S_{t}E_{t}^{\top}\right\rVert^{2}+37\bar{\eta}_{t}\delta\sigma_{1}\left\lVert\Delta_{t}\right\rVert_{F}.$

#### Bounding $\left\lVert S_{t+1}E_{t+1}^{\top}\right\rVert$:

First, note that

$\displaystyle S_{t+1}E_{t+1}^{\top}$
$\displaystyle=\tilde{S}_{t+1}\tilde{E}_{t+1}^{\top}+\underbrace{V^{\top}R_{t}U_{t}\tilde{E}_{t+1}^{\top}+\tilde{S}_{t+1}U_{t}^{\top}R_{t}^{\top}V_{\perp}+V^{\top}R_{t}U_{t}U_{t}^{\top}R_{t}^{\top}V_{\perp}}_{\text{deviation}}.$

Similar to the signal term, the main idea behind our proof is to first control
the norm of the deviation term, and then invoke Proposition 3 for
$\tilde{S}_{t+1}\tilde{E}_{t+1}^{\top}$. We first provide an upper bound for
$\left\lVert V^{\top}R_{t}U_{t}\tilde{E}_{t+1}^{\top}\right\rVert$

$\left\lVert
V^{\top}R_{t}U_{t}\tilde{E}_{t+1}^{\top}\right\rVert\leq\left\lVert
R_{t}\right\rVert\left\lVert U_{t}\tilde{E}_{t+1}^{\top}\right\rVert\leq
3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert
U_{t}\tilde{E}_{t+1}^{\top}\right\rVert.$

To bound $\left\lVert U_{t}\tilde{E}_{t+1}^{\top}\right\rVert$, one can write

$\displaystyle\left\lVert U_{t}\tilde{E}_{t+1}^{\top}\right\rVert$
$\displaystyle\leq\left\lVert U_{t}\right\rVert\left\lVert
E_{t}-\bar{\eta}_{t}S_{t}^{\top}S_{t}E_{t}^{\top}-\bar{\eta}_{t}E_{t}E_{t}^{\top}E_{t}\right\rVert$
$\displaystyle\leq 2\left(\left\lVert S_{t}\right\rVert+\left\lVert
E_{t}\right\rVert\right)\left\lVert E_{t}\right\rVert$ $\displaystyle\leq
5{\sigma_{1}},$

where we used the assumption $\left\lVert S_{t}\right\rVert\leq
1.01\sqrt{\sigma_{1}}$ and $\left\lVert
E_{t}\right\rVert\leq\sqrt{\sigma_{1}}$. Similar to (97), we have

$\displaystyle\left\lVert\tilde{S}_{t+1}U_{t}^{\top}R_{t}^{\top}V_{\perp}\right\rVert$
$\displaystyle\leq\left\lVert\tilde{S}_{t+1}U_{t}^{\top}\right\rVert\left\lVert
R_{t}\right\rVert$ $\displaystyle\leq\left\lVert
S_{t}-\bar{\eta}_{t}\left(\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}+S_{t}E_{t}^{\top}E_{t}\right)\right\rVert\left\lVert
R_{t}\right\rVert$ $\displaystyle\leq
6\bar{\eta}_{t}\delta\sqrt{\sigma_{1}}\left\lVert\Delta_{t}\right\rVert_{F},$

and

$\left\lVert
V^{\top}R_{t}U_{t}U_{t}^{\top}R_{t}^{\top}V_{\perp}\right\rVert\leq\left\lVert
U_{t}U_{t}^{\top}\right\rVert\left\lVert R_{t}\right\rVert^{2}\leq
10\sigma_{1}\bar{\eta}_{t}^{2}\delta^{2}\left\lVert\Delta_{t}\right\rVert_{F}^{2}\leq\bar{\eta}_{t}\delta\sigma_{1}\left\lVert\Delta_{t}\right\rVert_{F}.$

Moreover, we have already shown in Proposition 3 that

$\left\lVert\tilde{S}_{t+1}\tilde{E}_{t+1}^{\top}\right\rVert\leq\left(1-\bar{\eta}_{t}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)+2\bar{\eta}_{t}\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert+2\bar{\eta}_{t}\left\lVert
E_{t}E_{t}\right\rVert\right)\left\lVert S_{t}E_{t}^{\top}\right\rVert.$ (98)

Combining the above inequalities leads to

$\displaystyle\left\lVert S_{t+1}E_{t+1}^{\top}\right\rVert$
$\displaystyle\leq\left(1-\bar{\eta}_{t}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)+2\bar{\eta}_{t}\left\lVert\Sigma-
S_{t}S_{t}^{\top}\right\rVert+2\bar{\eta}_{t}\left\lVert
E_{t}E_{t}\right\rVert\right)\left\lVert
S_{t}E_{t}^{\top}\right\rVert+22\bar{\eta}_{t}\delta\sigma_{1}\left\lVert\Delta_{t}\right\rVert_{F}.$

#### Bounding $\left\lVert S_{t+1}S_{t+1}^{\top}\right\rVert$:

First, note that

$S_{t+1}S_{t+1}^{\top}=\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}+\underbrace{V^{\top}R_{t}U_{t}S_{t+1}^{\top}+S_{t+1}U_{t}^{\top}R_{t}^{\top}V+V^{\top}R_{t}U_{t}U_{t}^{\top}R_{t}^{\top}V}_{\text{deviation}}.$

Similar to our previous arguments, we will provide an upper bound on the
deviation term, and then resort to Proposition 3 to provide an upper bound for
$\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}$. First, note that

$\displaystyle\left\lVert V^{\top}R_{t}U_{t}S_{t+1}^{\top}\right\rVert$
$\displaystyle\leq\left\lVert
V^{\top}R_{t}VS_{t}S_{t+1}^{\top}\right\rVert+\left\lVert
V^{\top}R_{t}V_{\perp}E_{t}S_{t+1}^{\top}\right\rVert$ $\displaystyle\leq
3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left(\left\lVert
S_{t}S_{t+1}^{\top}\right\rVert+\left\lVert
E_{t}S_{t+1}^{\top}\right\rVert\right),$ (99)

where we used Lemma 22 in the last inequality. On the other hand

$\displaystyle\left\lVert S_{t}S_{t+1}^{\top}\right\rVert$
$\displaystyle=\left\lVert
S_{t}\left(S_{t}^{\top}-\bar{\eta}_{t}\left(S_{t}^{\top}\left(S_{t}S_{t}^{\top}-\Sigma\right)+E_{t}^{\top}E_{t}S_{t}^{\top}\right)+U_{t}^{\top}R_{t}^{\top}V\right)\right\rVert$
$\displaystyle\leq\left\lVert
S_{t}S_{t}^{\top}\right\rVert\left(1+\bar{\eta}_{t}\left\lVert
S_{t}S_{t}^{\top}-\Sigma\right\rVert+\bar{\eta}_{t}\left\lVert
E_{t}E_{t}^{\top}\right\rVert\right)+\left\lVert
S_{t}U_{t}^{\top}R_{t}^{\top}V\right\rVert$ $\displaystyle\leq 2\left\lVert
S_{t}S_{t}^{\top}\right\rVert+\left\lVert
S_{t}S_{t}^{\top}V^{\top}R_{t}^{\top}V\right\rVert+\left\lVert
S_{t}E_{t}^{\top}V_{\perp}^{\top}R_{t}^{\top}V\right\rVert$ $\displaystyle\leq
3\left\lVert
S_{t}S_{t}^{\top}\right\rVert+3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert
S_{t}E_{t}^{\top}\right\rVert.$

Similarly, we have

$\left\lVert E_{t}S_{t+1}^{\top}\right\rVert\leq 3\left\lVert
E_{t}S_{t}^{\top}\right\rVert+3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert
E_{t}E_{t}^{\top}\right\rVert.$

The above two inequalities combined with (99) results in

$\displaystyle 2\left\lVert V^{\top}R_{t}U_{t}S_{t+1}^{\top}\right\rVert\leq
216\bar{\eta}_{t}\sigma_{1}^{2}\sqrt{r}\delta.$

which follows from our assumption on $\left\lVert S_{t}\right\rVert$,
$\left\lVert E_{t}\right\rVert$ and $\delta$. Similarly, one can show that

$\displaystyle\left\lVert
V^{\top}R_{t}U_{t}U_{t}^{\top}R_{t}^{\top}V\right\rVert\leq\bar{\eta}_{t}\sigma_{1}^{2}\sqrt{r}\delta.$

Therefore, the norm of the deviation term is upper bounded by
$217\bar{\eta}_{t}\sigma_{1}^{2}\sqrt{r}\delta$. Moreover, Proposition 3
implies

$\displaystyle\left\lVert\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right\rVert\leq\left(1+2\sigma_{1}\bar{\eta}_{t}+4\sigma_{1}^{2}\bar{\eta}_{t}^{2}\right)\left\lVert
S_{t}S_{t}^{\top}\right\rVert-2\bar{\eta}_{t}\left\lVert
S_{t}S_{t}^{\top}\right\rVert^{2}+\bar{\eta}_{t}^{2}\left\lVert
S_{t}S_{t}^{\top}\right\rVert^{3},$

which in turn leads to

$\displaystyle\left\lVert
S_{t+1}S_{t+1}^{\top}\right\rVert\leq\left(1+2\sigma_{1}\bar{\eta}_{t}+4\sigma_{1}^{2}\bar{\eta}_{t}^{2}\right)\left\lVert
S_{t}S_{t}^{\top}\right\rVert-2\bar{\eta}_{t}\left\lVert
S_{t}S_{t}^{\top}\right\rVert^{2}+\bar{\eta}_{t}^{2}\left\lVert
S_{t}S_{t}^{\top}\right\rVert^{3}+217\bar{\eta}_{t}\sigma_{1}^{2}\sqrt{r}\delta.$

The rest of the proof is analogous to that of Proposition 3, and hence,
omitted for brevity.$\hfill\square$

###  D.4 Proof of Proposition 6

#### Bounding $\left\lVert G_{t+1}\right\rVert$:

To provide an upper bound for $\left\lVert G_{t+1}\right\rVert=\left\lVert
E_{t+1}\mathsf{P}_{S_{t+1}}^{\perp}\right\rVert$ in terms of $\left\lVert
G_{t}\right\rVert=\left\lVert E_{t}\mathsf{P}_{S_{t}}^{\perp}\right\rVert$, it
is crucial to characterize the relationship between the projection operators
$\mathsf{P}_{S_{t+1}}^{\perp}$ and $\mathsf{P}_{S_{t}}^{\perp}$. To this goal,
we decompose $\mathsf{P}_{S_{t+1}}^{\perp}$ as follows

$\displaystyle\mathsf{P}_{S_{t+1}}^{\perp}=\mathsf{P}_{S_{t}}\mathsf{P}_{S_{t+1}}^{\perp}+\mathsf{P}_{S_{t}}^{\perp}\mathsf{P}_{S_{t+1}}^{\perp}.$

Based on the above decomposition, $G_{t+1}$ can be written as

$\displaystyle
G_{t+1}=\underbrace{E_{t+1}\mathsf{P}_{S_{t}}\mathsf{P}_{S_{t+1}}^{\perp}}_{(A)}+\underbrace{E_{t+1}\mathsf{P}_{S_{t}}^{\perp}\mathsf{P}_{S_{t+1}}^{\perp}}_{(B)}.$

We first study $(A)$. Let $M_{t}D_{t}N_{t}^{\top}$ be the singular value
decomposition of $S_{t}$, where $M_{t}\in\mathbb{R}^{r\times r}$ and
$N_{t}\in\mathbb{R}^{r^{\prime}\times r}$ are (row) orthonormal matrices, and
$D_{t}\in\mathbb{R}^{r\times r}$ is a diagonal matrix collecting the singular
values of $S_{t}$. Based on this definition, we have
$\mathsf{P}_{S_{t}}=N_{t}N_{t}^{\top}$. On the other hand, we have
$S_{t+1}\mathsf{P}_{S_{t}}\mathsf{P}_{S_{t+1}}^{\perp}=-S_{t+1}\mathsf{P}_{S_{t}}^{\perp}\mathsf{P}_{S_{t+1}}^{\perp}$,
which is equivalent to

$S_{t+1}N_{t}N_{t}^{\top}\mathsf{P}_{S_{t+1}}^{\perp}=-S_{t+1}\mathsf{P}_{S_{t}}^{\perp}\mathsf{P}_{S_{t+1}}^{\perp}.$
(100)

Our next technical lemma shows that $S_{t+1}N_{t}$ is invertible.

######  Lemma 24.

The matrix $S_{t+1}N_{t}$ is invertible.

The proof of this lemma can be found in Appendix F.3. Lemma (24) combined with
(100) leads to

$N_{t}^{\top}\mathsf{P}_{S_{t+1}}^{\perp}=-\left(S_{t+1}N_{t}\right)^{-1}S_{t+1}\mathsf{P}_{S_{t}}^{\perp}\mathsf{P}_{S_{t+1}}^{\perp}.$

Therefore, we have

$\displaystyle(A)=$ $\displaystyle
E_{t+1}\mathsf{P}_{S_{t}}\mathsf{P}_{S_{t+1}}^{\perp}$ $\displaystyle=$
$\displaystyle E_{t+1}N_{t}N_{t}^{\top}\mathsf{P}_{S_{t+1}}^{\perp}$
$\displaystyle=$ $\displaystyle-
E_{t+1}N_{t}\left(S_{t+1}N_{t}\right)^{-1}S_{t+1}\mathsf{P}_{S_{t}}^{\perp}\mathsf{P}_{S_{t+1}}^{\perp}$
$\displaystyle=$
$\displaystyle\underbrace{-E_{t+1}N_{t}\left(S_{t+1}N_{t}\right)^{-1}\tilde{S}_{t+1}\mathsf{P}_{S_{t}}^{\perp}\mathsf{P}_{S_{t+1}}^{\perp}}_{(A_{1})}-\underbrace{E_{t+1}N_{t}\left(S_{t+1}N_{t}\right)^{-1}\left(S_{t+1}-\tilde{S}_{t+1}\right)\mathsf{P}_{S_{t}}^{\perp}\mathsf{P}_{S_{t+1}}^{\perp}}_{(A_{2})}.$

We first control $(A_{1})$. Observe that

$\tilde{S}_{t+1}\mathsf{P}^{\perp}_{S_{t}}=\left(S_{t}-\bar{\eta}_{t}\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}-\bar{\eta}_{t}S_{t}E_{t}^{\top}E_{t}\right)\mathsf{P}^{\perp}_{S_{t}}=-\bar{\eta}_{t}S_{t}E_{t}^{\top}G_{t}.$

Therefore, we have

$\displaystyle(A_{1})$
$\displaystyle=\bar{\eta}_{t}E_{t+1}N_{t}\left(S_{t+1}N_{t}\right)^{-1}S_{t}E_{t}^{\top}G_{t}\mathsf{P}_{S_{t+1}}^{\perp}.$
(101)

On the other hand, note that
$E_{t+1}=E_{t}-\bar{\eta}_{t}E_{t}\left(S_{t}^{\top}S_{t}+E_{t}^{\top}E_{t}\right)+V_{\perp}^{\top}R_{t}U_{t}$.
Hence, we have

$(B)=\left(I-\bar{\eta}_{t}E_{t}E_{t}^{\top}\right)G_{t}\mathsf{P}_{S_{t+1}}^{\perp}+V_{\perp}^{\top}R_{t}V_{\perp}G_{t}\mathsf{P}_{S_{t+1}}^{\perp}.$
(102)

Combining equations (101) and (102), we obtain

$G_{t+1}=\left(I-\bar{\eta}_{t}E_{t}E_{t}^{\top}+\bar{\eta}_{t}E_{t+1}N_{t}\left(S_{t+1}N_{t}\right)^{-1}S_{t}E_{t}^{\top}\right)G_{t}\mathsf{P}_{S_{t+1}}^{\perp}+V_{\perp}^{\top}R_{t}V_{\perp}G_{t}\mathsf{P}_{S_{t+1}}^{\perp}+(A_{2}),$

which results in

$\displaystyle\left\lVert G_{t+1}\right\rVert$
$\displaystyle\leq\underbrace{\left\lVert
I-\bar{\eta}_{t}E_{t}E_{t}^{\top}+\bar{\eta}_{t}E_{t+1}N_{t}\left(S_{t+1}N_{t}\right)^{-1}S_{t}E_{t}^{\top}\right\rVert}_{(C)}\left\lVert
G_{t}\right\rVert+\left\lVert R_{t}\right\rVert\left\lVert
G_{t}\right\rVert+\left\lVert(A_{2})\right\rVert.$

Therefore, it remains to control the terms $\left\lVert(C)\right\rVert$ and
$\left\lVert(A_{2})\right\rVert$. First, we provide an upper bound on
$\left\lVert(C)\right\rVert$. Define
$S_{t+1}N_{t}=\left(I+\Xi\right)S_{t}N_{t}$, where
$\Xi=S_{t+1}N_{t}\left(S_{t}N_{t}\right)^{-1}-I$ (note that
$S_{t}N_{t}=M_{t}D_{t}$ which implies that $S_{t}N_{t}$ is invertible). Hence,
we have

$\displaystyle\left\lVert(C)\right\rVert$
$\displaystyle\leq\underbrace{\left\lVert
I-\bar{\eta}_{t}E_{t}E_{t}^{\top}+\bar{\eta}_{t}E_{t+1}N_{t}\left(S_{t}N_{t}\right)^{-1}S_{t}E_{t}^{\top}\right\rVert}_{(C_{1})}+\underbrace{\bar{\eta}_{t}\left\lVert
E_{t+1}N_{t}\left(S_{t}N_{t}\right)^{-1}\right\rVert\left\lVert(I+\Xi)^{-1}-I\right\rVert\left\lVert
S_{t}E_{t}^{\top}\right\rVert}_{(C_{2})}.$ (103)

It is shown in the proof of Lemma 24 that $\left\lVert\Xi\right\rVert\leq
3\bar{\eta}_{t}\left\lVert\Delta_{t}\right\rVert\leq 1/2$. Therefore, one can
write
$\left\lVert(I+\Xi)^{-1}-I\right\rVert\leq\left\lVert\Xi\right\rVert\left\lVert\left(I+\Xi\right)^{-1}\right\rVert\leq
6\bar{\eta}_{t}\left\lVert\Delta_{t}\right\rVert$. To provide an upper bound
for $\left\lVert E_{t+1}N_{t}\left(S_{t}N_{t}\right)^{-1}\right\rVert$, one
can write

$\displaystyle E_{t+1}N_{t}\left(S_{t}N_{t}\right)^{-1}$
$\displaystyle=E_{t+1}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}$
$\displaystyle=\left(E_{t}-\bar{\eta}_{t}E_{t}\left(S_{t}^{\top}S_{t}+E_{t}^{\top}E_{t}\right)+V_{\perp}^{\top}R_{t}U_{t}\right)S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}$
$\displaystyle=\left(I-\bar{\eta}_{t}E_{t}E_{t}^{\top}\right)H_{t}-\bar{\eta}_{t}E_{t}S_{t}^{\top}+V_{\perp}^{\top}R_{t}U_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}$
$\displaystyle=\left(I-\bar{\eta}_{t}E_{t}E_{t}^{\top}\right)H_{t}-\bar{\eta}_{t}E_{t}S_{t}^{\top}+V_{\perp}^{\top}R_{t}V+V_{\perp}^{\top}R_{t}V_{\perp}H_{t},$

where $H_{t}=E_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}$. Therefore,
we have

$\displaystyle\left\lVert
E_{t+1}N_{t}\left(S_{t}N_{t}\right)^{-1}\right\rVert$
$\displaystyle\leq\left\lVert H_{t}\right\rVert+\bar{\eta}_{t}\left\lVert
E_{t}S_{t}^{\top}\right\rVert+\left\lVert R_{t}\right\rVert(1+\left\lVert
H_{t}\right\rVert)$ $\displaystyle\leq\left\lVert
H_{t}\right\rVert+\bar{\eta}_{t}\left\lVert
E_{t}S_{t}^{\top}\right\rVert+4\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}.$

Hence, we obtain

$\displaystyle\left\lVert C_{2}\right\rVert\leq
6\bar{\eta}_{t}^{2}\left\lVert\Delta_{t}\right\rVert\left(\left\lVert
H_{t}\right\rVert+\bar{\eta}_{t}\left\lVert
E_{t}S_{t}^{\top}\right\rVert+\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\right)\left\lVert
E_{t}S_{t}^{\top}\right\rVert.$

To control $\left\lVert(C_{1})\right\rVert$, we use triangle inequality to
arrive at the following decomposition

$\displaystyle(C_{1})$ $\displaystyle\leq\underbrace{\left\lVert
I-\bar{\eta}_{t}E_{t}E_{t}^{\top}+\bar{\eta}_{t}E_{t}N_{t}\left(S_{t}N_{t}\right)^{-1}S_{t}E_{t}^{\top}\right\rVert}_{(C_{11})}+\underbrace{\bar{\eta}_{t}^{2}\left\lVert
S_{t}S_{t}^{\top}E_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}S_{t}E_{t}^{\top}\right\rVert}_{(C_{12})}$
$\displaystyle+\underbrace{\bar{\eta}_{t}^{2}\left\lVert
E_{t}E_{t}^{\top}E_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}S_{t}E_{t}^{\top}\right\rVert}_{(C_{13})}+\underbrace{\bar{\eta}_{t}\left\lVert
R_{t}U_{t}N_{t}\left(S_{t}N_{t}\right)^{-1}S_{t}E_{t}^{\top}\right\rVert}_{(C_{14})}.$

It is easy to see that $\left\lVert(C_{11})\right\rVert=\left\lVert
I-\bar{\eta}_{t}G_{t}G_{t}^{\top}\right\rVert\leq 1$, due to the assumed upper
bound on $\bar{\eta}_{t}$ and $\left\lVert E_{t}E_{t}^{\top}\right\rVert$.
Moreover, one can verify that
$\left\lVert(C_{12})\right\rVert\leq\bar{\eta}_{t}^{2}\left\lVert
E_{t}S_{t}^{\top}\right\rVert^{2}$,
$\left\lVert(C_{13})\right\rVert\leq\bar{\eta}_{t}^{2}\left\lVert
E_{t}\right\rVert^{4}$, and $\left\lVert(C_{14})\right\rVert\leq
3\bar{\eta}_{t}^{2}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left(1+\left\lVert
H_{t}\right\rVert\right)\left\lVert S_{t}E_{t}^{\top}\right\rVert\leq
6\bar{\eta}_{t}^{2}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert
S_{t}E_{t}^{\top}\right\rVert$. Combining the derived upper bounds for
$\left\lVert C_{1}\right\rVert$ and $\left\lVert C_{2}\right\rVert$, we have

$(C)\leq 1+\bar{\eta}_{t}^{2}\left(2\left\lVert
E_{t}S_{t}^{\top}\right\rVert^{2}+\left\lVert
E_{t}\right\rVert^{4}+7\delta\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert
E_{t}S_{t}^{\top}\right\rVert+6\left\lVert
H_{t}\right\rVert\left\lVert\Delta_{t}\right\rVert\left\lVert
E_{t}S_{t}^{\top}\right\rVert\right).$

To complete the proof, it remains to provide an upper bound for
$\left\lVert(A_{2})\right\rVert$. First, note that
$\left(S_{t+1}-\tilde{S}_{t+1}\right)\mathsf{P}_{S_{t}}^{\perp}=V^{\top}R_{t}V_{\perp}G_{t}$.
Given this equality, one can write

$\displaystyle\left\lVert A_{2}\right\rVert\leq$ $\displaystyle\left\lVert
E_{t+1}N_{t}\left(S_{t+1}N_{t}\right)^{-1}V^{\top}R_{t}V_{\perp}G_{t}\mathsf{P}_{S_{t+1}}^{\perp}\right\rVert$
$\displaystyle\leq$ $\displaystyle\left\lVert
E_{t+1}N_{t}\left(S_{t+1}N_{t}\right)^{-1}\right\rVert\left\lVert
R_{t}\right\rVert\left\lVert G_{t}\right\rVert$ $\displaystyle\leq$
$\displaystyle 3\bar{\eta}_{t}\delta\left\lVert
E_{t+1}N_{t}\left(S_{t+1}N_{t}\right)^{-1}\right\rVert\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert
G_{t}\right\rVert.$

Therefore, it suffices to provide an upper bound for $\left\lVert
E_{t+1}N_{t}\left(S_{t+1}N_{t}\right)^{-1}\right\rVert$:

$\displaystyle\left\lVert
E_{t+1}N_{t}\left(S_{t+1}N_{t}\right)^{-1}\right\rVert$
$\displaystyle\leq\left\lVert
E_{t+1}N_{t}\left(S_{t}N_{t}\right)^{-1}\right\rVert\left\lVert
S_{t}N_{t}\left(S_{t+1}N_{t}\right)^{-1}\right\rVert$
$\displaystyle\leq\left\lVert
E_{t+1}N_{t}\left(S_{t}N_{t}\right)^{-1}\right\rVert\left\lVert(I+\Xi)^{-1}\right\rVert$
$\displaystyle\leq 2\left\lVert
E_{t+1}N_{t}\left(S_{t}N_{t}\right)^{-1}\right\rVert$ $\displaystyle\leq 2.$

Combining the above inequalities leads to

$\displaystyle\left\lVert(A_{2})\right\rVert$ $\displaystyle\leq
6\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert
G_{t}\right\rVert.$

Finally, combining the derived upper bounds for $(C)$ and $(A_{2})$ gives rise
to the following inequalities

$\displaystyle\left\lVert G_{t+1}\right\rVert$
$\displaystyle\leq\left(1+2\bar{\eta}_{t}^{2}\left\lVert
E_{t}S_{t}^{\top}\right\rVert^{2}+\bar{\eta}_{t}^{2}\left\lVert
E_{t}\right\rVert^{4}+6\bar{\eta}_{t}^{2}\left\lVert
H_{t}\right\rVert\left\lVert\Delta_{t}\right\rVert\left\lVert
E_{t}S_{t}^{\top}\right\rVert+7\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\right)\left\lVert
G_{t}\right\rVert$ $\displaystyle\leq\left(1+2\bar{\eta}_{t}^{2}\left\lVert
E_{t}S_{t}^{\top}\right\rVert^{2}+\bar{\eta}_{t}^{2}\left\lVert
E_{t}\right\rVert^{4}+2\bar{\eta}_{t}^{2}\left\lVert\Delta_{t}\right\rVert\left\lVert
E_{t}S_{t}^{\top}\right\rVert+7\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\right)\left\lVert
G_{t}\right\rVert.$

#### Bounding $\left\lVert F_{t+1}\right\rVert:$

Similar to the previous part, we use the decomposition
$\mathsf{P}_{S_{t+1}}=\mathsf{P}_{S_{t}}\mathsf{P}_{S_{t+1}}+\mathsf{P}_{S_{t}}^{\perp}\mathsf{P}_{S_{t+1}}$
to write

$\displaystyle
F_{t+1}=E_{t+1}\mathsf{P}_{S_{t+1}}=\underbrace{E_{t+1}\mathsf{P}_{S_{t}}\mathsf{P}_{S_{t+1}}}_{(A)}+\underbrace{E_{t+1}\mathsf{P}_{S_{t}}^{\perp}\mathsf{P}_{S_{t+1}}}_{(B)}.$

First, we provide an upper bound for $\left\lVert(B)\right\rVert$:

$\displaystyle\left\lVert{({B})}\right\rVert$ $\displaystyle=\left\lVert
E_{t+1}\mathsf{P}_{S_{t}}^{\perp}\left(\mathsf{P}_{S_{t+1}}-\mathsf{P}_{S_{t}}\right)\right\rVert$
$\displaystyle\leq\left\lVert
E_{t+1}\mathsf{P}_{S_{t}}^{\perp}\right\rVert\left\lVert\mathsf{P}_{S_{t+1}}-\mathsf{P}_{S_{t}}\right\rVert$
$\displaystyle=\left\lVert\left(I-\bar{\eta}_{t}E_{t}E_{t}^{\top}\right)G_{t}+V^{\top}_{\perp}R_{t}U_{t}\mathsf{P}_{S_{t}}^{\perp}\right\rVert\left\lVert\mathsf{P}_{S_{t+1}}-\mathsf{P}_{S_{t}}\right\rVert$
$\displaystyle\leq\left(\left\lVert G_{t}\right\rVert+\left\lVert
V^{\top}_{\perp}R_{t}V_{\perp}G_{t}\right\rVert\right)\left\lVert\mathsf{P}_{S_{t+1}}-\mathsf{P}_{S_{t}}\right\rVert$
$\displaystyle\leq\left(\left\lVert
G_{t}\right\rVert+3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert
G_{t}\right\rVert\right)\left\lVert\mathsf{P}_{S_{t+1}}-\mathsf{P}_{S_{t}}\right\rVert$
$\displaystyle\leq 2\left\lVert
G_{t}\right\rVert\left\lVert\mathsf{P}_{S_{t+1}}-\mathsf{P}_{S_{t}}\right\rVert.$
(104)

To control $\left\lVert\mathsf{P}_{S_{t+1}}-\mathsf{P}_{S_{t}}\right\rVert$,
we use the following technical lemma.

######  Lemma 25 (Theorem 2.4, Chen et al. [5]).

Let $A\in\mathbb{R}^{m\times n}$, and $B=A+E\in\mathbb{R}^{m\times n}$ have
the same rank. Then, we have

$\left\lVert\mathsf{P}_{A}-\mathsf{P}_{B}\right\rVert\leq\left\lVert
EA^{\dagger}\right\rVert\vee\left\lVert EB^{\dagger}\right\rVert.$

Due to Proposition 4 and our assumptions, we have
$\lambda_{\min}(S_{t+1}S_{t+1}^{\top})\geq\lambda_{\min}(S_{t}S_{t}^{\top})>0$,
and hence, both $S_{t+1}S_{t+1}^{\top}$ and $S_{t}S_{t}^{\top}$ are rank-$r$.
Invoking Lemma 25, we have

$\displaystyle\left\lVert\mathsf{P}_{S_{t+1}}-\mathsf{P}_{S_{t}}\right\rVert$
$\displaystyle\leq\left\lVert\left(S_{t+1}-S_{t}\right)S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}\right\rVert$
(105)
$\displaystyle=\left\lVert\left(-\bar{\eta}_{t}\left(\left(S_{t}S_{t}^{\top}-\Sigma\right)S_{t}+S_{t}E^{\top}_{t}E_{t}\right)+V^{\top}R_{t}U_{t}\right)S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}\right\rVert$
$\displaystyle\leq\bar{\eta}_{t}\left\lVert
S_{t}S_{t}^{\top}-\Sigma\right\rVert+\bar{\eta}_{t}\left\lVert
S_{t}E_{t}^{\top}\right\rVert\left\lVert H_{t}\right\rVert+\left\lVert
R_{t}\right\rVert\left(1+\left\lVert H_{t}\right\rVert\right)$
$\displaystyle\leq\bar{\eta}_{t}\left\lVert
S_{t}S_{t}^{\top}-\Sigma\right\rVert+\bar{\eta}_{t}\left\lVert
S_{t}E_{t}^{\top}\right\rVert+6\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}$
$\displaystyle\leq 3\bar{\eta}_{t}\left\lVert\Delta_{t}\right\rVert,$

where in the last inequality, we used the following auxiliary lemma.

######  Lemma 26.

If $\left\lVert\Delta_{t}\right\rVert\geq\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}$, then we have
$\left\lVert\Delta_{t}\right\rVert_{F}\leq
5\sqrt{r}\left\lVert\Delta_{t}\right\rVert$.

###### Proof.

Recall the signal-residual decomposition

$\Delta_{t}=V\left(S_{t}S_{t}^{\top}-\Sigma\right)V^{\top}+VS_{t}E_{t}^{\top}V_{\perp}^{\top}+V_{\perp}E_{t}S_{t}^{\top}V^{\top}+V_{\perp}F_{t}F_{t}^{\top}V_{\perp}^{\top}+V_{\perp}G_{t}G_{t}^{\top}V_{\perp}^{\top}.$

One can write

$\displaystyle\left\lVert\Delta_{t}\right\rVert_{F}$
$\displaystyle\leq\sqrt{r}\left(\left\lVert
S_{t}S_{t}^{\top}-\Sigma\right\rVert+2\left\lVert
S_{t}E_{t}^{\top}\right\rVert+\left\lVert
F_{t}F_{t}^{\top}\right\rVert\right)+\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}$
$\displaystyle=4\sqrt{r}\left\lVert\Delta_{t}\right\rVert+\left\lVert\Delta_{t}\right\rVert$
$\displaystyle\leq 5\sqrt{r}\left\lVert\Delta_{t}\right\rVert,$

which completes the proof. ∎

Combining (105) with (104) leads to

$\displaystyle\left\lVert(B)\right\rVert\leq
6\bar{\eta}_{t}\left\lVert\Delta_{t}\right\rVert\left\lVert
G_{t}\right\rVert.$

Next, we will provide an upper bound for $(A)$. One can write

$\displaystyle\left\lVert\left({A}\right)\right\rVert$
$\displaystyle\leq\left\lVert E_{t+1}\mathsf{P}_{S_{t}}\right\rVert$
$\displaystyle\leq\left\lVert\left(E_{t}-\bar{\eta}_{t}E_{t}\left(E_{t}^{\top}E_{t}+S^{\top}_{t}S_{t}\right)+V^{\top}_{\perp}R_{t}U_{t}\right)\mathsf{P}_{S_{t}}\right\rVert$
$\displaystyle\leq\left\lVert
F_{t}-\bar{\eta}_{t}E_{t}E_{t}^{\top}F_{t}-\bar{\eta}_{t}F_{t}S^{\top}_{t}S_{t}\right\rVert+\left\lVert
V^{\top}_{\perp}R_{t}U_{t}\mathsf{P}_{S_{t}}\right\rVert.$ (106)

The first term in the above inequality can be bounded as follows

$\displaystyle\left\lVert
F_{t}-\bar{\eta}_{t}E_{t}E_{t}^{\top}F_{t}-\bar{\eta}_{t}F_{t}S^{\top}_{t}S_{t}\right\rVert$
$\displaystyle\leq\left\lVert\left(0.5I-\bar{\eta}_{t}E_{t}E_{t}^{\top}\right)F_{t}\right\rVert+\left\lVert
F_{t}\left(0.5I-\bar{\eta}_{t}S^{\top}_{t}S_{t}\right)\right\rVert$
$\displaystyle\leq\left(\left\lVert
0.5I-\bar{\eta}_{t}E_{t}E_{t}^{\top}\right\rVert+\left\lVert
0.5I-\bar{\eta}_{t}S^{\top}_{t}S_{t}\right\rVert\right)\left\lVert
F_{t}\right\rVert$
$\displaystyle\leq\left(1-\bar{\eta}_{t}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)\right)\left\lVert
F_{t}\right\rVert.$

Moreover, we have

$\displaystyle\left\lVert
V^{\top}_{\perp}R_{t}U_{t}\mathsf{P}_{S_{t}}\right\rVert\leq\left\lVert
R_{t}\right\rVert\left(\left\lVert S_{t}\right\rVert+\left\lVert
F_{t}\right\rVert\right)\leq
3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left(\left\lVert
S_{t}\right\rVert+\left\lVert F_{t}\right\rVert\right).$

Therefore, we have

$\displaystyle\left\lVert\left({A}\right)\right\rVert\leq\left(1-\bar{\eta}_{t}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)+3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\right)\left\lVert
F_{t}\right\rVert+3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert
S_{t}\right\rVert.$

Finally, combining the derived upper bounds for $(A)$ and $(B)$ leads to

$\displaystyle\left\lVert F_{t+1}\right\rVert\leq$
$\displaystyle\left(1-\bar{\eta}_{t}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)+3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\right)\left\lVert
F_{t}\right\rVert+3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert
S_{t}\right\rVert+6\bar{\eta}_{t}\left\lVert\Delta_{t}\right\rVert\left\lVert
G_{t}\right\rVert,$

which completes the proof.$\hfill\square$

###  D.5 Proof of Lemma 6

Recall that $U_{0}=\alpha B$, where $BB^{\top}$ is the best rank-$r^{\prime}$
approximation of
$C\in\frac{1}{2m}\sum_{i=1}^{m}\mathrm{Sign}\left(y_{i}\right)\left({A_{i}+A_{i}^{\top}}\right)$.
Since $\mathrm{rank}(X^{\star})=r$, Sign-RIP implies

$\left\lVert C-\varphi(X^{\star})\frac{X^{\star}}{\left\lVert
X^{\star}\right\rVert_{F}}\right\rVert\leq\varphi(X^{\star})\delta.$

Note that $BB^{\top}$ is the best rank-$r^{\prime}$ approximation of $C$. We
have

$\displaystyle\left\lVert
BB^{\top}-\varphi(X^{\star})\frac{X^{\star}}{\left\lVert
X^{\star}\right\rVert_{F}}\right\rVert$ $\displaystyle\leq\left\lVert
BB^{\top}-C\right\rVert+\left\lVert
C-\varphi(X^{\star})\frac{X^{\star}}{\left\lVert
X^{\star}\right\rVert_{F}}\right\rVert$
$\displaystyle\leq\left|\lambda_{r^{\prime}+1}(C)\right|+\varphi(X^{\star})\delta$
$\displaystyle\leq\left\lVert C-\varphi(X^{\star})\frac{X^{\star}}{\left\lVert
X^{\star}\right\rVert_{F}}\right\rVert+\varphi(X^{\star})\delta$
$\displaystyle\leq 2\varphi(X^{\star})\delta.$

Therefore, based on the definition of $U_{0}$, we have

$\left\lVert
U_{0}U_{0}^{\top}-\alpha^{2}\varphi(X^{\star})\frac{X^{\star}}{\left\lVert
X^{\star}\right\rVert_{F}}\right\rVert\leq
2\alpha^{2}\varphi(X^{\star})\delta.$

Given this bound, one can write

$\displaystyle\left\lVert
S_{0}S_{0}^{\top}-\alpha^{2}\varphi(X^{\star})\frac{\Sigma}{\left\lVert
X^{\star}\right\rVert_{F}}\right\rVert$ $\displaystyle=\left\lVert
V^{\top}\left(U_{0}U_{0}^{\top}-\alpha^{2}\varphi(X^{\star})\frac{X^{\star}}{\left\lVert
X^{\star}\right\rVert_{F}}\right)V\right\rVert$ $\displaystyle\leq\left\lVert
U_{0}U_{0}^{\top}-\alpha^{2}\varphi(X^{\star})\frac{X^{\star}}{\left\lVert
X^{\star}\right\rVert_{F}}\right\rVert$ $\displaystyle\leq
2\alpha^{2}\varphi(X^{\star})\delta.$

Similarly, we have

$\displaystyle\left\lVert S_{0}E_{0}^{\top}\right\rVert$
$\displaystyle=\left\lVert
V^{\top}\left(U_{0}U_{0}^{\top}-\alpha^{2}\varphi(X^{\star})\frac{X^{\star}}{\left\lVert
X^{\star}\right\rVert_{F}}\right)V_{\perp}\right\rVert\leq
2\alpha^{2}\varphi(X^{\star})\delta,$ $\displaystyle\left\lVert
E_{0}E_{0}^{\top}\right\rVert$ $\displaystyle=\left\lVert
V_{\perp}^{\top}\left(U_{0}U_{0}^{\top}-\alpha^{2}\varphi(X^{\star})\frac{X^{\star}}{\left\lVert
X^{\star}\right\rVert_{F}}\right)V_{\perp}\right\rVert\leq
2\alpha^{2}\varphi(X^{\star})\delta.$

This completes the proof.$\hfill\square$

###  D.6 Proof of Lemma 7

We prove this lemma by induction on $t$. First, due to Lemma 6, it is easy to
verify that (45)-(48) hold for $t=0$. Now, suppose that (45)-(47) are
satisfied for $t<T_{end}$. Moreover, without loss of generality, we assume
that $\left\lVert\Delta_{t}\right\rVert_{F}\gtrsim
d\alpha^{2-\mathcal{O}(\sqrt{r}\kappa^{2}\delta)}$ for every $0\leq t\leq
T_{end}$; otherwise, the statement of the lemma holds. Together with the
induction hypothesis on $\left\lVert G_{t}\right\rVert$, this implies that
$\left\lVert\Delta_{t}\right\rVert_{F}\geq\zeta$, for $\zeta>0$ defined in
Propositions 4, 5, and 6.

#### Bounding $\left\lVert F_{t+1}\right\rVert$:

In order to apply Proposition 6, first we verify its assumptions. One can
write $\left\lVert E_{t}E_{t}^{\top}\right\rVert=\left\lVert
F_{t}\right\rVert^{2}+\left\lVert G_{t}\right\rVert^{2}$. Therefore, we have
$\left\lVert E_{t}E_{t}^{\top}\right\rVert\leq\sigma_{1}$, due to the
induction hypothesis on $\left\lVert F_{t}\right\rVert$ and $\left\lVert
G_{t}\right\rVert$. On the other hand, $\left\lVert
S_{t}S_{t}^{\top}\right\rVert\leq 1.01\sigma_{1}$ and $\left\lVert
E_{t}S_{t}^{\top}(S_{t}S_{t}^{\top})^{-1}\right\rVert\leq 1/3$ due to our
induction hypothesis. It remains to show that
$(4r,\delta,\varepsilon,\mathcal{S})$-Sign-RIP with
$\varepsilon\geq\sqrt{d}\bar{\varphi}\alpha$ implies
$(4r,\delta,\sqrt{d}\left\lVert G_{t}\right\rVert^{2},\mathcal{S})$-Sign-RIP.
To show this, first note that $(4r,\delta,\varepsilon_{1},\mathcal{S})$-Sign-
RIP implies $(4r,\delta,\varepsilon_{2},\mathcal{S})$-Sign-RIP, for any
$\varepsilon_{2}\leq\varepsilon_{1}$. Using this fact, it suffices to show
that $\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}\leq\sqrt{d}\bar{\varphi}\alpha\lesssim\varepsilon$,
which is immediate due to our induction hypothesis on $\left\lVert
G_{t}\right\rVert$, and our choice of $\delta$. Therefore, Proposition 6 holds
and we have

$\displaystyle\left\lVert F_{t+1}\right\rVert\leq$
$\displaystyle\left(1-\bar{\eta}_{t}\lambda_{\min}\left(S_{t}S_{t}^{\top}\right)+3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\right)\left\lVert
F_{t}\right\rVert+3\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\left\lVert
S_{t}\right\rVert+6\bar{\eta}_{t}\left\lVert\Delta_{t}\right\rVert\left\lVert
G_{t}\right\rVert.$ (107)

Due to our induction hypothesis, (107) can be simplified as

$\displaystyle\left\lVert F_{t+1}\right\rVert\leq$
$\displaystyle\left(1+75\sqrt{r}\sigma_{1}\bar{\eta}_{t}\delta\right)\left\lVert
F_{t}\right\rVert+80\sqrt{r}\sigma_{1}^{1.5}\bar{\eta}_{t}\delta+30\sigma_{1}\bar{\eta}_{t}\left\lVert
G_{t}\right\rVert$ $\displaystyle\leq$ $\displaystyle\left\lVert
F_{t}\right\rVert+100\sqrt{r}\sigma_{1}^{1.5}\bar{\eta}_{t}\delta+30\sigma_{1}\bar{\eta}_{t}\left\lVert
G_{t}\right\rVert$ $\displaystyle\leq$ $\displaystyle\left\lVert
F_{t}\right\rVert+100\sqrt{r}\sigma_{1}^{1.5}\bar{\eta}_{t}\delta+30\sigma_{1}\bar{\eta}_{t}\sqrt{\alpha\bar{\varphi}\delta}$
$\displaystyle\leq$
$\displaystyle\eta\bar{\varphi}^{2}\left(100\sqrt{r}\sigma_{1}^{1.5}\delta+30\sigma_{1}\sqrt{\alpha\bar{\varphi}\delta}\right)(t+2),$

where in the first inequality, we use Lemma 26 and the induction hypothesis on
$\left\lVert\Delta_{t}\right\rVert$. Moreover, in the last inequality, we used
the induction hypothesis on $\left\lVert G_{t}\right\rVert$.

#### Bounding $\left\lVert S_{t+1}S_{t+1}^{\top}\right\rVert$:

Similar to our previous argument, it is easy to verify that the assumptions of
Proposition 5 are satisfied at iteration $t$. Therefore, $\left\lVert
S_{t+1}S_{t+1}^{\top}\right\rVert\leq 1.01\sigma_{1}$ readily follows from
Proposition 5.

#### Bounding $\left\lVert U_{t+1}U_{t+1}^{\top}-X^{\star}\right\rVert$:

Note that

$\displaystyle\left\lVert
U_{t+1}U_{t+1}^{\top}-X^{\star}\right\rVert\leq\left\lVert\Sigma-
S_{t+1}S_{t+1}^{\top}\right\rVert+2\left\lVert
S_{t+1}E_{t+1}^{\top}\right\rVert+\left\lVert
E_{t+1}E_{t+1}^{\top}\right\rVert.$

On the other hand, we have

$\displaystyle\left\lVert E_{t+1}E_{t+1}^{\top}\right\rVert\leq\left\lVert
F_{t+1}\right\rVert^{2}+\left\lVert G_{t+1}\right\rVert^{2}\leq
0.5\sigma_{1}.$

where the last inequality is due to our choice of $\delta$ and $\alpha$.
Similarly, we can show that $\left\lVert
S_{t+1}E_{t+1}^{\top}\right\rVert\leq\sigma_{1}$. This together with
$\left\lVert\Sigma-S_{t+1}S_{t+1}^{\top}\right\rVert\leq\left\lVert
S_{t+1}S_{t+1}^{\top}\right\rVert+\sigma_{1}\leq 2.01\sigma_{1}$ leads to

$\displaystyle\left\lVert U_{t+1}U_{t+1}^{\top}-X^{\star}\right\rVert\leq
5\sigma_{1}.$

#### Establishing $S_{t+1}S_{t+1}^{\top}\succ 0$:

The proof follows directly from the application of Proposition 4. The details
are omitted due to its similarity to the proof of (36) in Lemma 5.

#### Bounding $\left\lVert
E_{t+1}S_{t+1}^{\top}\left(S_{t+1}S_{t+1}^{\top}\right)^{-1}\right\rVert$:

To streamline the proof, let
$H_{t}=E_{t}S_{t}^{\top}\left(S_{t}S_{t}^{\top}\right)^{-1}$. Our goal is to
prove $\left\lVert H_{t}\right\rVert\leq 1/3$ by showing the following
recursive relationship.

######  Lemma 27.

For every $0\leq s\leq t$, we have

$\displaystyle\left\lVert
H_{s+1}\right\rVert\leq(1-c\bar{\eta}_{t}\sigma_{r})\left\lVert
H_{s}\right\rVert+c^{\prime}\sqrt{r}\sigma_{1}\bar{\eta}_{t}\delta,$ (108)

where $c,c^{\prime}>0$ are some universal constants.

The proof of Lemma 27 can be found in Appendix F.4. Equipped with this lemma,
we are ready to derive the desired result. First, due to Lemma 6, we have

$\displaystyle\left\lVert H_{0}\right\rVert\leq\frac{\left\lVert
E_{0}S_{0}^{\top}\right\rVert}{\lambda_{\min}(S_{0}S_{0}^{\top})}\leq\frac{2\alpha^{2}\delta{\varphi}(X^{\star})}{\alpha^{2}\varphi(X^{\star})\left(\frac{1}{\sqrt{r}\kappa}-2\delta\right)}\leq
4\sqrt{r}\kappa\delta,$

provided that $\delta\leq\frac{1}{4\sqrt{r}\kappa}$. On the other hand, (108)
implies that

$\displaystyle\left\lVert
H_{t+1}\right\rVert-\frac{c^{\prime}}{c}\sqrt{r}\kappa\delta\leq(1-c\bar{\eta}_{t}\sigma_{r})^{t+1}\left(\left\lVert
H_{0}\right\rVert-\frac{c^{\prime}}{c}\sqrt{r}\kappa\delta\right)\leq\left\lVert
H_{0}\right\rVert+\frac{c^{\prime}}{c}\sqrt{r}\kappa\delta.$

Therefore, due to our choice of $\delta$, we have

$\left\lVert
H_{t+1}\right\rVert\leq\left(4\sqrt{r}\kappa+\frac{2c^{\prime}}{c}\sqrt{r}\kappa\right)\delta\lesssim\sqrt{r}\kappa\delta\leq
1/3.$

#### Bounding $\left\lVert G_{t+1}\right\rVert$:

Due to Proposition 6, we have

$\displaystyle\left\lVert
G_{t+1}\right\rVert\leq\left(1+\bar{\eta}_{t}^{2}\left(2\left\lVert
E_{t}S_{t}^{\top}\right\rVert^{2}+\left\lVert
E_{t}\right\rVert^{4}+6\left\lVert
E_{t}S_{t}(S_{t}S_{t})^{-1}\right\rVert\left\lVert\Delta_{t}\right\rVert\left\lVert
E_{t}S_{t}^{\top}\right\rVert\right)+7\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\right)\left\lVert
G_{t}\right\rVert.$

Moreover, one can write

$\displaystyle\bar{\eta}_{t}^{2}\left\lVert
E_{t}S_{t}^{\top}\right\rVert^{2}\lesssim\bar{\eta}_{t}\left\lVert
E_{t}\right\rVert^{2}\lesssim
r\sigma_{1}^{3}\bar{\eta}_{t}^{2}\delta^{2}t^{2}+\sigma_{1}^{2}\bar{\eta}_{t}^{2}\alpha\bar{\varphi}\delta
t^{2}\lesssim\sqrt{r}\kappa\delta\log\left(\frac{1}{\alpha}\right).$

Similarly, it can be shown that

$\bar{\eta}_{t}^{2}\left\lVert
E_{t}\right\rVert^{4}\vee\bar{\eta}_{t}^{2}\left\lVert
H_{t}\right\rVert\left\lVert\Delta_{t}\right\rVert\left\lVert
E_{t}S_{t}^{\top}\right\rVert\vee\bar{\eta}_{t}\delta\left\lVert\Delta_{t}\right\rVert_{F}\lesssim\sqrt{r}\kappa\delta\log\left(\frac{1}{\alpha}\right).$

Therefore, for some universal constant $C>0$, we have

$\displaystyle\left\lVert G_{t+1}\right\rVert$
$\displaystyle\leq\left(1+C\sqrt{r}\kappa\delta\log\left(\frac{1}{\alpha}\right)\right)\left\lVert
G_{t}\right\rVert.$

Hence, we have

$\displaystyle\left\lVert G_{t+1}\right\rVert$
$\displaystyle\leq\left(1+C\sqrt{r}\kappa\delta\log\left(\frac{1}{\alpha}\right)\right)^{t+1}\left\lVert
G_{0}\right\rVert$
$\displaystyle\leq\left(1+C\sqrt{r}\kappa\delta\log\left(\frac{1}{\alpha}\right)\right)^{C^{\prime}\frac{\log({1}/{\alpha})}{\bar{\eta}_{t}\sigma_{r}}}\left\lVert
G_{0}\right\rVert$
$\displaystyle\leq\exp\left(C^{{}^{\prime\prime}}\sqrt{r}\kappa^{2}\delta\log\left(\frac{1}{\alpha}\right)\right)\left\lVert
G_{0}\right\rVert$
$\displaystyle\leq\alpha^{-\mathcal{O}\left(\sqrt{r}\kappa^{2}\delta\right)}\left\lVert
G_{0}\right\rVert$
$\displaystyle\leq\alpha^{1-\mathcal{O}\left(\sqrt{r}\kappa^{2}\delta\right)}\sqrt{\bar{\varphi}\delta},$

where in the last inequality, we used the upper bound $\left\lVert
G_{0}\right\rVert\leq\left\lVert E_{0}\right\rVert$ and Lemma 6.

##  Appendix E Proofs of Outlier Noise Model

###  E.1 Preliminaries

Given the update rule $U_{t+1}=U_{t}-2\eta_{t}Q_{t}U_{t}$, we consider the
following decomposition

$\displaystyle
U_{t+1}=\tilde{U}_{t+1}+R_{t}U_{t},\quad\text{where}\quad\tilde{U}_{t+1}=U_{t}-\frac{2\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\Delta_{t}U_{t},\
R_{t}=\frac{2\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\Delta_{t}-2\eta_{t}Q_{t},$
(109)

In the above decomposition, $\tilde{U}_{t+1}$ resembles one iteration of GD on
$\bar{f}_{\ell_{2}}(U)$ with the “effective” step-size
$\frac{\eta\rho^{t}}{2\left\lVert\Delta_{t}\right\rVert}$. Moreover, the term
$R_{t}U_{t}$ captures the deviation of SubGM and GD. Similar to the noiseless
setting, the main idea behind our proof technique is to show that $R_{t}$
remains small throughout the iterations of SubGM, and consequently, SubGM
behaves similar to GD. To this goal, we first provide an upper bound on
$\left\lVert\Delta_{t}\right\rVert_{F}$ in terms of
$\left\lVert\Delta_{t}\right\rVert$.

######  Lemma 28.

Suppose that $\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}\leq\left\lVert\Delta_{t}\right\rVert$. Then, we have
$\left\lVert\Delta_{t}\right\rVert_{F}\leq
2(1+\sqrt{r})\left\lVert\Delta\right\rVert$.

###### Proof.

Due to our proposed signal-residual decomposition, one can write

$\displaystyle\left\lVert\Delta_{t}\right\rVert_{F}$
$\displaystyle\leq\left\lVert\underbrace{V\left(S_{t}S_{t}^{\top}-\Sigma\right)V^{\top}+VS_{t}E_{t}^{\top}V_{\perp}^{\top}+V_{\perp}E_{t}S_{t}^{\top}V^{\top}+V_{\perp}F_{t}F_{t}^{\top}V_{\perp}^{\top}}_{\text{rank-$4r$}}\right\rVert_{F}+\left\lVert\underbrace{V_{\perp}G_{t}G_{t}^{\top}V_{\perp}^{\top}}_{\text{small
norm}}\right\rVert_{F}$
$\displaystyle\leq\sqrt{4r}\left\lVert{V\left(S_{t}S_{t}^{\top}-\Sigma\right)V^{\top}+VS_{t}E_{t}^{\top}V_{\perp}^{\top}+V_{\perp}E_{t}S_{t}^{\top}V^{\top}+V_{\perp}F_{t}F_{t}^{\top}V_{\perp}^{\top}}\right\rVert+\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}$
$\displaystyle\leq\sqrt{4r}\left\lVert\Delta_{t}\right\rVert+\sqrt{4r}\left\lVert
V_{\perp}G_{t}G_{t}^{\top}V_{\perp}^{\top}\right\rVert+\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}$ $\displaystyle\leq
2(1+\sqrt{r})\left\lVert\Delta_{t}\right\rVert,$

where the last inequality follows from the assumption $4r\leq d$ and
$\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}\leq\left\lVert\Delta_{t}\right\rVert$. This completes
the proof. ∎

Equipped with this technical lemma, we next provide an upper bound on
$\left\lVert R_{t}\right\rVert$.

######  Lemma 29.

Suppose that the measurements satisfy
$\left(4r,\delta,\varepsilon,\mathcal{S}\right)$-Sign-RIP with
$\delta<\frac{1}{4(1+\sqrt{r})}$, $\varepsilon=\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}$, $\mathcal{S}=\left\\{X:\left\lVert
X\right\rVert_{F}\geq\zeta\right\\}$ for $\zeta=\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}\left(\frac{1}{\delta}\vee\sqrt{d}\right)$, and
$\sqrt{d}\left\lVert
G_{t}\right\rVert^{2}\leq\left\lVert\Delta_{t}\right\rVert$. Then, we have
$\left\lVert R_{t}\right\rVert\leq 8(1+\sqrt{r})\eta\rho^{t}\delta$.

###### Proof.

One can write

$\displaystyle R_{t}$
$\displaystyle=\frac{2\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\Delta_{t}-\frac{2\eta\rho^{t}}{\left\lVert
Q_{t}\right\rVert}Q_{t}$ $\displaystyle=-\frac{2\eta\rho^{t}}{\left\lVert
Q_{t}\right\rVert}\left(Q_{t}-\varphi(\Delta_{t})\frac{\Delta_{t}}{\left\lVert\Delta_{t}\right\rVert_{F}}\right)-\frac{2\eta\rho^{t}\varphi(\Delta_{t})}{\left\lVert
Q_{t}\right\rVert\left\lVert\Delta_{t}\right\rVert_{F}}\Delta_{t}+\frac{2\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\Delta_{t}$
$\displaystyle=-\frac{2\eta\rho^{t}}{\left\lVert
Q_{t}\right\rVert}\left(Q_{t}-\varphi(\Delta_{t})\frac{\Delta_{t}}{\left\lVert\Delta_{t}\right\rVert_{F}}\right)+\frac{\left\lVert
Q_{t}\right\rVert-\varphi(\Delta_{t})\frac{\left\lVert\Delta_{t}\right\rVert}{\left\lVert\Delta_{t}\right\rVert_{F}}}{\left\lVert
Q_{t}\right\rVert}\frac{2\eta\rho^{t}}{\left\lVert\Delta_{t}\right\rVert}\Delta_{t}.$

The above equality implies that

$\displaystyle\left\lVert R_{t}\right\rVert$
$\displaystyle\leq\frac{2\eta\rho^{t}}{\left\lVert
Q_{t}\right\rVert}\left\lVert
Q_{t}-{\varphi(\Delta_{t})}\frac{\Delta_{t}}{\left\lVert\Delta_{t}\right\rVert_{F}}\right\rVert+2\eta\rho^{t}\cdot\frac{\left|\left\lVert
Q_{t}\right\rVert-\varphi(\Delta_{t})\frac{\left\lVert\Delta_{t}\right\rVert}{\left\lVert\Delta_{t}\right\rVert_{F}}\right|}{\left\lVert
Q_{t}\right\rVert}$ (110) $\displaystyle\leq\left(\frac{1}{\left\lVert
Q_{t}\right\rVert}\right)2\eta\rho^{t}\varphi(\Delta_{t})\delta,$

where in the last inequality, we used Sign-RIP. Next, we provide an upper
bound for $1/\left\lVert Q_{t}\right\rVert$. Due to Sign-RIP, we have
$\left\lVert
Q_{t}\right\rVert\geq\left(\frac{\left\lVert\Delta_{t}\right\rVert}{\left\lVert\Delta_{t}\right\rVert_{F}}-\delta\right)\varphi(\Delta_{t})$.
On the other hand, due to Lemma 28, we have
$\frac{\left\lVert\Delta_{t}\right\rVert}{\left\lVert\Delta_{t}\right\rVert_{F}}\leq\frac{1}{2(1+\sqrt{r})}$.
Combining these inequalities with (110), we have

$\displaystyle\left\lVert
R_{t}\right\rVert\leq\frac{2}{\frac{1}{2(1+\sqrt{r})}-\delta}\cdot\eta\rho^{t}\delta\leq
8(1+\sqrt{r})\eta\rho^{t}\delta,$

where the last inequality is due to the assumption
$\delta\leq\frac{1}{4(1+\sqrt{r})}$. ∎

###  E.2 Proof of Proposition 7

The proof is almost a line-by-line reconstruction of the proof of Proposition
4 in Appendix D.2. For brevity, we only provide a sketch of the proof. Similar
to (89), one can write

$\displaystyle S_{t+1}$ $\displaystyle=\tilde{S}_{t+1}+V^{\top}R_{t}U_{t}.$
(111)

Given this decomposition, we characterize the growth rate of
$\lambda_{\min}(S_{t+1}S_{t+1}^{\top})$ by first resorting to a more tractable
lower bound. In particular, we define
$M:=\left(I+\Xi\right)\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\left(I+\Xi\right)^{\top}$,
where
$\Xi:=V^{\top}R_{t}U_{t}\tilde{S}_{t+1}^{\top}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)^{-1}$.
Based on the definition of $M$, a series of inequalities analogous to (91) can
be used to show that
$\lambda_{\min}(S_{t+1}S_{t+1}^{\top})\geq\lambda_{\min}(M)$. Therefore, it
suffices to provide a lower bound for $\lambda_{\min}(M)$. Similar to the
proof of Proposition 4, we first show that
$\lambda_{\min}(M)\approx\lambda_{\min}(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top})$:

$\displaystyle\left|\lambda_{\min}(M)-\lambda_{\min}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)\right|$
$\displaystyle\leq
3\left\lVert\Xi\right\rVert\lambda_{\min}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)\leq
192\sqrt{r}\eta\rho^{t}\lambda_{\min}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right).$

Combining the above inequality with the one-step dynamic of
$\lambda_{\min}\left(\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}\right)$ from
Proposition 2 completes the proof.$\hfill\square$

###  E.3 Proof of Proposition 8

Similar to the minimum eigenvalue dynamics, the proof is identical to the
proof of Proposition 5. Hence, we only provide a sketch. Similar to (94), one
can write

$\displaystyle\Sigma-
S_{t+1}S_{t+1}^{\top}=\Sigma-\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}{-V^{\top}R_{t}U_{t}\tilde{S}_{t+1}^{\top}-\tilde{S}_{t+1}U_{t}^{\top}R_{t}^{\top}V-V^{\top}R_{t}U_{t}U_{t}^{\top}R_{t}^{\top}V}.$

Lemma 29 combined with an argument similar to Appendix D.3 leads to

$\displaystyle\left\lVert
V^{\top}R_{t}U_{t}\tilde{S}_{t+1}^{\top}+\tilde{S}_{t+1}U_{t}^{\top}R_{t}^{\top}V+V^{\top}R_{t}U_{t}U_{t}^{\top}R_{t}^{\top}V\right\rVert\leq
193\sqrt{r}\eta\rho^{t}\sigma_{1}\delta.$

The above bound combined with the one-step dynamics of
$\Sigma-\tilde{S}_{t+1}\tilde{S}_{t+1}^{\top}$ in Proposition 3 completes the
proof for the one-step dynamics of $\Sigma-S_{t+1}S_{t+1}^{\top}$. The
dynamics of the cross term (27) and the upper bound on $\left\lVert
S_{t+1}S_{t+1}^{\top}\right\rVert$ (28) can be deduced in a similar fashion.
The details are omitted for brevity.$\hfill\square$

###  E.4 Proof of Proposition 9

The proof of Proposition 9 is identical to that of Proposition 6, with a key
difference that $\left\lVert R_{t}\right\rVert\leq 16\sqrt{r}\eta\rho^{t}$.
The details are omitted for brevity.$\hfill\square$

###  E.5 Proof of Lemma 9

The proof is based on an inductive argument similar to the proof of Lemma 7 in
Appendix D.6. Due to our special initialization, it is easy to verify that the
statements of the lemma are satisfied for $t=0$. Now suppose that (56)-(61)
are satisfied for $t$. Due to Proposition 9, one can write

$\displaystyle\left\lVert G_{t+1}\right\rVert$
$\displaystyle\leq\left(1+5\eta^{2}\rho^{2t}+49\sqrt{r}\eta_{0}\rho^{t}\delta\right)\left\lVert
G_{t}\right\rVert,$
$\displaystyle\leq\exp\left({5\eta^{2}\rho^{2t}+49\sqrt{r}\eta\rho^{t}\delta}\right)\left\lVert
G_{t}\right\rVert,$ $\displaystyle\leq\left\lVert
G_{0}\right\rVert\prod_{s=0}^{t}\exp\left({5\eta^{2}\rho^{2s}+49\sqrt{r}\eta_{0}\rho^{s}\delta}\right)$
$\displaystyle\leq\left\lVert
G_{0}\right\rVert\exp\left({\sum_{s=0}^{t}5\eta^{2}\rho^{2s}+49\sqrt{r}\eta_{0}\rho^{s}\delta}\right)$
$\displaystyle\leq\left\lVert
G_{0}\right\rVert\exp\left({\frac{5\eta^{2}}{1-\rho^{2}}+\frac{49\sqrt{r}\eta\delta}{1-\rho}}\right).$

Due to $\rho=1-\Theta(\eta/(\kappa\log(1/\alpha)))$ and $\eta\lesssim
1/(\kappa\log(1/\alpha))$, we have

$\frac{5\eta^{2}}{1-\rho^{2}}\lesssim\eta\kappa\log(1/\alpha)\leq
1/2,\quad\text{and}\quad\frac{49\sqrt{r}\eta\delta}{1-\rho}\lesssim\sqrt{r}\kappa\delta\log(1/\alpha).$

Combining the above inequalities leads

$\left\lVert G_{t+1}\right\rVert\leq 2\left\lVert
G_{0}\right\rVert\alpha^{-\mathcal{O}(\sqrt{r}\kappa\delta)}\leq
2\sqrt{2}\alpha^{1-\mathcal{O}(\sqrt{r}\kappa\delta)}\sqrt{\bar{\varphi}\delta},$

where the last inequality is due to our special initialization technique and
Lemma 6. The remaining bounds in Lemma 9 can be established similar to Lemma
7. The details are omitted for brevity. $\hfill\square$

##  Appendix F Omitted Proofs

###  F.1 Proof of Lemma 19

To prove this lemma, we use one-step discretization technique. First note
that, for any $X\in\mathcal{S}_{k,\varepsilon}$, there exists a matrix in
$X^{\prime}\in\mathcal{S}_{k}$ such that $\left\lVert
X-X^{\prime}\right\rVert_{F}\leq{\varepsilon}$. Suppose that
$\mathcal{N}_{k,\xi}$ is a $\xi$-net of $\mathcal{S}_{k}$ where
$\xi\geq\varepsilon$. Based on the definition of $\xi$-net, there exists
$X^{\prime\prime}\in\mathcal{N}_{k,\xi}$ such that $\left\lVert
X^{\prime}-X^{\prime\prime}\right\rVert_{F}\leq\xi$. This implies that
$\left\lVert X-X^{\prime\prime}\right\rVert_{F}\leq\left\lVert
X-X^{\prime}\right\rVert_{F}+\left\lVert
X^{\prime}-X^{\prime\prime}\right\rVert_{F}\leq 2\xi$, and hence,
$\mathcal{N}_{k,\xi}$ is a $2\xi$-net of $\mathcal{S}_{k,\varepsilon}$. Given
this fact, one can write the following chain of inequalities for every
$Y\in\mathbb{S}$:

$\displaystyle\mathbb{E}\left[\mathcal{G}_{Y}\right]$
$\displaystyle\leq\underbrace{\mathbb{E}\left[\sup_{X^{\prime}\in\mathcal{N}_{k,\xi}}\frac{1}{m}\sum_{i=1}^{m}\mathrm{Sign}\left(\left\langle
A_{i},X^{\prime}\right\rangle-s_{i}\right)\left\langle
A_{i},Y\right\rangle-\varphi(X^{\prime})\left\langle\frac{X^{\prime}}{\left\lVert
X^{\prime}\right\rVert_{F}},Y\right\rangle\right]}_{{(A)}}$ (112)
$\displaystyle+\underbrace{\mathbb{E}\left[\sup_{\left\lVert
X-X^{\prime}\right\rVert_{F}\leq
2\xi}\frac{1}{m}\sum_{i=1}^{m}\left(\mathrm{Sign}\left(\left\langle
A_{i},X\right\rangle-s_{i}\right)-\mathrm{Sign}\left(\left\langle
A_{i},X^{\prime}\right\rangle-s_{i}\right)\right)\left\langle
A_{i},Y\right\rangle\right]}_{(B)}$
$\displaystyle+\underbrace{\sup_{\left\lVert X-X^{\prime}\right\rVert_{F}\leq
2\xi}\left\langle\varphi(X)\frac{X}{\left\lVert
X\right\rVert_{F}}-\varphi(X^{\prime})\frac{X^{\prime}}{\left\lVert
X^{\prime}\right\rVert_{F}},Y\right\rangle}_{(C)}.$

We control each term in the above inequality separately.

#### Bounding ${(A)}$.

To control ${(A)}$, note that
$\frac{1}{m}\sum_{i=1}^{m}\mathrm{Sign}\left(\left\langle
A_{i},X^{\prime}\right\rangle-s_{i}\right)\left\langle
A_{i},Y\right\rangle-\varphi(X^{\prime})\left\langle\frac{X^{\prime}}{\left\lVert
X^{\prime}\right\rVert_{F}},Y\right\rangle$ is
$\mathcal{O}\left(1/m\right)$-sub-Gaussian and ${(A)}$ is the supremum of the
sub-Gaussian random variable over a the finite set $\mathcal{N}_{k,\xi}$.
Hence, the Maximum Inequality implies that

${(A)}\lesssim\sqrt[]{\frac{dk}{m}\log\left(\frac{R}{\xi}\right)}.$ (113)

#### Bounding ${(B)}$.

Invoking Hölder’s inequality, one can write

$\displaystyle{(B)}$ $\displaystyle\leq\mathbb{E}\left[\sup_{\left\lVert
X-X^{\prime}\right\rVert_{F}\leq
2\xi}\left(\frac{1}{m}\sum_{i=1}^{m}\left|\mathrm{Sign}\left(\left\langle
A_{i},X\right\rangle-s_{i}\right)-\mathrm{Sign}\left(\left\langle
A_{i},X^{\prime}\right\rangle-s_{i}\right)\right|\right)\max_{1\leq i\leq
m}|\left\langle A_{i},Y\right\rangle|\right].$

Note that if $|\left\langle A_{i},X-X^{\prime}\right\rangle|\leq|\left\langle
A_{i},X^{\prime}-\lambda s_{i}\right\rangle|$, then
$\mathrm{Sign}(\left\langle A_{i},X^{\prime}\right\rangle-\lambda
s_{i})=\mathrm{Sign}(\left\langle A_{i},X\right\rangle-\lambda s_{i})$.
Therefore, the above term can be further bounded by

$\displaystyle\mathbb{E}\left[\sup_{\left\lVert
X-X^{\prime}\right\rVert_{F}\leq
2\xi}\left(\frac{1}{m}\sum_{i=1}^{m}\left|\mathrm{Sign}\left(\left\langle
A_{i},X\right\rangle-s_{i}\right)-\mathrm{Sign}\left(\left\langle
A_{i},X^{\prime}\right\rangle-s_{i}\right)\right|\right)\max_{1\leq i\leq
m}|\left\langle A_{i},Y\right\rangle|\right]$ (114) $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\sup_{\left\lVert
X-X^{\prime}\right\rVert_{F}\leq
2\xi}\left(\frac{1}{m}\sum_{i=1}^{m}\mathbbm{1}\left(|\left\langle
A_{i},X-X^{\prime}\right\rangle|\geq|\left\langle
A_{i},X^{\prime}\right\rangle-s_{i}|\right)\right)\max_{1\leq i\leq
m}|\left\langle A_{i},Y\right\rangle|\right]$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\sup_{\left\lVert
X-X^{\prime}\right\rVert_{F}\leq
2\xi}\left(\frac{1}{m}\sum_{i=1}^{m}\mathbbm{1}\left(|\left\langle
A_{i},X-X^{\prime}\right\rangle|\geq t\right)+\mathbbm{1}\left(|\left\langle
A_{i},X^{\prime}\right\rangle-s_{i}|\leq t\right)\right)\max_{1\leq i\leq
m}|\left\langle A_{i},Y\right\rangle|\right]$ $\displaystyle\leq$
$\displaystyle\underbrace{\mathbb{E}\left[\sup_{\left\lVert
X-X^{\prime}\right\rVert_{F}\leq
2\xi}\left(\frac{1}{m}\sum_{i=1}^{m}\mathbbm{1}\left(|\left\langle
A_{i},X-X^{\prime}\right\rangle|\geq t\right)\right)\max_{1\leq i\leq
m}|\left\langle A_{i},Y\right\rangle|\right]}_{(B_{1})}$
$\displaystyle+\underbrace{\mathbb{E}\left[\sup_{X^{\prime}\in\mathcal{N}_{k,\xi}}\left(\frac{1}{m}\sum_{i=1}^{m}\mathbbm{1}\left(|\left\langle
A_{i},X^{\prime}\right\rangle-s_{i}|\leq t\right)\right)\max_{1\leq i\leq
m}|\left\langle A_{i},Y\right\rangle|\right]}_{(B_{2})}.$

For $(B_{1})$, we have

$\displaystyle(B_{1})$
$\displaystyle\leq\mathbb{E}\left[\left(\frac{1}{m}\sum_{i=1}^{m}\mathbbm{1}\left(\left\lVert
A_{i}\right\rVert_{F}\geq\frac{t}{2\xi}\right)\right)\max_{1\leq i\leq
m}|\left\langle A_{i},Y\right\rangle|\right]$ (115)
$\displaystyle\leq\mathbb{E}\left[\mathbbm{1}\left(\left\lVert
A_{i}\right\rVert_{F}\geq\frac{t}{2\xi}\right)\right]\mathbb{E}\left[\max_{j\neq
i}|\left\langle
A_{j},Y\right\rangle|\right]+\mathbb{E}\left[\mathbbm{1}\left(\left\lVert
A_{i}\right\rVert_{F}\geq\frac{t}{2\xi}\right)|\left\langle
A_{i},Y\right\rangle|\right]$