# The Power of Preconditioning in Overparameterized
Low-Rank Matrix Sensing

Xingyu Xu
CMU Carnegie Mellon University; Email<EMAIL_ADDRESS>Yandi Shen
UChicago University of Chicago; Email<EMAIL_ADDRESS>Yuejie
Chi11footnotemark: 1
CMU  Cong Ma22footnotemark: 2
UChicago

(February 2023; Revised November 2023)

###### Abstract

We propose ScaledGD($\lambda$), a preconditioned gradient descent method to
tackle the low-rank matrix sensing problem when the true rank is unknown, and
when the matrix is possibly ill-conditioned. Using overparameterized factor
representations, ScaledGD($\lambda$) starts from a small random
initialization, and proceeds by gradient descent with a specific form of
damped preconditioning to combat bad curvatures induced by
overparameterization and ill-conditioning. ScaledGD($\lambda$) is remarkably
robust to ill-conditioning compared to vanilla gradient descent (GD) even with
overparameterization. Specifically, we show that, under the restricted
isometry property (RIP) of the sensing operator, ScaledGD($\lambda$) converges
to the true low-rank matrix at a constant linear rate after a small number of
iterations that scales only logarithmically with respect to the condition
number and the problem dimension. This significantly improves over the
convergence rate of vanilla GD which suffers from a polynomial dependency on
the condition number. Furthermore, we show that in the presence of measurement
noise, ScaledGD($\lambda$) converges to the minimax optimal error up to a
multiplicative factor of the condition number at the same rate as in the
noiseless setting, which is the first nearly minimax-optimal overparameterized
gradient method for low-rank matrix sensing. Our results also extend to the
setting when the matrix is only approximately low-rank under the Gaussian
design. Our work provides evidence on the power of preconditioning in
accelerating the convergence without hurting generalization in
overparameterized learning.

Keywords: low-rank matrix sensing, overparameterization, preconditioned
gradient descent method, random initialization, ill-conditioning

###### Contents

  1. 1 Introduction
    1. 1.1 Our contributions: a preview
    2. 1.2 Related work
  2. 2 Problem formulation
    1. 2.1 Model and assumptions
    2. 2.2 ScaledGD($\lambda$) for overparameterized low-rank matrix sensing
  3. 3 Main results
    1. 3.1 The overparameterization setting
    2. 3.2 The exact parameterization setting
    3. 3.3 The noisy setting
    4. 3.4 The approximately low-rank setting
  4. 4 Analysis
    1. 4.1 Preliminaries: decomposition of the iterates
    2. 4.2 Proof roadmap
    3. 4.3 Phase I: approximate power iterations
    4. 4.4 Phase II: exponential amplification of the signal
    5. 4.5 Phase III: local convergence
    6. 4.6 Proofs of main theorems
  5. 5 Numerical experiments
  6. 6 Discussions
  7. A Preliminaries
    1. A.1 Proof of Lemma 2
    2. A.2 Proof of Proposition 1
    3. A.3 Consequences of RIP
    4. A.4 Matrix perturbation results
  8. B Decompositions of key terms
    1. B.1 Proof of Lemma 13
    2. B.2 Proof of Lemma 14
    3. B.3 Proof of Lemma 15
  9. C Proofs for Phase I
    1. C.1 Establishing the base case: Finding a valid $t_{1}$
    2. C.2 Establishing the induction step
  10. D Proofs for Phase II
    1. D.1 Proof of Lemma 4
    2. D.2 Proof of Corollary 1
    3. D.3 Proof of Lemma 5
    4. D.4 Proof of Corollary 2
  11. E Proofs for Phase III
    1. E.1 Proof of Lemma 27
    2. E.2 Proof of Lemma 28
  12. F Proofs for the noisy and the approximate low-rank settings
    1. F.1 Proof of Theorem 4
    2. F.2 Proof of Theorem 5
  13. G Proof of Theorem 6
    1. G.1 Generalization of Phase I
    2. G.2 Generalization of Phase II
    3. G.3 Generalization of Phase III
    4. G.4 Proof of Theorem 6

##  1 Introduction

Low-rank matrix recovery plays an essential role in modern machine learning
and signal processing. To fix ideas, let us consider estimating a
rank-$r_{\star}$ positive semidefinite matrix $M_{\star}\in\mathbb{R}^{n\times
n}$ based on a few linear measurements $y\coloneqq\mathcal{A}(M_{\star})$,
where $\mathcal{A}:\mathbb{R}^{n\times n}\to\mathbb{R}^{m}$ models the
measurement process. Significant research efforts have been devoted to
tackling low-rank matrix recovery in a statistically and computationally
efficient manner in recent years. Perhaps the most well-known method is convex
relaxation (Candès and Plan,, 2011; Recht et al.,, 2010; Davenport and
Romberg,, 2016), which seeks the matrix with lowest nuclear norm to fit the
observed measurements:

$\displaystyle\min_{M\succeq 0}\quad\|M\|_{*}\qquad\text{s.t.}\quad
y=\mathcal{A}(M).$

While statistically optimal, convex relaxation is prohibitive in terms of both
computation and memory as it directly operates in the ambient matrix domain,
i.e., $\mathbb{R}^{n\times n}$. To address this challenge, nonconvex
approaches based on low-rank factorization have been proposed (Burer and
Monteiro,, 2005):

$\displaystyle\min_{X\in\mathbb{R}^{n\times
r}}\quad\frac{1}{4}\big{\|}\mathcal{A}(XX^{\top})-y\big{\|}_{2}^{2},$ (1)

where $r$ is a user-specified rank parameter. Despite nonconvexity, when the
rank is correctly specified, i.e., when $r=r_{\star}$, the problem (1) admits
computationally efficient solvers (Chi et al.,, 2019), e.g., gradient descent
(GD) with spectral initialization or with small random initialization.
However, three main challenges remain when applying the factorization-based
nonconvex approach (1) in practice.

  * •

Unknown rank. First, the true rank $r_{\star}$ is often unknown, which makes
it infeasible to set $r=r_{\star}$. One necessarily needs to consider an
overparameterized setting in which $r$ is set conservatively, i.e., one sets
$r\geq r_{\star}$ or even $r=n$.

  * •

Poor conditioning. Second, the ground truth matrix $M_{\star}$ may be ill-
conditioned, which is commonly encountered in practice. Existing approaches
such as gradient descent are still computationally expensive in such settings
as the number of iterations necessary for convergence increases with the
condition number.

  * •

Robustness to noise and approximate low-rankness. Last but not least, it is
desirable that the performance is robust when the measurement $y$ is
contaminated by noise and when $M_{\star}$ is approximately low-rank.

In light of these two challenges, the main goal of this work is to address the
following question:

Can one develop an efficient and robust method for solving ill-conditioned
matrix recovery in the overparameterized setting?

parameterization | reference | algorithm | init. | iteration complexity
---|---|---|---|---
$r>r_{\star}$ |  Stöger and Soltanolkotabi, (2021) $\frac{1^{7^{7^{7}}}}{1^{7^{7^{7}}}}$ | GD | random | $\kappa^{8}+\kappa^{6}\log(\kappa n/\varepsilon)$
Zhang et al., (2021) $\frac{1^{7^{7^{7}}}}{1^{7^{7^{7}}}}$ | PrecGD | spectral | $\log(1/\varepsilon)$
Theorem 2 $\frac{1^{7^{7^{7}}}}{1^{7^{7^{7}}}}$ | ScaledGD($\lambda$) | random | $\log\kappa\cdot\log(\kappa n)+\log(1/\varepsilon)$
$r=r_{\star}$ |  Tong et al., 2021a  $\frac{1^{7^{7^{7}}}}{1^{7^{7^{7}}}}$ | ScaledGD | spectral | $\log(1/\varepsilon)$
Stöger and Soltanolkotabi, (2021) $\frac{1^{7^{7^{7}}}}{1^{7^{7^{7}}}}$ | GD | random | $\kappa^{8}\log(\kappa n)+\kappa^{2}\log(1/\varepsilon)$
Theorem 3 $\frac{1^{7^{7^{7}}}}{1^{7^{7^{7}}}}$ | ScaledGD($\lambda$) | random | $\log\kappa\cdot\log(\kappa n)+\log(1/\varepsilon)$

Table 1: Comparison of iteration complexity with existing algorithms for low-
rank matrix sensing under Gaussian designs. Here, $n$ is the matrix dimension,
$r_{\star}$ is the true rank, $r$ is the overparameterized rank, and $\kappa$
is the condition number of the problem instance (see Section 2 for a formal
problem formulation). It is important to note that in the overparameterized
setting ($r>r_{\star}$), the sample complexity of Zhang et al., (2021) scales
polynomially with the overparameterized rank $r$, while that of Stöger and
Soltanolkotabi, (2021) and ours only scale polynomially with the true rank
$r_{\star}$.

###  1.1 Our contributions: a preview

The main contribution of the current paper is to answer the question
affirmatively by developing a _preconditioned_ gradient descent method
(ScaledGD($\lambda$)) that converges to the (possibly ill-conditioned) low-
rank matrix in a fast and global manner, even with overparamterized rank
$r\geq r_{\star}$.

######  Theorem 1 (Informal).

Under overparameterization $r\geq r_{\star}$ and mild statistical assumptions,
ScaledGD($\lambda$)—when starting from a sufficiently small random
initialization—achieves a relative $\varepsilon$-accuracy, i.e.,
$\|X_{t}X_{t}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}\leq\varepsilon\|M_{\star}\|$,
with no more than an order of

$\log\kappa\cdot\log(\kappa n)+\log(1/\varepsilon)$

iterations, where $\kappa$ is the condition number of the problem. Moreover,
in the presence of measurement noise, ScaledGD($\lambda$) converges to the
nearly minimax-optimal error with the same rate as above.

The above theorem suggests that from a small random initialization,
ScaledGD($\lambda$) converges at a constant linear rate—independent of the
condition number—after a small logarithmic number of iterations. Overall, the
iteration complexity is nearly independent of the condition number and the
problem dimension, making it extremely suitable for solving large-scale and
ill-conditioned problems. To the best of our knowledge, ScaledGD($\lambda$) is
the first provably minimax-optimal overparameterized gradient method for low-
rank matrix sensing. Our results also extend to the setting when the matrix
$M_{\star}$ is only approximately low-rank under the Gaussian design. See
Table 1 for a summary of comparisons with prior art in the noiseless setting.

Our algorithm ScaledGD($\lambda$) is closely related to scaled gradient
descent (ScaledGD) (Tong et al., 2021a, ), a recently proposed preconditioned
gradient descent method that achieves a $\kappa$-independent convergence rate
under spectral initialization and exact parameterization. We modify the
preconditioner design by introducing a fixed damping term, which prevents the
preconditioner itself from being ill-conditioned due to overparameterization;
the modified preconditioner preserves the low computational overhead when the
overparameterization is moderate. In the exact parameterization setting, our
result extends ScaledGD beyond local convergence by characterizing the number
of iterations it takes to enter the local basin of attraction from a small
random initialization.

Moreover, our results shed light on the power of preconditioning in
accelerating the optimization process over vanilla GD while still guaranteeing
generalization in overparameterized learning models (Amari et al.,, 2020).
Remarkably, despite the existence of an infinite number of global minima in
the landscape of (1) that do not generalize, i.e., not corresponding to the
ground truth, starting from a small random initialization, GD (Li et al.,,
2018; Stöger and Soltanolkotabi,, 2021) is known to converge to a
generalizable solution without explicit regularization. However, GD takes
$O(\kappa^{8}+\kappa^{6}\log(\kappa n/\varepsilon))$ iterations to reach
$\varepsilon$-accuracy, which is unacceptable even for moderate condition
numbers. On the other hand, while common wisdom suggests that preconditioning
accelerates convergence, it is yet unclear if it still converges to a
generalizable global minimum. Our work answers this question in the
affirmative for overparameterized low-rank matrix sensing, where
ScaledGD($\lambda$) significantly accelerates the convergence against the poor
condition number—both in the initial phase and in the local phase—without
hurting generalization, which is corroborated in Figure 1.

Figure 1: Comparison between ScaledGD($\lambda$) and GD. The learning rate of
GD has been fine-tuned to achieve fastest convergence for each $\kappa$, while
that of ScaledGD($\lambda$) is fixed to $0.3$. The initialization scale
$\alpha$ in each case has been fine-tuned so that the final accuracy is
$10^{-9}$. The details of the experiment are deferred to Section 5.

###  1.2 Related work

Significant efforts have been devoted to understanding nonconvex optimization
for low-rank matrix estimation in recent years, see Chi et al., (2019) and
Chen and Chi, (2018) for recent overviews. By reparameterizing the low-rank
matrix into a product of factor matrices, also known as the Burer-Monteiro
factorization (Burer and Monteiro,, 2005), the focus point has been examining
if the factor matrices can be recovered—up to invertible
transformations—faithfully using simple iterative algorithms in a provably
efficient manner. However, the majority of prior efforts suffer from the
limitations that they assume an exact parameterization where the rank of the
ground truth is given or estimated somewhat reliably, and rely on a carefully
constructed initialization (e.g., using the spectral method (Chen et al.,,
2021)) in order to guarantee global convergence in a polynomial time. The
analyses adopted in the exact parameterization case fail to generalize when
overparameterization presents, and drastically new approaches are called for.

##### Overparameterization in low-rank matrix sensing.

Li et al., (2018) made a theoretical breakthrough that showed that gradient
descent converges globally to any prescribed accuracy even in the presence of
full overparameterization ($r=n$), with a small random initialization, where
their analyses were subsequently adapted and extended in Stöger and
Soltanolkotabi, (2021) and Zhuo et al., (2021). Ding et al., (2021)
investigated robust low-rank matrix recovery with overparameterization from a
spectral initialization, and Ma and Fattahi, (2022) examined the same problem
from a small random initialization with noisy measurements. Zhang et al.,
(2021, 2022) developed a preconditioned gradient descent method for
overparameterized low-rank matrix sensing. Last but not least, a number of
other notable works that study overparameterized low-rank models include, but
are not limited to, Soltanolkotabi et al., (2018); Geyer et al., (2020); Oymak
and Soltanolkotabi, (2019); Zhang, (2021, 2022).

##### Global convergence from random initialization without
overparameterization.

Despite nonconvexity, it has been established recently that several structured
learning models admit global convergence via simple iterative methods even
when initialized randomly even without overparameterization. For example, Chen
et al., (2019) showed that phase retrieval converges globally from a random
initialization using a near-minimal number of samples through a delicate
leave-one-out analysis. In addition, the efficiency of randomly initialized GD
is established for complete dictionary learning (Gilboa et al.,, 2019; Bai et
al.,, 2018), multi-channel sparse blind deconvolution (Qu et al.,, 2019; Shi
and Chi,, 2021), asymmetric low-rank matrix factorization (Ye and Du,, 2021),
and rank-one matrix completion (Kim and Chung,, 2022). Moving beyond GD, Lee
and Stöger, (2022) showed that randomly initialized alternating least-squares
converges globally for rank-one matrix sensing, whereas Chandrasekher et al.,
(2022) developed sharp recovery guarantees of alternating minimization for
generalized rank-one matrix sensing with sample-splitting and random
initialization.

##### Algorithmic or implicit regularization.

Our work is related to the phenomenon of algorithmic or implicit
regularization (Gunasekar et al.,, 2017), where the trajectory of simple
iterative algorithms follows a path that maintains desirable properties
without explicit regularization. Along this line, Ma et al., (2019); Chen et
al., 2020a ; Li et al., (2021) highlighted the implicit regularization of GD
for several statistical estimation tasks, Ma et al., (2021) showed that GD
automatically balances the factor matrices in asymmetric low-rank matrix
sensing, where Jiang et al., (2022) analyzed the algorithmic regularization in
overparameterized asymmetric matrix factorization in a model-free setting.

##  2 Problem formulation

Section 2.1 introduces the problem of low-rank matrix sensing, and Section 2.2
provides background on the proposed ScaledGD($\lambda$) algorithm developed
for the possibly overparameterized case.

###  2.1 Model and assumptions

Suppose that the ground truth $M_{\star}\in\mathbb{R}^{n\times n}$ is a
positive-semidefinite (PSD) matrix of rank $r_{\star}\ll n$, whose (compact)
eigendecomposition is given by

$M_{\star}=U_{\star}\Sigma_{\star}^{2}U_{\star}^{\top}.$

Here, the columns of $U_{\star}\in\mathbb{R}^{n\times r_{\star}}$ specify the
set of eigenvectors, and $\Sigma_{\star}\in\mathbb{R}^{r_{\star}\times
r_{\star}}$ is a diagonal matrix where the diagonal entries are ordered in a
non-increasing fashion. Setting $X_{\star}\coloneqq
U_{\star}\Sigma_{\star}\in\mathbb{R}^{n\times r_{\star}}$, we can rewrite
$M_{\star}$ as

$M_{\star}=X_{\star}X_{\star}^{\top}.$ (2)

We call $X_{\star}$ the ground truth low-rank factor matrix, whose condition
number $\kappa$ is defined as

$\kappa\coloneqq\frac{\sigma_{\max}(X_{\star})}{\sigma_{\min}(X_{\star})}.$
(3)

Here we recall that $\sigma_{\max}(X_{\star})$ and $\sigma_{\min}(X_{\star})$
are the largest and the smallest singular values of $X_{\star}$, respectively.

Instead of having access to $M_{\star}$ directly, we wish to recover
$M_{\star}$ from a set of random linear measurements $\mathcal{A}(M_{\star})$,
where $\mathcal{A}:\operatorname{Sym}_{2}(\mathbb{R}^{n})\to\mathbb{R}^{m}$ is
a linear map from the space of $n\times n$ symmetric matrices to
$\mathbb{R}^{m}$, namely

$y=\mathcal{A}(M_{\star}),$ (4)

or equivalently,

$\quad y_{i}=\langle A_{i},M_{\star}\rangle,\qquad 1\leq i\leq m.$

We are interested in recovering $M_{\star}$ based on the measurements $y$ and
the sensing operator $\mathcal{A}$ in a provably efficient manner, even when
the true rank $r_{\star}$ is unknown.

###  2.2 ScaledGD($\lambda$) for overparameterized low-rank matrix sensing

Inspired by the factorized representation (2), we aim to recover the low-rank
matrix $M_{\star}$ by solving the following optimization problem (Burer and
Monteiro,, 2005):

$\min_{X\in\mathbb{R}^{n\times r}}\quad
f(X)\coloneqq\frac{1}{4}\big{\|}\mathcal{A}(XX^{\top})-y\big{\|}_{2}^{2},$ (5)

where $r$ is a predetermined rank parameter, possibly different from
$r_{\star}$. It is evident that for any rotation matrix $O\in\mathcal{O}_{r}$,
it holds that $f(X)=f(XO)$, leading to an infinite number of global minima of
the loss function $f$.

##### A prelude: exact parameterization.

When $r$ is set to be the true rank $r_{\star}$ of $M_{\star}$, Tong et al.,
2021a  set forth a provable algorithmic approach called scaled gradient
descent (ScaledGD)—gradient descent with a specific form of
preconditioning—that adopts the following update rule

$\displaystyle\textsf{ScaledGD:}\qquad X_{t+1}$
$\displaystyle=X_{t}-\eta\nabla f(X_{t})(X_{t}^{\top}X_{t})^{-1}$ (6)
$\displaystyle=X_{t}-\eta\mathcal{A^{*}A}(X_{t}X_{t}^{\top}-M_{\star})X_{t}(X_{t}^{\top}X_{t})^{-1}.$

Here, $X_{t}$ is the $t$-th iterate, $\nabla f(X_{t})$ is the gradient of $f$
at $X=X_{t}$, and $\eta>0$ is the learning rate. Moreover,
$\mathcal{A}^{*}:\mathbb{R}^{m}\mapsto\operatorname{Sym}_{2}(\mathbb{R}^{n})$
is the adjoint operator of $\mathcal{A}$, that is
$\mathcal{A}^{*}(y)=\sum_{i=1}^{m}y_{i}A_{i}$ for $y\in\mathbb{R}^{m}$.

At the expense of light computational overhead, ScaledGD is remarkably robust
to ill-conditioning compared with vanilla gradient descent (GD). It is
established in Tong et al., 2021a  that ScaledGD, when starting from spectral
initialization, converges linearly at a constant rate—independent of the
condition number $\kappa$ of $X_{\star}$ (cf. (3)); in contrast, the iteration
complexity of GD (Tu et al.,, 2016; Zheng and Lafferty,, 2015) scales on the
order of $\kappa^{2}$ from the same initialization, therefore GD becomes
exceedingly slow when the problem instance is even moderately ill-conditioned,
a scenario that is quite commonly encountered in practice.

#####  ScaledGD($\lambda$): overparametrization under unknown rank.

In this paper, we are interested in the so-called overparameterization regime,
where $r_{\star}\leq r\leq n$. From an operational perspective, the true rank
$r_{\star}$ is related to model order, e.g., the number of sources or targets
in a scene of interest, which is often unavailable and makes it necessary to
consider the misspecified setting. Unfortunately, in the presence of
overparameterization, the original ScaledGD algorithm is no longer
appropriate, as the preconditioner $(X_{t}^{\top}X_{t})^{-1}$ might become
numerically unstable to calculate. Therefore, we propose a new variant of
ScaledGD by adjusting the preconditioner as

$\displaystyle\textsf{ScaledGD($\lambda$):}\qquad X_{t+1}$
$\displaystyle=X_{t}-\eta\nabla f(X_{t})(X_{t}^{\top}X_{t}+\lambda I)^{-1},$
(7)
$\displaystyle=X_{t}-\eta\mathcal{A^{*}A}(X_{t}X_{t}^{\top}-M_{\star})X_{t}(X_{t}^{\top}X_{t}+\lambda
I)^{-1},$

where $\lambda>0$ is a fixed damping parameter. The new algorithm is dubbed as
ScaledGD($\lambda$), and it recovers the original ScaledGD when $\lambda=0$.
Similar to ScaledGD, a key property of ScaledGD($\lambda$) is that the
iterates $\\{X_{t}\\}$ are equivariant with respect to the parameterization of
the factor matrix. Specifically, taking a rotationally equivalent factor
$X_{t}O$ with an arbitrary $O\in\mathcal{O}_{r}$, and feeding it into the
update rule (7), the next iterate

$X_{t}O-\eta\mathcal{A^{*}A}(X_{t}X_{t}^{\top}-M_{\star})X_{t}O(O^{\top}X_{t}^{\top}X_{t}O+\lambda
I)^{-1}=X_{t+1}O$

is rotated simultaneously by the same rotation matrix $O$. In other words, the
recovered matrix sequence $M_{t}=X_{t}X_{t}^{\top}$ is invariant with respect
to the parameterization of the factor matrix.

######  Remark 1.

We note that a related variant of ScaledGD, called PrecGD, has been proposed
recently in Zhang et al., (2021, 2022) for the overparameterized setting,
which follows the update rule

$\displaystyle\textsf{PrecGD:}\qquad
X_{t+1}=X_{t}-\eta\mathcal{A^{*}A}(X_{t}X_{t}^{\top}-M_{\star})X_{t}(X_{t}^{\top}X_{t}+\lambda_{t}I)^{-1},$
(8)

where the damping parameters $\lambda_{t}=\sqrt{f(X_{t})}$ are selected in an
iteration-varying manner assuming the algorithm is initialized properly. In
contrast, ScaledGD($\lambda$) assumes a fixed damping parameter $\lambda$
throughout the iterations. We shall provide more detailed comparisons with
PrecGD in Section 3.

##  3 Main results

Before formally presenting our theorems, let us introduce several key
assumptions that will be in effect throughout this paper.

##### Restricted Isometry Property.

A key property of the operator $\mathcal{A}(\cdot)$ is the celebrated
Restricted Isometry Property (RIP) (Recht et al.,, 2010), which says that the
operator $\mathcal{A}(\cdot)$ approximately preserves the distances between
low-rank matrices. The formal definition is given as follows.

######  Definition 1 (Restricted Isometry Property).

The linear map $\mathcal{A}(\cdot)$ is said to obey rank-$r$ RIP with a
constant $\delta_{r}\in[0,1)$, if for all matrices
$M\in\operatorname{Sym}_{2}(\mathbb{R}^{n})$ of rank at most $r$, it holds
that

$(1-\delta_{r})\|M\|_{\operatorname{\mathsf{F}}}^{2}\leq\big{\|}\mathcal{A}(M)\big{\|}_{2}^{2}\leq(1+\delta_{r})\|M\|_{\operatorname{\mathsf{F}}}^{2}.$
(9)

The Restricted Isometry Constant (RIC) is defined to be the smallest positive
$\delta_{r}$ such that (9) holds.

The RIP is a standard assumption in low-rank matrix sensing, which has been
verified to hold with high probability for a wide variety of measurement
operators. The following lemma establishes the RIP for the Gaussian design.

######  Lemma 1.

(Candès and Plan,, 2011) If the sensing operator $\mathcal{A}(\cdot)$ follows
the Gaussian design, i.e., the entries of $\\{A_{i}\\}_{i=1}^{m}$ are
independent up to symmetry with diagonal elements sampled from
$\mathcal{N}(0,1/m)$ and off-diagonal elements from $\mathcal{N}(0,1/2m)$,
then with high probability, $\mathcal{A}(\cdot)$ satisfies rank-$r$ RIP with
constant $\delta_{r}$, as long as $m\geq Cnr/\delta_{r}^{2}$ for some
sufficiently large universal constant $C>0$.

We make the following assumption about the operator $\mathcal{A}(\cdot)$.

######  Assumption 1.

The operator $\mathcal{A}(\cdot)$ satisfies the rank-$(r_{\star}+1)$ RIP with
$\delta_{r_{\star}+1}\eqqcolon\delta$. Furthermore, there exist a sufficiently
small constant $c_{\delta}>0$ and a sufficiently large constant $C_{\delta}>0$
such that

$\delta\leq c_{\delta}r_{\star}^{-1/2}\kappa^{-C_{\delta}}.$ (10)

##### Small random initialization.

Similar to Li et al., (2018); Stöger and Soltanolkotabi, (2021), we set the
initialization $X_{0}$ to be a small random matrix, i.e.,

$X_{0}=\alpha G,$ (11)

where $G\in\mathbb{R}^{n\times r}$ is some matrix considered to be normalized
and $\alpha>0$ controls the magnitude of the initialization. To simplify
exposition, we take $G$ to be a standard random Gaussian matrix, that is, $G$
is a random matrix with i.i.d. entries distributed as $\mathcal{N}(0,1/n)$.

##### Choice of parameters.

Last but not least, the parameters of ScaledGD($\lambda$) are selected
according to the following assumption.

######  Assumption 2.

There exist some universal constants $c_{\eta},c_{\lambda},C_{\alpha}>0$ such
that $(\eta,\lambda,\alpha)$ in ScaledGD($\lambda$) satisfy the following
conditions:

$\displaystyle\mathsf{(learning~{}rate)}$
$\displaystyle\qquad\qquad\qquad\eta\leq c_{\eta},$ (12a)
$\displaystyle\mathsf{(damping~{}parameter)}$
$\displaystyle\qquad\frac{1}{100}c_{\lambda}\sigma_{\min}^{2}(X_{\star})\leq\lambda\leq
c_{\lambda}\sigma_{\min}^{2}(X_{\star}),$ (12b)
$\displaystyle\mathsf{(initialization~{}size)}$
$\displaystyle\qquad\log\frac{\|X_{\star}\|}{\alpha}\geq\frac{C_{\alpha}}{\eta}\log(2\kappa)\cdot\log(2\kappa
n).$ (12c)

We are now in place to present the main theorems.

###  3.1 The overparameterization setting

We begin with our main theorem, which characterizes the performance of
ScaledGD($\lambda$) with overparameterization.

######  Theorem 2.

Suppose Assumptions 1 and 2 hold. With high probability (with respect to the
realization of the random initialization $G$), there exists a universal
constant $C_{\min}>0$ such that for some $T\leq
T_{\min}\coloneqq\frac{C_{\min}}{\eta}\log\frac{\|X_{\star}\|}{\alpha}$, we
have

$\|X_{T}X_{T}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}\leq\alpha^{1/3}\|X_{\star}\|^{5/3}.$

In particular, for any prescribed accuracy target $\varepsilon\in(0,1)$, by
choosing a sufficiently small $\alpha$ fulfilling both (12c) and
$\alpha\leq\varepsilon^{3}\|X_{\star}\|$, we have
$\|X_{T}X_{T}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}\leq\varepsilon\|M_{\star}\|$.

A few remarks are in order.

##### Iteration complexity.

Theorem 2 shows that by choosing an appropriate $\alpha$, ScaledGD($\lambda$)
finds an $\varepsilon$-accurate solution, i.e.,
$\|X_{t}X_{t}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}\leq\varepsilon\|M_{\star}\|$,
in no more than an order of

$\log\kappa\cdot\log(\kappa n)+\log(1/\varepsilon)$

iterations. Roughly speaking, this asserts that ScaledGD($\lambda$) converges
at a constant linear rate after an initial phase of approximately
$O(\log\kappa\cdot\log(\kappa n))$ iterations. Most notably, the iteration
complexity is nearly independent of the condition number $\kappa$, with a
small overhead only through the poly-logarithmic additive term
$O(\log\kappa\cdot\log(\kappa n))$. In contrast, GD requires
$O(\kappa^{8}+\kappa^{6}\log(\kappa n/\varepsilon))$ iterations to converge
from a small random initialization to $\varepsilon$-accuracy; see Stöger and
Soltanolkotabi, (2021); Li et al., (2018). Thus, the convergence of GD is much
slower than ScaledGD($\lambda$) even for mildly ill-conditioned matrices.

##### Sample complexity.

The sample complexity of ScaledGD($\lambda$) hinges upon the Assumption 1.
When the sensing operator $\mathcal{A}(\cdot)$ follows the Gaussian design,
this assumption is fulfilled as long as $m\gtrsim
nr_{\star}^{2}\cdot\mathsf{poly}(\kappa)$. Notably, our sample complexity
depends only on the true rank $r_{\star}$, but not on the overparameterized
rank $r$ — a crucial feature in order to provide meaningful guarantees when
the overparameterized rank $r$ is close to the full dimension $n$. The
dependency on $\kappa$ in the sample complexity, on the other end, has been
generally unavoidable in nonconvex low-rank estimation (Chi et al.,, 2019).

##### Comparison with Zhang et al., (2021, 2022).

As mentioned earlier, our proposed algorithm ScaledGD($\lambda$) is similar to
PrecGD proposed in Zhang et al., (2021) that adopts an iteration-varying
damping parameter in ScaledGD (Tong et al., 2021a, ). In terms of theoretical
guarantees, Zhang et al., (2021) only provides the local convergence for
PrecGD assuming an initialization close to the ground truth; in contrast, we
provide global convergence guarantees where a small random initialization is
used. More critically, the sample complexity of PrecGD (Zhang et al.,, 2021)
depends on the overparameterized rank $r$, while ours only depends on the true
rank $r_{\star}$. While Zhang et al., (2022) also studied variants of PrecGD
with global convergence guarantees, they require additional operations such as
gradient perturbations and switching between different algorithmic stages,
which are harder to implement in practice. Our theory suggests that additional
perturbation is unnecessary to ensure the global convergence of
ScaledGD($\lambda$), as ScaledGD($\lambda$) automatically adapts to different
curvatures of the optimization landscape throughout the entire trajectory.

###  3.2 The exact parameterization setting

We now single out the exact parametrization case, i.e., when $r=r_{\star}$. In
this case, our theory suggests that ScaledGD($\lambda$) converges to the
ground truth even from a random initialization with a fixed scale $\alpha>0$.

######  Theorem 3.

Assume that $r=r_{\star}$. Suppose Assumptions 1 and 2 hold. With high
probability (with respect to the realization of the random initialization
$G$), there exist some universal constants $C_{\min}>0$ and $c>0$ such that
for some $T\leq T_{\min}=\frac{C_{\min}}{\eta}\log(\|X_{\star}\|/\alpha)$, we
have for any $t\geq T$

$\|X_{t}X_{t}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}\leq(1-c\eta)^{t-T}\|M_{\star}\|.$

Theorem 3 shows that with some fixed initialization scale $\alpha$,
ScaledGD($\lambda$) takes at most an order of

$\log\kappa\cdot\log(\kappa n)+\log(1/\varepsilon)$

iterations to converge to $\varepsilon$-accuracy for any $\varepsilon>0$ in
the exact parameterization case. Compared with ScaledGD (Tong et al., 2021a, )
which takes $O(\log(1/\varepsilon))$ iterations to converge from a spectral
initialization, we only pay a logarithmic order $O(\log\kappa\cdot\log(\kappa
n))$ of additional iterations to converge from a random initialization. In
addition, once the algorithms enter the local regime, both ScaledGD($\lambda$)
and ScaledGD behave similarly and converge at a fast constant linear rate,
suggesting the effect of damping is locally negligible. Furthermore, compared
with GD (Stöger and Soltanolkotabi,, 2021) which requires
$O(\kappa^{8}\log(\kappa n)+\kappa^{2}\log(1/\varepsilon))$ iterations to
achieve $\varepsilon$-accuracy, our theory again highlights the benefit of
ScaledGD($\lambda$) in boosting the global convergence even for mildly ill-
conditioned matrices.

###  3.3 The noisy setting

We next consider the case where the measurements are contaminated by noise
$\xi=(\xi_{i})_{i=1}^{m}$, that is

$y=\mathcal{A}(M_{\star})+\xi,\quad\text{or more concretely}\quad
y_{i}=\langle A_{i},M_{\star}\rangle+\xi_{i},\quad 1\leq i\leq m.$ (13)

Instantiating (7) with the noisy measurements, the update rule of
ScaledGD($\lambda$) can be written as

$X_{t+1}=X_{t}-\eta\big{(}\mathcal{A^{*}A}(X_{t}X_{t}^{\top})-\mathcal{A}^{*}(y)\big{)}X_{t}(X_{t}^{\top}X_{t}+\lambda
I)^{-1}.$ (14)

For simplicity, we make the following mild assumption on the noise.

######  Assumption 3.

We assume that $\xi_{i}$’s are independent with $\mathcal{A}(\cdot)$, and are
i.i.d. Gaussian, i.e.,

$\xi_{i}\stackrel{{\scriptstyle\text{i.i.d.}}}{{\sim}}\mathcal{N}(0,\sigma^{2}),\quad
1\leq i\leq m.$

Our theory demonstrates that ScaledGD($\lambda$) achieves the minimax-optimal
error in this noisy setting as long as the noise is not too large.

######  Theorem 4.

Assume that $\sigma\sqrt{n}\leq c_{\sigma}\kappa^{-C_{\sigma}}\|M_{\star}\|$
for some sufficiently small universal constant $c_{\sigma}>0$ and some
sufficiently large universal constant $C_{\sigma}>0$. Then the following holds
with high probability (with respect to the realization of the random
initialization $G$ and the noise $\xi$). Suppose Assumptions 1, 2 and 3 hold.
Given a prescribed accuracy target $\varepsilon\in(0,1)$, suppose further that
$\alpha\leq\varepsilon^{3}\|X_{\star}\|$. There exist universal constants
$C_{\min}>0$, $C_{\ref{thm:noisy}}>0$, such that for some $T\leq
T_{\min}\coloneqq\frac{C_{\min}}{\eta}\log\frac{\|X_{\star}\|}{\alpha}$, we
have

$\displaystyle\|X_{T}X_{T}^{\top}-M_{\star}\|$
$\displaystyle\leq\max\left(\varepsilon\|M_{\star}\|,~{}C_{\ref{thm:noisy}}\kappa^{4}\sigma\sqrt{n}\right),$
$\displaystyle\|X_{T}X_{T}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}$
$\displaystyle\leq\max\left(\varepsilon\|M_{\star}\|,~{}C_{\ref{thm:noisy}}\kappa^{4}\sigma\sqrt{nr_{\star}}\right).$

A few remarks are in order.

##### Minimax optimality.

Theorem 4 suggests that as long as the noise level is not too large, by
setting the optimization error $\varepsilon$ sufficiently small, i.e.,
$\varepsilon\|M_{\star}\|\asymp\kappa^{4}\sigma\sqrt{n}$, ScaledGD($\lambda$)
finds a solution that satisfies

$\displaystyle\|X_{T}X_{T}^{\top}-M_{\star}\|\lesssim\kappa^{4}\sigma\sqrt{n},\qquad\|X_{T}X_{T}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}\lesssim\kappa^{4}\sigma\sqrt{nr_{\star}}$
(15)

in no more than $\log\kappa\cdot\log(\kappa
n)+\log\left(\frac{\|M_{\star}\|}{\kappa^{4}\sigma\sqrt{n}}\right)$
iterations, the number of which again only depends logarithmically on the
problem parameters. When $\kappa$ is upper bounded by a constant, our result
is minimax optimal, in the sense that the final error matches the minimax
lower bound in the classical work of Candès and Plan, (2011), which we recall
here for completeness: for any estimator $\widehat{M}(y)$ based on the
measurement $y$ defined in (13), for any $r_{\star}\leq n$, there always
exists some $M_{\star}\in\mathbb{R}^{n\times n}$ of rank $r_{\star}$ such that

$\|\widehat{M}(y)-M_{\star}\|\gtrsim\sigma\sqrt{n},\qquad\|\widehat{M}(y)-M_{\star}\|_{\operatorname{\mathsf{F}}}\gtrsim\sigma\sqrt{nr_{\star}}$

with probability at least $0.99$ (with respect to the realization of the noise
$\xi$). To the best of our knowledge, Theorem 4 is the first result to
establish the minimax optimality (up to multiplicative factors of $\kappa$) of
overparameterized gradient methods in the context of low-rank matrix sensing.
We remark that similar sub-optimality with respect to $\kappa$ is also
observed in Chen et al., 2020b .

##### Consistency.

It is often desirable that the estimator is (asymptotically) consistent, i.e.,
the estimation error converges to $0$ as the number of samples $m\to\infty$.
To see that Theorem 4 indicates ScaledGD($\lambda$) indeed produces a
consistent estimator, let us consider again the Gaussian design. In this case,
$\langle A_{i},M_{\star}\rangle$ is on the order of $\|M_{\star}\|/\sqrt{m}$,
thus the signal-to-noise ratio can be measured by
$\mathsf{SNR}\coloneqq(\|M_{\star}\|/\sqrt{m})^{2}/\sigma^{2}=\|M_{\star}\|^{2}/(m\sigma^{2})$.
With this notation, Theorem 4 asserts that the final error is
$O\big{(}\mathsf{SNR}^{-1/2}\sqrt{\frac{n}{m}}\|M_{\star}\|\big{)}$ in
operator norm and
$O\big{(}\mathsf{SNR}^{-1/2}\sqrt{\frac{nr_{\star}}{m}}\|M_{\star}\|\big{)}$
in Frobenius norm, both of which converge to $0$ at a rate of
$\sqrt{\frac{nr_{\star}}{m}}$ as $m\to\infty$ when $\mathsf{SNR}$ is fixed.

###  3.4 The approximately low-rank setting

Last but not least, we examine a more general model of $M_{\star}$, which does
not need to be exactly low-rank, but only approximately low-rank. Instead of
recovering $M_{\star}$ exactly, one seeks to find a low-rank approximation to
$M_{\star}$ from its linear measurements. To set up, let
$M_{\star}\in\mathbb{R}^{n\times n}$ be a general PSD ground truth matrix,
where its spectral decomposition is given by
$M_{\star}=\sum_{i=1}^{n}\sigma_{i}u_{i}u_{i}^{\top}$, with

$\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{n}.$

For any given $r\leq n$, let $M_{r}$ be the best rank-$r$ approximation of
$M_{\star}$ and $M_{r}^{\prime}$ be the residual, i.e.,

$M_{\star}=\underbrace{\sum_{i=1}^{r}\sigma_{i}u_{i}u_{i}^{\top}}_{\eqqcolon
M_{r}}+\underbrace{\sum_{i=r+1}^{n}\sigma_{i}u_{i}u_{i}^{\top}}_{\eqqcolon
M_{r}^{\prime}}.$ (16)

If $\widehat{M}_{r}$ is a rank-$r$ approximation to $M_{\star}$, the
approximation error can be measured by
$\|\widehat{M}_{r}-M_{\star}\|_{\operatorname{\mathsf{F}}}$. It is well-known
that the best rank-$r$ approximation in this sense is exactly $M_{r}$, and the
optimal error is thus $\|M_{r}^{\prime}\|_{\operatorname{\mathsf{F}}}$. By
picking a larger $r$, one has a smaller approximation error
$\|M_{r}^{\prime}\|_{\operatorname{\mathsf{F}}}$, but a higher memory
footprint for the low-rank approximation $M_{r}$ whose condition number also
grows with $r$.

For simplicity, we consider the Gaussian design (cf. Lemma 1) in this
subsection, which is less general than the RIP. The following theorem
demonstrates that, as long as the sample size satisfies $m\gtrsim
nr_{\star}^{2}\cdot\mathsf{poly}(\kappa)$, ScaledGD($\lambda$) automatically
adapts to the available sample size and produces a near-optimal
rank-$r_{\star}$ approximation to $M_{\star}$ in spite of
overparameterization.

######  Theorem 5.

Assume that $M_{\star}$ is given in (16) and the sensing operator
$\mathcal{A}$ follows the Gaussian design with $m\geq
Cnr_{\star}^{2}\kappa^{C}$, where $\kappa=\sigma_{1}/\sigma_{r_{\star}}$ is
the condition number of $M_{r_{\star}}$. In addition, assume
$\|M_{r_{\star}}^{\prime}\|\leq c_{\sigma}\kappa^{-C_{\sigma}}\|M_{\star}\|$
and $\|M_{r_{\star}}^{\prime}\|_{\operatorname{\mathsf{F}}}\leq
c_{\sigma}\kappa^{-C_{\sigma}}\sqrt{\frac{m}{n}}\|M_{\star}\|$. Then the
following holds with high probability (with respect to the realization of the
random initialization $G$ and the sensing operator $\mathcal{A}$). Suppose
Assumption 2 holds for $M_{r_{\star}}=X_{\star}X_{\star}^{\top}$. Given a
prescribed accuracy target $\varepsilon\in(0,1)$, suppose further that
$\alpha\leq\varepsilon^{3}\|X_{\star}\|$. there exist universal constants
$C_{\min}>0$, $C_{\ref{thm:approx}}>0$, such that for some $T\leq
T_{\min}\coloneqq\frac{C_{\min}}{\eta}\log\frac{\|X_{\star}\|}{\alpha}$, we
have

$\displaystyle\|X_{T}X_{T}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}$
$\displaystyle\leq\max\left(\varepsilon\|M_{\star}\|,~{}C_{\ref{thm:approx}}\kappa^{4}\|M_{r_{\star}}^{\prime}\|_{\operatorname{\mathsf{F}}}\right).$

Here, $C>0,C_{\sigma}>0$ are some sufficiently large universal constants, and
$c_{\sigma}>0$ is some sufficiently small universal constant.

######  Remark 2.

Theorem 5 also holds in the matrix factorization setting, i.e., when
$\mathcal{A}$ is the identity operator.

Theorem 5 suggests that as long as $M_{\star}$ is well approximated by a low-
rank matrix, by setting the optimization error $\varepsilon$ sufficiently
small, i.e.,
$\varepsilon\|M_{\star}\|\asymp\kappa^{4}\|M_{r_{\star}}^{\prime}\|_{\operatorname{\mathsf{F}}}$,
ScaledGD($\lambda$) finds a solution that satisfies

$\displaystyle\|X_{T}X_{T}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}\lesssim\kappa^{4}\|M_{r_{\star}}^{\prime}\|_{\operatorname{\mathsf{F}}}$
(17)

in no more than $\log\kappa\cdot\log(\kappa
n)+\log\left(\frac{\|M_{\star}\|}{\kappa^{4}\|M_{r_{\star}}^{\prime}\|_{\operatorname{\mathsf{F}}}}\right)$
iterations, which again only depend on the problem parameters logarithmically.
This suggests that if the residual $M_{r_{\star}}^{\prime}$ is small,
ScaledGD($\lambda$) produces an approximate solution to the best
rank-$r_{\star}$ approximation problem with near-optimal error, up to a
multiplicative factor depending only on $\kappa$, without knowing the rank
$r_{\star}$ a priori. To our best knowledge, this is the first near-optimal
theoretical guarantee for approximate low-rank matrix sensing using gradient-
based methods.

##  4 Analysis

In this section, we present the main steps for proving Theorem 2 and Theorem
3. The proofs of Theorem 4 and Theorem 5 will follow the same ideas with minor
modification. The detailed proofs are collected in the appendix. All of our
statements will be conditioned on the following high probability event
regarding the initialization matrix $G$:

$\mathcal{E}=\\{\|G\|\leq
C_{G}\\}\cap\\{\sigma_{\min}(\widehat{U}^{\top}G)\geq(2n)^{-C_{G}}\\},$ (18)

where $\widehat{U}\in\mathbb{R}^{n\times r_{\star}}$ is an orthonormal basis
of the eigenspace associated with the $r_{\star}$ largest eigenvalues of
$\mathcal{A^{*}A}(M_{\star})$, and $C_{G}>0$ is some sufficiently large
universal constant. It is a standard result in random matrix theory that
$\mathcal{E}$ happens with high probability, as verified by the following
lemma.

######  Lemma 2.

With respect to the randomness in $G$, the event $\mathcal{E}$ happens with
probability at least $1-(cn)^{-C_{G}(r-r_{\star}+1)/2}-2\exp(-cn)$, where
$c>0$ is some universal constant.

###### Proof.

See Appendix A.1. ∎

###  4.1 Preliminaries: decomposition of the iterates

Before embarking on the main proof, we present a useful decomposition (cf.
(19)) of the iterate $X_{t}$ into a signal term, a misalignment error term,
and an overparametrization error term. Choose some matrix
$U_{{\star,\perp}}\in\mathbb{R}^{n\times(n-r_{\star})}$ such that
$[U_{\star},U_{{\star,\perp}}]$ is orthonormal. Then we can define

$S_{t}\coloneqq U_{\star}^{\top}X_{t}\in\mathbb{R}^{r_{\star}\times
r},\quad\mbox{and}\quad N_{t}\coloneqq
U_{{\star,\perp}}^{\top}X_{t}\in\mathbb{R}^{(n-r_{\star})\times r}.$

Let the SVD of $S_{t}$ be

$S_{t}=U_{t}\Sigma_{t}V_{t}^{\top},$

where $U_{t}\in\mathbb{R}^{r_{\star}\times r_{\star}}$,
$\Sigma_{t}\in\mathbb{R}^{r_{\star}\times r_{\star}}$, and
$V_{t}\in\mathbb{R}^{r\times r_{\star}}$. Similar to $U_{{\star,\perp}}$, we
define the orthogonal complement of $V_{t}$ as
$V_{{t,\perp}}\in\mathbb{R}^{r\times(r-r_{\star})}$. When $r=r_{\star}$ we
simply set $V_{{t,\perp}}=0$.

We are now ready to present the main decomposition of $X_{t}$, which we use
repeatedly in later analysis.

######  Proposition 1.

The following decomposition holds:

$X_{t}=\underbrace{U_{\star}\widetilde{S}_{t}V_{t}^{\top}}_{\mathsf{signal}}+\underbrace{U_{{\star,\perp}}\widetilde{N}_{t}V_{t}^{\top}}_{\mathsf{misalignment}}+\underbrace{U_{{\star,\perp}}\widetilde{O}_{t}V_{{t,\perp}}^{\top}}_{\mathsf{overparametrization}},$
(19)

where

$\widetilde{S}_{t}\coloneqq S_{t}V_{t}\in\mathbb{R}^{r_{\star}\times
r_{\star}},\quad\widetilde{N}_{t}\coloneqq
N_{t}V_{t}\in\mathbb{R}^{(n-r_{\star})\times
r_{\star}},\quad\mbox{and}\quad\widetilde{O}_{t}\coloneqq
N_{t}V_{{t,\perp}}\in\mathbb{R}^{(n-r_{\star})\times(r-r_{\star})}.$ (20)

###### Proof.

See Appendix A.2. ∎

Several remarks on the decomposition are in order.

  * •

First, since $V_{{t,\perp}}$ spans the obsolete subspace arising from
overparameterization, $\widetilde{O}_{t}$ naturally represents the error
incurred by overparameterization; in particular, in the well-specified case
(i.e., $r=r_{\star}$), one has zero overparameterization error, i.e.,
$\widetilde{O}_{t}=0$.

  * •

Second, apart from the rotation matrix $V_{t}$, $\widetilde{S}_{t}$ documents
the projection of the iterates $X_{t}$ onto the signal space $U_{\star}$.
Similarly, $\widetilde{N}_{t}$ characterizes the misalignment of the iterates
with the signal subspace $U_{\star}$. It is easy to observe that in order for
$X_{t}X_{t}^{\top}\approx M_{\star}$, one must have
$\widetilde{S}_{t}\widetilde{S}_{t}^{\top}\approx\Sigma_{\star}^{2}$, and
$\widetilde{N}_{t}\approx 0$.

  * •

Last but not least, the extra rotation induced by $V_{t}$ is extremely useful
in making the signal/misalignment terms rationally invariant. To see this,
suppose that we rotate the current iterate by $X_{t}\mapsto X_{t}Q$ with some
rotational matrix $Q\in\mathcal{O}_{r}$, then $S_{t}\mapsto S_{t}Q$ but
$\widetilde{S}_{t}$ remains unchanged, and similarly for $\widetilde{N}_{t}$.

###  4.2 Proof roadmap

Our analysis breaks into a few phases that characterize the dynamics of the
key terms in the above decomposition, which we provide a roadmap to facilitate
understanding. Denote

$C_{\max}\coloneqq\begin{cases}4C_{\min},&r>r_{\star},\\\
\infty,&r=r_{\star},\end{cases}\qquad\mbox{and}\qquad
T_{\max}\coloneqq\frac{C_{\max}}{\eta}\log(\|X_{\star}\|/\alpha),$

where $T_{\max}$ represents the largest index of the iterates that we maintain
error control. The analysis boils down to the following phases, indicated by
time points $t_{1},t_{2},t_{3},t_{4}$ that satisfy

$\displaystyle t_{1}\leq T_{\min}/16,\quad t_{1}\leq t_{2}\leq
t_{1}+T_{\min}/16,\quad t_{2}\leq t_{3}\leq t_{2}+T_{\min}/16,\quad t_{3}\leq
t_{4}\leq t_{3}+T_{\min}/16.$

  * •

Phase I: approximate power iterations. In the initial phase,
ScaledGD($\lambda$) behaves similarly to GD, which is shown in Stöger and
Soltanolkotabi, (2021) to approximate the power method in the first few
iterations up to $t_{1}$. After this phase, namely for $t\in[t_{1},T_{\max}]$,
although the signal strength is still quite small, it begins to be aligned
with the ground truth with the overparameterization error kept relatively
small.

  * •

Phase II: exponential amplification of the signal. In this phase,
ScaledGD($\lambda$) behaves somewhat as a mixture of GD and ScaledGD with a
proper choice of the damping parameter
$\lambda\asymp\sigma_{\min}^{2}(X_{\star})$, which ensures the signal strength
first grows exponentially fast to reach a constant level no later than
$t_{2}$, and then reaches the desired level no later than $t_{3}$, i.e.,
$\widetilde{S}_{t}\widetilde{S}_{t}^{\top}\approx\Sigma_{\star}^{2}$.

  * •

Phase III: local linear convergence. At the last phase, ScaledGD($\lambda$)
behaves similarly to ScaledGD, which converges linearly at a rate independent
of the condition number. Specifically, for $t\in[t_{3},T_{\max}]$, the
reconstruction error
$\|X_{t}X_{t}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}$ converges at a
linear rate up to some small overparameterization error, until reaching the
desired accuracy for any $t\in[t_{4},T_{\max}]$.

###  4.3 Phase I: approximate power iterations

It has been observed in Stöger and Soltanolkotabi, (2021) that when
initialized at a small scaled random matrix, the first few iterations of GD
mimic the power iterations on the matrix $\mathcal{A^{*}A}(M_{\star})$. When
it comes to ScaledGD($\lambda$), since the initialization size $\alpha$ is
chosen to be much smaller than the damping parameter $\lambda$, the
preconditioner $(X_{t}^{\top}X_{t}+\lambda I)^{-1}$ behaves like $(\lambda
I)^{-1}$ in the beginning. This renders ScaledGD($\lambda$) akin to gradient
descent in the initial phase. As a result, we also expect the first few
iterations of ScaledGD($\lambda$) to be similar to the power iterations, i.e.,

$X_{t}\approx\left(I+\frac{\eta}{\lambda}\mathcal{A^{*}A}(M_{\star})\right)^{t}X_{0},\qquad\text{when
}t\text{ is small}.$

Such proximity between ScaledGD($\lambda$) and power iterations can indeed be
justified in the beginning period, which allows us to deduce the following
nice properties after the initial iterates of ScaledGD($\lambda$).

######  Lemma 3.

Under the same setting as Theorem 2, there exists an iteration number
$t_{1}:t_{1}\leq T_{\min}/16$ such that

$\sigma_{\min}(\widetilde{S}_{t_{1}})\geq\alpha^{2}/\|X_{\star}\|,$ (21)

and that, for any $t\in[t_{1},T_{\max}]$, $\widetilde{S}_{t}$ is invertible
and one has

$\displaystyle\|\widetilde{O}_{t}\|$
$\displaystyle\leq(C_{\ref{lem:p1.5}.b}\kappa
n)^{-C_{\ref{lem:p1.5}.b}}\|X_{\star}\|\sigma_{\min}\big{(}(\Sigma_{\star}^{2}+\lambda
I)^{-1/2}\widetilde{S}_{t}\big{)},$ (22a) $\displaystyle\|\widetilde{O}_{t}\|$
$\displaystyle\leq\left(1+\frac{\eta}{12C_{\max}\kappa}\right)^{t-t_{1}}\alpha^{5/6}\|X_{\star}\|^{1/6},$
(22b) $\displaystyle\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|$
$\displaystyle\leq c_{\ref{lem:p1.5}}\kappa^{-C_{\delta}/2}\|X_{\star}\|,$
(22c) $\displaystyle\|\widetilde{S}_{t}\|$ $\displaystyle\leq
C_{\ref{lem:p1.5}.a}\kappa\|X_{\star}\|,$ (22d)

where $C_{\ref{lem:p1.5}.a}$, $C_{\ref{lem:p1.5}.b}$, $c_{\ref{lem:p1.5}}$ are
some positive constants satisfying $C_{\ref{lem:p1.5}.a}\lesssim
c_{\lambda}^{-1/2}$, $c_{\ref{lem:p1.5}}\lesssim c_{\delta}/c_{\lambda}^{3}$,
and $C_{\ref{lem:p1.5}.b}$ can be made arbitrarily large by increasing
$C_{\alpha}$.

###### Proof.

See Appendix C. ∎

######  Remark 3.

Let us record two immediate consequences of (22), which sometimes are more
convenient for later analysis. From (22a), we may deduce

$\displaystyle\|\widetilde{O}_{t}\|$
$\displaystyle\leq(C_{\ref{lem:p1.5}.b}\kappa
n)^{-C_{\ref{lem:p1.5}.b}}\|X_{\star}\|\sigma_{\min}(\Sigma_{\star}^{2}+\lambda
I)^{-1/2}\sigma_{\min}(\widetilde{S}_{t})$
$\displaystyle\leq\kappa(C_{\ref{lem:p1.5}.b}\kappa
n)^{-C_{\ref{lem:p1.5}.b}}\sigma_{\min}(\widetilde{S}_{t})$
$\displaystyle\leq(C_{\ref{lem:p1.5}.b}^{\prime}\kappa
n)^{-C_{\ref{lem:p1.5}.b}^{\prime}}\sigma_{\min}(\widetilde{S}_{t}),$ (23)

where $C_{\ref{lem:p1.5}.b}^{\prime}=C_{\ref{lem:p1.5}.b}/2$, provided
$C_{\ref{lem:p1.5}.b}>4$. It is clear that $C_{\ref{lem:p1.5}.b}^{\prime}$ can
also be made arbitrarily large by enlarging $C_{\alpha}$. Similarly, from
(22b), we may deduce

$\displaystyle\|\widetilde{O}_{t}\|\leq\left(1+\frac{\eta}{12C_{\max}\kappa}\right)^{t-t_{1}}\alpha^{5/6}\|X_{\star}\|^{1/6}$
$\displaystyle\leq\left(1+\frac{\eta}{12C_{\max}\kappa}\right)^{\frac{C_{\max}}{\eta}\log(\|X_{\star}\|/\alpha)}\alpha^{5/6}\|X_{\star}\|^{1/6}$
$\displaystyle\leq(\|X_{\star}\|/\alpha)^{1/12}\alpha^{5/6}\|X_{\star}\|^{1/6}=\alpha^{3/4}\|X_{\star}\|^{1/4}.$
(24)

Lemma 3 ensures the iterates of ScaledGD($\lambda$) maintain several desired
properties after iteration $t_{1}$, as summarized in (22). In particular, for
any $t\in[t_{1},T_{\max}]$: (i) the overparameterization error
$\|\widetilde{O}_{t}\|$ remains small relatively to the signal strength
measured in terms of the scaled minimum singular value
$\sigma_{\min}\big{(}(\Sigma_{\star}^{2}+\lambda
I)^{-1/2}\widetilde{S}_{t}\big{)}$, and remains bounded with respect to the
size of the initialization $\alpha$ (cf. (22a) and (22b) and their
consequences (3) and (24)); (ii) the scaled misalignment-to-signal ratio
remains bounded, suggesting the iterates remain aligned with the ground truth
signal subspace $U_{\star}$ (cf. (22c)); (iii) the size of the signal
component $\widetilde{S}_{t}$ remains bounded (cf. (22d)). These properties
play an important role in the follow-up analysis.

######  Remark 4.

It is worth noting that, the scaled minimum singular value
$\sigma_{\min}((\Sigma_{\star}^{2}+\lambda I)^{-1/2}\widetilde{S}_{t})$ plays
a key role in our analysis, which is in sharp contrast to the use of the
vanilla minimum singular value $\sigma_{\min}(\widetilde{S}_{t})$ in the
analysis of gradient descent (Stöger and Soltanolkotabi,, 2021). This new
measure of signal strength is inspired by the scaled distance for ScaledGD
introduced in Tong et al., 2021a ; Tong et al., (2022), which carefully takes
the preconditioner design into consideration. Similarly, the metrics
$\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|$ in (22c) and
$\big{\|}\Sigma_{\star}^{-1}(\widetilde{S}_{t+1}\widetilde{S}_{t+1}^{\top}-\Sigma_{\star}^{2})\Sigma_{\star}^{-1}\big{\|}$
(to be seen momentarily) are also scaled for similar considerations to unveil
the fast convergence (almost) independent of the condition number.

###  4.4 Phase II: exponential amplification of the signal

By the end of Phase I, the signal strength is still quite small (cf. (21)),
which is far from the desired level. Fortunately, the properties established
in Lemma 3 allow us to establish an exponential amplification of the signal
term $\widetilde{S}_{t}$ thereafter, which can be further divided into two
stages.

  1. 1.

In the first stage, the signal is boosted to a constant level, i.e.,
$\widetilde{S}_{t}\widetilde{S}_{t}^{\top}\succeq\frac{1}{10}\Sigma_{\star}^{2}$;

  2. 2.

In the second stage, the signal grows further to the desired level, i.e.,
$\widetilde{S}_{t}\widetilde{S}_{t}^{\top}\approx\Sigma_{\star}^{2}$.

We start with the first stage, which again uses
$\sigma_{\min}\big{(}(\Sigma_{\star}^{2}+\lambda
I)^{-1/2}\widetilde{S}_{t}\big{)}$ as a measure of signal strength in the
following lemma.

######  Lemma 4.

For any $t$ such that (22) holds, we have

$\sigma_{\min}\big{(}(\Sigma_{\star}^{2}+\lambda
I)^{-1/2}\widetilde{S}_{t+1}\big{)}\geq(1-2\eta)\sigma_{\min}\big{(}(\Sigma_{\star}^{2}+\lambda
I)^{-1/2}\widetilde{S}_{t}\big{)}.$

Moreover, if $\sigma_{\min}\big{(}(\Sigma_{\star}^{2}+\lambda
I)^{-1/2}\widetilde{S}_{t}\big{)}\leq 1/3$, then

$\sigma_{\min}\big{(}(\Sigma_{\star}^{2}+\lambda
I)^{-1/2}\widetilde{S}_{t+1}\big{)}\geq\left(1+\frac{1}{8}\eta\right)\sigma_{\min}\big{(}(\Sigma_{\star}^{2}+\lambda
I)^{-1/2}\widetilde{S}_{t}\big{)}.$

###### Proof.

See Appendix D.1. ∎

The second half of Lemma 4 uncovers the exponential growth of the signal
strength $\sigma_{\min}\big{(}(\Sigma_{\star}^{2}+\lambda
I)^{-1/2}\widetilde{S}_{t}\big{)}$ until a constant level after several
iterations, which resembles the exponential growth of the signal strength in
GD (Stöger and Soltanolkotabi,, 2021). This is formally established in the
following corollary.

######  Corollary 1.

There exists an iteration number $t_{2}:t_{1}\leq t_{2}\leq t_{1}+T_{\min}/16$
such that for all $t\in[t_{2},T_{\max}]$, we have

$\widetilde{S}_{t}\widetilde{S}_{t}^{\top}\succeq\frac{1}{10}\Sigma_{\star}^{2}.$
(25)

###### Proof.

See Appendix D.2. ∎

We next aim to show that
$\widetilde{S}_{t}\widetilde{S}_{t}^{\top}\approx\Sigma_{\star}^{2}$ after the
signal strength is above the constant level. To this end, the behavior of
ScaledGD($\lambda$) becomes closer to that of ScaledGD, and it turns out to be
easier to work with
$\big{\|}\Sigma_{\star}^{-1}(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}-\Sigma_{\star}^{2})\Sigma_{\star}^{-1}\big{\|}$
as a measure of the scaled recovery error of the signal component. We
establish the approximate exponential shrinkage of this measure in the
following lemma.

######  Lemma 5.

For all $t\in[t_{2},T_{\max}]$ with $t_{2}$ given in Corollary 1, one has

$\big{\|}\Sigma_{\star}^{-1}(\widetilde{S}_{t+1}\widetilde{S}_{t+1}^{\top}-\Sigma_{\star}^{2})\Sigma_{\star}^{-1}\big{\|}\leq\left(1-\eta\right)\big{\|}\Sigma_{\star}^{-1}(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}-\Sigma_{\star}^{2})\Sigma_{\star}^{-1}\big{\|}+\frac{1}{100}\eta.$
(26)

###### Proof.

See Appendiex D.3. ∎

With the help of Lemma 5, it is straightforward to establish the desired
approximate recovery guarantee of the signal component, i.e.,
$\widetilde{S}_{t}\widetilde{S}_{t}^{\top}\approx\Sigma_{\star}^{2}$.

######  Corollary 2.

There exists an iteration number $t_{3}:t_{2}\leq t_{3}\leq t_{2}+T_{\min}/16$
such that for any $t\in[t_{3},T_{\max}]$, one has

$\frac{9}{10}\Sigma_{\star}^{2}\preceq\widetilde{S}_{t}\widetilde{S}_{t}^{\top}\preceq\frac{11}{10}\Sigma_{\star}^{2}.$
(27)

###### Proof.

See Appendix D.4. ∎

###  4.5 Phase III: local convergence

Corollary 2 tells us that after iteration $t_{3}$, we enter a local region in
which $\widetilde{S}_{t}\widetilde{S}_{t}^{\top}$ is close to the ground truth
$\Sigma_{\star}^{2}$. In this local region, the behavior of
ScaledGD($\lambda$) becomes closer to that of ScaledGD analyzed in Tong et
al., 2021a . We turn attention to the reconstruction error
$\|X_{t}X_{t}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}$ that measures
the generalization performance, and show it converges at a linear rate
independent of the condition number up to some small overparameterization
error.

######  Lemma 6.

There exists some universal constant $c_{\ref{lem:p3}}>0$ such that for any
$t:t_{3}\leq t\leq T_{\max}$, we have

$\|X_{t}X_{t}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}\leq(1-c_{\ref{lem:p3}}\eta)^{t-t_{3}}\sqrt{r_{\star}}\|M_{\star}\|+8c_{\ref{lem:p3}}^{-1}\|M_{\star}\|\max_{t_{3}\leq\tau\leq
t}\left(\frac{\|\widetilde{O}_{\tau}\|}{\|X_{\star}\|}\right)^{1/2}.$ (28)

In particular, there exists an iteration number $t_{4}:t_{3}\leq t_{4}\leq
t_{3}+T_{\min}/16$ such that for any $t\in[t_{4},T_{\max}]$, we have

$\|X_{t}X_{t}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}\leq\alpha^{1/3}\|X_{\star}\|^{5/3}\leq\varepsilon\|M_{\star}\|.$
(29)

Here, $\varepsilon$ and $\alpha$ are as stated in Theorem 2.

###### Proof.

See Appendix E. ∎

###  4.6 Proofs of main theorems

Now we are ready to collect the results in the preceding sections to prove our
main results, i.e., Theorem 2 and Theorem 3. The proofs of Theorem 4 and
Theorem 5 follows from similar ideas but with additional technicality, thus
are postponed to Appendix F.

We start with proving Theorem 2. By Lemma 3, Corollary 1, Corollary 2 and
Lemma 6, the final $t_{4}$ given by Lemma 6 is no more than $4\times
T_{\min}/16\leq T_{\min}/2$, thus (29) holds for all
$t\in[T_{\min}/2,T_{\max}]$, in particular, for some $T\leq T_{\min}$, as
claimed.

Now we consider Theorem 3. In case that $r=r_{\star}$, it follows from
definition that $\widetilde{O}_{t}=0$ vanishes for all $t$. It follows from
Lemma 6, in particular from (28), that

$\|X_{t}X_{t}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}\leq(1-c_{\ref{lem:p3}}\eta)^{t-t_{3}}\sqrt{r_{\star}}\|M_{\star}\|,$

for any $t\geq t_{3}$ (recall that $T_{\max}=\infty$ by definition when
$r=r_{\star}$). Note that
$(1-c_{\ref{lem:p3}}\eta)^{t}\sqrt{r_{\star}}\leq(1-c_{\ref{lem:p3}}\eta)^{t-T+t_{3}}$
if $T-t_{3}\geq 4\log(r_{\star})/(c_{\ref{lem:p3}}\eta)$ given that $\eta\leq
c_{\eta}$ is sufficiently small. Thus for any $t\geq T$ we have

$\|X_{t}X_{t}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}\leq(1-c_{\ref{lem:p3}}\eta)^{t-T}\|M_{\star}\|.$

It is clear that one may choose such $T$ which also satisfies $T\leq
t_{3}+8/(c_{\ref{lem:p3}}\eta)\leq t_{3}+T_{\min}/16$. We have already shown
in the proof of Theorem 2 that $t_{3}\leq 4\times T_{\min}/16\leq T_{\min}/4$,
thus $T\leq T_{\min}$ as desired.

######  Remark 5.

In the overparameterized setting, our theory guarantees the reconstruction
error to be small until some iteration $T_{\max}$. This is consistent with the
phenomenon known as _early stopping_ in prior works of learning with
overparameterized models (Stöger and Soltanolkotabi,, 2021; Li et al.,, 2018).

##  5 Numerical experiments

In this section, we conduct numerical experiments to demonstrate the efficacy
of ScaledGD($\lambda$) for solving overparameterized low-rank matrix sensing.
We set the ground truth matrix
$X_{\star}=U_{\star}\Sigma_{\star}\in\mathbb{R}^{n\times r_{\star}}$ where
$U_{\star}\in\mathbb{R}^{n\times r_{\star}}$ is a random orthogonal matrix and
$\Sigma_{\star}\in\mathbb{R}^{r_{\star}\times r_{\star}}$ is a diagonal matrix
whose condition number is set to be $\kappa$. We set $n=150$ and
$r_{\star}=3$, and use random Gaussian measurements with $m=10nr_{\star}$. The
overparameterization rank $r$ is set to be $5$ unless otherwise specified.

##### Comparison with overparameterized GD.

We run ScaledGD($\lambda$) and GD with random initialization and compare their
convergence speeds under different condition numbers $\kappa$ of the ground
truth $X_{\star}$; the result is depicted in Figure 1. Even for a moderate
range of $\kappa$, GD slows down significantly while the convergence speed of
ScaledGD($\lambda$) remains almost the same with a almost negligible initial
phase, which is consistent with our theory. The advantage of
ScaledGD($\lambda$) enlarges as $\kappa$ increase, and is already more than
10x times faster than GD when $\kappa=7$.

##### Effect of initialization size.

We study the effect of the initialization scale $\alpha$ on the reconstruction
accuracy of ScaledGD($\lambda$). We fix the learning rate $\eta$ to be a
constant and vary the initialization scale. We run ScaledGD($\lambda$) until
it converges.111More precisely, in accordance with our theory which requires
early stopping, we stop the algorithm once we detected that the training error
no longer decreases significantly for a long time (e.g. $100$ iterations). The
resulting reconstruction errors and their corresponding initialization scales
are plotted in Figure 2. It can be inferred that the reconstruction error
increases with respect to $\alpha$, which is consistent with our theory.

Figure 2: Relative reconstruction error versus initialization scale $\alpha$.
The slope of the dashed line is approximately $1$.

##### Comparison with Zhang et al., (2021).

We compare ScaledGD($\lambda$) with the algorithm $\mathsf{PrecGD}$ proposed
in Zhang et al., (2021), which also has a $\kappa$-independent convergence
rate assuming a sufficiently good initialization using spectral
initialization. However, $\mathsf{PrecGD}$ requires RIP of rank $r$, thus
demanding $O(nr^{2})$ many samples instead of $O(nr_{\star}^{2})$ as in GD and
ScaledGD($\lambda$). This can be troublesome for larger $r$. To demonstrate
this point, we run ScaledGD($\lambda$) and $\mathsf{PrecGD}$ with different
overparameterization rank $r$ while fixing all other parameters. The results
are shown in Figure 3. It can be seen that the convergence rate of
$\mathsf{PrecGD}$ and ScaledGD($\lambda$) are almost the same when the rank is
exactly specified ($r=r_{\star}=3$), though ScaledGD($\lambda$) requires a few
more iterations for the initial phases222Usually this has no significant
implication on the computational cost: the amount of computations required in
the initial phases for ScaledGD($\lambda$) is approximately the same as that
required by the spectral initialization for $\mathsf{PrecGD}$.. When $r$ goes
higher, ScaledGD($\lambda$) is almost unaffected, while $\mathsf{PrecGD}$
suffers from a significant drop in the convergence rate and even breaks down
with a moderate overparameterization $r=20$.

Figure 3: Relative reconstruction error versus the number of iterates with
different overparameterization rank $r$ for ScaledGD($\lambda$) and
$\mathsf{PrecGD}$.

##### Noisy setting.

Though our theoretical results here are formulated in the noiseless setting,
empirical evidence indicates our algorithm ScaledGD($\lambda$) also works in
the noisy setting. Modifying the equation (4) for noiseless measurements, we
assume the noisy measurements $y_{i}=\langle A_{i},M\rangle+\xi_{i}$ where
$\xi_{i}\sim\mathcal{N}(0,\sigma^{2})$ are i.i.d. Gaussian noises. The minimax
lower bound for the reconstruction error
$\|X_{t}X_{t}^{\top}-M_{\star}\|_{\operatorname{\mathsf{F}}}$ is denoted by
$\mathcal{E}_{\mathsf{stat}}=\sigma\sqrt{nr_{\star}}$ (Candès and Plan,,
2011). We compare the reconstruction error of ScaledGD($\lambda$) with
$\mathcal{E}_{\mathsf{stat}}$ under different noise levels $\sigma$. The
results are shown in Figure 4. It can be seen that the final error of
ScaledGD($\lambda$) matches the minimax optimal error
$\mathcal{E}_{\mathsf{stat}}$ within a small multiplicative factor for all
noise levels.

Figure 4: The relative reconstruction error of ScaledGD($\lambda$) versus the
number of iterates for ScaledGD($\lambda$) in the noisy setting, where it is
observed that the final error of ScaledGD($\lambda$) approaches the minimax
error.

##  6 Discussions

This paper demonstrates that an appropriately preconditioned gradient descent
method, called ScaledGD($\lambda$), guarantees an accelerated convergence to
the ground truth low-rank matrix in overparameterized low-rank matrix sensing,
when initialized from a sufficiently small random initialization. Furthermore,
in the case of exact parameterization, our analysis guarantees the fast global
convergence of ScaledGD($\lambda$) from a small random initialization.
Collectively, this complements and represents a major step forward from prior
analyses of ScaledGD (Tong et al., 2021a, ) by allowing overparametrization
and small random initialization. This works opens up a few exciting future
directions that are worth further exploring.

  * •

Asymmetric case. Our current analysis is confined to the recovery of low-rank
positive semidefinite matrices, with only one factor matrix to be recovered.
It remains to generalize this analysis to the recovery of general low-rank
matrices with overparameterization.

  * •

Robust setting. Many applications encounter corrupted measurements that call
for robust recovery algorithms that optimize nonsmooth functions such as the
least absolute deviation loss. One such example is the scaled subgradient
method (Tong et al., 2021b, ), which is the nonsmooth counterpart of ScaledGD
robust to ill-conditioning, and it’ll be interesting to study its performance
under overparameterization.

  * •

Other overparameterized learning models. Our work provides evidence on the
power of preconditioning in accelerating the convergence without hurting
generalization in overparameterized low-rank matrix sensing, which is one kind
of overparameterized learning models. It will be greatly desirable to extend
the insights developed herein to other overparameterized learning models, for
example tensors (Tong et al.,, 2022; Dong et al.,, 2022) and neural networks
(Wang et al.,, 2021).

## Acknowledgements

The work of X. Xu and Y. Chi is supported in part by Office of Naval Research
under N00014-19-1-2404, and by National Science Foundation under CCF-1901199,
DMS-2134080 and ECCS-2126634. The work of C. Ma is supported in part by
National Science Foundation under DMS-2311127.

## References

  * Amari et al., (2020) Amari, S.-i., Ba, J., Grosse, R. B., Li, X., Nitanda, A., Suzuki, T., Wu, D., and Xu, J. (2020).  When does preconditioning help or hurt generalization?  In International Conference on Learning Representations.
  * Bai et al., (2018) Bai, Y., Jiang, Q., and Sun, J. (2018).  Subgradient descent learns orthogonal dictionaries.  In International Conference on Learning Representations.
  * Bhatia, (1997) Bhatia, R. (1997).  Matrix analysis, volume 169.  Springer New York, NY.
  * Burer and Monteiro, (2005) Burer, S. and Monteiro, R. D. C. (2005).  Local minima and convergence in low-rank semidefinite programming.  Mathematical Programming, 103(3):427–444.
  * Candès and Plan, (2010) Candès, E. J. and Plan, Y. (2010).  Matrix completion with noise.  Proceedings of the IEEE, 98(6):925–936.
  * Candès and Plan, (2011) Candès, E. J. and Plan, Y. (2011).  Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements.  IEEE Transactions on Information Theory, 57(4):2342–2359.
  * Chandrasekher et al., (2022) Chandrasekher, K. A., Lou, M., and Pananjady, A. (2022).  Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization.  arXiv preprint arXiv:2207.09660.
  * (8) Chen, J., Liu, D., and Li, X. (2020a).  Nonconvex rectangular matrix completion via gradient descent without $\ell_{2,\infty}$ regularization.  IEEE Transactions on Information Theory, 66(9):5806–5841.
  * Chen and Chi, (2018) Chen, Y. and Chi, Y. (2018).  Harnessing structures in big data via guaranteed low-rank matrix estimation: Recent theory and fast algorithms via convex and nonconvex optimization.  IEEE Signal Processing Magazine, 35(4):14 – 31.
  * Chen et al., (2019) Chen, Y., Chi, Y., Fan, J., and Ma, C. (2019).  Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval.  Mathematical Programming, 176(1-2):5–37.
  * Chen et al., (2021) Chen, Y., Chi, Y., Fan, J., and Ma, C. (2021).  Spectral methods for data science: A statistical perspective.  Foundations and Trends® in Machine Learning, 14(5):566–806.
  * (12) Chen, Y., Chi, Y., Fan, J., Ma, C., and Yan, Y. (2020b).  Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization.  SIAM Journal on Optimization, 30(4):3098–3121.
  * Chi et al., (2019) Chi, Y., Lu, Y. M., and Chen, Y. (2019).  Nonconvex optimization meets low-rank matrix factorization: An overview.  IEEE Transactions on Signal Processing, 67(20):5239–5269.
  * Davenport and Romberg, (2016) Davenport, M. A. and Romberg, J. (2016).  An overview of low-rank matrix recovery from incomplete observations.  IEEE Journal of Selected Topics in Signal Processing, 10(4):608–622.
  * Ding et al., (2021) Ding, L., Jiang, L., Chen, Y., Qu, Q., and Zhu, Z. (2021).  Rank overspecified robust matrix recovery: Subgradient method and exact recovery.  Advances in Neural Information Processing Systems, 34:26767–26778.
  * Dong et al., (2022) Dong, H., Tong, T., Ma, C., and Chi, Y. (2022).  Fast and provable tensor robust principal component analysis via scaled gradient descent.  arXiv preprint arXiv:2206.09109.
  * Geyer et al., (2020) Geyer, K., Kyrillidis, A., and Kalev, A. (2020).  Low-rank regularization and solution uniqueness in over-parameterized matrix sensing.  In International Conference on Artificial Intelligence and Statistics, pages 930–940. PMLR.
  * Gilboa et al., (2019) Gilboa, D., Buchanan, S., and Wright, J. (2019).  Efficient dictionary learning with gradient descent.  In International Conference on Machine Learning, pages 2252–2259. PMLR.
  * Gunasekar et al., (2017) Gunasekar, S., Woodworth, B. E., Bhojanapalli, S., Neyshabur, B., and Srebro, N. (2017).  Implicit regularization in matrix factorization.  In Advances in Neural Information Processing Systems, pages 6151–6159.
  * Jiang et al., (2022) Jiang, L., Chen, Y., and Ding, L. (2022).  Algorithmic regularization in model-free overparameterized asymmetric matrix factorization.  arXiv preprint arXiv:2203.02839.
  * Kim and Chung, (2022) Kim, D. and Chung, H. W. (2022).  Rank-1 matrix completion with gradient descent and small random initialization.  arXiv preprint arXiv:2212.09396.
  * Lee and Stöger, (2022) Lee, K. and Stöger, D. (2022).  Randomly initialized alternating least squares: Fast convergence for matrix sensing.  arXiv preprint arXiv:2204.11516.
  * Li et al., (2021) Li, Y., Ma, C., Chen, Y., and Chi, Y. (2021).  Nonconvex matrix factorization from rank-one measurements.  IEEE Transactions on Information Theory, 67(3):1928–1950.
  * Li et al., (2018) Li, Y., Ma, T., and Zhang, H. (2018).  Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations.  In Conference On Learning Theory, pages 2–47. PMLR.
  * Ma et al., (2021) Ma, C., Li, Y., and Chi, Y. (2021).  Beyond Procrustes: Balancing-free gradient descent for asymmetric low-rank matrix sensing.  IEEE Transactions on Signal Processing, 69:867–877.
  * Ma et al., (2019) Ma, C., Wang, K., Chi, Y., and Chen, Y. (2019).  Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution.  Foundations of Computational Mathematics, pages 1–182.
  * Ma and Fattahi, (2022) Ma, J. and Fattahi, S. (2022).  Global convergence of sub-gradient method for robust matrix recovery: Small initialization, noisy measurements, and over-parameterization.  arXiv preprint arXiv:2202.08788.
  * Oymak and Soltanolkotabi, (2019) Oymak, S. and Soltanolkotabi, M. (2019).  Overparameterized nonlinear learning: Gradient descent takes the shortest path?  In International Conference on Machine Learning, pages 4951–4960. PMLR.
  * Qu et al., (2019) Qu, Q., Li, X., and Zhu, Z. (2019).  A nonconvex approach for exact and efficient multichannel sparse blind deconvolution.  Advances in Neural Information Processing Systems, 32.
  * Recht et al., (2010) Recht, B., Fazel, M., and Parrilo, P. A. (2010).  Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization.  SIAM Review, 52(3):471–501.
  * Rudelson and Vershynin, (2009) Rudelson, M. and Vershynin, R. (2009).  Smallest singular value of a random rectangular matrix.  Communications on Pure and Applied Mathematics, 62(12):1707–1739.
  * Shi and Chi, (2021) Shi, L. and Chi, Y. (2021).  Manifold gradient descent solves multi-channel sparse blind deconvolution provably and efficiently.  IEEE Transactions on Information Theory, 67(7):4784–4811.
  * Soltanolkotabi et al., (2018) Soltanolkotabi, M., Javanmard, A., and Lee, J. D. (2018).  Theoretical insights into the optimization landscape of over-parameterized shallow neural networks.  IEEE Transactions on Information Theory, 65(2):742–769.
  * Stöger and Soltanolkotabi, (2021) Stöger, D. and Soltanolkotabi, M. (2021).  Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction.  Advances in Neural Information Processing Systems, 34:23831–23843.
  * (35) Tong, T., Ma, C., and Chi, Y. (2021a).  Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent.  Journal of Machine Learning Research, 22(150):1–63.
  * (36) Tong, T., Ma, C., and Chi, Y. (2021b).  Low-rank matrix recovery with scaled subgradient methods: Fast and robust convergence without the condition number.  IEEE Transactions on Signal Processing, 69:2396–2409.
  * Tong et al., (2022) Tong, T., Ma, C., Prater-Bennette, A., Tripp, E., and Chi, Y. (2022).  Scaling and scalability: Provable nonconvex low-rank tensor estimation from incomplete measurements.  Journal of Machine Learning Research, 23(163):1–77.
  * Tu et al., (2016) Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M., and Recht, B. (2016).  Low-rank solutions of linear matrix equations via Procrustes flow.  In International Conference Machine Learning, pages 964–973.
  * Vershynin, (2012) Vershynin, R. (2012).  Introduction to the non-asymptotic analysis of random matrices.  In Eldar, Y. C. and Kutyniok, G., editors, Compressed Sensing, pages 210–268. Cambridge University Press.
  * Wang et al., (2021) Wang, T., Buchanan, S., Gilboa, D., and Wright, J. (2021).  Deep networks provably classify data on curves.  Advances in Neural Information Processing Systems, 34:28940–28953.
  * Ye and Du, (2021) Ye, T. and Du, S. S. (2021).  Global convergence of gradient descent for asymmetric low-rank matrix factorization.  Advances in Neural Information Processing Systems, 34:1429–1439.
  * Zhang et al., (2022) Zhang, G., Fattahi, S., and Zhang, R. Y. (2022).  Preconditioned gradient descent for overparameterized nonconvex burer–monteiro factorization with global optimality certification.  arXiv preprint arXiv:2206.03345.
  * Zhang et al., (2021) Zhang, J., Fattahi, S., and Zhang, R. Y. (2021).  Preconditioned gradient descent for over-parameterized nonconvex matrix factorization.  Advances in Neural Information Processing Systems, 34:5985–5996.
  * Zhang, (2021) Zhang, R. Y. (2021).  Sharp global guarantees for nonconvex low-rank matrix recovery in the overparameterized regime.  arXiv preprint arXiv:2104.10790.
  * Zhang, (2022) Zhang, R. Y. (2022).  Improved global guarantees for the nonconvex Burer–Monteiro factorization via rank overparameterization.  arXiv preprint arXiv:2207.01789.
  * Zheng and Lafferty, (2015) Zheng, Q. and Lafferty, J. (2015).  A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements.  In Advances in Neural Information Processing Systems, pages 109–117.
  * Zhuo et al., (2021) Zhuo, J., Kwon, J., Ho, N., and Caramanis, C. (2021).  On the computational and statistical complexity of over-parameterized matrix sensing.  arXiv preprint arXiv:2102.02756.

##  Appendix A Preliminaries

This section collects several preliminary results that are useful in later
proofs. In general, for a matrix $A$, we will denote by $U_{A}$ the first
factor in its compact SVD $A=U_{A}\Sigma_{A}V_{A}^{\top}$, unless otherwise
specified.

###  A.1 Proof of Lemma 2

It is a standard result in random matrix theory (Vershynin,, 2012; Rudelson
and Vershynin,, 2009) that an $M\times N$ ($M\geq N$) random matrix $G_{0}$
with i.i.d. standard Gaussian entries satisfies

$\displaystyle\mathbb{P}\left(\|G_{0}\|\leq
4\big{(}\sqrt{M}+\sqrt{N}\big{)}\right)$ $\displaystyle\geq 1-\exp(-M/C),$
(30a)
$\displaystyle\mathbb{P}\left(\sigma_{\min}(G_{0})\geq\varepsilon\big{(}\sqrt{M}-\sqrt{N-1}\big{)}\right)$
$\displaystyle\geq 1-(C\varepsilon)^{M-N+1}-\exp(-M/C),$ (30b)

for some universal constant $C>0$ and for any $\varepsilon>0$. Applying (30a)
to the random matrix $\sqrt{n}G$ which is an $n\times r$ random matrix with
i.i.d. standard Gaussian entries, we have

$\|G\|\leq 4(\sqrt{n}+\sqrt{r})/\sqrt{n}\leq 8$

with probability at least $1-\exp(-n/C)$.

Turning to the bound on $\sigma_{\min}^{-1}(\widehat{U}^{\top}G)$, observe
that $\sqrt{n}\widehat{U}^{\top}G$ is a $r_{\star}\times r$ random matrix with
i.i.d. standard Gaussian entries, thus applying (30b) to
$\sqrt{n}\widehat{U}^{\top}G$ with $\varepsilon=(2n)^{-C_{G}+1}$ yields

$\sigma_{\min}^{-1}(\widehat{U}^{\top}G)\leq(2n)^{C_{G}-1}(\sqrt{r}-\sqrt{r_{\star}-1})^{-1}\leq(2n)^{C_{G}-1}(2\sqrt{r})\leq(2n)^{C_{G}}$

with probability at least $1-(2n/C)^{-(C_{G}-1)(r-r_{\star}+1)}-\exp(-n/C)$.
Here, the second inequality follows from

$\frac{1}{\sqrt{r}-\sqrt{r_{\star}-1}}\leq\frac{1}{\sqrt{r}-\sqrt{r-1}}=\sqrt{r}+\sqrt{r-1}<2\sqrt{r}.$

Combining the above two bounds directly implies the desired probability bound
if we choose $c=1/C$ and choose a large $C_{G}$ such that $C_{G}\geq 8$ and
$C_{G}-1\geq C_{G}/2$.

###  A.2 Proof of Proposition 1

Using the definitions of $S_{t}$ and $N_{t}$, we have

$\displaystyle
X_{t}=(U_{\star}U_{\star}^{\top}+U_{{\star,\perp}}U_{{\star,\perp}}^{\top})X_{t}$
$\displaystyle=U_{\star}S_{t}+U_{{\star,\perp}}N_{t}$
$\displaystyle=U_{\star}\widetilde{S}_{t}V_{t}^{\top}+U_{{\star,\perp}}N_{t}(V_{t}V_{t}^{\top}+V_{{t,\perp}}V_{{t,\perp}}^{\top})$
$\displaystyle=U_{\star}\widetilde{S}_{t}V_{t}^{\top}+U_{{\star,\perp}}\widetilde{N}_{t}V_{t}^{\top}+U_{{\star,\perp}}\widetilde{O}_{t}V_{{t,\perp}}^{\top},$

where in the second line, we used the relation
$\widetilde{S}_{t}=S_{t}V_{t}=U_{t}\Sigma_{t}V_{t}^{\top}V_{t}=U_{t}\Sigma_{t}$
and thus

$S_{t}=\widetilde{S}_{t}V_{t}^{\top}.$ (31)

###  A.3 Consequences of RIP

The first result is a standard consequence of RIP, see, for example Stöger and
Soltanolkotabi, (2021, Lemma 7.3).

######  Lemma 7.

Suppose that the linear map
$\mathcal{A}:\operatorname{Sym}_{2}(\mathbb{R}^{n})\to\mathbb{R}^{m}$
satisfies Assumption 1. Then we have

$\|(\operatorname{\mathcal{I}}-\mathcal{A^{*}A})(Z)\|\leq\delta\|Z\|_{\operatorname{\mathsf{F}}}$

for any $Z\in\operatorname{Sym}_{2}(\mathbb{R}^{n})$ with rank at most
$r_{\star}$.

We need another straightforward consequence of RIP, given by the following
lemma.

######  Lemma 8.

Under the same setting as Lemma 7, we have

$\|(\operatorname{\mathcal{I}}-\mathcal{A^{*}A})(Z)\|\leq 2\delta\sqrt{(r\lor
r_{\star})/r_{\star}}\|Z\|_{\operatorname{\mathsf{F}}}\leq\frac{2(r\lor
r_{\star})\delta}{\sqrt{r_{\star}}}\|Z\|$

for any $Z\in\operatorname{Sym}_{2}(\mathbb{R}^{n})$ with rank at most $r$.

###### Proof.

Without loss of generality we may assume $r\geq r_{\star}$, thus $r\lor
r_{\star}=r$. We claim that it is possible to decompose $Z=\sum_{i\leq\lceil
r/r_{\star}\rceil}Z_{i}$ where
$Z_{i}\in\operatorname{Sym}_{2}(\mathbb{R}^{n})$,
$\operatorname{\mathrm{rank}}(Z_{i})\leq r_{\star}$ and $Z_{i}Z_{j}=0$ if
$i\neq j$. To see why this is the case, notice the spectral decomposition of
$Z$ gives $r$ rank-one components that are mutually orthogonal, thus we may
divide them into $\lceil r/r_{\star}\rceil$ subgroups indexed by
$i=1,\ldots,\lceil r/r_{\star}\rceil$, such that each subgroup contains at
most $r_{\star}$ components. Let $Z_{i}$ be the sum of the components in the
subgroup $i$, it is easy to check that $Z_{i}$ has the desired property.

The property of the decomposition yields

$\|Z\|_{\operatorname{\mathsf{F}}}^{2}=\operatorname{\mathrm{tr}}(Z^{2})=\sum_{i,j\leq\lceil
r/r_{\star}\rceil}\operatorname{\mathrm{tr}}(Z_{i}Z_{j})=\sum_{i\leq\lceil
r/r_{\star}\rceil}\|Z_{i}\|_{\operatorname{\mathsf{F}}}^{2}.$ (32)

But for each $Z_{i}$, Lemma 7 implies

$\|(\operatorname{\mathcal{I}}-\mathcal{A^{*}A})(Z_{i})\|\leq\delta\|Z_{i}\|_{\operatorname{\mathsf{F}}}.$

Summing up for $i\leq\lceil r/r_{\star}\rceil$ yields

$\|(\operatorname{\mathcal{I}}-\mathcal{A^{*}A})(Z)\|\leq\sum_{i\leq\lceil
r/r_{\star}\rceil}\|(\operatorname{\mathcal{I}}-\mathcal{A^{*}A})(Z_{i})\|\leq\delta\sum_{i\leq\lceil
r/r_{\star}\rceil}\|Z_{i}\|_{\operatorname{\mathsf{F}}}\leq\delta\sqrt{\lceil
r/r_{\star}\rceil}\,\|Z\|_{\operatorname{\mathsf{F}}},$

where the last inequality follows from (32) and from Cauchy-Schwarz
inequality.

The first inequality in Lemma 8 follows from the above inequality by noting
that $\lceil r/r_{\star}\rceil\leq 2r/r_{\star}$ given $r\geq r_{\star}$ which
was assumed in the beginning of the proof. The second inequality in Lemma 8
follows from $\|Z\|_{\operatorname{\mathsf{F}}}\leq\sqrt{r}\|Z\|$. ∎

###  A.4 Matrix perturbation results

The next few results are all on matrix perturbations. We first present a
perturbation result on matrix inverse.

######  Lemma 9.

Assume that $A,B$ are square matrices of the same dimension, and that $A$ is
invertible. If $\|A^{-1}B\|\leq 1/2$, then

$(A+B)^{-1}=A^{-1}+A^{-1}BQA^{-1},\quad\text{for some }\|Q\|\leq 2.$

Similarly, if $\|BA^{-1}\|\leq 1/2$, then we have

$(A+B)^{-1}=A^{-1}+A^{-1}QBA^{-1},\quad\text{for some }\|Q\|\leq 2.$

In particular, if $\|B\|\leq\sigma_{\min}(A)/2$, then both of the above
equations hold.

###### Proof.

The claims follow from the identity

$(A+B)^{-1}=A^{-1}-A^{-1}B(I+A^{-1}B)^{-1}A^{-1}=A^{-1}-A^{-1}(I+BA^{-1})^{-1}BA^{-1}.$

For the first claim when $\|A^{-1}B\|\leq 1/2$, we set $Q:=-(I+A^{-1}B)^{-1}$,
which satisfies $\|Q\|=\|(I+A^{-1}B)^{-1}\|\leq\frac{1}{1-\|A^{-1}B\|}\leq 2$.
The second claim follows similarly. Finally, we note that when
$\|B\|\leq\sigma_{\min}(A)/2$, it holds

$\|A^{-1}B\|\leq\frac{1}{\sigma_{\min}(A)}\|B\|\leq\frac{1}{2}\qquad\mbox{and}\qquad\|BA^{-1}\|\leq\|B\|\frac{1}{\sigma_{\min}(A)}\leq\frac{1}{2},$

thus completing the proof. ∎

Next, we focus on the minimum singular value of certain matrix of form $I+AB$.

######  Lemma 10.

If $A$, $B$ are positive definite matrices of the same size, we have

$\sigma_{\min}(I+AB)\geq\kappa^{-1/2}(A),\quad\text{where
}\kappa(A)\coloneqq\frac{\|A\|}{\sigma_{\min}(A)}.$

###### Proof.

Writing $I+AB=A^{1/2}(I+A^{1/2}BA^{1/2})A^{-1/2}$, we obtain

$\sigma_{\min}(I+AB)\geq\sigma_{\min}(A^{1/2})\sigma_{\min}(A^{-1/2})\sigma_{\min}(I+A^{1/2}BA^{1/2}).$

The proof is completed by noting that
$\sigma_{\min}(A^{1/2})=\sigma_{\min}^{1/2}(A)$,
$\sigma_{\min}(A^{-1/2})=\|A\|^{-1/2}$, and that
$\sigma_{\min}(I+A^{1/2}BA^{1/2})\geq 1$ since $A^{1/2}BA^{1/2}$ is positive
semidefinite. ∎

The last result still concerns the minimum singular value of a matrix of
interest.

######  Lemma 11.

There exists a universal constant $c_{\ref{lem:la-aux}}>0$ such that if
$\Lambda$ is a positive definite matrix obeying $\|\Lambda\|\leq
c_{\ref{lem:la-aux}}$ and $\sigma_{\min}(Y)\leq 1/3$, then for any $\eta\leq
c_{\ref{lem:la-aux}}$ we have

$\sigma_{\min}\Big{(}\\!\left((1-\eta)I+\eta(YY^{\top}+\Lambda)^{-1}\right)Y\Big{)}\geq\left(1+\frac{\eta}{6}\right)\sigma_{\min}(Y).$
(33)

###### Proof.

Denote $Z=YY^{\top}$ and let $U\Sigma U^{\top}=Z+\Lambda$ be the spectral
decomposition of $Z+\Lambda$. By a coordinate transform one may assume
$Z+\Lambda=\Sigma$. It suffices to show

$\lambda_{\min}\Big{(}\\!\left((1-\eta)I+\eta\Sigma^{-1}\right)Z\left((1-\eta)I+\eta\Sigma^{-1}\right)\\!\Big{)}\geq\left(1+\frac{1}{6}\eta\right)^{2}\lambda_{\min}(Z).$
(34)

For simplicity we denote $\zeta=\lambda_{\min}(Z)$, which is by assumption
smaller than $1/9$. Fix $K=1/4$ so that $K\geq 2\zeta+4c_{\ref{lem:la-aux}}$
by choosing $c_{\ref{lem:la-aux}}$ to be small enough. By permuting
coordinates we may further assume that the diagonal matrix $\Sigma$ is of the
following form:

$\Sigma=\begin{bmatrix}\Sigma_{\leq K}&\\\ &\Sigma_{>K}\end{bmatrix},$ (35)

where $\Sigma_{\leq K}$, $\Sigma_{>K}$ are diagonal matrices such that
$\lambda_{\max}(\Sigma_{\leq K})\leq K$ and $\lambda_{\min}(\Sigma_{>K})>K$.
It suffices to consider the case where $\Sigma_{>K}$ is not degenerate,
because otherwise $\lambda_{\max}(\Sigma)\leq K\leq 1/2$, and the desired (34)
follows as

$\displaystyle\lambda_{\min}\Big{(}\\!\left((1-\eta)I+\eta\Sigma^{-1}\right)Z\left((1-\eta)I+\eta\Sigma^{-1}\right)\\!\Big{)}\geq\big{(}1-\eta+\eta\lambda_{\max}^{-1}(\Sigma)\big{)}^{2}\lambda_{\min}(Z)\geq(1+\eta)^{2}\lambda_{\min}(Z).$

For the rest of the proof, we assume the block corresponding to $\Sigma_{>K}$
is not degenerate.

Divide $Z$ into blocks of the same shape as (35):

$Z=\begin{bmatrix}Z_{0}&A\\\ A^{\top}&Z_{1}\end{bmatrix}.$ (36)

The purpose of such division is to facilitate computation of minimum
eigenvalues by Schur’s complement lemma. For preparation, we make a few simple
observations. Since $Z=\Sigma-\Lambda$, we see that $A$ being an off-diagonal
submatrix of $Z$ satisfies $\|A\|\leq\|\Lambda\|\leq c_{\ref{lem:la-aux}}$,
and similarly $\|Z_{0}-\Sigma_{\leq K}\|\leq c_{\ref{lem:la-aux}}$,
$\|Z_{1}-\Sigma_{>K}\|\leq c_{\ref{lem:la-aux}}$. In particular, we have

$\lambda_{\min}(Z_{1})\geq\lambda_{\min}(\Sigma_{>K})-c_{\ref{lem:la-
aux}}>K-c_{\ref{lem:la-aux}}\geq 2\zeta+3c_{\ref{lem:la-aux}}>\zeta,$ (37)

which implies $Z_{1}-\zeta I$ is positive definite and invertible. Thus by
Schur’s complement lemma, $Z\succeq\zeta I$ is equivalent to

$Z_{0}-\zeta I-A(Z_{1}-\zeta I)^{-1}A^{\top}\succeq 0,$ (38)

which provides an analytic characterization for the minimum eigenvalue $\zeta$
of $Z$.

The rest of the proof follows from the following steps: we will first show
again by Schur’s complement lemma that (34) admits a similar analytic
characterization. More precisely, denoting
$\zeta^{\prime}=(1+\frac{\eta}{6})^{2}\zeta$,
$\Sigma_{0}=(1-\eta)I+\eta\Sigma_{\leq K}^{-1}$ and
$\Sigma_{1}=(1-\eta)I+\eta\Sigma_{>K}^{-1}$, then (34) is equivalent to

$Z_{0}-\zeta^{\prime}\Sigma_{0}^{-2}-A(Z_{1}-\zeta^{\prime}\Sigma_{1}^{-2})^{-1}A^{\top}\succeq
0.$ (39)

After proving they are equivalent, we will prove that (39) holds as long as
the following sufficient condition holds

$Z_{0}-(1+3\eta)^{-2}\zeta^{\prime}I-A(Z_{1}-\zeta I)^{-1}A^{\top}-10\eta\zeta
A(Z_{1}-\zeta I)^{-2}A^{\top}\succeq 0.$ (40)

In the last step, we establish the above sufficient condition to complete the
proof.

##### Step 1: equivalence between (34) and (39).

First notice that

$\left((1-\eta)I+\eta\Sigma^{-1}\right)Z\left((1-\eta)I+\eta\Sigma^{-1}\right)=\begin{bmatrix}\Sigma_{0}Z_{0}\Sigma_{0}&\Sigma_{0}A\Sigma_{1}\\\
\Sigma_{1}A^{\top}\Sigma_{0}&\Sigma_{1}Z_{1}\Sigma_{1}\end{bmatrix}.$ (41)

In order to invoke Schur’s complement lemma, we need to verify
$\Sigma_{1}Z_{1}\Sigma_{1}-\zeta^{\prime}I\succ 0$. Observe that by definition
we have

$\Sigma_{0}\succeq\big{(}1+(K^{-1}-1)\eta\big{)}I=(1+3\eta)I,\quad\Sigma_{1}\succeq(1-\eta)I.$
(42)

Hence

$\Sigma_{1}Z_{1}\Sigma_{1}-\zeta^{\prime}I\succeq(1-\eta)^{2}Z_{1}-\left(1+\frac{1}{6}\eta\right)^{2}\zeta
I\succ 2(1-\eta)^{2}\zeta I-\left(1+\frac{1}{6}\eta\right)^{2}\zeta I\succ 0,$

where in the second inequality we used $Z_{1}-2\zeta I\succ 0$ proved in (37),
and in the last inequality we used $\eta\leq c_{\eta}$ with $c_{\eta}$
sufficiently small. This completes the verification that
$\Sigma_{1}Z_{1}\Sigma_{1}-\zeta^{\prime}I\succ 0$. Now, invoking Schur’s
complement lemma yields that (34) is equivalent to

$\Sigma_{0}Z_{0}\Sigma_{0}-\zeta^{\prime}I-\Sigma_{0}A\Sigma_{1}(\Sigma_{1}Z_{1}\Sigma_{1}-\zeta^{\prime}I)^{-1}\Sigma_{1}A^{\top}\Sigma_{0}\succeq
0,$

which simplifies easily to (39), as claimed.

##### Step 2: establishing (40) as a sufficient condition for (39).

By (42), it follows that

$\displaystyle(Z_{1}-\zeta^{\prime}\Sigma_{1}^{-2})^{-1}$
$\displaystyle\preceq(Z_{1}-(1-\eta)^{-2}\zeta^{\prime}I)^{-1}$
$\displaystyle=\Big{(}Z_{1}-\zeta
I-\big{(}(1-\eta)^{-2}\zeta^{\prime}-\zeta\big{)}I\Big{)}^{-1},$ (43)

where we used the well-known fact that $A\preceq B$ implies $B^{-1}\preceq
A^{-1}$ for positive definite matrices $A$ and $B$ (cf. (Bhatia,, 1997,
Proposition V.1.6)). We aim to apply Lemma 9 to control the above term, by
treating $((1-\eta)^{-2}\zeta^{\prime}-\zeta)I$ as a perturbation term. For
this purpose we need to verify

$\left|(1-\eta)^{-2}\zeta^{\prime}-\zeta\right|\leq\frac{1}{2}\lambda_{\min}(Z_{1}-\zeta
I).$ (44)

Given $\eta\leq c_{\eta}$ with sufficiently small $c_{\eta}$, we have
$(1-\eta)^{-2}\leq 1+3\eta$, $(1+\frac{1}{6}\eta)^{2}\leq 1+\eta$, and
$(1+3\eta)(1+\eta)\leq 1+5\eta$, thus

$0\leq(1-\eta)^{-2}\big{(}1+\frac{1}{6}\eta\big{)}^{2}\zeta-\zeta=(1-\eta)^{-2}\zeta^{\prime}-\zeta\leq(1+3\eta)(1+\eta)\zeta-\zeta\leq
5\eta\zeta<\zeta/2,$

where the last inequality follows from $c_{\eta}\leq 1/10$. On the other hand,
invoking (37), we obtain

$\frac{1}{2}\zeta\leq\frac{1}{2}\big{(}\lambda_{\min}(Z_{1})-\zeta\big{)}=\frac{1}{2}\lambda_{\min}(Z_{1}-\zeta
I),$

which verifies (44). Thus we may apply Lemma 9 to show

$\displaystyle\left\|(Z_{1}-\zeta I)\left((Z_{1}-\zeta
I)^{-1}-\left(Z_{1}-\zeta
I-((1-\eta)^{-2}\zeta^{\prime}-\zeta)I\right)^{-1}\right)(Z_{1}-\zeta
I)\right\|\leq 2\left|(1-\eta)^{-2}\zeta^{\prime}-\zeta\right|\leq
10\eta\zeta,$

therefore

$\left(Z_{1}-\zeta
I-((1-\eta)^{-2}\zeta^{\prime}-\zeta)I\right)^{-1}\preceq(Z_{1}-\zeta
I)^{-1}+10\eta\zeta(Z_{1}-\zeta I)^{-2}.$

Together with (43), this implies

$(Z_{1}-\zeta^{\prime}\Sigma_{1}^{-2})^{-1}\preceq(Z_{1}-\zeta
I)^{-1}+10\eta\zeta(Z_{1}-\zeta I)^{-2}.$ (45)

Combining (42) and (45), we see that a sufficient condition for (39) to hold
is (40).

##### Step 3: establishing (40).

It is clear that (40) is implied by

$\zeta I-(1+3\eta)^{-2}\zeta^{\prime}I-10\eta\zeta A(Z_{1}-\zeta
I)^{-2}A^{\top}\succeq 0,$ (46)

by leveraging the relation $Z_{0}\succeq\zeta I+A(Z_{1}-\zeta I)^{-1}A^{\top}$
from (38).

Hence, it boils down to prove (46). Recalling $\|A\|\leq c_{\ref{lem:la-
aux}}$, and from (37), we know $\lambda_{\min}(Z_{1}-\zeta I)\geq
K-c_{\ref{lem:la-aux}}-\zeta\geq\zeta+3c_{\ref{lem:la-aux}}$. Thus

$\|A(Z_{1}-\zeta I)^{-2}A^{\top}\|\leq\|A\|^{2}\|(Z_{1}-\zeta I)^{-2}\|\leq
c_{\ref{lem:la-aux}}^{2}/(\zeta+3c_{\ref{lem:la-aux}})^{2}\leq 1/9.$

Therefore, to prove (46) it suffices to show

$\zeta-(1+3\eta)^{-2}\zeta^{\prime}\geq\frac{10}{9}\eta\zeta.$ (47)

It is easy to verify that the above inequality holds for our choice
$\zeta^{\prime}=(1+\frac{1}{6}\eta)^{2}\zeta$. In fact, given $\eta\leq
c_{\eta}$ for sufficiently small $c_{\eta}$, we have $(1+3\eta)^{-2}\leq
1-4\eta$, $(1+\frac{1}{6}\eta)^{2}\leq 1+\eta$. These together yield

$\zeta-(1+3\eta)^{-2}\big{(}1+\frac{1}{6}\eta\big{)}^{2}\zeta\geq\zeta-(1-4\eta)(1+\eta)\zeta=3\eta\zeta+4\eta^{2}\zeta\geq
3\eta\zeta\geq\frac{10}{9}\eta\zeta,$

establishing (47) as desired. ∎

##  Appendix B Decompositions of key terms

In this section, we first present a useful bound of a key error quantity

$\Delta_{t}\coloneqq(\operatorname{\mathcal{I}}-\mathcal{A^{*}A})(X_{t}X_{t}^{\top}-M_{\star}),$
(48)

where $X_{t}$ is the iterate of ScaledGD($\lambda$) given in (7).

######  Lemma 12.

Suppose $\mathcal{A}(\cdot)$ satisfies Assumption 1. For any $t\geq 0$ such
that (22) holds, we have

$\|\Delta_{t}\|\leq
8\delta\left(\|\widetilde{S}_{t}\widetilde{S}_{t}^{\top}-\Sigma_{\star}^{2}\|_{\operatorname{\mathsf{F}}}+\|\widetilde{S}_{t}\|\|\widetilde{N}_{t}\|_{\operatorname{\mathsf{F}}}+n\|\widetilde{O}_{t}\|^{2}\right).$
(49)

In particular, there exists some constant $c_{\ref{lem:Delta-bound}}\lesssim
c_{\delta}/c_{\lambda}^{3}$ such that

$\|\Delta_{t}\|\leq
16(C_{\ref{lem:p1.5}.a}+1)^{2}c_{\delta}\kappa^{-2C_{\delta}/3}\|X_{\star}\|^{2}\leq
c_{\ref{lem:Delta-bound}}\kappa^{-2C_{\delta}/3}\|X_{\star}\|^{2}.$ (50)

###### Proof.

The decomposition (19) in Proposition 1 yields

$X_{t}X_{t}^{\top}=U_{\star}\widetilde{S}_{t}\widetilde{S}_{t}^{\top}U_{\star}^{\top}+U_{\star}\widetilde{S}_{t}\widetilde{N}_{t}^{\top}U_{{\star,\perp}}^{\top}+U_{{\star,\perp}}\widetilde{N}_{t}\widetilde{S}_{t}^{\top}U_{\star}^{\top}+U_{{\star,\perp}}\widetilde{N}_{t}\widetilde{N}_{t}^{\top}U_{{\star,\perp}}^{\top}+U_{{\star,\perp}}\widetilde{O}_{t}\widetilde{O}_{t}^{\top}U_{{\star,\perp}}^{\top}.$

Since $M_{\star}=U_{\star}\Sigma_{\star}^{2}U_{\star}^{\top}$, we have

$X_{t}X_{t}^{\top}-M_{\star}=\underbrace{U_{\star}(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}-\Sigma_{\star}^{2})U_{\star}^{\top}}_{=:T_{1}}+\underbrace{U_{\star}\widetilde{S}_{t}\widetilde{N}_{t}^{\top}U_{{\star,\perp}}^{\top}+U_{{\star,\perp}}\widetilde{N}_{t}\widetilde{S}_{t}^{\top}U_{\star}^{\top}}_{=:T_{2}}+\underbrace{U_{{\star,\perp}}\widetilde{N}_{t}\widetilde{N}_{t}^{\top}U_{{\star,\perp}}^{\top}}_{=:T_{3}}+\underbrace{U_{{\star,\perp}}\widetilde{O}_{t}\widetilde{O}_{t}^{\top}U_{{\star,\perp}}^{\top}}_{=:T_{4}}.$
(51)

Note that $U_{\star}\in\mathbb{R}^{n\times r_{\star}}$ is of rank $r_{\star}$,
thus $T_{1}$ has rank at most $r_{\star}$ and $T_{2}$ has rank at most
$2r_{\star}$. Similarly, since $\widetilde{N}_{t}=N_{t}V_{t}$ while
$V_{t}\in\mathbb{R}^{r\times r_{\star}}$ is of rank $r_{\star}$, $T_{3}$ has
rank at most $r_{\star}$. It is also trivial that $T_{4}$ as an $n\times n$
matrix has rank at most $n$. Invoking Lemma 8, we obtain

$\displaystyle\|(\operatorname{\mathcal{I}}-\mathcal{A^{*}A})(T_{1})\|$
$\displaystyle\leq
2\delta\|U_{\star}(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}-\Sigma_{\star}^{2})U_{\star}^{\top}\|_{\operatorname{\mathsf{F}}}\leq
2\delta\|\widetilde{S}_{t}\widetilde{S}_{t}^{\top}-\Sigma_{\star}^{2}\|_{\operatorname{\mathsf{F}}},$
$\displaystyle\|(\operatorname{\mathcal{I}}-\mathcal{A^{*}A})(T_{2})\|$
$\displaystyle\leq
2\sqrt{3}\delta\|U_{\star}\widetilde{S}_{t}\widetilde{N}_{t}^{\top}U_{{\star,\perp}}^{\top}+U_{{\star,\perp}}\widetilde{N}_{t}\widetilde{S}_{t}^{\top}U_{\star}^{\top}\|_{\operatorname{\mathsf{F}}}\leq
4\sqrt{2}\delta\|\widetilde{S}_{t}\|\|\widetilde{N}_{t}\|_{\operatorname{\mathsf{F}}},$
$\displaystyle\|(\operatorname{\mathcal{I}}-\mathcal{A^{*}A})(T_{3})\|$
$\displaystyle\leq
2\delta\|U_{{\star,\perp}}\widetilde{N}_{t}\widetilde{N}_{t}^{\top}U_{{\star,\perp}}^{\top}\|_{\operatorname{\mathsf{F}}}\leq
2\delta\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|\|\widetilde{S}_{t}\|\|\Sigma_{\star}^{-1}\|\|\widetilde{N}_{t}\|_{\operatorname{\mathsf{F}}}\leq\delta\|\widetilde{S}_{t}\|\|\widetilde{N}_{t}\|_{\operatorname{\mathsf{F}}},$
$\displaystyle\|(\operatorname{\mathcal{I}}-\mathcal{A^{*}A})(T_{4})\|$
$\displaystyle\leq 2\delta
n\|U_{{\star,\perp}}\widetilde{O}_{t}\widetilde{O}_{t}^{\top}U_{{\star,\perp}}^{\top}\|\leq
2\delta n\|\widetilde{O}_{t}\|^{2},$

where the third line follows from
$\|\Sigma_{\star}^{-1}\|=\kappa\|X_{\star}\|^{-1}$ and from (22c) in view that
$C_{\delta}$ is sufficiently large and $c_{\ref{lem:p1.5}}$ is sufficiently
small. The conclusion (49) follows from summing up the above inequalities.

For the remaining part of the lemma, note that the following inequalities that
bound the individual terms of (49) can be inferred from (22): namely,

$\|\widetilde{S}_{t}\widetilde{S}_{t}^{\top}-\Sigma_{\star}\|_{\operatorname{\mathsf{F}}}\leq\sqrt{2r_{\star}}\|\widetilde{S}_{t}\widetilde{S}_{t}^{\top}-\Sigma_{\star}\|\leq\sqrt{2r_{\star}}(C_{\ref{lem:p1.5}.a}^{2}\kappa^{2}+1)\|X_{\star}\|^{2}$

by (22d), and

$\displaystyle\|\widetilde{S}_{t}\|\|\widetilde{N}_{t}\|_{\operatorname{\mathsf{F}}}$
$\displaystyle\leq\sqrt{r_{\star}}\|\widetilde{S}_{t}\|\|\widetilde{N}_{t}\|$
$\displaystyle\leq\sqrt{r_{\star}}(C_{\ref{lem:p1.5}.a}\kappa\|X_{\star}\|)\cdot\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|\cdot\|\widetilde{S}_{t}\|\cdot\|\Sigma_{\star}^{-1}\|$
$\displaystyle\leq\sqrt{r_{\star}}(C_{\ref{lem:p1.5}.a}\kappa\|X_{\star}\|)\cdot(c_{\ref{lem:p1.5}}\kappa^{-C_{\delta}/2}\|X_{\star}\|)\cdot(C_{\ref{lem:p1.5}.a}\kappa\|X_{\star}\|)\cdot\sigma_{\min}^{-1}(\Sigma_{\star})$
$\displaystyle=\sqrt{r_{\star}}c_{\ref{lem:p1.5}}C_{\ref{lem:p1.5}.a}^{2}\kappa^{3}\|X_{\star}\|^{2}\kappa^{-C_{\delta}/2}$
$\displaystyle\leq\sqrt{r_{\star}}C_{\ref{lem:p1.5}.a}^{2}\|X_{\star}\|^{2},$

where the first inequality uses the fact that $\widetilde{N}_{t}=N_{t}V_{t}$
contains a rank-$r_{\star}$ factor $V_{t}$, hence has rank at most
$r_{\star}$; the second line follows from (22d), the third line follows from
(22c) and (22d), and the last line follows from choosing $c_{\delta}$
sufficiently small such that $c_{\ref{lem:p1.5}}\leq 1$ (which is possible
since $c_{\ref{lem:p1.5}}\lesssim c_{\delta}/c_{\lambda}^{3})$ and from
choosing $C_{\delta}\geq 6$ such that $\kappa^{3}\kappa^{-C_{\delta}/2}\leq
1$. Finally, from (22b) and its corollary (24), we have

$2n\|\widetilde{O}_{t}\|^{2}\leq
2n\alpha^{3/2}\|X_{\star}\|^{1/2}\leq\|X_{\star}\|^{2},$

since from (12c) it is easy to show that $\alpha\leq(2n)^{-2/3}\|X_{\star}\|$.

Combining these inequalities and (49) yields

$\|\Delta_{t}\|\leq
8\delta\sqrt{r_{\star}}(\sqrt{2}C_{\ref{lem:p1.5}.a}^{2}\kappa^{2}+1+C_{\ref{lem:p1.5}.a}^{2}+1)\|X_{\star}\|^{2}\leq
16\delta\sqrt{r_{\star}}\kappa^{2}(C_{\ref{lem:p1.5}.a}^{2}+1)\|X_{\star}\|^{2}.$
(52)

Recalling that by (10) we have $\delta\sqrt{r_{\star}}\kappa^{2}\leq
c_{\delta}\kappa^{-C_{\delta}+2}\leq c_{\delta}\kappa^{-2C_{\delta}/3}$ as
long as $C_{\delta}\geq 6$, we obtain the desired conclusion. We may choose
$c_{\ref{lem:Delta-bound}}=32(C_{\ref{lem:p1.5}.a}+1)^{2}c_{\delta}$, and the
bound $c_{\ref{lem:Delta-bound}}\lesssim c_{\delta}/c_{\lambda}\lesssim
c_{\delta}/c_{\lambda}^{3}$ follows from $C_{\ref{lem:p1.5}.a}\lesssim
c_{\lambda}^{-1/2}$. ∎

We next present several useful decompositions of the signal term $S_{t+1}$ and
the noise term $N_{t+1}$, which are extremely useful in later developments.

######  Lemma 13.

For any $t$ such that $\widetilde{S}_{t}$ is invertible and (22) holds, we
have

$\displaystyle S_{t+1}$
$\displaystyle=\left((1-\eta)I+\eta(\Sigma_{\star}^{2}+\lambda
I+{E}^{a}_{t})(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\right)\widetilde{S}_{t}V_{t}^{\top}+\eta{E}^{b}_{t},$ (53a)
$\displaystyle N_{t+1}$
$\displaystyle=\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\left((1-\eta)\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I+\eta{E}^{c}_{t}\right)(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}V_{t}^{\top}$
$\displaystyle\qquad+\eta{E}^{e}_{t}(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}V_{t}^{\top}+\widetilde{O}_{t}V_{{t,\perp}}^{\top}+\eta{E}^{d}_{t},$
(53b)

where the error terms satisfy

$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|{E}^{a}_{t}|\kern-1.07639pt|\kern-1.07639pt|}$
$\displaystyle\leq
2c_{\ref{lem:p1.5}}\kappa^{-4}\|X_{\star}\|\cdot{|\kern-1.07639pt|\kern-1.07639pt|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}|\kern-1.07639pt|\kern-1.07639pt|}+2{|\kern-1.07639pt|\kern-1.07639pt|U_{\star}^{\top}\Delta_{t}|\kern-1.07639pt|\kern-1.07639pt|},$
(54a)
$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|{E}^{b}_{t}|\kern-1.07639pt|\kern-1.07639pt|}$
$\displaystyle\leq\left(\frac{\|\widetilde{O}_{t}\|}{\sigma_{\min}(\widetilde{S}_{t})}\right)^{3/4}\sigma_{\min}(\widetilde{S}_{t})\leq\frac{1}{20}\kappa^{-10}\sigma_{\min}(\widetilde{S}_{t}),$
(54b)
$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|{E}^{c}_{t}|\kern-1.07639pt|\kern-1.07639pt|}$
$\displaystyle\leq\kappa^{-4}\|X_{\star}\|\cdot{|\kern-1.07639pt|\kern-1.07639pt|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}|\kern-1.07639pt|\kern-1.07639pt|},$
(54c)
$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|{E}^{d}_{t}|\kern-1.07639pt|\kern-1.07639pt|}$
$\displaystyle\leq\left(\frac{\|\widetilde{O}_{t}\|}{\sigma_{\min}(\widetilde{S}_{t})}\right)^{3/4}\sigma_{\min}(\widetilde{S}_{t}),$
(54d)
$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|{E}^{e}_{t}|\kern-1.07639pt|\kern-1.07639pt|}$
$\displaystyle\leq
2{|\kern-1.07639pt|\kern-1.07639pt|U_{\star}^{\top}\Delta_{t}|\kern-1.07639pt|\kern-1.07639pt|}+c_{\ref{lem:Delta-
bound}}\kappa^{-5}\|X_{\star}\|\cdot{|\kern-1.07639pt|\kern-1.07639pt|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}|\kern-1.07639pt|\kern-1.07639pt|}.$
(54e) Moreover, we have
$\displaystyle\|{E}^{b}_{t}\|\leq\frac{1}{24C_{\max}\kappa}\|\widetilde{O}_{t}\|,$
(54f)
$\displaystyle\|{E}^{d}_{t}\|\leq\frac{1}{24C_{\max}\kappa}\|\widetilde{O}_{t}\|.$
(54g)

Here,
${|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}$
can either be the Frobenius norm or the spectral norm.

To proceed, we would need the approximate update equation of the rotated
signal term $\widetilde{S}_{t+1}$, and the rotated misalignment term
$\widetilde{N}_{t+1}\widetilde{S}_{t+1}^{-1}$ later in the proof. Since
directly analyzing the evolution of these two terms seems challenging, we
resort to two surrogate matrices $S_{t+1}V_{t}+S_{t+1}V_{{t,\perp}}Q$, and
$(N_{t+1}V_{t}+N_{t+1}V_{{t,\perp}}Q)(S_{t+1}V_{t}+S_{t+1}V_{{t,\perp}}Q)^{-1}$,
as documented in the following two lemmas.

######  Lemma 14.

For any $t$ such that $\widetilde{S}_{t}$ is invertible and (22) holds, and
any matrix $Q\in\mathbb{R}^{(r-r_{\star})\times r_{\star}}$ with $\|Q\|\leq
2$, we have

$S_{t+1}V_{t}+S_{t+1}V_{{t,\perp}}Q=(I+\eta{E}^{\ref{lem:S-surrogate}}_{t})\left((1-\eta)I+\eta(\Sigma_{\star}^{2}+\lambda
I)(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\right)\widetilde{S}_{t},$ (55)

where ${E}^{\ref{lem:S-surrogate}}_{t}\in\mathbb{R}^{r_{\star}\times
r_{\star}}$ is a matrix (depending on $Q$) satisfying

$\|{E}^{\ref{lem:S-surrogate}}_{t}\|\leq\frac{1}{200(C_{\ref{lem:p1.5}.a}+1)^{4}\kappa^{5}}.$

Here, $C_{\ref{lem:p1.5}.a}>0$ is given in Lemma 3.

######  Lemma 15.

For any $t$ such that $\widetilde{S}_{t}$ is invertible and (22) holds, and
any matrix $Q\in\mathbb{R}^{(r-r_{\star})\times r_{\star}}$ with $\|Q\|\leq
2$, we have

$\displaystyle(N_{t+1}V_{t}+N_{t+1}V_{{t,\perp}}Q)(S_{t+1}V_{t}+S_{t+1}V_{{t,\perp}}Q)^{-1}$
$\displaystyle=\widetilde{N}_{t}\widetilde{S}_{t}^{-1}(1+\eta{E}^{\ref{lem:NS-
surrogate}.a}_{t})\big{(}(1-\eta)\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I\big{)}\big{(}(1-\eta)\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I+\eta\Sigma_{\star}^{2}\big{)}^{-1}(1+\eta{E}^{\ref{lem:S-surrogate}}_{t})^{-1}+\eta{E}^{\ref{lem:NS-
surrogate}.b}_{t}$

where ${E}^{\ref{lem:NS-surrogate}.a}_{t}$, ${E}^{\ref{lem:NS-
surrogate}.b}_{t}$ are matrices (depending on $Q$) satisfying

$\displaystyle\|{E}^{\ref{lem:NS-surrogate}.a}_{t}\|$
$\displaystyle\leq\frac{1}{200(C_{\ref{lem:p1.5}.a}+1)^{4}\kappa^{5}},$ (56a)
$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|{E}^{\ref{lem:NS-
surrogate}.b}_{t}|\kern-1.07639pt|\kern-1.07639pt|}$ $\displaystyle\leq
400c_{\lambda}^{-1}\kappa^{2}\|X_{\star}\|^{-2}{|\kern-1.07639pt|\kern-1.07639pt|U_{\star}^{\top}\Delta_{t}|\kern-1.07639pt|\kern-1.07639pt|}+\frac{1}{64(C_{\ref{lem:p1.5}.a}+1)^{2}\kappa^{5}\|X_{\star}\|}{|\kern-1.07639pt|\kern-1.07639pt|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}|\kern-1.07639pt|\kern-1.07639pt|}$
$\displaystyle\phantom{\leq}+\frac{1}{64}\left(\frac{\|\widetilde{O}_{t}\|}{\sigma_{\min}(\widetilde{S}_{t})}\right)^{2/3}.$
(56b)

Here,
${|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}$
can either be the Frobenius norm or the spectral norm, and
$C_{\ref{lem:p1.5}.a}>0$ is given in Lemma 3.

###  B.1 Proof of Lemma 13

We split the proof into three steps: (1) provide several useful approximation
results regarding the matrix inverses utilizing the facts that
$\|\widetilde{O}_{t}\|$ and
$\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|$ are small (as
shown by Lemma 3); (2) proving the claims (53a), (54a), (54b), and (54f)
associated with the signal term $S_{t+1}$; (3) proving the claims (53b),
(54c), (54d), (54e), and (54g) associated with the noise term $N_{t+1}$. Note
that our approximation results in step (1) include choices of some matrices
$\\{Q_{i}\\}$ with small spectral norms, whose choices may be different from
lemma to lemma for simplicity of presentation;

####  B.1.1 Step 1: preliminaries

We know from (22) that the overparametrization error $\widetilde{O}_{t}$ is
negligible compared to the signals $\widetilde{S}_{t}$ and
$\sigma_{\min}(X_{\star})$. This combined with the decomposition (19) reveals
a desired approximation $(X_{t}^{\top}X_{t}+\lambda
I)^{-1}\approx(V_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t})V_{t}^{\top}+\lambda
I)^{-1}$. This approximation is formalized in the lemma below.

######  Lemma 16.

If $\lambda\geq 4(\|\widetilde{O}_{t}\|^{2}\vee
2\|\widetilde{N}_{t}\|\|\widetilde{O}_{t}\|)$ for some $t$, then

$\displaystyle(X_{t}^{\top}X_{t}+\lambda I)^{-1}$
$\displaystyle=\left(V_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t})V_{t}^{\top}+\lambda
I\right)^{-1}$
$\displaystyle\phantom{=}+\left(V_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t})V_{t}^{\top}+\lambda
I\right)^{-1}{E}^{\ref{prop:pre-
approx0}.a}_{t}\left(V_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t})V_{t}^{\top}+\lambda
I\right)^{-1}$
$\displaystyle=\left(V_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t})V_{t}^{\top}+\lambda
I\right)^{-1}\left(I+{E}^{\ref{prop:pre-approx0}.b}_{t}\right)$ (57)

where the error terms ${E}^{\ref{prop:pre-approx0}.a}_{t}$,
${E}^{\ref{prop:pre-approx0}.b}_{t}$ can be expressed as

$\displaystyle{E}^{\ref{prop:pre-approx0}.a}_{t}$
$\displaystyle=(V_{{t,\perp}}\widetilde{O}_{t}^{\top}\widetilde{O}_{t}V_{{t,\perp}}^{\top}+V_{t}\widetilde{N}_{t}^{\top}\widetilde{O}_{t}V_{{t,\perp}}^{\top}+V_{{t,\perp}}{\widetilde{O}_{t}}^{\top}\widetilde{N}_{t}V_{t}^{\top})Q_{1},$
(58a) $\displaystyle{E}^{\ref{prop:pre-approx0}.b}_{t}$
$\displaystyle=\lambda^{-1}{E}^{\ref{prop:pre-approx0}.a}_{t}Q_{2},$ (58b)

for some matrices $Q_{1},Q_{2}$ such that $\max\\{\|Q_{1}\|,\|Q_{2}\|\\}\leq
2$.

###### Proof.

Expanding $X_{t}^{\top}X_{t}$ according to (19), we have

$X_{t}^{\top}X_{t}=V_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t})V_{t}^{\top}+V_{{t,\perp}}\widetilde{O}_{t}^{\top}\widetilde{O}_{t}V_{{t,\perp}}^{\top}+V_{t}\widetilde{N}_{t}^{\top}\widetilde{O}_{t}V_{{t,\perp}}^{\top}+V_{{t,\perp}}{\widetilde{O}_{t}}^{\top}\widetilde{N}_{t}V_{t}^{\top}.$

The conclusion readily follows from Lemma 9 by setting therein
$A=V_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t})V_{t}^{\top}+\lambda
I$ and
$B=V_{{t,\perp}}\widetilde{O}_{t}^{\top}\widetilde{O}_{t}V_{{t,\perp}}^{\top}+V_{t}\widetilde{N}_{t}^{\top}\widetilde{O}_{t}V_{{t,\perp}}^{\top}+V_{{t,\perp}}{\widetilde{O}_{t}}^{\top}\widetilde{N}_{t}V_{t}^{\top}$,
where the condition $\|A^{-1}B\|\leq 1/2$ is satisfied since

$\displaystyle\|A^{-1}B\|\leq\sigma_{\min}(A)^{-1}\|B\|\leq\lambda^{-1}\cdot(\|\widetilde{O}_{t}\|^{2}+2\|\widetilde{O}_{t}\|\|\widetilde{N}_{t}\|)\leq
1/2.$

∎

Moreover, the dominating term on the right hand side of (57) can be
equivalently written as

$\displaystyle\left(V_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t})V_{t}^{\top}+\lambda
I\right)^{-1}$
$\displaystyle=\Big{(}V_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)V_{t}^{\top}+\lambda V_{{t,\perp}}V_{{t,\perp}}^{\top}\Big{)}^{-1}$
$\displaystyle=V_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}V_{t}^{\top}+\lambda^{-1}V_{{t,\perp}}V_{{t,\perp}}^{\top}.$ (59)

When the misalignment error
$\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|$ is small, we
expect
$(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}\approx(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\lambda I)^{-1}$,
which is formalized in the following lemma that establishes
$(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\widetilde{S}_{t}\widetilde{N}_{t}^{\top}\widetilde{N}_{t}\widetilde{S}_{t}^{-1}+\lambda
I)^{-1}\approx(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda I)^{-1}$, due
to the following approximation

$\displaystyle(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}$
$\displaystyle=\widetilde{S}_{t}^{-1}(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\widetilde{S}_{t}\widetilde{N}_{t}^{\top}\widetilde{N}_{t}\widetilde{S}_{t}^{-1}+\lambda
I)^{-1}\widetilde{S}_{t}$
$\displaystyle\approx\widetilde{S}_{t}^{-1}(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}=(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\lambda
I)^{-1}.$

######  Lemma 17.

If
$\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|\leq\sigma_{\min}(X_{\star})/16$
for some $t$, then

$\displaystyle(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\widetilde{S}_{t}\widetilde{N}_{t}^{\top}\widetilde{N}_{t}\widetilde{S}_{t}^{-1}+\lambda
I)^{-1}=(I+{E}^{\ref{prop:rearranged-inv-
approx}}_{t})(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda I)^{-1},$ (60)

where the error term ${E}^{\ref{prop:rearranged-inv-approx}}_{t}$ is a matrix
defined as

${E}^{\ref{prop:rearranged-inv-
approx}}_{t}=\kappa^{2}\|X_{\star}\|^{-2}\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|Q_{1}(\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star})Q_{2},$
(61)

where $Q_{1}$, $Q_{2}$ are matrices of appropriate dimensions satisfying
$\|Q_{1}\|\leq 1$, $\|Q_{2}\|\leq 2$. In particular, we have

${|\kern-1.07639pt|\kern-1.07639pt|{E}^{\ref{prop:rearranged-inv-
approx}}_{t}|\kern-1.07639pt|\kern-1.07639pt|}\leq
2\kappa^{2}\|X_{\star}\|^{-2}\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|\cdot{|\kern-1.07639pt|\kern-1.07639pt|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}|\kern-1.07639pt|\kern-1.07639pt|},$
(62)

where
${|\kern-1.07639pt|\kern-1.07639pt|\cdot|\kern-1.07639pt|\kern-1.07639pt|}$
can be either the operator norm or the Frobenius norm.

###### Proof.

In order to apply Lemma 9, setting
$A=\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda I$ and
$B=\widetilde{S}_{t}\widetilde{N}_{t}^{\top}\widetilde{N}_{t}\widetilde{S}_{t}^{-1}$,
it is straightforward to verify that

$\|A^{-1}B\|=\|(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}\widetilde{N}_{t}^{\top}\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\|\leq\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\|^{2}\leq\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|^{2}\|\Sigma_{\star}^{-1}\|^{2}\leq(1/16)^{2},$

where we use the obvious fact that
$\|(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}\widetilde{S}_{t}^{\top}\|\leq 1$. Applying Lemma 9,
we obtain

$\displaystyle(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\widetilde{S}_{t}\widetilde{N}_{t}^{\top}\widetilde{N}_{t}\widetilde{S}_{t}^{-1}+\lambda
I)^{-1}-(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda I)^{-1}$
$\displaystyle=(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}\widetilde{N}_{t}^{\top}\widetilde{N}_{t}\widetilde{S}_{t}^{-1}Q(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}$ $\displaystyle=(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}\widetilde{S}_{t}^{\top}\Sigma_{\star}^{-1}(\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star})^{\top}(\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star})\Sigma_{\star}^{-1}Q(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}$

for some matrix $Q$ with $\|Q\|\leq 2$. Since one may further write

$\displaystyle(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\widetilde{S}_{t}\widetilde{N}_{t}^{\top}\widetilde{N}_{t}\widetilde{S}_{t}^{-1}+\lambda
I)^{-1}-(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda I)^{-1}$
$\displaystyle=\|\Sigma_{\star}^{-1}\|^{2}\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}\widetilde{S}_{t}^{\top}\frac{\Sigma_{\star}^{-1}}{\|\Sigma_{\star}^{-1}\|}\frac{(\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star})^{\top}}{\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|}(\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star})\frac{\Sigma_{\star}^{-1}}{\|\Sigma_{\star}^{-1}\|}Q(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1},$

the conclusion follows by setting ${E}^{\ref{prop:rearranged-inv-approx}}_{t}$
as in (61) with

$\displaystyle Q_{1}=(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}\widetilde{S}_{t}^{\top}\frac{\Sigma_{\star}^{-1}}{\|\Sigma_{\star}^{-1}\|}\frac{(\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star})^{\top}}{\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|},\quad
Q_{2}=\frac{\Sigma_{\star}^{-1}}{\|\Sigma_{\star}^{-1}\|}Q.$

The last inequality (62) is then a direct consequence of (61). ∎

####  B.1.2 Step 2: a key recursion

Recall the definition $\Delta_{t}$ in (48), we can rewrite the update equation
(7) as

$X_{t+1}=X_{t}-\eta(X_{t}X_{t}^{\top}-M_{\star})X_{t}(X_{t}^{\top}X_{t}+\lambda
I)^{-1}+\eta\Delta_{t}X_{t}(X_{t}^{\top}X_{t}+\lambda I)^{-1}.$ (63)

Multiplying both sides of (63) by $U_{\star}^{\top}$ on the left, we obtain

$\displaystyle S_{t+1}$ $\displaystyle=S_{t}-\eta
S_{t}X_{t}^{\top}X_{t}(X_{t}^{\top}X_{t}+\lambda
I)^{-1}+\eta\Sigma_{\star}^{2}S_{t}(X_{t}^{\top}X_{t}+\lambda I)^{-1}+\eta
U_{\star}^{\top}\Delta_{t}X_{t}(X_{t}^{\top}X_{t}+\lambda I)^{-1}$
$\displaystyle=(1-\eta)S_{t}+\eta(\Sigma_{\star}^{2}+\lambda
I+U_{\star}^{\top}\Delta_{t}U_{\star})S_{t}(X_{t}^{\top}X_{t}+\lambda
I)^{-1}+\eta
U_{\star}^{\top}\Delta_{t}U_{{\star,\perp}}N_{t}(X_{t}^{\top}X_{t}+\lambda
I)^{-1}.$ (64)

Similarly, multiplying both sides of (63) by $U_{{\star,\perp}}^{\top}$, we
obtain

$\displaystyle N_{t+1}$ $\displaystyle=N_{t}\left(I-\eta
X_{t}^{\top}X_{t}(X_{t}^{\top}X_{t}+\lambda I)^{-1}\right)+\eta
U_{{\star,\perp}}^{\top}\Delta_{t}X_{t}(X_{t}^{\top}X_{t}+\lambda I)^{-1}$
$\displaystyle=(1-\eta)N_{t}+\eta\lambda N_{t}(X_{t}^{\top}X_{t}+\lambda
I)^{-1}+\eta
U_{{\star,\perp}}^{\top}\Delta_{t}U_{\star}S_{t}(X_{t}^{\top}X_{t}+\lambda
I)^{-1}+\eta
U_{{\star,\perp}}^{\top}\Delta_{t}U_{{\star,\perp}}N_{t}(X_{t}^{\top}X_{t}+\lambda
I)^{-1}.$ (65)

These expressions motivate the need to study the terms
$S_{t}(X_{t}^{\top}X_{t}+\lambda I)^{-1}$ and $N_{t}(X_{t}^{\top}X_{t}+\lambda
I)^{-1}$, which we formalize in the following lemma.

######  Lemma 18.

Under the same setting as Lemma 13, we have

$\displaystyle S_{t}(X_{t}^{\top}X_{t}+\lambda I)^{-1}$
$\displaystyle=(I+{E}^{\ref{prop:rearranged-inv-
approx}}_{t})(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}V_{t}^{\top}+{E}^{\ref{lem:scaled-S-N-approx}.a}_{t},$
(66a) $\displaystyle N_{t}(X_{t}^{\top}X_{t}+\lambda I)^{-1}$
$\displaystyle=\widetilde{N}_{t}\widetilde{S}_{t}^{-1}(I+{E}^{\ref{prop:rearranged-
inv-approx}}_{t})(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}V_{t}^{\top}+\lambda^{-1}\widetilde{O}_{t}V_{{t,\perp}}^{\top}+{E}^{\ref{lem:scaled-
S-N-approx}.b}_{t},$ (66b)

where ${E}^{\ref{prop:rearranged-inv-approx}}_{t}$ is given in (61), and the
error terms ${E}^{\ref{lem:scaled-S-N-approx}.a}_{t}$, ${E}^{\ref{lem:scaled-
S-N-approx}.b}_{t}$ can be expressed as

$\displaystyle{E}^{\ref{lem:scaled-S-N-approx}.a}_{t}$
$\displaystyle=\kappa\lambda^{-1}\|X_{\star}\|^{-1}\|\widetilde{O}_{t}\|Q_{1}(\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star})^{\top}Q_{2},$
(67a) $\displaystyle{E}^{\ref{lem:scaled-S-N-approx}.b}_{t}$
$\displaystyle=\left(\widetilde{N}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}V_{t}^{\top}+\lambda^{-1}\widetilde{O}_{t}V_{{t,\perp}}^{\top}\right){E}^{\ref{prop:pre-
approx0}.b}_{t}$
$\displaystyle=\lambda^{-1}(\|\widetilde{N}_{t}\|Q_{3}+\|\widetilde{O}_{t}\|Q_{4}){E}^{\ref{prop:pre-
approx0}.b}_{t}.$ (67b)

for some matrices $\\{Q_{i}\\}_{1\leq i\leq 4}$ with spectral norm bounded by
$2$, and ${E}^{\ref{prop:pre-approx0}.b}_{t}$ defined in (58b).

###### Proof.

To begin, combining Lemma 16 and the discussion thereafter (cf. (57)–(B.1.1))
and the fact that $\widetilde{S}_{t}=S_{t}V_{t}$, we have for some matrix $Q$
with $\|Q\|\leq 2$ that

$\displaystyle S_{t}(X_{t}^{\top}X_{t}+\lambda I)^{-1}$
$\displaystyle=\widetilde{S}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}V_{t}^{\top}\left(I+{E}^{\ref{prop:pre-approx0}.b}_{t}\right)$
$\displaystyle=\widetilde{S}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}V_{t}^{\top}+\widetilde{S}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}\lambda^{-1}\widetilde{N}_{t}^{\top}\widetilde{O}_{t}Q$
$\displaystyle=(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\widetilde{S}_{t}\widetilde{N}_{t}^{\top}\widetilde{N}_{t}\widetilde{S}_{t}^{-1}+\lambda
I)^{-1}\widetilde{S}_{t}V_{t}^{\top}$
$\displaystyle\phantom{=}+\widetilde{S}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}\widetilde{S}_{t}^{\top}(\widetilde{N}_{t}\widetilde{S}_{t}^{-1})^{\top}(\widetilde{O}_{t}/\lambda)Q.$
(68)

Note that the condition of Lemma 16 can be verified as follows: since

$\displaystyle\|\widetilde{O}_{t}\|$ $\displaystyle\leq
C_{\ref{lem:p1.5}.b}^{-C_{\ref{lem:p1.5}.b}}\kappa^{-3}\cdot\|X_{\star}\|\cdot\sigma_{\min}\big{(}(\Sigma_{\star}^{2}+\lambda
I)^{-1/2}\big{)}\cdot\|\widetilde{S}_{t}\|\leq
C_{\ref{lem:p1.5}.b}^{-C_{\ref{lem:p1.5}.b}}C_{\ref{lem:p1.5}.a}\sigma_{\min}(X_{\star}),$
$\displaystyle\|\widetilde{N}_{t}\|$
$\displaystyle\leq\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|\cdot\|\Sigma_{\star}^{-1}\|\cdot\|\widetilde{S}_{t}\|\leq
c_{\ref{lem:p1.5}}\kappa^{-C_{\delta}/2}\|X_{\star}\|\cdot\frac{C_{\ref{lem:p1.5}.a}\kappa\|X_{\star}\|}{\sigma_{\min}(X_{\star})}\leq
c_{\ref{lem:p1.5}}C_{\ref{lem:p1.5}.a}\sigma_{\min}(X_{\star})$

provided $C_{\delta}\geq 6$, the bounds $c_{\ref{lem:p1.5}}\lesssim
c_{\delta}/c_{\lambda}^{3}$ and $C_{\ref{lem:p1.5}.a}\lesssim
c_{\lambda}^{-1/2}$ imply that when we choose $C_{\alpha}$ to be large enough
(depending on $c_{\lambda}$, $c_{\delta}$),

$\displaystyle
2\|\widetilde{N}_{t}\|\|\widetilde{O}_{t}\|\vee\|\widetilde{O}_{t}\|^{2}\leq\lambda/4,$

as desired.

Now the first term in (68) can be handled by invoking Lemma 17, since its
condition is verified by
$\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|\leq
c_{\ref{lem:p1.5}}\kappa^{-(C_{\delta}/2-1)}\sigma_{\min}(X_{\star})\leq\sigma_{\min}(X_{\star})/16$
provided $C_{\delta}\geq 2$ and $c_{\ref{lem:p1.5}}\leq 1/16$ by choosing
$c_{\delta}$ sufficiently small (depending on $c_{\lambda}$). Namely,

$\displaystyle(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\widetilde{S}_{t}\widetilde{N}_{t}^{\top}\widetilde{N}_{t}\widetilde{S}_{t}^{-1}+\lambda
I)^{-1}\widetilde{S}_{t}V_{t}^{\top}=(I+{E}^{\ref{prop:rearranged-inv-
approx}}_{t})(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}V_{t}^{\top}.$

For the second term, by noting that

$\|\widetilde{S}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}\widetilde{S}_{t}^{\top}\|\leq\|\widetilde{S}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\lambda
I)^{-1}\widetilde{S}_{t}^{\top}\|\leq 1,$

it can be expressed as

$\lambda^{-1}\|\widetilde{O}_{t}\|\widetilde{S}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\lambda
I)^{-1}\widetilde{S}_{t}^{\top}(\widetilde{N}_{t}\widetilde{S}_{t}^{-1})^{\top}(\widetilde{O}_{t}/\|\widetilde{O}_{t}\|)Q=\kappa\lambda^{-1}\|X_{\star}\|^{-1}\|\widetilde{O}_{t}\|Q_{1}(\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star})^{\top}Q_{2}$

for $Q_{1}=\widetilde{S}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\lambda
I)^{-1}\widetilde{S}_{t}^{\top}\cdot\kappa^{-1}\|X_{\star}\|\Sigma_{\star}^{-1}$
with $\|Q_{1}\|\leq 1$ and $Q_{2}=(\widetilde{O}_{t}/\|\widetilde{O}_{t}\|)Q$
which satisfies $\|Q_{2}\|\leq\|Q\|\leq 2$. Applying the above two bounds to
(68) yields (66a).

Similarly, moving to (66b), it follows that

$\displaystyle N_{t}(X_{t}^{\top}X_{t}+\lambda I)^{-1}=$
$\displaystyle\left(\widetilde{N}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}V_{t}^{\top}+\lambda^{-1}\widetilde{O}_{t}V_{{t,\perp}}^{\top}\right)\left(I+{E}^{\ref{prop:pre-
approx0}.b}_{t}\right)$ $\displaystyle=$
$\displaystyle\widetilde{N}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}V_{t}^{\top}+\lambda^{-1}\widetilde{O}_{t}V_{{t,\perp}}^{\top}+{E}^{\ref{lem:scaled-
S-N-approx}.b}_{t},$ (69)

where we have

$\displaystyle{E}^{\ref{lem:scaled-S-N-approx}.b}_{t}$
$\displaystyle=\left(\widetilde{N}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}V_{t}^{\top}+\lambda^{-1}\widetilde{O}_{t}V_{{t,\perp}}^{\top}\right){E}^{\ref{prop:pre-
approx0}.b}_{t}$
$\displaystyle=\lambda^{-1}(\|\widetilde{N}_{t}\|Q_{3}+\|\widetilde{O}_{t}\|Q_{4}){E}^{\ref{prop:pre-
approx0}.b}_{t}$

for some matrices $Q_{3},Q_{4}$ with $\|Q_{3}\|,\|Q_{4}\|\leq 1$. In the last
line we used
$\|(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}\|\leq\lambda^{-1}$. For the first term of (69), we use Lemma 17 and
obtain

$\displaystyle\widetilde{N}_{t}(\widetilde{S}_{t}^{\top}\widetilde{S}_{t}+\widetilde{N}_{t}^{\top}\widetilde{N}_{t}+\lambda
I)^{-1}V_{t}^{\top}$
$\displaystyle=\widetilde{N}_{t}\widetilde{S}_{t}^{-1}(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\widetilde{S}_{t}\widetilde{N}_{t}^{\top}\widetilde{N}_{t}\widetilde{S}_{t}^{-1}+\lambda
I)^{-1}\widetilde{S}_{t}V_{t}^{\top}$
$\displaystyle=\widetilde{N}_{t}\widetilde{S}_{t}^{-1}(I+{E}^{\ref{prop:rearranged-
inv-approx}}_{t})(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\widetilde{S}_{t}V_{t}^{\top}.$

This yields the representation in (66b).

∎

####  B.1.3 Step 3: proofs associated with $S_{t+1}$.

With the help of Lemma 18, we are ready to prove (53a) and the associated norm
bounds (54a), (54b), and (54f). To begin with, we plug (66a), (66b) into (64)
and use $S_{t}=\widetilde{S}_{t}V_{t}^{\top}$ to obtain

$S_{t+1}=\left((1-\eta)I+\eta(\Sigma_{\star}^{2}+\lambda
I+{E}^{a}_{t})(\widetilde{S}_{t}\widetilde{S}_{t}^{\top}+\lambda
I)^{-1}\right)\widetilde{S}_{t}V_{t}^{\top}+\eta{E}^{b}_{t},$

where the error terms ${E}^{a}_{t}$ and ${E}^{b}_{t}$ are

$\displaystyle{E}^{a}_{t}$ $\displaystyle\coloneqq
U_{\star}^{\top}\Delta_{t}U_{\star}+(\Sigma_{\star}^{2}+U_{\star}^{\top}\Delta_{t}U_{\star}+\lambda
I){E}^{\ref{prop:rearranged-inv-
approx}}_{t}+U_{\star}^{\top}\Delta_{t}U_{{\star,\perp}}\widetilde{N}_{t}\widetilde{S}_{t}^{-1}(I+{E}^{\ref{prop:rearranged-
inv-approx}}_{t}),$ $\displaystyle{E}^{b}_{t}$
$\displaystyle\coloneqq(\Sigma_{\star}^{2}+U_{\star}^{\top}\Delta_{t}U_{\star}+\lambda
I){E}^{\ref{lem:scaled-S-N-
approx}.a}_{t}+U_{\star}^{\top}\Delta_{t}U_{{\star,\perp}}(\lambda^{-1}\widetilde{O}_{t}V_{{t,\perp}}^{\top}+{E}^{\ref{lem:scaled-
S-N-approx}.b}_{t}).$

This establishes the identity (53a). To control
${|\kern-1.07639pt|\kern-1.07639pt|{E}^{a}_{t}|\kern-1.07639pt|\kern-1.07639pt|}$,
we observe that

$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|{E}^{a}_{t}|\kern-1.07639pt|\kern-1.07639pt|}$
$\displaystyle\leq{|\kern-1.07639pt|\kern-1.07639pt|U_{\star}^{\top}\Delta_{t}|\kern-1.07639pt|\kern-1.07639pt|}+\|\Sigma_{\star}^{2}+U_{\star}^{\top}\Delta_{t}U_{\star}+\lambda
I\|\cdot{|\kern-1.07639pt|\kern-1.07639pt|{E}^{\ref{prop:rearranged-inv-
approx}}_{t}|\kern-1.07639pt|\kern-1.07639pt|}+{|\kern-1.07639pt|\kern-1.07639pt|U_{\star}^{\top}\Delta_{t}|\kern-1.07639pt|\kern-1.07639pt|}\cdot\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|\cdot\|\Sigma_{\star}^{-1}\|\cdot(1+\|{E}^{\ref{prop:rearranged-
inv-approx}}_{t}\|)$ $\displaystyle\leq\left(1+c_{\ref{lem:Delta-
bound}}\kappa^{-2C_{\delta}/3}+c_{\lambda}\right)\|X_{\star}\|^{2}\cdot{|\kern-1.07639pt|\kern-1.07639pt|{E}^{\ref{prop:rearranged-
inv-
approx}}_{t}|\kern-1.07639pt|\kern-1.07639pt|}+{|\kern-1.07639pt|\kern-1.07639pt|U_{\star}^{\top}\Delta_{t}|\kern-1.07639pt|\kern-1.07639pt|}+c_{\ref{lem:p1.5}}\kappa^{-C_{\delta}/2}\|X_{\star}\|\cdot\sigma_{\min}^{-1}(X_{\star})\cdot(1+\|{E}^{\ref{prop:rearranged-
inv-
approx}}_{t}\|)\cdot{|\kern-1.07639pt|\kern-1.07639pt|U_{\star}^{\top}\Delta_{t}|\kern-1.07639pt|\kern-1.07639pt|}$
$\displaystyle\leq
2\|X_{\star}\|^{2}\cdot{|\kern-1.07639pt|\kern-1.07639pt|{E}^{\ref{prop:rearranged-
inv-
approx}}_{t}|\kern-1.07639pt|\kern-1.07639pt|}+\left(1+c_{\ref{lem:p1.5}}(1+\|{E}^{\ref{prop:rearranged-
inv-
approx}}_{t}\|)\right){|\kern-1.07639pt|\kern-1.07639pt|U_{\star}^{\top}\Delta_{t}|\kern-1.07639pt|\kern-1.07639pt|},$

where the second line follows from Lemma 12 and Equations (12b), (22c); the
last line holds since $c_{\ref{lem:Delta-bound}},c_{\lambda}$ are sufficiently
small and $C_{\delta}$ is sufficiently large. Now we invoke the bound (62) in
Lemma 17 to see

$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|{E}^{\ref{prop:rearranged-inv-
approx}}_{t}|\kern-1.07639pt|\kern-1.07639pt|}\leq
2\kappa^{2}\|X_{\star}\|^{-2}\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|{|\kern-1.07639pt|\kern-1.07639pt|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}|\kern-1.07639pt|\kern-1.07639pt|}$
$\displaystyle\leq
2c_{\ref{lem:p1.5}}\kappa^{2}\kappa^{-C_{\delta}/2}\|X_{\star}\|^{-1}{|\kern-1.07639pt|\kern-1.07639pt|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}|\kern-1.07639pt|\kern-1.07639pt|}$
$\displaystyle\leq
2c_{\ref{lem:p1.5}}\kappa^{-4}\|X_{\star}\|^{-1}{|\kern-1.07639pt|\kern-1.07639pt|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}|\kern-1.07639pt|\kern-1.07639pt|},$

where the last line follows again by choosing sufficiently large
$C_{\delta}\geq 12$. Furthermore, since
$\|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}\|\leq
c_{\ref{lem:p1.5}}\kappa^{-C_{\delta}/2}\|X_{\star}\|$ for small enough
$c_{\ref{lem:p1.5}}$, we obtain $\|{E}^{\ref{prop:rearranged-inv-
approx}}_{t}\|\leq 1$. Combining these inequalities yields the claimed bound

${|\kern-1.07639pt|\kern-1.07639pt|{E}^{a}_{t}|\kern-1.07639pt|\kern-1.07639pt|}\leq
2c_{\ref{lem:p1.5}}\kappa^{-4}\|X_{\star}\|\cdot{|\kern-1.07639pt|\kern-1.07639pt|\widetilde{N}_{t}\widetilde{S}_{t}^{-1}\Sigma_{\star}|\kern-1.07639pt|\kern-1.07639pt|}+2{|\kern-1.07639pt|\kern-1.07639pt|U_{\star}^{\top}\Delta_{t}|\kern-1.07639pt|\kern-1.07639pt|}.$

The bound of
${|\kern-1.07639pt|\kern-1.07639pt|{E}^{b}_{t}|\kern-1.07639pt|\kern-1.07639pt|}$
and $\|{E}^{b}_{t}\|$ can be proved in a similar way, utilizing the bound for