Singular Subspace Perturbation Bounds via Rectangular Random Matrix Diffusions

## Abstract

Abstract Given a matrix A ∈ ℝ m × d 𝐴 superscript ℝ 𝑚 𝑑 A\in\mathbb{R}^{m\times d} italic_A ∈ blackboard_R start_POSTSUPERSCRIPT italic_m × italic_d end_POSTSUPERSCRIPT with singular values σ 1 ≥ ⋯ ≥ σ d subscript 𝜎 1 ⋯ subscript 𝜎 𝑑 \sigma_{1}\geq\cdots\geq\sigma_{d} italic_σ start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ≥ ⋯ ≥ italic_σ start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT , and a random matrix G ∈ ℝ m × d 𝐺 superscript ℝ 𝑚 𝑑 G\in\mathbb{R}^{m\times d} italic_G ∈ blackboard_R start_POSTSUPERSCRIPT italic_m × italic_d end_POSTSUPERSCRIPT with iid N ⁢ ( 0 , T ) 𝑁 0 𝑇 N(0,T) italic_N ( 0 , italic_T ) entries for some T > 0 𝑇 0 T>0 italic_T > 0 , we derive new bounds on the Frobenius distance between subspaces spanned by the top- k 𝑘 k italic_k (right) singular vectors of A 𝐴 A italic_A and A + G 𝐴 𝐺 A+G italic_A + italic_G .
This problem arises in numerous applications in statistics where a data matrix may be corrupted by Gaussian noise, and in the analysis of the Gaussian mechanism in differential privacy, where Gaussian noise is added to data to preserve private information.
We show that, for matrices A 𝐴 A italic_A where the gaps in the top- k 𝑘 k italic_k singular values are roughly Ω ⁢ ( σ k − σ k + 1 ) Ω subscript 𝜎 𝑘 subscript 𝜎 𝑘 1 \Omega(\sigma_{k}-\sigma_{k+1}) roman_Ω ( italic_σ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT - italic_σ start_POSTSUBSCRIPT italic_k + 1 end_POSTSUBSCRIPT ) the expected Frobenius distance between the subspaces is O ~ ⁢ ( d σ k − σ k + 1 × T ) ~ 𝑂 𝑑 subscript 𝜎 𝑘 subscript 𝜎 𝑘 1 𝑇 \tilde{O}(\frac{\sqrt{d}}{\sigma_{k}-\sigma_{k+1}}\times\sqrt{T}) over~ start_ARG italic_O end_ARG ( divide start_ARG square-root start_ARG italic_d end_ARG end_ARG start_ARG italic_σ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT - italic_σ start_POSTSUBSCRIPT italic_k + 1 end_POSTSUBSCRIPT end_ARG × square-root start_ARG italic_T end_ARG ) , improving on previous bounds by a factor of m d ⁢ k 𝑚 𝑑 𝑘 \frac{\sqrt{m}}{\sqrt{d}}\sqrt{k} divide start_ARG square-root start_ARG italic_m end_ARG end_ARG start_ARG square-root start_ARG italic_d end_ARG end_ARG square-root start_ARG italic_k end_ARG .
To obtain our bounds we view the perturbation to the singular vectors as a diffusion process– the Dyson-Bessel process– and use tools from stochastic calculus to track the evolution of the subspace spanned by the top- k 𝑘 k italic_k singular vectors.

## 1 Introduction

Given a matrix $A\in\mathbb{R}^{m\times d}$ with $d\leq m$ and singular values $\sigma_{1}\geq\cdots\geq\sigma_{d}$, one oftentimes wishes to approximate the right-singular vectors of $A$ by a lower rank matrix of some rank $k<d$ [, , , , ].
For instance, one may wish to learn the subspace spanned by the top-$k$ right-singular vectors of $A$, in which case one may seek a projection matrix which minimizes the distance to the projection matrix onto the subspace spanned by the top-$k$ right-singular vectors of $A$. One can also consider the related problem of recovering a matrix $\hat{M}_{k}$ which minimizes the Frobenius distance $\|\hat{M}_{k}-A^{\top}A\|_{F}$ to the covariance matrix $A^{\top}A$ of the data $A$.
Roughly speaking, both of these problems are instances of the following general problem: given a set of numbers $\gamma_{1}\geq\cdots\geq\gamma_{d}$ and denoting by $\Gamma:=\mathrm{diag}(\gamma_{1},\cdots,\gamma_{d})$ and by $A=U\Sigma V^{\top}$ a singular value decomposition of $A$, find a matrix $M\in\mathcal{O}_{\Gamma^{2}}$ which minimizes the Frobenius distance $\|M-V^{\top}\Gamma^{2}V\|_{F}$, where $\mathcal{O}_{\Gamma^{2}}:=\{U\Gamma^{2}U^{\top}:U\in O(d)\}$ denotes the orbit of $\Gamma^{2}$ under the orthogonal group.
Plugging in $\gamma_{i}=1$ for $i\leq k$ and $\gamma_{i}=0$ for $i>k$, we recover the problem of finding a projection matrix which minimizes the Frobenius distance to the projection matrix onto the subspace spanned by to top-$k$ right-singular vectors of $A$.
And, roughly speaking, when we set $\gamma_{i}\approx\sigma_{i}$ for $i\leq k$ and $\gamma_{i}=0$ for $i>k$, we recover the problem of finding a rank-$k$ covariance matrix which minimizes the Frobenius distance to the covariance matrix of $A$.

In many applications, the matrix $A$ is perturbed by a “noise” matrix $E\in\mathbb{R}^{m\times d}$ and one only has access to a perturbed matrix $A+E$.
Oftentimes, the noise matrix consist of iid Gaussian entries.
For instance, in statistics applications, and signal and image processing applications, this noise may arise as natural background Gaussian noise obscuring a “signal” matrix $A$ [, , , , ].
In differential privacy applications, Gaussian noise may be artificially added to the data matrix $A$, or to a machine learning algorithm trained on the data $A$, to hide sensitive information about individuals in the dataset [, ]; see e.g. [, , ] where symmetric-matrix Gaussian noise is added to covariance matrices to guarantee privacy.
The addition of Gaussian noise to ensure privacy is referred to as the Gaussian mechanism, and is known to satisfy $(\varepsilon,\delta)$-differential privacy guarantees.

### 1.1 Related work

Multiple prior works have shown singular subspace perturbation bounds when $E\in\mathbb{R}^{m\times d}$ may be any (deterministic) matrix.
For instance, the Davis-Kahan-Wedin sine-Theta theorem [, ] implies a bound of roughly

$$ $|||V_{k}V_{k}^{\top}-\hat{V}_{k}\hat{V}_{k}^{\top}|||\leq\dfrac{\sqrt{k}|||E|| |}{\sigma_{k}-\sigma_{k+1}},$ (1) $$

where $V_{k},\hat{V}_{k}$ are, respectively, the matrices whose columns are the top-$k$ right-singular vectors of $A$ and $\hat{A}:=A+E$, and $|||\cdot|||$ is e.g. the Frobenius norm $\|\cdot\|_{F}$ or the spectral norm $\|\cdot\|_{2}$.
These bounds are tight (for sufficiently small $|||E|||$) in the general setting where $E\in\mathbb{R}^{m\times d}$ may be any (deterministic) matrix.

When the perturbation $E$ is, e.g., a Gaussian random matrix with iid $N(0,T)$ entries for some $T>0$, one can plug in high-probability concentration bounds, which imply that $\|E\|_{2}\leq O(\sqrt{m}))$ w.h.p., to the deterministic bounds in (1) to obtain a bound of

$$ $\|V_{k}V_{k}^{\top}-\hat{V}_{k}\hat{V}_{k}^{\top}\|_{F}\leq\dfrac{\sqrt{k} \sqrt{m}}{\sigma_{k}-\sigma_{k+1}}\times\sqrt{T}$ $$

w.h.p.
However, the resulting bounds may not be tight.

Multiple works have obtained tighter bounds than those implied by the deterministic bounds in (1), in different settings when $E$ is a random matrix from some known distribution or class of distributions (see e.g. [, , , ]).
In particular, [], show that if the entries of $E$ satisfy concentration properties which generalize those of Gaussian distributions, and $A$ has rank $r\leq d$, then

$$ $\|\hat{V}_{k}\hat{V}_{k}^{\top}-V_{k}V_{k}^{\top}\|_{F}\leq O\left(k\left( \dfrac{\sqrt{r}}{\sigma_{k}-\sigma_{k+1}}+\dfrac{m}{\sigma_{k}(\sigma_{k}- \sigma_{k+1})}+\dfrac{\sqrt{m}}{\sigma_{k}}\right)\right)$ (2) $$

w.h.p.

Subspace perturbation bounds have also been obtained in different settings where the input matrix, and random matrix perturbation, is a symmetric matrix (see e.g. [, , ]).
For instance, [] obtain perturbation bounds for covariance matrices perturbed by symmetric Gaussian noise, and apply these perturbation bounds to a version of the Gaussian mechanism to obtain tighter utility bounds for covariance matrix approximation problems under $(\varepsilon,\delta)$-differential privacy. [, ] improve on some of their utility bounds by viewing the addition of the symmetric Gaussian noise as a symmetric-matrix valued stochastic process, and use tools from and stochastic calculus and random matrix theory to bound the perturbation to the symmetric matrix eigenvectors.

### 1.2 Our Contributions

Given any matrix $A\in\mathbb{R}^{m\times d}$, and a set of numbers $\gamma_{1}\geq\cdots\geq\gamma_{d}$, our main result (Theorem 2.2) is a bound on the perturbation to the matrix $V^{\top}\Gamma^{2}V\in\mathcal{O}_{\Gamma^{2}}$ where $A=U\Sigma V^{\top}$ is a singular value decomposition of $A$. We show that, if the matrix $A$ is perturbed by a matrix $E=\sqrt{T}G$, where $T>0$ and $G$ is a Gaussian random matrix with iid $N(0,1)$ entries, the right-singular vectors $\hat{V}=(\hat{v}_{1},\cdots,\hat{v}_{d})$ of the perturbed matrix $A+\sqrt{T}G$ satisfy the bound

$$ $\mathbb{E}\left[\|\hat{V}\Gamma^{\top}\Gamma\hat{V}^{\top}-V\Gamma^{\top} \Gamma V^{\top}\|_{F}\right]\leq O\left(\sqrt{\sum_{i=1}^{k}\sum_{j=i+1}^{d} \dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}}\sqrt {T}\right),$ $$

where the right-hand-side is a sum-of-squares of the ratios of the eigenvalue gaps of $\Gamma$ and $\Sigma$.

Plugging in different values of $\gamma$, we obtain as corollaries bounds for the subspace recovery and low-rank covariance matrix approximation problems.
In particular, show that $\|V_{k}V_{k}^{\top}-\hat{V}_{k}\hat{V}_{k}^{\top}\|_{F}\leq O\left(\dfrac{
\sqrt{d}}{\sigma_{k}-\sigma_{k+1}}\sqrt{T}\right)$ whenever the top-$k$ singular value gaps of $A$ are roughly $\Omega(\max(\sigma_{k}-\sigma_{k+1},\sqrt{m}\sqrt{T}))$ (Corollary 2.3).
This improves (in expectation) on the bounds implied by both [, ] and [] by a factor of roughly $\frac{\sqrt{m}}{\sqrt{d}}\sqrt{k}$ in the above setting where $E$ is a Gaussian random matrix.
In particular, our bound replaces those bounds’ dependence on the number of rows $m$ with the number of columns $d$.
This can lead to a large improvement in many applications, as one oftentimes has that the number $m$ of rows in the data matrix (corresponding to the number of datapoints) is much larger than the number of columns $d$ (which oftentimes correspond to different features in the data).
Our results also imply similar improvements for the low-rank covariance matrix approximation problem (Corrollary 2.4).

To obtain our bounds, building on several previous works, including [, , , , ],
we view the perturbation of a matrix $A\in\mathbb{R}^{m\times d}$ by Gaussian noise as a Brownian motion on the entries of an $\mathbb{R}^{m\times d}$ matrix, $\Phi(t):=A+B(t)$ where $B(t)$ is a $m\times d$ matrix whose entries undergo iid standard Brownian motions.
This Brownian motion induces a stochastic diffusion process on the singular values and singular vectors of $\Phi(t)$, referred to as the Dyson-Bessel process.
The evolution of these eigenvalues and eigenvectors is determined by a system of stochastic differential equations (see e.g. [, , ]).
This allows us to use Ito’s lemma from stochastic calculus to track the evolution of the Frobenius distance as a stochastic integral of a sum-of-squares of perturbations to the (right)-singular vectors of $\Phi(t)$.
In particular, the stochastic evolution of the eigenvectors allows us to bypass higher-order matrix derivative terms that arise in Taylor expansions of deterministic perturbations, as these terms vanish in the stochastic derivative when the perturbation is a Brownian motion, due to the independence of random noise additions at each infinitesimal time-step of the Brownian motion.
This in turn allows us to obtain stronger bounds than would be possible in the deterministic setting.

## 2 Main results

For any $d>0$, denote by $\mathrm{O}(d)$ the group of orthogonal of $d\times d$ matrices.
For any diagonal matrix $\Lambda\in\mathbb{R}^{d\times d}$, denote by $\mathcal{O}_{\Lambda}:=\{U\Lambda U^{\top}:U\in O(d)\}$ the orbit of $\Lambda$ under the orthogonal group.

Given any matrix $A\in\mathbb{R}^{m\times d}$, where $d\leq m$, with singular values $\sigma_{1}\geq...\geq\sigma_{d}\geq 0$ and corresponding orthonormal right-singular vectors $v_{1},...v_{d}$, and given any numbers $\gamma_{1}\geq\cdots\geq\gamma_{d}$, our main result (Theorem 2.2) is a bound on the perturbation to the matrix $V^{\top}\Gamma^{2}V\in\mathcal{O}_{\Gamma^{2}}$, where $V:=[v_{1},...v_{d}]\in\mathbb{R}^{d\times d}$ and
$\Gamma:=\mathrm{diag}(\gamma_{1},\ldots,\gamma_{d})$.

Our main result holds under the following assumption on the gaps in the top $k+1$ singular values $\sigma_{1}\geq...\geq\sigma_{k+1}$ of the matrix $A$.
We note that this assumption is satisfied on many real-world datasets whose singular values exhibit exponential decay (see e.g. Appendix J of [] for examples of datasets with exponentially-decaying singular values).

###### Assumption 2.1 ( $A,k,T,\sigma,\gamma)$ (Singular value gaps).

The gaps in the top $k+1$ singular values $\sigma_{1}\geq...\geq\sigma_{k+1}$ of the matrix $A\in\mathbb{R}^{m\times d}$ satisfy $\sigma_{i}-\sigma_{i+1}\geq 8\sqrt{T}\sqrt{m}\log(\frac{1}{\delta})$ for every $i\in[k]$, where $\delta:=\frac{1}{8d\gamma_{1}^{2}}\times\frac{\gamma_{1}^{2}-\gamma_{d}^{2}}{(
\sigma_{1}-\sigma_{d})^{2}}$.

We now state our main result.

###### Theorem 2.2 ( Main result).

Let $T>0$.
Given a rectangular matrix $A\in\mathbb{R}^{m\times d}$ with singular values $\sigma_{1}\geq...\geq\sigma_{d}\geq 0$ and corresponding orthonormal right-singular vectors $v_{1},...v_{d}$ (and denote $V:=[v_{1},...v_{d}]\in\mathbb{R}^{d\times d}$).
Let $G$ be a matrix with i.i.d. $N(0,1)$ entries, and consider the perturbed matrix $\hat{A}:=A+\sqrt{T}G\in\mathbb{R}^{m\times d}$.

Define $\hat{\sigma}_{1}\geq...\geq\hat{\sigma}_{d}\geq 0$ to be the singular values of $\hat{A}$ with corresponding orthonormal right-singular vectors $\hat{v}_{1},...\hat{v}_{d}$ (and denote $\hat{V}:=[\hat{v}_{1},...\hat{v}_{d}]$).

Let $\gamma_{1}\geq...\geq\gamma_{d}\geq 0$ and $k\in[d]$ be any numbers such that $\gamma_{i}=0$ for $i>k$, and define $\Gamma\coloneqq$ diag $(\gamma_{1},...,\gamma_{d})$.
Then if $A$ satisfies Assumption 2.1 for $(A,k,T,\sigma,\gamma)$, we have

$$ $\mathbb{E}\left[\|\hat{V}\Gamma^{\top}\Gamma\hat{V}^{\top}-V\Gamma^{\top} \Gamma V^{\top}\|_{F}^{2}\right]\leq O\left(\sum_{i=1}^{k}\sum_{j=i+1}^{d} \dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}\right )T.$ (3) $$

We give an overview of the proof of Theorem 2.2 in Section 4. The full proof is given in Appendix A.

###### Assumption 2.1 ( A , k , T , σ , γ ) A,k,T,\sigma,\gamma) italic_A , italic_k , italic_T , italic_σ , italic_γ ) (Singular value gaps).

###### Theorem 2.2 ( Main result).

### 2.1 Application to singular subspace recovery.

To obtain a pertubration bound for the subspace recovery problem, we plug in $\gamma_{i}=1$ for all $i\leq k$, and $\gamma_{i}=0$ for all $i>k$, into Theorem 2.2.

###### Corollary 2.3 ( Subspace recovery).

Let $T>0$.
Given a rectangular matrix $A\in\mathbb{R}^{m\times d}$ with singular values $\sigma_{1}\geq...\geq\sigma_{d}\geq 0$ and corresponding right-singular vectors $v_{1},...v_{d}$.
Let $G$ be a matrix with i.i.d. $N(0,1)$ entries, and consider the perturbed matrix $\hat{A}=A+\sqrt{T}G$.

For any $k\in[d]$, define the $d\times k$ matrices $V_{k}=[v_{1},...v_{k}]$ and $\hat{V}_{k}=[\hat{v}_{1},...\hat{v}_{k}]$ where $\hat{v}_{1},\cdots,\hat{v}_{k}$ denote the right-singular vectors of $\hat{A}$ corresponding to its top-$k$ singular values.
Then if $A$ satisfies Assumption 2.1($A,k,T,\sigma,\gamma$) where $\gamma=(1,\cdots,1,0,\cdots,0)$ is the vector with the first $k$ entries equal to $1$, we have

$$ $\mathbb{E}\left[\|\hat{V}_{k}\hat{V}_{k}^{\top}-V_{k}V_{k}^{\top}\|_{F}\right] \leq O\left(\dfrac{\sqrt{kd}}{\sigma_{k}-\sigma_{k+1}}\sqrt{T}\right).$ (4) $$

Moreover, if we further have that $\sigma_{i}-\sigma_{i+1}\geq\Omega(\sigma_{k}-\sigma_{k+1})$ for all $i\leq k$, then

$$ $\mathbb{E}\left[\|\hat{V}_{k}\hat{V}_{k}^{\top}-V_{k}V_{k}^{\top}\|_{F}\right] \leq O\left(\dfrac{\sqrt{d}}{\sigma_{k}-\sigma_{k+1}}\sqrt{T}\right).$ (5) $$

The proof of Corollary 2.3 is given in Appendix B.

Corollary 2.3 improves, in the setting where the perturbation $G$ is a Gaussian random matrix, by a factor of $\frac{\sqrt{m}}{\sqrt{d}}$ (in expectation) on the bound $\|\hat{V}_{k}\hat{V}_{k}^{\top}-V_{k}V_{k}^{\top}\|_{F}\leq O(\dfrac{\sqrt{km}
}{\sigma_{k}-\sigma_{k+1}}\sqrt{T})$
w.h.p. implied by the Davis-Kahan-Wedin sine-Theta theorem [, ], whenever Assumption 2.1 is satisfied.
If we also have that $\sigma_{i}-\sigma_{i+1}\geq\Omega(\sigma_{k}-\sigma_{k+1})$ for all $i\leq k$ (as is the case for many real-world datasets which may exhibit exponential decay in their singular values), the improvement is $\sqrt{k}\frac{\sqrt{m}}{\sqrt{d}}$

Moreover,
Corollary 2.3 also improves, in the setting where the perturbation $G$ is a Gaussian random matrix, by a factor of $\sqrt{k}\frac{\sqrt{m}}{\sqrt{d}}$, on the bound of $\|\hat{V}_{k}\hat{V}_{k}^{\top}-V_{k}V_{k}^{\top}\|_{F}\leq O(k\frac{\sqrt{m}}
{\sigma_{k}}\sqrt{T})$ w.h.p. implied by Theorem 18 of [], when Assumption 2.1 is satisfied and e.g. $\sigma_{k}-\sigma_{k+1}=\Omega(\sigma_{k})$ (as is also the case for many real-world datasets).
If we also have that $\sigma_{i}-\sigma_{i+1}\geq\Omega(\sigma_{k}-\sigma_{k+1})$ for all $i\leq k$, the improvement is $k\frac{\sqrt{m}}{\sqrt{d}}$.

###### Corollary 2.3 ( Subspace recovery).

### 2.2 Application to rank- k 𝑘 k italic_k covariance matrix approximation.

To obtain a perturbation bound for the rank-$k$ covariance matrix approximation problem, we plug in $\gamma_{i}=\sigma_{i}$ for all $i\leq k$, and $\gamma_{i}=\sigma_{i}$ for all $i>k$, into Theorem 2.2.

###### Corollary 2.4 ( Rank- $k$ covariance matrix approximation).

Let $T>0$.
Given a rectangular matrix $A\in\mathbb{R}^{m\times d}$ with singular values $\sigma_{1}\geq...\geq\sigma_{d}\geq 0$ and with right-singular vectors $v_{1},...v_{d}$, where we define $V:=[v_{1},...v_{d}]\in\mathbb{R}^{d\times d}$.
Let $G$ be a matrix with i.i.d. $N(0,1)$ entries, and consider the perturbed matrix that outputs $\hat{A}=A+\sqrt{T}G$.

For any $k\in[d]$, define $\Sigma_{k}\coloneqq$ diag $(\sigma_{1},...,\sigma_{k},0,...0)$. Define $\hat{\sigma}_{1}\geq...\geq\hat{\sigma}_{d}\geq 0$ to be the singular values of $\hat{A}$ with corresponding orthonormal right-singular vectors $\hat{v}_{1},...\hat{v}_{d}$, where we define $\hat{V}:=[\hat{v}_{1},...\hat{v}_{d}]$, and define $\hat{\Sigma}_{k}\coloneqq$ diag $(\hat{\sigma}_{1},...,\hat{\sigma}_{k},0,...0)$.
Then if $A$ satisfies Assumption 2.1 for $(A,k,T,\sigma,\gamma)$ for $\gamma=(\sigma_{1},\cdots,\sigma_{k},0,\cdots,0)$, we have

$$ $\mathbb{E}\left[\|\hat{V}\hat{\Sigma}_{k}^{\top}\hat{\Sigma}_{k}\hat{V}^{\top} -V\Sigma_{k}^{\top}\Sigma_{k}V^{\top}\|_{F}^{2}\right]\leq O\left(d\|\Sigma_{k }\|_{F}^{2}+k\sum_{j=k+1}^{d}\left(\sigma_{k}\dfrac{\sigma_{k}}{\sigma_{k}- \sigma_{j}}\right)^{2}\right)T.$ (6) $$

The proof of Corollary 2.4 is given in Appendix C.
In particular, Corollary 2.4 implies that

$$ $\displaystyle\sqrt{\mathbb{E}\left[\|\hat{V}\hat{\Sigma}_{k}^{\top}\hat{\Sigma }_{k}\hat{V}^{\top}-V\Sigma_{k}^{\top}\Sigma_{k}V^{\top}\|_{F}^{2}\right]}$ $\displaystyle\leq O\left(\sqrt{k}\sqrt{d}\left(\sigma_{1}+\sigma_{k}\dfrac{ \sigma_{k}}{\sigma_{k}-\sigma_{k+1}}\right)\right)\sqrt{T}.$ $$

Corollary 2.4 improves, in the setting where the perturbation $G$ is a Gaussian random matrix, by a factor of $\frac{\sqrt{m}}{\sqrt{d}}$ (in expectation) on the bound of
$\|\hat{V}\hat{\Sigma}_{k}^{\top}\hat{\Sigma}_{k}\hat{V}^{\top}-V\Sigma_{k}^{
\top}\Sigma_{k}V^{\top}\|_{F}\leq O(k^{1.5}\sqrt{m}\sqrt{T}\sigma_{1}+\sigma_{
k}^{2}\frac{\sqrt{k}\sqrt{m}}{\sigma_{k}-\sigma_{k+1}}\sqrt{T})$ w.h.p. implied by the Davis-Kahan-Wedin sine-Theta theorem [, ] whenever Assumption 2.1 is satisfied (see Appendix D for details).
If we also have that $\sigma_{k}-\sigma_{k+1}=\Omega(\sigma_{k})$, the improvement is $\frac{\sqrt{m}}{\sqrt{d}}k$.

Moreover, Corollary 2.4 also improves, when the perturbation is Gaussian, by a factor of $\frac{\sqrt{m}}{\sqrt{d}}\sqrt{k}$ (in expectation) on the bound implied by Theorem 18 of [] whenever e.g. $\sigma_{k}-\sigma_{k+1}=\Omega(\sigma_{k})$, as in this setting their bound implies $\|\hat{V}\hat{\Sigma}_{k}^{\top}\hat{\Sigma}_{k}\hat{V}^{\top}-V\Sigma_{k}^{
\top}\Sigma_{k}V^{\top}\|_{F}\leq O\left(\sigma_{1}k\sqrt{m}\sqrt{T}\right)$ w.h.p. (see Appendix D for details).

###### Remark 2.5 ( Tightness in full-rank special case).

In the special case where $k=d$, we have
$\|(A+\sqrt{T}G)^{\top}(A+\sqrt{T}G)-A^{\top}A\|_{F}=\|\sqrt{T}A^{\top}G+\sqrt{
T}G^{\top}A+TG^{\top}G\|_{F}=\Theta(\|A^{\top}G\|_{F}\sqrt{T})=\Theta(\|\Sigma
_{d}\|_{F}\sqrt{d}\sqrt{T})$
with high probability.
Thus, Corollary 2.4 is tight for this special case.

The last equality above holds w.h.p. because $\|A^{\top}G\|_{F}^{2}=\mathrm{tr}(G^{\top}AA^{\top}G)=\mathrm{tr}(G^{\top}
\Sigma_{d}\Sigma_{d}^{\top}G)=\mathrm{tr}(\Sigma_{d}\Sigma_{d}^{\top}GG^{\top}
)=\|\Sigma_{d}\|_{F}^{2}d$ w.h.p., where we may assume without loss of generality that $A$ is a diagonal matrix because the distribution of $G$ is invariant w.r.t. multiplication by orthogonal matrices.

###### Corollary 2.4 ( Rank- k 𝑘 k italic_k covariance matrix approximation).

###### Remark 2.5 ( Tightness in full-rank special case).

## 3 Preliminaries

In this section, we present preliminary materials used in the proof of our main result.
In particular, we present the aformentioned matrix-valued Brownian motion process $\Phi(t)$ in Section 3.1.
Next, we present the stochastic differential equations (SDEs) which govern the evolution of the singular values of right-singular vectors of $\Phi(t)$ in Section 3.2.

### 3.1 Dyson-Bessel process

We consider the matrix-valued stochastic motion process, $\Phi(t)$, where, for all $t\geq 0$, the entries of $\Phi(t)$ evolve as independent standard Brownian motions with initial condition $\Phi(0)=A$.
In particular, at time $t=T$ we have $\Phi(T)=A+\sqrt{T}G$ where $G$ is an $m\times d$ Gaussian random matrix with iid $N(0,1)$ entries.

Recall that $\sigma_{1}\geq\ldots\geq\sigma_{d}$ denote the singular values of $A$.
At every time $t>0$, we denote (with slight abuse of notation) the singular values of $\Phi(t)$ by $\sigma_{1}(t)\geq\sigma_{2}(t)\geq\dots\geq\sigma_{d}(t)$.
In particular $\sigma_{i}\equiv\sigma_{i}(0)$ for all $i\in[d]$, and the singular values $\sigma_{1}(t),\ldots,\sigma_{d}(t)$ are distinct at every time $t>0$ with probability 1 (see e.g. []).
The matrix-valued Brownian motion $\Phi(t)$ induces stochastic diffusion processes on the singular values $\sigma_{i}(t)$ and singular vectors $v_{i}(t)$, referred to as the Dyson-Bessel process.
The dynamics of the singular values $\sigma_{i}(t)$ of the Dyson-Bessel process are given by the following system of stochastic differential equations (see e.g. [] or Theorem 1 in []),

$$ $\mathrm{d}\sigma_{i}(t)=\mathrm{d}\beta_{ii}(t)+\left(\frac{1}{2\sigma_{i}(t)} \sum_{\{j\in[d]:j\neq i\}}\frac{(\sigma_{i}(t))^{2}+(\sigma_{j}(t))^{2}}{( \sigma_{i}(t))^{2}-(\sigma_{j}(t))^{2}}+\frac{m-1}{2\sigma_{i}(t)}\right) \mathrm{d}t,\qquad\forall 1\leq i\leq d,$ (7) $$

where $\beta_{ii},1\leq i\leq d$ is a family of independent one-dimensional Brownian motions.

### 3.2 Right singular vector SDE

The dynamics of right-singular vectors $v_{i}(t)$ of the Dyson-Bessel process are governed by the following stochastic differential equations (see e.g. [] or Theorem 2 in []),

$$ $\displaystyle\mathrm{d}v_{i}(t)$ $\displaystyle=\sum_{\{j\in[d]:j\neq i\}}v_{j}(t)\sqrt{\dfrac{(\sigma_{j}(t))^{ 2}+(\sigma_{i}(t))^{2}}{((\sigma_{j}(t))^{2}-(\sigma_{i}(t))^{2})^{2}}}\mathrm {d}\beta_{ji}(t)-\frac{v_{i}(t)}{2}\sum_{\{j\in[d]:j\neq i\}}\dfrac{(\sigma_{j }(t))^{2}+(\sigma_{i}(t))^{2}}{((\sigma_{j}(t))^{2}-(\sigma_{i}(t))^{2})^{2}} \mathrm{d}t$ $\displaystyle=\sum_{\{j\in[d]:j\neq i\}}v_{j}(t)c_{ij}(t)\mathrm{d}\beta_{ji}( t)-\frac{v_{i}(t)}{2}\sum_{\{j\in[d]:j\neq i\}}c_{ij}^{2}(t)\mathrm{d}t,\qquad \forall 1\leq i\leq d,$ (8) $$

where $\beta_{ij}(t),1\leq i<j\leq d$, is a family of independent standard one-dimensional Brownian motions, and the $\beta_{ij}(t)$ form a skew-symmetric matrix, i.e. $\beta_{ij}(t)=-\beta_{ji}(t)$ for all $t\geq 0$.
For convenience, in the above equation, we denote $c_{ij}(t):=\sqrt{\frac{(\sigma_{j}(t))^{2}+(\sigma_{i}(t))^{2}}{((\sigma_{j}(t
))^{2}-(\sigma_{i}(t))^{2})^{2}}}=c_{ji}(t)$ for all $i,j\in[d]$.

### 3.3 Ito’s Lemma

We will also use the following result from stochastic Calculus, Ito’s Lemma, which is a generalization of the chain rule in deterministic calculus.

###### Lemma 3.1 ( Ito’s Lemma [ 16 ] ).

Let $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a second-order differentiable function, and let $X(t)$ be a diffusion process on $\mathbb{R}^{d}$.
Then

$$ $\textstyle\mathrm{d}f(X_{t})=(\nabla f(X_{t}))^{\top}\mathrm{d}X_{t}+\frac{1}{ 2}(\mathrm{d}X_{t})^{\top}(\nabla^{2}f(X_{t}))\mathrm{d}X_{t}\qquad\forall t \geq 0.$ $$

###### Lemma 3.1 ( Ito’s Lemma [ 16 ] ).

### 3.4 Other preliminaries

We will use the following deterministic eigenvalue perturbation bound

###### Lemma 3.2 ( Weyl’s Inequality [ 28 ] ).

Let $A,E\in\mathbb{R}^{m\times d}$ is a matrix.
Denote by $\sigma_{1}\geq\ldots\geq\sigma_{d}$ the singular values of $A$ and by $\hat{\sigma}_{1}\geq\ldots\geq\hat{\sigma}_{d}$ the singular values of $A+E$.
Then

$$ $|\sigma_{i}-\hat{\sigma}_{i}|\leq\|E\|_{2}\qquad\forall i\in[d].$ $$

The following concentration bound, Theorem 4.4.5 of [] applied to Gaussian random matrices, will allow us to bound the spectral norm of the Gaussian perturbation $G$ (which in turn will allow us to apply (3.2) to bound the perturbations to eigenvalues).

###### Lemma 3.3 ( Spectral-norm concentration bound for Gaussian matrices [ 26 ] ).

If $G\in\mathbb{R}^{m\times d}$ is a Gaussian random matrix with iid $N(0,1)$ entries, then

$$ $\mathbb{P}(\|G\|_{2}>\sqrt{m}+\sqrt{d}+s)<2e^{-s^{2}}\qquad\forall s>0.$ $$

###### Lemma 3.2 ( Weyl’s Inequality [ 28 ] ).

###### Lemma 3.3 ( Spectral-norm concentration bound for Gaussian matrices [ 26 ] ).

## 4 Overview of proof of Theorem 2.2

We present an overview of the proof of Theorem 2.2 along with the main technical lemmas used in the proof.
In Steps 1 and 2 we express the perturbed matrix, and its quantities of interest derived from its right-singular vectors, as matrix-valued diffusions.
Steps 3, 4, and 5 present the main technical lemmas, and we complete the proof in Step 6.
The full proof is given in Appendix A.5.

### 4.1 Viewing the perturbed matrix as a matrix-valued Brownian motion.

To obtain our bounds, we begin by defining the matrix-valued Brownian motion,

$$ $\Phi(t):=A+B(t)\qquad\qquad\forall t\geq 0,$ $$

where the entries of $B(t)$ evolve as independent standard Brownian motions initialized at 0 0.
In particular, at time $t=0$ we have $\Phi(0)=A$, and at time $t=T$ we have $\Phi(T)=A+\sqrt{T}G$ where $G$ is an $m\times d$ Gaussian random matrix with iid $N(0,1)$ entries.

### 4.2 Projecting the matrix Brownian motion onto the orthogonal orbit 𝒪 Γ 2 subscript 𝒪 superscript Γ 2 \mathcal{O}_{\Gamma^{2}} caligraphic_O start_POSTSUBSCRIPT roman_Γ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_POSTSUBSCRIPT .

Denote by $A=U\Sigma V^{\top}$ and $\hat{A}=\hat{U}\hat{\Sigma}\hat{V}^{\top}$ singular value decompositions of $A$ and $\hat{A}$, respectively, where $U,\hat{U}\in\mathrm{O}(m)$, $V,\hat{V}\in\mathrm{O}(d)$, and $\Sigma,\hat{\Sigma}\in\mathbb{R}^{m\times d}$ are diagonal.

Recall that our goal is to bound the quantity $\mathbb{E}[\|\hat{V}\Gamma^{\top}\Gamma\hat{V}^{\top}-V\Gamma^{\top}\Gamma V^{
\top}\|_{F}]$, where $A^{\top}A=V\Sigma^{\top}\Sigma V^{\top}$ and $\hat{A}^{\top}\hat{A}=\hat{V}\hat{\Sigma}^{\top}\hat{\Sigma}\hat{V}^{\top}$ are eigenvalue decompositions of $A^{\top}A$ and $\hat{A}^{\top}\hat{A}$.
To obtain a bound on this quantity,
we first define a stochastic process $\Psi(t)$ for which $\Psi(0)=V\Gamma^{\top}\Gamma V^{\top}$ and $\Psi(T)=\hat{V}\Gamma^{\top}\Gamma\hat{V}^{\top}$.
We then bound the expected Frobenius distance

$$ $\mathbb{E}[\|\hat{V}\Gamma^{\top}\Gamma\hat{V}^{\top}-V\Gamma^{\top}\Gamma V^{ \top}\|_{F}]=\mathbb{E}[\|\Psi(T)-\Psi(0)\|_{F}]$ $$

by integrating the stochastic derivative of $\Psi(t)$ over the time period $[0,T]$.

Towards this end, at every time $t\geq 0$, define $\Phi(t):=U(t)\Sigma(t)V(t)^{\top}$ to be a singular value decomposition of the rectangular matrix $\Phi(t)$, where $\Sigma(t)\in\mathbb{R}^{m\times d}$ is a diagonal matrix whose diagonal entries are the singular values $\sigma_{1}(t)\geq\cdots\geq\sigma_{d}(t)$ of $\Phi(t)$.
$V(t)=[v_{1}(t),\cdots,v_{d}(t)]$ is a $d\times d$ orthogonal matrix whose columns $v_{1}(t),\cdots,v_{d}(t)$ are the corresponding right-singular vectors of $\Phi(t)$.
$V(t)\in\mathrm{O}(m)$ is an $m\times m$ orthogonal matrix whose columns are left-singular vectors of $\Phi(t)$.

At every time, denote by $\Psi(t)\in\mathcal{O}_{\Gamma^{2}}$ to be the symmetric matrix with given eigen values $\Gamma(t)^{\top}\Gamma(t)$ and eigenvectors given by the columns of $V(t)$:

$$ $\Psi(t):=V(t)\Gamma(t)^{\top}\Gamma(t)V(t)^{\top},\forall t\in[0,T].$ $$

In other words, $\Psi(t)\in\mathcal{O}_{\Gamma^{2}}$ is the Frobenius-distance minimizing projection of the matrix Brownian motion $\Phi(t)$ onto the orthogonal orbit manifold $\mathcal{O}_{\Gamma^{2}}$.

### 4.3 Deriving an expression for the stochastic derivative d ⁢ Ψ ⁢ ( t ) d Ψ 𝑡 \mathrm{d}\Psi(t) roman_d roman_Ψ ( italic_t ) .

To bound the expected squared Frobenius distance $\mathbb{E}\left[\|\Psi(T)-\Psi(0)\|_{F}^{2}\right]$ we would like to express it as an integral in terms of the stochastic derivative of $\Phi(t)$.

Towards this end, we use the stochastic differential equations which govern the evolution of the eigenvectors of the Dyson-Bessel process (A.1) to derive an expression for the stochastic derivative $\mathrm{d}\Psi(t)$ of the matrix diffusion $\Psi(t)$ (Lemma A.2),

$$ $\displaystyle\mathrm{d}\Psi(t)$ $\displaystyle=\sum_{i=1}^{d}\gamma_{i}^{2}\mathrm{d}(v_{i}(t)v_{i}^{\top}(t))$ $\displaystyle\sum_{i=1}^{d}\sum_{j\neq i}(\gamma_{i}^{2}-\gamma_{j}^{2})\left[ \dfrac{c_{ij}(t)}{2}\mathrm{d}\beta_{ji}(t)(v_{i}(t)v_{j}^{\top}(t)+v_{j}(t)v_ {i}^{\top}(t))-c_{ij}^{2}(t)\mathrm{d}t(v_{i}(t)v_{i}^{\top}(t))\right].$ (9) $$

### 4.4 Using Gaussian concentration and Weyl’s inequality to bound the singular value gaps.

The above equation (4.3) for the stochastic derivative $\mathrm{d}\Psi(t)$ includes terms $c_{ij}(t)$, whose magnitude is proportional to the inverse of the gaps in the squared singular values $\sigma_{i}^{2}(t)-\sigma_{j}^{2}(t)$ for each $i,j\in[d]$.
In order to bound these terms, we use Weyl’s inequality (3.2) together with standard concentration bounds for the spectral norm of Gaussian random matrices (Lemma 3.3), to show that the gaps $\sigma_{i}(t)-\sigma_{j}(t)$ in the top $k+1$ singular values satisfy (Lemma A.3),

$$ $\sigma_{i}(t)-\sigma_{j}(t)\geq\dfrac{1}{2}(\sigma_{i}-\sigma_{j})\qquad \forall t\in[0,T],\,\,i<j\leq k+1$ $$

with high probability at least $1-\delta$, provided that the initial gaps are sufficiently large to satisfy Assumption 2.1($A,k,T,\sigma,\gamma$) .

This implies that, with high probability at least $1-\delta$, the inverse-eigenvalue gap terms in (4.3) satisfy (Lemma A.4)

$$ $\displaystyle c_{ij}(t)$ $\displaystyle=\sqrt{\frac{(\sigma_{j}(t))^{2}+(\sigma_{i}(t))^{2}}{((\sigma_{j }(t))^{2}-(\sigma_{i}(t))^{2})^{2}}}$ $\displaystyle\leq\dfrac{4}{\sigma_{i}-\sigma_{j}},\qquad\forall i<j,\,\,t\in[0 ,T].$ (10) $$

### 4.5 Integrating the stochastic derivative of d Ψ ⁢ ( t ) Ψ 𝑡 \Psi(t) roman_Ψ ( italic_t ) over the time interval [ 0 , T ] 0 𝑇 [0,T] [ 0 , italic_T ] .

Next we express the expected squared Frobenius distance $\mathbb{E}\left[\|\Psi(T)-\Psi(0)\|_{F}^{2}\right]$ as an integral $\mathbb{E}\left[\|\Psi(T)-\Psi(0)\|_{F}^{2}\right]=\mathbb{E}\left[\|\int_{0}^
{T}\mathrm{d}\Psi(t)\|_{F}^{2}\right]$.

Next, we apply Ito’s Lemma (Lemma 3.1) to $f(\Psi(t))$ where $f(X):=\|\cdot\|_{F}^{2}$, and plug in our high-probability bound on the inverse eigenvalue gap terms $c_{ij}(t)$ (4.4), to derive an upper bound for the integral $\mathbb{E}\left[\|\int_{0}^{T}\mathrm{d}\Psi(t)\|_{F}^{2}\right]$, which gives roughly (Lemma A.5)

$$ $\displaystyle\mathbb{E}\left[\|\Psi(T)-\Psi(0)\|_{F}^{2}\right]$ $\displaystyle\leq\int_{0}^{T}\mathbb{E}\left[\sum_{i=1}^{d}\sum_{j\neq i}( \gamma_{i}^{2}-\gamma_{j}^{2})^{2}c_{ij}^{2}(t)\right]\mathrm{d}t+T\int_{0}^{T }\mathbb{E}\left[\sum_{i=1}^{d}\left(\sum_{j\neq i}(\gamma_{i}^{2}-\gamma_{j}^ {2})^{2}c_{ij}^{2}(t)\right)^{2}\right]\mathrm{d}t$ $\displaystyle\leq\int_{0}^{T}\mathbb{E}\left[\sum_{i=1}^{d}\sum_{j\neq i} \dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}\right ]\mathrm{d}t+T\int_{0}^{T}\mathbb{E}\left[\sum_{i=1}^{d}\left(\sum_{j\neq i} \dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})}{(\sigma_{i}-\sigma_{j})^{2}}\right)^{2 }\right]\mathrm{d}t.$ (11) $$

Noting that the second term on the right-hand side of (4.5)is at least as small as the first term, and applying the Cauchy-Schwarz inequality to the second term, we get that (Theorem 2.2),

$$ $\displaystyle\mathbb{E}\left[\|\hat{V}\Gamma^{\top}\Gamma\hat{V}^{\top}-V \Gamma^{\top}\Gamma V^{\top}\|_{F}^{2}\right]$ $\displaystyle=\mathbb{E}\left[\|\Psi(T)-\Psi(0)\|_{F}^{2}\right]$ $\displaystyle\leq O\left(\sum_{i=1}^{k}\sum_{j=i+1}^{d}\dfrac{(\gamma_{i}^{2}- \gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}\right)T.$ $$

## 5 Conclusion

In this paper, we obtain Frobenius-norm bounds on the perturbation to the singular subspace spanned by the top-$k$ singular vectors of a matrix $A\in\mathbb{R}^{m\times d}$, when $A$ is perturbed by an $m\times d$ Gaussian random matrix.
Our bounds improve, in many settings where the perturbation is Gaussian, on bounds implied by previous works, by a factor of roughly $\frac{\sqrt{m}}{\sqrt{d}}\sqrt{k}$.
This may lead to a large improvement in many applications, as one oftentimes has that the number $m$ of rows in the data matrix (corresponding to the number of datapoints) is much larger than the number of columns $d$ (which oftentimes correspond to different features in the data).
To obtain our bounds we view use tools from stochastic calculus to track the evolution of the subspace spanned by the top-$k$ singular vectors.

On the other hand, we note that our bounds assume that the top-$k$ singular value gaps of $A$ are roughly $\Omega(\sqrt{m})$; while this assumption may hold in settings where the data matrix has fast-decaying singular values, it would be interesting to see if it is possible to relax this assumption.
Moreover, we note that our bounds only apply in the special case when the perturbation $G$ is Gaussian, and it would be interesting to see whether our bounds can be extended to other random matrix distributions.

## Appendix A Proof Theorem 2.2

### A.1 Proof of Lemma A.1

We first decomposite the matrix $\Psi(t)$ as a sum of its right-singular vectors: $\Psi(t)=\sum_{i=1}^{d}\gamma_{i}^{2}(v_{i}(t)v_{i}^{\top}(t))$.
Thus we have

$$ $\mathrm{d}\Psi(t)=\sum_{i=1}^{d}\gamma_{i}^{2}\mathrm{d}(v_{i}(t)v_{i}^{\top}( t))$ (12) $$

We begin by computing the stochastic derivative $\mathrm{d}v_{i}(t)v_{i}^{\top}(t)$ for each $i\in[d]$, by applying the formula in (A.1), together with Ito’s Lemma (Lemma 3.1).

###### Lemma A.1 (Stochastic derivative of $v_{i}(t)v_{i}(t)^{\top}$ ) .

For all $t\in[0,T]$,

$$ $\mathrm{d}\left(v_{i}(t)v_{i}^{\top}(t)\right)=\sum_{j\neq i}v_{j}(t)c_{ij}(t) \mathrm{d}\beta_{ji}(t)-\frac{1}{2}v_{i}(t)\sum_{j\neq i}c_{ij}^{2}(t)\mathrm{ d}t.$ $$

###### Proof.

The dynamic of right-singular vectors [] are the following:

$$ $\displaystyle\mathrm{d}v_{i}(t)$ $\displaystyle=\sum_{j\neq i}v_{j}(t)\sqrt{\dfrac{\lambda_{j}(t)+\lambda_{i}(t) }{(\lambda_{j}(t)-\lambda_{i}(t))^{2}}}\mathrm{d}\beta_{ji}(t)-\frac{1}{2}v_{i }(t)\sum_{j\neq i}\dfrac{\lambda_{j}(t)+\lambda_{i}(t)}{(\lambda_{j}(t)- \lambda_{i}(t))^{2}}\mathrm{d}t$ $\displaystyle=\sum_{j\neq i}v_{j}(t)c_{ij}(t)\mathrm{d}\beta_{ji}(t)-\frac{1}{ 2}v_{i}(t)\sum_{j\neq i}c_{ij}^{2}(t)\mathrm{d}t.$ $$

Thus, we have

$$ $\displaystyle\mathrm{d}\left(v_{i}(t)v_{i}^{\top}(t)\right)=\left(v_{i}(t)+ \mathrm{d}v_{i}(t)\right)\left(v_{i}(t)+\mathrm{d}v_{i}(t)\right)^{\top}-v_{i} (t)v_{i}^{\top}(t)$ $\displaystyle=\left(v_{i}(t)+\sum_{j\neq i}v_{j}(t)c_{ij}(t)\mathrm{d}\beta_{ ji}(t)-\frac{1}{2}v_{i}(t)\sum_{j\neq i}c_{ij}^{2}\mathrm{d}t\right)$ $\displaystyle\qquad\qquad\times\left(v_{i}(t)^{\top}+\sum_{j\neq i}v_{j}(t)^{ \top}c_{ij}(t)\mathrm{d}\beta_{ji}(t)-\frac{1}{2}v_{i}(t)^{\top}\sum_{j\neq i} c_{ij}^{2}(t)\mathrm{d}t\right)-v_{i}(t)v_{i}(t)^{\top}$ $\displaystyle=v_{i}(t)\left(\sum_{j\neq i}v_{j}^{\top}(t)c_{ij}(t)\mathrm{d} \beta_{ji}(t)\right)-\frac{1}{2}v_{i}(t)v_{i}^{\top}(t)\sum_{j\neq i}c_{ij}^{2 }(t)\mathrm{d}t+\left(\sum_{j\neq i}v_{j}(t)c_{ij}(t)\mathrm{d}\beta_{ji}(t) \right)v_{i}^{\top}(t)$ $\displaystyle+\left(\sum_{j\neq i}v_{j}(t)c_{ij}(t)\mathrm{d}\beta_{ji}(t) \right)\left(\sum_{j\neq i}v_{j}^{\top}(t)c_{ij}(t)\mathrm{d}\beta_{ji}(t) \right)-\frac{1}{2}v_{i}(t)v_{i}^{\top}(t)\sum_{j\neq i}c_{ij}^{2}(t)\mathrm{d }t+o(\mathrm{d}t)$ $\displaystyle=v_{i}(t)\left(\sum_{j\neq i}v_{j}^{\top}(t)c_{ij}(t)\mathrm{d} \beta_{ji}(t)\right)+\left(\sum_{j\neq i}v_{j}(t)c_{ij}(t)\mathrm{d}\beta_{ji} (t)\right)v_{i}^{\top}(t)-v_{i}(t)v_{i}^{\top}(t)\sum_{j\neq i}c_{ij}^{2}(t) \mathrm{d}t$ $\displaystyle+\sum_{k\neq i}\sum_{j\neq i}v_{k}(t)v_{j}^{\top}(t)c_{ik}(t)c_{ ij}(t)\mathrm{d}\beta_{ki}(t)\mathrm{d}\beta_{ji}(t)$ $\displaystyle=v_{i}(t)\left(\sum_{j\neq i}v_{j}^{\top}(t)c_{ij}(t)\mathrm{d} \beta_{ji}(t)\right)+\left(\sum_{j\neq i}v_{j}(t)c_{ij}(t)\mathrm{d}\beta_{ji} (t)\right)v_{i}^{\top}(t)-v_{i}(t)v_{i}^{\top}(t)\sum_{j\neq i}c_{ij}^{2}(t) \mathrm{d}t$ $\displaystyle+\sum_{k\neq i}\sum_{j\neq i}v_{k}(t)v_{j}^{\top}(t)c_{ik}(t)c_{ ij}(t)\mathbbm{1}_{\{(kj)=(ii)\}}\mathrm{d}t$ $\displaystyle=\sum_{j\neq i}c_{ij}(t)\mathrm{d}\beta_{ji}(t)(v_{i}(t)v_{j}^{ \top}(t)+v_{j}(t)v_{i}^{\top}(t))-\sum_{j\neq i}c_{ij}^{2}(t)\mathrm{d}t(v_{i} (t)v_{i}^{\top}(t)-v_{j}(t)v_{j}^{\top}(t)).$ $$

∎

###### Lemma A.1 (Stochastic derivative of v i ⁢ ( t ) ⁢ v i ⁢ ( t ) ⊤ subscript 𝑣 𝑖 𝑡 subscript 𝑣 𝑖 superscript 𝑡 top v_{i}(t)v_{i}(t)^{\top} italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_t ) italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_t ) start_POSTSUPERSCRIPT ⊤ end_POSTSUPERSCRIPT ) .

###### Proof.

### A.2 Proof of Lemma A.2

Recall that

$$ $\Psi(t)=\sum_{i=1}^{d}\gamma_{i}^{2}(v_{i}(t)v_{i}^{\top}(t)).$ $$

We now apply Lemma A.1 to compute the stochastic derivative of $\Psi(t)$.

###### Lemma A.2 (Stochastic derivative of $\Psi(t)$ ) .

For all $t\in[0,T]$, we have that

$$ $\mathrm{d}\Psi(t)=\sum_{i=1}^{d}\sum_{j\neq i}(\gamma_{i}^{2}-\gamma_{j}^{2}) \left[\dfrac{c_{ij}(t)}{2}\mathrm{d}\beta_{ji}(t)(v_{i}(t)v_{j}^{\top}(t)+v_{j }(t)v_{i}^{\top}(t))-c_{ij}^{2}(t)\mathrm{d}t(v_{i}(t)v_{i}^{\top}(t))\right].$ $$

###### Proof.

$$ $\displaystyle\mathrm{d}\Psi(t)$ $\displaystyle=\sum_{i=1}^{d}\gamma_{i}^{2}\mathrm{d}(v_{i}(t)v_{i}^{\top}(t))$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{d}\gamma_{i}^{2}\left(\sum_{j\neq i}c_{ij}(t)\mathrm{ d}\beta_{ji}(t)(v_{i}(t)v_{j}^{\top}(t)+v_{j}(t)v_{i}^{\top}(t))-\sum_{j\neq i }c_{ij}^{2}(t)\mathrm{d}t(v_{i}(t)v_{i}^{\top}(t)-v_{j}(t)v_{j}^{\top}(t))\right)$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{d}\sum_{j\neq i}\gamma_{i}^{2}c_{ij}(t)\mathrm{d} \beta_{ji}(t)(v_{j}(t)v_{i}^{\top}(t)+v_{i}(t)v_{j}^{\top}(t))-\sum_{i=1}^{d} \sum_{j\neq i}\gamma_{i}^{2}c_{ij}^{2}(t)\mathrm{d}t(v_{i}(t)v_{i}^{\top}(t)-v _{j}(t)v_{j}^{\top}(t))$ $\displaystyle=$ $\displaystyle\dfrac{1}{2}\sum_{i=1}^{d}\sum_{j\neq i}(\gamma_{i}^{2}-\gamma_{j }^{2})c_{ij}(t)\mathrm{d}\beta_{ji}(t)(v_{i}v_{j}(t)^{\top}+v_{j}(t)v_{i}^{ \top})$ $\displaystyle\qquad\qquad-\dfrac{1}{2}\sum_{i=1}^{d}\sum_{j\neq i}(\gamma_{i}^ {2}-\gamma_{j}^{2})c_{ij}^{2}(t)\mathrm{d}t(v_{i}v_{i}^{\top}-v_{j}(t)v_{j}(t) ^{\top})$ $\displaystyle=$ $\displaystyle\dfrac{1}{2}\sum_{i=1}^{d}\sum_{j\neq i}(\gamma_{i}^{2}-\gamma_{j }^{2})c_{ij}(t)\mathrm{d}\beta_{ji}(t)(v_{i}v_{j}(t)^{\top}+v_{j}(t)v_{i}(t)^{ \top})-\sum_{i=1}^{d}\sum_{j\neq i}(\gamma_{i}^{2}-\gamma_{j}^{2})c_{ij}^{2}(t )\mathrm{d}tv_{i}v_{i}^{\top},$ $$

note that the last two equations are because of these observations:

$$ $\displaystyle c_{ij}(t)\mathrm{d}\beta_{ij}(t)(v_{j}(t)v_{i}(t)^{\top}+v_{i}(t )v_{j}(t)^{\top})$ $\displaystyle=-c_{ij}(t)\mathrm{d}\beta_{ji}(t)(v_{j}(t)v_{i}(t)^{\top}+v_{i}( t)v_{j}(t)^{\top})$ $\displaystyle c_{ij}^{2}(t)\mathrm{d}t(v_{i}(t)v_{i}(t)^{\top}-v_{j}(t)v_{j}(t )^{\top})$ $\displaystyle=-c_{ij}^{2}(t)\mathrm{d}t(v_{j}(t)v_{j}(t)^{\top}-v_{i}(t)v_{i}( t)^{\top})$ $\displaystyle(\gamma_{i}^{2}-\gamma_{j}^{2})c_{ij}^{2}(t)\mathrm{d}t(v_{i}(t)v _{i}(t)^{\top}-v_{j}(t)v_{j}(t)^{\top})$ $\displaystyle=(\gamma_{j}^{2}-\gamma_{i}^{2})c_{ij}^{2}(t)\mathrm{d}t(v_{j}(t) v_{j}(t)^{\top}-v_{i}(t)v_{i}(t)^{\top}).$ $$

∎

###### Lemma A.2 (Stochastic derivative of Ψ ⁢ ( t ) Ψ 𝑡 \Psi(t) roman_Ψ ( italic_t ) ) .

###### Proof.

### A.3 Proofs of Lemmas A.3 and A.4

Next, we show high-probability bounds on the singular gaps $\sigma_{i}(t)-\sigma_{j}(t)$ (Lemma A.3) and coefficients $c_{ij}(t)$ (Lemma A.4).

###### Lemma A.3 (Bound on singular gaps:) .

Suppose that Assumption 2.1 for $(A,k,T,\sigma,\gamma)$ is satisfied. Then for all $t\in[0,T]$, with probability $1-\delta$ where $\delta:=\frac{1}{8d\gamma_{1}^{2}}\times\frac{\gamma_{1}^{2}-\gamma_{d}^{2}}{(
\sigma_{1}-\sigma_{d})^{2}}$, we have
$|\sigma_{i}(t)-\sigma_{j}(t)|\geq\dfrac{1}{2}(\sigma_{i}-\sigma_{j})$ for any $i<j$.

###### Proof.

With probability $1-\delta$, by Lemma 3.3, we have $\|G\|_{2}\leq 2\sqrt{\max\{m,d\}}\log(\frac{1}{\delta})=2\sqrt{m}\log(\frac{1}
{\delta})$. We know $|\sigma_{i}(t)-\sigma_{i}|\leq\sigma_{i}+\|G\|_{2}=\sigma_{i}+2\sqrt{m}\log(
\frac{1}{\delta})$ for any $i$,
therefore, we bound $|\sigma_{i}(t)-\sigma_{j}(t)|=|\sigma_{i}(t)-\sigma_{j}(t)|\geq\sigma_{i}-
\sigma_{j}-4\sqrt{m}\log(\frac{1}{\delta})\geq\dfrac{1}{2}(\sigma_{i}-\sigma_{
j})$ for any $i<j$ and any $t\in[0,T]$.
∎

The following proposition shows that the symmetric coefficients $c_{ij}(t)$ are bounded by the reciprocal of the initial singular value gaps.

###### Lemma A.4 (Bound of coefficients $c_{ij}(t)$ ) .

Suppose that Assumption 2.1 for $(A,k,T,\sigma,\gamma)$ is satisfied. Then for all $t\in[0,T]$, with probability $1-\delta$ where $\delta:=\frac{1}{8d\gamma_{1}^{2}}\times\frac{\gamma_{1}^{2}-\gamma_{d}^{2}}{(
\sigma_{1}-\sigma_{d})^{2}}$, we have

$$ $c_{ij}(t)\leq\dfrac{4}{\sigma_{i}-\sigma_{j}},\quad\text{for any $i<j$}.$ $$

###### Proof.

By Lemma A.3, we have we have with probability at least $1-\delta$

$$ $\displaystyle c_{ij}(t)$ $\displaystyle=\dfrac{\sqrt{\sigma_{j}^{2}(t)+\sigma_{i}^{2}(t)}}{|\sigma_{j}^{ 2}(t)-\sigma_{i}^{2}(t)|}$ $\displaystyle\leq 2\dfrac{\sigma_{j}(t)+\sigma_{i}(t)}{|\sigma_{j}(t)-\sigma_{ i}(t)|(\sigma_{i}(t)+\sigma_{i}(t))}$ $\displaystyle=\dfrac{2}{|\sigma_{j}(t)-\sigma_{i}(t)|}=\dfrac{2}{|\sigma_{i}(t )-\sigma_{j}(t)|}\leq\dfrac{4}{\sigma_{i}-\sigma_{j}},\quad\text{for any $i<j$.}$ $$

∎

###### Lemma A.3 (Bound on singular gaps:) .

###### Proof.

###### Lemma A.4 (Bound of coefficients c i ⁢ j ⁢ ( t ) subscript 𝑐 𝑖 𝑗 𝑡 c_{ij}(t) italic_c start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT ( italic_t ) ) .

###### Proof.

### A.4 Proof of Lemma A.5

Next, to bound the quantity $\mathbb{E}\left[\|\Psi(T)-\Psi(0)\|_{F}^{2}\right]$, use Lemma A.2 together with Ito’s Lemma (Lemma 3.1), and then apply Lemma A.4 to the resulting expression (Lemma A.5).

###### Lemma A.5 (Bound the Frobenius error as an integral of $\Psi(t)$ ) .

$$ $\displaystyle\mathbb{E}\left[\|\Psi(T)-\Psi(0)\|_{F}^{2}\right]$ $\displaystyle\leq 64\int_{0}^{T}\mathbb{E}\left[\sum_{i=1}^{d}\sum_{j\neq i} \dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}\right ]\mathrm{d}t+32T\int_{0}^{T}\mathbb{E}\left[\sum_{i=1}^{d}\left(\sum_{j\neq i} \dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})}{(\sigma_{i}-\sigma_{j})^{2}}\right)^{2 }\right]\mathrm{d}t.$ (13) $$

###### Proof.

Let $E$ be the event that $|\sigma_{i}(t)-\sigma_{j}(t)|\geq\dfrac{1}{2}(\sigma_{i}-\sigma_{j})$ for any $i<j$ and any $t\in[0,T]$.
By Lemma A.3, we have $\mathbb{P}(E)\geq 1-\delta$.

We have

$$ $\displaystyle\|\Psi(T)-\Psi(0)\|_{F}^{2}=\|\int_{o}^{T}\mathrm{d}\Psi(t)\|_{F} ^{2}$ $\displaystyle=\|\dfrac{1}{2}\int_{0}^{T}\sum_{i=1}^{d}\sum_{j\neq i}|\gamma_{i }^{2}-\gamma_{j}^{2}||c_{ij}(t)|\mathrm{d}\beta_{ji}(t)(v_{i}(t)v_{j}(t)^{\top }+v_{j}(t)v_{i}(t)^{\top})$ $\displaystyle\qquad\qquad-\int_{0}^{T}\sum_{i=1}^{d}\sum_{j\neq i}(\gamma_{i}^ {2}-\gamma_{j}^{2})c_{ij}^{2}(t)\mathrm{d}tv_{i}(t)v_{i}(t)^{\top}\|_{F}^{2}$ $\displaystyle\leq 3\left\|\dfrac{1}{2}\int_{0}^{T}\sum_{i=1}^{d}\sum_{j\neq i} |\gamma_{i}^{2}-\gamma_{j}^{2}||c_{ij}(t)|\mathrm{d}\beta_{ji}(t)(v_{i}(t)v_{j }(t)^{\top}+v_{j}(t)v_{i}(t)^{\top})\right\|_{F}^{2}$ $\displaystyle\qquad\qquad\qquad+3\left\|\int_{0}^{T}\sum_{i=1}^{d}\sum_{j\neq i }(\gamma_{i}^{2}-\gamma_{j}^{2})c_{ij}^{2}(t)v_{i}(t)v_{i}(t)^{\top}\mathrm{d} t\right\|_{F}^{2}$ $\displaystyle=3I_{2}+3I_{2}$ (14) $$

where, for convenience, we have define

$$ $I_{1}:=\left\|\dfrac{1}{2}\int_{0}^{T}\sum_{i=1}^{d}\sum_{j\neq i}|\gamma_{i}^ {2}-\gamma_{j}^{2}||c_{ij}(t)|\mathrm{d}\beta_{ji}(t)(v_{i}(t)v_{j}(t)^{\top}+ v_{j}(t)v_{i}(t)^{\top})\right\|_{F}^{2}$ $$

and

$$ $I_{2}:=\left\|\int_{0}^{T}\sum_{i=1}^{d}\sum_{j\neq i}(\gamma_{i}^{2}-\gamma_{ j}^{2})c_{ij}^{2}(t)v_{i}(t)v_{i}(t)^{\top}\mathrm{d}t\right\|_{F}^{2}.$ $$

To evaluate the first integral $I_{1}$, define $X(t)=\int_{0}^{T}\sum_{i=1}^{d}\sum_{j\neq i}|\gamma_{i}^{2}-\gamma_{j}^{2}||c
_{ij}(t)|\mathrm{d}\beta_{ji}(t)(v_{i}(t)v_{j}(t)^{\top}+v_{j}(t)v_{i}(t)^{
\top})$, we have that

$$ $\mathrm{d}X(t)=\sum_{i=1}^{d}\sum_{j\neq i}|\gamma_{i}^{2}-\gamma_{j}^{2}||c_{ ij}(t)|\mathrm{d}\beta_{ji}(t)(v_{i}(t)v_{j}(t)^{\top}+v_{j}(t)v_{i}(t)^{\top} ):=\sum_{i=1}^{d}\sum_{j\neq i}R_{ji}(t)\mathrm{d}\beta_{ji}(t)$ $$

where $R_{ji}(t):=|\gamma_{i}^{2}-\gamma_{j}^{2}|\times|c_{ij}(t)|\times(v_{i}(t)v_{j
}(t)^{\top}+v_{j}(t)v_{i}(t)^{\top})$,
so its $[l,r]$ component is

$$ $\mathrm{d}X(t)[l,r]=\sum_{i=1}^{d}\sum_{j\neq i}R_{ji}(t)[l,r]\mathrm{d}\beta_ {ji}(t).$ $$

Defining the function $f(X):=\|X\|_{F}^{2}:=\sum_{l=1}^{d}\sum_{r=1}^{d}X^{2}[l,r]$ and applying Ito’s Lemma (Lemma 3.1), we have

$$ $\displaystyle\mathrm{d}f(X)$ $\displaystyle=\sum_{l=1}^{d}\sum_{r=1}^{d}2X(t)[l,r]\mathrm{d}X(t)[l,r]+\dfrac {1}{2}\sum_{l=1}^{d}\sum_{r=1}^{d}2<\mathrm{d}X(t)[l,r],\mathrm{d}X(t)[l,r]>$ $\displaystyle=\sum_{l=1}^{d}\sum_{r=1}^{d}2X(t)[l,r]\sum_{i=1}^{d}\sum_{j\neq i }R_{ji}(t)[l,r]\mathrm{d}\beta_{ji}(t)+\sum_{l=1}^{d}\sum_{r=1}^{d}\sum_{i=1}^ {d}\sum_{j\neq i}R_{ji}^{2}(t)[l,r]\mathrm{d}t.$ $$

Thus,

$$ $\displaystyle\mathbb{E}(I_{1}\times 1_{E})$ $\displaystyle=\mathbb{E}\left[(f(X(T))-f(X(0))\times 1_{E}\right]=0+\mathbb{E} [\int_{0}^{T}\sum_{l=1}^{d}\sum_{r=1}^{d}\sum_{i=1}^{d}\sum_{j\neq i}R_{ji}^{2 }(t)[l,r]\mathrm{d}t\times 1_{E}]$ $\displaystyle=\mathbb{E}[\int_{0}^{T}\sum_{l=1}^{d}\sum_{r=1}^{d}\sum_{i=1}^{d }\sum_{j\neq i}\left(|\gamma_{i}^{2}-\gamma_{j}^{2}||c_{ij}(t)|(v_{i}(t)v_{j}( t)^{\top}+v_{j}(t)v_{i}(t)^{\top})[l,r]\right)^{2}\mathrm{d}t\times 1_{E}]$ $\displaystyle=\mathbb{E}[\int_{0}^{T}\sum_{i=1}^{d}\sum_{j\neq i}\sum_{l=1}^{d }\sum_{r=1}^{d}\left(|\gamma_{i}^{2}-\gamma_{j}^{2}||c_{ij}(t)|(v_{i}(t)v_{j}( t)^{\top}+v_{j}(t)v_{i}(t)^{\top})[l,r]\right)^{2}\mathrm{d}t\times 1_{E}]$ $\displaystyle=\mathbb{E}[\int_{0}^{T}\sum_{i=1}^{d}\sum_{j\neq i}\||\gamma_{i} ^{2}-\gamma_{j}^{2}||c_{ij}(t)|(v_{i}(t)v_{j}(t)^{\top}+v_{j}(t)v_{i}(t)^{\top }))\|_{F}^{2}\mathrm{d}t\times 1_{E}]$ $\displaystyle=2\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{d}\sum_{j\neq i}(\gamma_{i}^ {2}-\gamma_{j}^{2})^{2}c_{ij}^{2}(t)\|(v_{i}(t)v_{j}(t)^{\top}+v_{j}(t)v_{i}(t )^{\top}))\|_{F}^{2}\mathrm{d}t\times 1_{E}]$ $\displaystyle\leq 2\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{d}\sum_{j\neq i}\dfrac{1 6(\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}2\mathrm{d}t ]=64\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{d}\sum_{j\neq i}\dfrac{(\gamma_{i}^{2}- \gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}\mathrm{d}t],$ (15) $$

where the last inequality holds since, whenever the event $E$ occurs, we have $|\sigma_{i}(t)-\sigma_{j}(t)|\geq\dfrac{1}{2}(\sigma_{i}-\sigma_{j})$ for any $i<j$ and any $t\in[0,T]$.

For the second integral $I_{2}$, we have

$$ $\displaystyle I_{2}$ $\displaystyle=\left\|\int_{0}^{T}\sum_{i=1}^{d}\sum_{j\neq i}(\gamma_{i}^{2}- \gamma_{j}^{2})c_{ij}^{2}(t)v_{i}(t)v_{i}(t)^{\top}\mathrm{d}t\right\|_{F}^{2}$ $\displaystyle=\left\|\int_{0}^{T}\sum_{i=1}^{d}\sum_{j\neq i}(\gamma_{i}^{2}- \gamma_{j}^{2})c_{ij}^{2}(t)v_{i}(t)v_{i}(t)^{\top}\times 1\,\,\mathrm{d}t \right\|_{F}^{2}$ $\displaystyle\leq\int_{0}^{T}\left\|\sum_{i=1}^{d}\sum_{j\neq i}(\gamma_{i}^{2 }-\gamma_{j}^{2})c_{ij}^{2}(t)v_{i}(t)v_{i}(t)^{\top}\right\|_{F}^{2}\mathrm{d }t\times\int_{0}^{T}1^{2}\mathrm{d}t$ $\displaystyle=T\int_{0}^{T}\sum_{i=1}^{d}\left\|\sum_{j\neq i}(\gamma_{i}^{2}- \gamma_{j}^{2})c_{ij}^{2}(t)v_{i}(t)v_{i}(t)^{\top}\right\|_{F}^{2}\mathrm{d}t$ $\displaystyle=T\int_{0}^{T}\sum_{i=1}^{d}\left(\sum_{j\neq i}(\gamma_{i}^{2}- \gamma_{j}^{2})c_{ij}^{2}(t)\right)^{2}\|v_{i}(t)v_{i}(t)^{\top}\|_{F}^{2} \mathrm{d}t$ $\displaystyle=T\int_{0}^{T}\sum_{i=1}^{d}\left(\sum_{j\neq i}(\gamma_{i}^{2}- \gamma_{j}^{2})c_{ij}^{2}(t)\right)^{2}\mathrm{d}t$ (16) $$

where the first inequality holds by the Cauchy-Schwartz inequality, the third and fourth equalities hold since $v_{i}(t)v_{i}(t)^{\top}v_{j}(t)v_{j}(t)^{\top}=0$ for all $i\neq j$.

Thus, since whenever the event $E$ occurs we have $|\sigma_{i}(t)-\sigma_{j}(t)|\geq\dfrac{1}{2}(\sigma_{i}-\sigma_{j})$ for any $i<j$ and any $t\in[0,T]$, (A.4) implies that

$$ $I_{2}\times\mathbbm{1}_{E}\leq 16T\int_{0}^{T}\sum_{i=1}^{d}\left(\sum_{j\neq i }\dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})}{(\sigma_{i}-\sigma_{j})^{2}}\right)^{ 2}\mathrm{d}t.$ (17) $$

We can express $\mathbb{E}[\|\Psi(T)-\Psi(0)\|_{F}^{2}]$ as the following sum,

$$ $\mathbb{E}[\|\Psi(T)-\Psi(0)\|_{F}^{2}]=\mathbb{E}[\|\Psi(T)-\Psi(0)\|_{F}^{2} \times 1_{E}]+\mathbb{E}[\|\Psi(T)-\Psi(0)\|_{F}^{2}\times 1_{E^{c}}]$ (18) $$

Combining (A.4) and (17), it follows that

$$ $\displaystyle\mathbb{E}[\|\Psi(T)-\Psi(0)\|_{F}^{2}\times 1_{E}]$ $\displaystyle\leq\mathbb{E}[\|\Psi(T)-\Psi(0)\|_{F}^{2}]$ $\displaystyle\leq\mathbb{E}[\dfrac{1}{2}I_{1}\times 1_{E}+I_{2}\times 1_{E}]$ $\displaystyle=\dfrac{1}{2}\mathbb{E}[I_{1}\times 1_{E}]+\mathbb{E}[I_{2}\times 1 _{E}]$ $\displaystyle\leq 32\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{d}\sum_{j\neq i}\dfrac{ (\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}\mathrm{d}t]+ 16T\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{d}\left(\sum_{j\neq i}\dfrac{(\gamma_{i} ^{2}-\gamma_{j}^{2})}{(\sigma_{i}-\sigma_{j})^{2}}\right)^{2}]\mathrm{d}t.$ (19) $$

Moreover, we have

$$ $\displaystyle\mathbb{E}[\|\Psi(T)-\Psi(0)\|_{F}^{2}\times 1_{E^{c}}]$ $\displaystyle\leq\mathbb{P}(E^{c})$ $\displaystyle\leq\mathbb{E}[4\|\Psi(T)\|_{F}^{2}+4\|\Psi(0)\|_{F}^{2}\times 1_ {E^{c}}]$ $\displaystyle\leq 8d\gamma_{1}^{2}\mathbb{P}(E^{c})$ $\displaystyle\leq 8d\gamma_{1}^{2}\times\delta$ $\displaystyle\leq\frac{\gamma_{1}^{2}-\gamma_{d}^{2}}{(\sigma_{1}-\sigma_{d})^ {2}}$ $\displaystyle\leq 32\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{d}\sum_{j\neq i}\dfrac{ (\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}\mathrm{d}t]+ 16T\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{d}\left(\sum_{j\neq i}\dfrac{(\gamma_{i} ^{2}-\gamma_{j}^{2})}{(\sigma_{i}-\sigma_{j})^{2}}\right)^{2}]\mathrm{d}t,$ (20) $$

where the fifth inequality holds since $\delta\leq\frac{1}{8d\gamma_{1}^{2}}\times\frac{\gamma_{1}^{2}-\gamma_{d}^{2}}
{(\sigma_{1}-\sigma_{d})^{2}}$.

Therefore, plugging (A.4) and (A.4) into (18), we have

$$ $\displaystyle\mathbb{E}[\|\Psi(T)-\Psi(0)\|_{F}^{2}]\leq 64\int_{0}^{T}\mathbb {E}[\sum_{i=1}^{d}\sum_{j\neq i}\dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{( \sigma_{i}-\sigma_{j})^{2}}\mathrm{d}t]+32T\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{ d}\left(\sum_{j\neq i}\dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})}{(\sigma_{i}- \sigma_{j})^{2}}\right)^{2}]\mathrm{d}t.$ $$

∎

###### Lemma A.5 (Bound the Frobenius error as an integral of Ψ ⁢ ( t ) Ψ 𝑡 \Psi(t) roman_Ψ ( italic_t ) ) .

###### Proof.

### A.5 Completing the proof of Theorem 2.2

We now complete the proof of the main result.

###### Proof of Theorem 2.2 .

From Lemma A.5, we have

$$ $\displaystyle\mathbb{E}\left[\|\hat{V}\Gamma^{\top}\Gamma\hat{V}^{\top}-V \Gamma^{\top}\Gamma V^{\top}\|_{F}^{2}\right]=\mathbb{E}\left[\|\Psi(T)-\Psi(0 )\|_{F}^{2}\right]$ $\displaystyle\leq 32\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{d}\sum_{j\neq i}\dfrac{ (\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}\mathrm{d}t]+ 16T\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{d}\left(\sum_{j\neq i}\dfrac{(\gamma_{i} ^{2}-\gamma_{j}^{2})}{(\sigma_{i}-\sigma_{j})^{2}}\right)^{2}]\mathrm{d}t$ $\displaystyle\leq 64\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{d}\sum_{j=i+1}^{d} \dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}} \mathrm{d}t]+32T\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{d}\left(\sum_{j=i+1}^{d} \dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})}{(\sigma_{i}-\sigma_{j})^{2}}\right)^{2 }]\mathrm{d}t$ $\displaystyle=64\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{k}\sum_{j=i+1}^{d}\dfrac{( \gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}\mathrm{d}t]+3 2T\int_{0}^{T}\mathbb{E}[\sum_{i=1}^{k}\left(\sum_{j=i+1}^{d}\dfrac{(\gamma_{i }^{2}-\gamma_{j}^{2})}{(\sigma_{i}-\sigma_{j})^{2}}\right)^{2}]\mathrm{d}t$ $\displaystyle=64T\sum_{i=1}^{k}\sum_{j=i+1}^{d}\dfrac{(\gamma_{i}^{2}-\gamma_{ j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}+32T^{2}\sum_{i=1}^{k}\left(\sum_{j=i +1}^{d}\dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})}{(\sigma_{i}-\sigma_{j})^{2}} \right)^{2}$ $\displaystyle=O\left(\sum_{i=1}^{k}\sum_{j=i+1}^{d}\dfrac{(\gamma_{i}^{2}- \gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}+T\sum_{i=1}^{k}\left(\sum_{j =i+1}^{d}\dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})}{(\sigma_{i}-\sigma_{j})^{2}} \right)^{2}\right)T.$ (21) $$

By the Cauchy-Schwarz inequality, we have that

$$ $\displaystyle\left(\sum_{j=i+1}^{d}\dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})}{( \sigma_{i}-\sigma_{j})^{2}}\right)^{2}$ $\displaystyle=\left(\sum_{j=i+1}^{d}\dfrac{1}{|\sigma_{i}-\sigma_{j}|}\times \dfrac{|\gamma_{i}^{2}-\gamma_{j}^{2}|}{|\sigma_{i}-\sigma_{j}|}\right)^{2}$ $\displaystyle\leq\left(\sum_{j=i+1}^{d}\dfrac{1}{(\sigma_{i}-\sigma_{j})^{2}} \right)\times\left(\sum_{j=i+1}^{d}\dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})^{2}} {(\sigma_{i}-\sigma_{j})^{2}}\right)$ $\displaystyle\leq\left(\sum_{j=i+1}^{d}\dfrac{1}{(\sqrt{d})^{2}}\right)\times \left(\sum_{j=i+1}^{d}\dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}- \sigma_{j})^{2}}\right)$ $\displaystyle\leq\sum_{j=i+1}^{d}\dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{( \sigma_{i}-\sigma_{j})^{2}}.$ (22) $$

Plugging (A.5) into (A.5), we have

$$ $\mathbb{E}\left[\|\hat{V}\Gamma^{\top}\Gamma\hat{V}^{\top}-V\Gamma^{\top} \Gamma V^{\top}\|_{F}^{2}\right]\leq O\left(\sum_{i=1}^{k}\sum_{j=i+1}^{d} \dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}\right )T.$ $$

∎

###### Proof of Theorem 2.2 .

## Appendix B Proof of Corollary 2.3

###### Proof of Corollary 2.3 .

To prove Corollary 2.3, we plug in $\gamma_{1}=\cdots=\gamma_{k}=1$ and $\gamma_{k+1}=\cdots=\gamma_{d}=0$ to Theorem 2.2. There are two cases.

In the first case, where $A$ may be any $m\times d$ matrix which satisfies Assumption 2.1, plugging in $\gamma_{1}=\cdots=\gamma_{k}=1$ and $\gamma_{k+1}=\cdots=\gamma_{d}=0$ to Theorem 2.2 we get

$$ $\displaystyle\mathbb{E}\left[\|\hat{V}_{k}\hat{V}_{k}^{\top}-V_{k}V_{k}^{\top} \|_{F}^{2}\right]$ $\displaystyle=\mathbb{E}\left[\|\hat{V}\Gamma^{\top}\Gamma\hat{V}^{\top}-V \Gamma^{\top}\Gamma V^{\top}\|_{F}^{2}\right]$ $\displaystyle\leq O\left(\sum_{i=1}^{k}\sum_{j=i+1}^{d}\dfrac{(\gamma_{i}^{2}- \gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}\right)T$ $\displaystyle=O\left(\sum_{i=1}^{k}\sum_{j=k+1}^{d}\dfrac{1}{(\sigma_{i}- \sigma_{j})^{2}}\right)T$ $\displaystyle\leq O\left(\sum_{i=1}^{k}\sum_{j=k+1}^{d}\dfrac{1}{(\sigma_{k}- \sigma_{k+1})^{2}}\right)T$ $\displaystyle\leq O\left(\dfrac{kd}{(\sigma_{k}-\sigma_{k+1})^{2}}T\right)$ (23) $$

where the first inequality holds by Theorem 2.2 and the second equality holds in that $\gamma_{1}=\cdots=\gamma_{k}=1$ and $\gamma_{k+1}=\cdots=\gamma_{d}=0$.

By Jensen’s Inequality, we have that

$$ $\mathbb{E}\left[\|\hat{V}_{k}\hat{V}_{k}^{\top}-V_{k}V_{k}^{\top}\|_{F}\right] \leq\sqrt{\mathbb{E}\left[\|\hat{V}_{k}\hat{V}_{k}^{\top}-V_{k}V_{k}^{\top}\|_ {F}^{2}\right]}\leq O(\dfrac{\sqrt{kd}}{(\sigma_{k}-\sigma_{k+1})})\sqrt{T}.$ $$

In the second case, where the singular values of $A$ also satisfy $\sigma_{i}-\sigma_{i+1}\geq\Omega(\sigma_{k}-\sigma_{k+1})$ for all $i\leq k$, we have

$$ $\displaystyle\mathbb{E}\left[\|\hat{V}_{k}\hat{V}_{k}^{\top}-V_{k}V_{k}^{\top} \|_{F}^{2}\right]$ $\displaystyle=\mathbb{E}\left[\|\hat{V}\Gamma^{\top}\Gamma\hat{V}^{\top}-V \Gamma^{\top}\Gamma V^{\top}\|_{F}^{2}\right]$ $\displaystyle\leq O\left(\sum_{i=1}^{k}\sum_{j=i+1}^{d}\dfrac{(\gamma_{i}^{2}- \gamma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}\right)T$ $\displaystyle=O\left(\sum_{i=1}^{k}\sum_{j=k+1}^{d}\dfrac{1}{(\sigma_{i}- \sigma_{j})^{2}}\right)T$ $\displaystyle\leq O\left(\sum_{i=1}^{k}\sum_{j=k+1}^{d}\dfrac{1}{(i-k-1)^{2}( \sigma_{k}-\sigma_{k+1})^{2}}\right)T$ $\displaystyle\leq O\left(\sum_{i=1}^{k}\dfrac{d}{(i-k-1)^{2}(\sigma_{k}-\sigma _{k+1})^{2}}\right)T$ $\displaystyle\leq O\left(\dfrac{d}{(\sigma_{k}-\sigma_{k+1})^{2}}\sum_{i=1}^{k }\dfrac{1}{i^{2}}\right)T$ $\displaystyle\leq O\left(\dfrac{d}{(\sigma_{k}-\sigma_{k+1})^{2}}\right)T$ (24) $$

where the first inequality holds by Theorem 2.2 and the second equality holds since $\gamma_{1}=\cdots=\gamma_{k}=1$ and $\gamma_{k+1}=\cdots=\gamma_{d}=0$, the second inequality holds since $\sigma_{i}-\sigma_{i+1}\geq\Omega(\sigma_{k}-\sigma_{k+1})$ for all $i\leq k$, and the last inequality holds since $\sum_{i=1}^{k}\frac{1}{i^{2}}\leq\sum_{i=1}^{\infty}\frac{1}{i^{2}}=O(1)$.

Thanks to Jensen’s Inequality, we have that

$$ $\mathbb{E}\left[\|\hat{V}_{k}\hat{V}_{k}^{\top}-V_{k}V_{k}^{\top}\|_{F}\right] \leq\sqrt{\mathbb{E}\left[\|\hat{V}_{k}\hat{V}_{k}^{\top}-V_{k}V_{k}^{\top}\|_ {F}^{2}\right]}\leq O(\dfrac{\sqrt{d}}{(\sigma_{k}-\sigma_{k+1})})\sqrt{T}.$ $$

∎

###### Proof of Corollary 2.3 .

## Appendix C Proof of Corollary 2.4

###### Proof of Corollary 2.4 .

We first bound the quantity $\mathbb{E}\left[\|\hat{V}{\Sigma}_{k}^{\top}\Sigma_{k}\hat{V}^{\top}-V\Sigma_{
k}^{\top}\Sigma_{k}V^{\top}\|_{F}\right]$.

Set $\gamma_{i}=\sigma_{i}$ for $i\leq k$ and $\gamma_{i}=0$ for $i>k$.
Then by Theorem 2.2 we have

$$ $\displaystyle\mathbb{E}\left[\|\hat{V}\Sigma_{k}^{\top}\Sigma_{k}\hat{V}^{\top }-V\Sigma_{k}^{\top}\Sigma_{k}V^{\top}\|_{F}^{2}\right]\leq O\left(\sum_{i=1}^ {k}\sum_{j=i+1}^{d}\dfrac{(\gamma_{i}^{2}-\gamma_{j}^{2})^{2}}{(\sigma_{i}- \sigma_{j})^{2}}\right)T$ $\displaystyle=O\left(\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}\dfrac{(\sigma_{i}^{2}- \sigma_{j}^{2})^{2}}{(\sigma_{i}-\sigma_{j})^{2}}+\sum_{i=1}^{k}\sum_{j=k+1}^{ d}\left(\dfrac{\sigma_{i}^{2}-0^{2}}{\sigma_{i}-\sigma_{j}}\right)^{2}\right)T$ $\displaystyle=O\left(\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}(\sigma_{i}+\sigma_{j})^{ 2}+\sum_{i=1}^{k}\sum_{j=k+1}^{d}\left(\dfrac{\sigma_{i}^{2}-\sigma_{k}^{2}}{ \sigma_{i}-\sigma_{j}}+\dfrac{\sigma_{k}^{2}}{\sigma_{i}-\sigma_{j}}\right)^{2 }\right)T$ $\displaystyle\leq O\left(\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}(\sigma_{i}+\sigma_{j })^{2}+\sum_{i=1}^{k}\sum_{j=k+1}^{d}\left(\sigma_{i}+\dfrac{\sigma_{k}^{2}}{ \sigma_{i}-\sigma_{j}}\right)^{2}\right)T$ $\displaystyle=O\left(\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}(\sigma_{i}+\sigma_{j})^{ 2}+\sum_{i=1}^{k}\sum_{j=k+1}^{d}\left(\sigma_{i}+\sigma_{k}\dfrac{\sigma_{k}} {\sigma_{i}-\sigma_{j}}\right)^{2}\right)T$ $\displaystyle\leq O\left(\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}(\sigma_{i}+\sigma_{j })^{2}+\sum_{i=1}^{k}\sum_{j=k+1}^{d}\left(\sigma_{i}+\sigma_{k}\dfrac{\sigma_ {k}}{\sigma_{k}-\sigma_{j}}\right)^{2}\right)T$ $\displaystyle\leq O\left(\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}(\sigma_{i}+\sigma_{j })^{2}+\sum_{i=1}^{k}\sum_{j=k+1}^{d}\sigma_{i}^{2}+\sum_{i=1}^{k}\sum_{j=k+1} ^{d}\left(\sigma_{k}\dfrac{\sigma_{k}}{\sigma_{k}-\sigma_{j}}\right)^{2}\right)T$ $\displaystyle\leq O\left(d\|\Sigma_{k}\|_{F}^{2}+\sum_{i=1}^{k}\sum_{j=k+1}^{d }\left(\sigma_{k}\dfrac{\sigma_{k}}{\sigma_{k}-\sigma_{j}}\right)^{2}\right)T$ $\displaystyle\leq O\left(d\|\Sigma_{k}\|_{F}^{2}+k(d-k)\left(\sigma_{k}\dfrac{ \sigma_{k}}{\sigma_{k}-\sigma_{k+1}}\right)^{2}\right)T.$ (25) $$

We next bound the quantity $\mathbb{E}\left[\|\hat{V}\hat{\Sigma}_{k}^{\top}\hat{\Sigma}_{k}\hat{V}^{\top}
-\hat{V}\Sigma_{k}^{\top}\Sigma_{k}\hat{V}^{\top}\|_{F}\right]$.

Let $E_{1}$ be the event when $\|G\|>\sqrt{\max(m,d)}\log(1/\delta)$.
By Lemma 3.3, we have $\mathbb{P}(E_{1})\geq 1-\delta$.

Since $\|\Sigma_{k}\|_{F}\leq\sqrt{k}\sigma_{1}$ and $\|\hat{\Sigma}_{k}\|_{F}<\sqrt{k}\sigma_{1}(t)$, we can use the bound

$$ $\|\Sigma_{k}^{\top}\Sigma_{k}-\hat{\Sigma}_{k}^{\top}\hat{\Sigma}_{k}\|_{F}<\| \Sigma_{k}^{\top}\Sigma_{k}\|_{F}+\|\hat{\Sigma}_{k}^{\top}\hat{\Sigma}_{k}\|_ {F}<k\sigma_{1}+k\sigma_{1}^{2}(t)<4k\sigma_{1}^{2}$ $$

and hence

$$ $\mathbb{E}[\|\Sigma_{k}^{\top}\Sigma_{k}-\hat{\Sigma}_{k}^{\top}\hat{\Sigma}_{ k}\|_{F}*1_{E_{1}}]<2\sqrt{k}\sigma_{1}*P(E_{1})<4k\sigma_{1}^{2}*\delta.$ $$

Recall that (from Assumption 2.1) $\delta<\frac{1}{k\sigma_{1}^{2}}$. Hence,

$$ $\mathbb{E}[\|\Sigma_{k}^{\top}\Sigma_{k}-\hat{\Sigma}_{k}^{\top}\hat{\Sigma}_{ k}\|_{F}*1_{E_{1}}]<4$ $$

Now consider the event $E_{1}^{c}$, where $\|G\|<\sqrt{\max(m,d)}\log(1/\delta)$.
From above, we have $\mathbb{P}(E_{1}^{c})=1-\mathbb{P}(E_{1})\leq\delta$.
For $E_{1}^{c}$ we get,

$$ $\displaystyle\mathbb{E}[\|\Sigma_{k}^{\top}\Sigma_{k}-\hat{\Sigma}_{k}^{\top} \hat{\Sigma}_{k}\|_{F}*1_{E_{1}^{c}}]$ $\displaystyle<\mathbb{E}[\|(\Sigma_{k}-\hat{\Sigma}_{k})(\Sigma_{k}+\hat{ \Sigma}_{k})\|_{F}*1_{E_{1}^{c}}]$ $\displaystyle<\mathbb{E}[\sqrt{T}\|G_{k}\|*(\|\Sigma_{k}\|_{F}+\|\hat{\Sigma}_ {k}\|_{F})*1_{E_{1}^{c}}]$ $\displaystyle<\mathbb{E}[2\sqrt{kT}\sigma_{1}\|G_{k}\|*1_{E_{1}^{c}}]$ $\displaystyle<2\sqrt{kd}\sigma_{1}\log(1/\delta)\sqrt{T}.$ $$

Finally, put the two cases together:

$$ $\displaystyle\mathbb{E}\left[\|\hat{V}\hat{\Sigma}_{k}^{\top}\hat{\Sigma}_{k} \hat{V}^{\top}-\hat{V}\Sigma_{k}^{\top}\Sigma_{k}\hat{V}^{\top}\|_{F}\right]$ $\displaystyle=\mathbb{E}[\|\Sigma_{k}-\hat{\Sigma}_{k}\|_{F}]$ $\displaystyle=\mathbb{E}[\|\Sigma_{k}-\hat{\Sigma}_{k}\|_{F}*1_{E_{1}}]+ \mathbb{E}[\|\Sigma_{k}-\hat{\Sigma}_{k}\|_{F}*1_{E_{1}^{c}}]$ $\displaystyle<4+2\sqrt{kd}\sigma_{1}\log(1/\delta)\sqrt{T}$ $\displaystyle=O(\sqrt{kd}\sigma_{1}\log(1/\delta))\sqrt{T}.$ (26) $$

Combining (C) and (C), we have

$$ $\displaystyle\mathbb{E}$ $\displaystyle\left[\|\hat{V}\hat{\Sigma}_{k}^{\top}\hat{\Sigma}_{k}\hat{V}^{ \top}-V\Sigma_{k}^{\top}\Sigma_{k}V^{\top}\|_{F}\right]$ $\displaystyle\leq\mathbb{E}\left[\|\hat{V}\hat{\Sigma}_{k}^{\top}\hat{\Sigma}_ {k}\hat{V}^{\top}-\hat{V}\Sigma_{k}^{\top}\Sigma_{k}\hat{V}^{\top}\|_{F}\right ]+\mathbb{E}\left[\|\hat{V}\Sigma_{k}^{\top}\Sigma_{k}\hat{V}^{\top}-V\Sigma_{ k}^{\top}\Sigma_{k}V^{\top}\|_{F}\right]$ $\displaystyle\leq O\left(\sqrt{d}\|\Sigma_{k}\|_{F}+\sqrt{k(d-k)}\left(\sigma_ {k}\dfrac{\sigma_{k}}{\sigma_{k}-\sigma_{k+1}}\right)\right)\sqrt{T}+O(\sqrt{ kd}\sigma_{1}\log(1/\delta))\sqrt{T}$ $\displaystyle\leq O\left(\sqrt{d}\|\Sigma_{k}\|_{F}+\sqrt{k(d-k)}\left(\sigma_ {k}\dfrac{\sigma_{k}}{\sigma_{k}-\sigma_{k+1}}\right)\right)\sqrt{T}.$ (27) $$

∎

###### Proof of Corollary 2.4 .

## Appendix D Additional comparisons for low-rank covariance approximation

In this section, we present how one can derive high-probability bounds on the quantity $\|\hat{V}\hat{\Sigma}_{k}^{2}\hat{V}^{\top}-V\Sigma_{k}^{2}V^{\top}\|_{F}$ from the subspace perturbation bounds of [, ] or [].

Towards this end, we note that

$$ $\|\hat{V}\hat{\Sigma}_{k}^{2}\hat{V}^{\top}-V\Sigma_{k}^{2}V^{\top}\|_{F}\leq \|\hat{V}\hat{\Sigma}_{k}^{2}\hat{V}^{\top}-\hat{V}\Sigma_{k}^{2}\hat{V}^{\top }\|_{F}+\|\hat{V}\Sigma_{k}^{2}\hat{V}^{\top}-V\Sigma_{k}^{2}V^{\top}\|_{F}.$ $$

The first term can be bounded as

$$ $\|\hat{V}\hat{\Sigma}_{k}^{2}\hat{V}^{\top}-\hat{V}\Sigma_{k}^{2}\hat{V}^{\top }\|_{F}=\|\hat{\Sigma}_{k}^{2}-\Sigma_{k}^{2}\|_{F}=\sum_{i=1}^{k}\hat{\sigma} _{i}^{2}-\sigma_{i}^{2},$ $$

which can be bounded using Weyl’s inequality (Lemma 3.2) together with the Gaussian concentration inequality in Lemma 3.3.

For the second term, we have

$$ $\displaystyle\|\hat{V}\Sigma_{k}^{2}\hat{V}^{\top}-V\Sigma_{k}^{2}V^{\top}\|_{F}$ $\displaystyle=\|\hat{V}\Sigma_{k}^{2}\hat{V}^{\top}-V\Sigma_{k}^{2}V^{\top}\|_ {F}$ $\displaystyle=\|\sum_{i=1}^{k-1}(\sigma_{i}^{2}-\sigma_{i+1}^{2})(\hat{V}_{i} \hat{V}_{i}^{\top}-V_{i}V_{i}^{\top})+\sigma_{k}^{2}(\hat{V}_{k}\hat{V}_{k}^{ \top}-V_{k}V_{k}^{\top})\|_{F}$ $\displaystyle\leq\sum_{i=1}^{k-1}(\sigma_{i}^{2}-\sigma_{i+1}^{2})\|\hat{V}_{i }\hat{V}_{i}^{\top}-V_{i}V_{i}^{\top}\|_{F}+\sigma_{k}^{2}\|\hat{V}_{k}\hat{V} _{k}^{\top}-V_{k}V_{k}^{\top}\|_{F}$ $\displaystyle\leq\sum_{i=1}^{k-1}(\sigma_{i}+\sigma_{i+1})(\sigma_{i}-\sigma_{ i+1})\|\hat{V}_{i}\hat{V}_{i}^{\top}-V_{i}V_{i}^{\top}\|_{F}+\sigma_{k}^{2}\| \hat{V}_{k}\hat{V}_{k}^{\top}-V_{k}V_{k}^{\top}\|_{F}$ $\displaystyle\leq\sum_{i=1}^{k-1}(\sigma_{i}-\sigma_{i+1})\frac{\sqrt{i}\sqrt{ d}}{\sigma_{i}-\sigma_{i+1}}+\sigma_{k}\frac{\sqrt{k}\sqrt{d}}{\sigma_{k}- \sigma_{k+1}}$ $\displaystyle=O\left(k^{1.5}\sqrt{d}+\frac{\sigma_{k}}{\sigma_{k}-\sigma_{k+1} }\sqrt{k}\sqrt{d}\right).$ (28) $$

Plugging into (D) the bound of $\|V_{i}V_{i}^{\top}-\hat{V}_{i}\hat{V}_{i}^{\top}\|_{F}\leq\frac{\sqrt{i}\sqrt
{m}}{\sigma_{i}-\sigma_{i+1}}\sqrt{T}$ w.h.p. implied by [, ], one has

$$ $\displaystyle\|\hat{V}\Sigma_{k}^{2}\hat{V}^{\top}-V\Sigma_{k}^{2}V^{\top}\|_{F}$ $\displaystyle\leq\sum_{i=1}^{k-1}(\sigma_{i}+\sigma_{i+1})(\sigma_{i}-\sigma_{ i+1})\frac{\sqrt{i}\sqrt{m}}{\sigma_{i}-\sigma_{i+1}}\sqrt{T}+\sigma_{k}^{2} \frac{\sqrt{k}\sqrt{m}}{\sigma_{k}-\sigma_{k+1}}\sqrt{T}$ $\displaystyle\leq\sqrt{m}\sqrt{T}\sum_{i=1}^{k-1}(\sigma_{i}+\sigma_{i+1}) \sqrt{i}+\sigma_{k}^{2}\frac{\sqrt{k}\sqrt{m}}{\sigma_{k}-\sigma_{k+1}}\sqrt{T}$ $\displaystyle\leq 2k^{1.5}\sqrt{m}\sqrt{T}\sigma_{1}+\sigma_{k}^{2}\frac{\sqrt {k}\sqrt{m}}{\sigma_{k}-\sigma_{k+1}}\sqrt{T}.$ $$

One can also instead plug in the bound from Theorem 18 of [] (restated here as (2) in Section 1.1) into (D).
When, e.g., $\sigma_{k}-\sigma_{k+1}\geq\Omega(\max(\sigma_{k},\sqrt{m}))$, (2) reduces to $\|\hat{V}\Sigma_{i}^{2}\hat{V}^{\top}-V\Sigma_{i}^{2}V^{\top}\|_{F}\leq O\left
(i\frac{\sqrt{m}}{\sigma_{i}}\sqrt{T}\right)$ for $i\leq k$ into (D).
Thus, plugging in this bound into (D), one has

$$ $\displaystyle\|\hat{V}\Sigma_{k}^{2}\hat{V}^{\top}-V\Sigma_{k}^{2}V^{\top}\|_{F}$ $\displaystyle\leq\sum_{i=1}^{k-1}(\sigma_{i}+\sigma_{i+1})(\sigma_{i}-\sigma_{ i+1})i\frac{\sqrt{m}}{\sigma_{i}}\sqrt{T}+\sigma_{k}^{2}k\frac{\sqrt{m}}{ \sigma_{k}}\sqrt{T}$ $\displaystyle\leq O\left(\sum_{i=1}^{k-1}(\sigma_{i}-\sigma_{i+1})i\sqrt{m} \sqrt{T}+\sigma_{k}k\sqrt{m}\sqrt{T}\right)$ $\displaystyle\leq O\left((\sigma_{1}-\sigma_{k})k\sqrt{m}\sqrt{T}+\sigma_{k}k \sqrt{m}\sqrt{T}\right)$ $\displaystyle\leq O\left(\sigma_{1}k\sqrt{m}\sqrt{T}\right).$ $$

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: 1- Could you please motivate the theoretical result with some examples, even simply using toy datasets on differential privacy?

2- Could you run a set of experiments on some datasets or even synthetic matrices that show the upper-bound and compares it to the real error?

2- Could you further motivate why tall matrices are of interest in this particular setting?

----
Technical Comments:

1- In Line 144, the authors referred to Appendix J of. Manghoubi et al. to justify the assumption of exponential decay. I have checked and their manuscript has no Appendix J. Could you clearly mention their result in the manuscript and correctly refer to their work?

2- Line 191 has no period in the end.

3- In Line 204, should it be $\gamma_i=0$ for $i>k$?

4- In scientific writing, when we use a certain theorem, equation, etc. we refer to them as first name and last name and therefore capitalize "Theorem" and "Equation". Could you further edit this on the manuscript in Line 292, 343, 355, etc.

5- The factor 64 and 32 in Eq. (14) is missing in Eq. (12).

6- In Line 393, the authors write "Noting that the second term on the right-hand side of (12) is at least as small as the first term". Could you explain why this is the case?

7- In Line 595 please explain why $\mathrm{d} v_i\mathrm{d} v_i^T$ is neglected.

8- Line 649 is not clear to me and the identities mentioned in 658-661 is not helping either. Please rewrite this section of the proof and explain why these identites and inequalities hold.

9- The proof of Lemma A.3, although seems very rudimentary and practical for the rest of the proofs, it is not clearly written. If we assume $|\sigma_i(t)-\sigma_i|\leq \sigma_i + \|G\|_2$, then the triangle inequality concludes $|\sigma_i(t)-\sigma_j(t)|=|\sigma_i(t)-\sigma_i +\sigma_j-\sigma_j(t) +\sigma_i - \sigma_j|\geq |\sigma_i - \sigma_j| - |\sigma_i(t)-\sigma_i +\sigma_j-\sigma_j(t) +\sigma_i | \geq |\sigma_i - \sigma_j| - \sigma_i-\sigma_j-4\sqrt{m}\log 1/\delta$, which is not what the authors claim. From what I understand the singular values of a perturbed matrix has the error bounded by the norm of that matrix. Therefore, $|\sigma_i(t)-\sigma_i|\leq \|G\|_2$ instead of $|\sigma_i(t)-\sigma_i|\leq \sigma_i + \|G\|_2$? Also, how does $T$ not appear in the inequality?

10- In Line 698, factor 2 is not needed since $\sigma_i(t)\geq 0$ and $\sqrt{a^2+b^2}\leq a+b$?

11- In 721 and 725, why there is factor 3? Frobenius is a norm and therefore has triangle inequality.

12- In Line 752, please either stick with the notation AA^T or instead use $\langle\rangle$ instead of $<>$.

13- From where does factor 2 in 772 appears?

14- In 775, should we have $4\mathrm{d}t$?
soundness: 3
strengths: The paper is concise and with a well-defined objective of finding the upper-bound on the error of singular vectors of perturbed matrices. The strength of the paper is therefore on the theoretical results.
summary: The paper provides a new upper-bound for the right singular vectors of a perturbed matrix by Gaussian noise. The authors show that under a set of extra assumptions compared to the literature, we are able to further reduce the bound for tall matrices. The authors used the same technique as Manghoubi et al. 2022 for using Dyson Brownian motions to analyze the singular values and vectors of the perturbed matrix.
weaknesses: Although I enjoyed reading the manuscript, I should mentioned as an ICLR submission, it is strangely formed. It is a very short introduction on the problem and the objective of the paper is not well-motivated. Furthermore, although abstractly mentioned that the results can be used in differentially private subspace reconstruction, there is neither further analysis on that (which is fairly easy to do) nor any experiments, including experiments that bridge the work to the machine learning / privacy area.

Furthermore, reading the paper and the abstract, it appears that the manuscript is written in a rush and with a variety of notational issues, brevity of explanations, etc. I mention such issues in Questions section. 

Finally, although the manuscript uses a similar approach as Manghoubi et al. 2022, it appears that they achieve a tighter bounds. This would ask for further missing explanation on what is the novelty of this paper compared to the literature and how is that making this new bound possible. In the next step, the authors are expected to show that how this reduction of the bound is not an incremental result and how it improves the methods that need such upper-bounds (e.g., DP-subspace-recovery) in real applications.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: I'm confused about the claim in the paper that Theorem 7 of O'Rourke et al. 2023 achieves a bound of $O(\sqrt{mk}/\sigma_k)$.  It seems that in Theorem 7 they assume that $ \sigma_i  - \sigma_{i+1}  \geq r^2 $ for $ i \in [k]$ (where $r$ is the rank of A). I maybe misunderstanding something but it seems that eq 8 of Theorem 7 then gives us an upper bound of $\frac{\sqrt{k}}{r}+ \frac{|| E ||_2}{\sigma_k} \leq \frac{\sqrt{k}}{r} +\frac{\sqrt{m}}{\sigma_k}$ ? Can the authors please clarify this?

Can the authors also discuss the assumptions used in O'Rourke et al. 2023 or other previous works to derive the bounds and how it compares to their own on the singular values gaps i.e.  $ \sigma_i  - \sigma_{i+1} \geq \Omega( \sigma_k -\sigma_{k+1} )$? This would be helpful in doing a more fair comparison of the bounds.

Though this is a very interesting and can definitely be published at ICLR, I would request other reviewers and the area chair to the issues I have raised above. I'm giving a marginal accept. Assuming the points I have raised above are resolved, I will be happy to give a stronger accept.
soundness: 3
strengths: Though someone with a more thorough grasp of stochastic calculus would be much better suited to comment on the merit of the exact proof technique used in the paper, I found the overall technique of viewing the noise addition as Brownian motion and then using stochastic differential equations to track the eigenspace evolution quite novel. 

The bounds on the Frobenius norm distance on the right singular subspace presented have an improved dependence of $\sqrt{d}$ instead of $\sqrt{m}$ and in many applications where we have $m>>d$, I think the bounds could be useful (when there are large enough singular value gaps).

That being said, I have a few concerns about the paper which I list below.
summary: This paper presents new bounds on the Frobenius norm of the perturbation to the singular subspace spanned by the top-k right singular vectors of a matrix $A \in \mathbb{R}^{m \times d}$, when $A$ is perturbed by a matrix $G \in \mathbb{R}^{m \times d}$ with Gaussian $\mathcal{N}(0,T)$ random entries. More specifically, assuming $A$ has a top-k singular value gap of at least $\Omega(\sqrt{mT})$ (i.e. $\sigma_i-\sigma_{i+1} \geq \Omega(\sqrt{mT}) $ for all $i \in [k]$), the paper bounds the expected Frobenius norm distance between the projection matrices on the top $k$ right singular subspaces of $A$ and $A+G$ by roughly $O( \frac{ \sqrt{kdT} }{ \sigma_k - \sigma_{k+1} })$ where $\sigma_1 \geq \ldots \geq \sigma_d \geq 0$ are the singular values of $A$. When $ \sigma_i  - \sigma_{i+1} \geq \Omega( \sigma_k -\sigma_{k+1} )$ for $i \in [k]$ is also true, the bound is $O(\frac{ \sqrt{dT} }{ \sigma_k - \sigma_{k+1}  })$ which improves upon previously known high probability bounds on the actual Frobenius norm distance by $\frac{\sqrt{m}}{\sqrt{d}}$. The paper also improves previously known bounds for the rank-k covariance matrix approximation by a factor of $\frac{\sqrt{m}}{\sqrt{d}}$. 

To derive the bounds, the paper views the addition of a gaussian noise matrix to $A$ as a Brownian motion on the entries of a matrix $\Phi(t) := A+B(t)$ where $B(t)$ is a matrix whose entries undergo standard Brownian motion. This Brownian motion induces a stochastic diffusion process, known as the Dyson-Bessel process on the singular values and singular vectors of $\Phi(t)$. The evolution of the eigenvalues and eigenvectors of of this matrix is determined by a system of stochastic differential equations. Using techniques from stochastic calculus (Ito's lemma), the evolution of the Frobenius distance can be tracked as a stochastic integral of a sum-of-squares of perturbations to the right singular vectors of $\Phi(t)$. Overall, higher order matrix derivatives which appear in the Taylor series expansion of deterministic perturbations vanish in the stochastic case due to the independence of random noise in the Brownian motion and this gives the stronger bounds.
weaknesses: Though this is not a weakness per se, I'm not sure how suited this paper is for ICLR which is primarily an applied ML venue. I feel at least a core theoretical venue like COLT or maybe a mathematics journal is better suited for this kind of work. That being said, if the authors are able to show a concrete ML related application of the utility of their bounds, that would make the paper a stronger contender for publication at ICLR and also improve the overall quality of the paper. For example, as mentioned in the paper, in differential privacy, gaussian noise is added to the data matrix to preserve privacy (Dwork et al 2014). Can the authors try to use their bounds to see if they can get any improved bounds in this case?

Also, the bounds in previous papers like O'Rourke et al. 2023 are high probability bounds while here, the bounds are just on the expected Forbenius norm. How difficult would it be to use the same techniques to get high probability bounds? 

I also have a couple of questions about comparison to previous work (specially to O'Rourke et al. 2023) which I list below in the questions section.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: In my opinion, the proposed bound may be used to improve the tradeoffs between privacy and accuracy of some differentially private algorithms in numerical linear algebra. Can authors show some with provable guarantees? Or can authors give any concrete applications of the improved bound in the machine learning literature?
soundness: 3
strengths: 1. The main proof technique requires a clever combination of many building blocks: They firstly regard the added Gaussian noise G as a Brownian motion. This Brownian motion induces a stochastic diffusion process on the singular values and singular vectors. The evolution of these eigenvalues and eigenvectors is determined by a system of stochastic differential equations. Then, one can apply Ito’s lemma from stochastic calculus to track and analyze the Frobenius norm distances between the top-k projection matrices. It requires solid work to make the entire theoretical analysis work.

1. The problem is very fundamental, and the improvement of the bound is by a factor of sqrt(n / d), when n >> d, this improvement is very significant.
summary: This paper studies the Frobenius norm distance between the projection matrix to the top rank-k row space of A and the projection matrix to the top rank-k row space of A + G where G is a random Gaussian matrix and A is a tall n x d matrix, i.e., n >> d. The previous result by O’Rourke et al. (2023) shows that if one considers both distances between the projection matrices corresponding to column space and row space, then they can get a tight result. In this work, authors gave an improved bound when considering the projection matrices to row spaces only.
weaknesses: 1. As mentioned in the conclusion, the result needs to assume a reasonable top-k singular value gap of A.

2. A bigger concern would be the interest of the audience of the venue. Although there are some potential applications of the derived bound for handling data corruption / noise, or differential privacy (Gaussian mechanism), there is no concrete application discussed in the paper.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: -
soundness: 3
strengths: I find the topic very interesting. Proving these results is non-trivial and insightful.
summary: The paper studies a very interesting problem, namely that of bounding the Frobenius norm of the subspaces spanned by the top-k singular vectors of any fixed matrix A and A+G. The paper is well structured and reads well, but has very few thematic overlaps with the ICLR. 

I am rejecting this paper for two reasons. First, the authors used the wrong template with significantly wider margins than the standard ICLR template. While this is nitpicking, choosing the right template comes with no overhead but is critical to maintain fair standards on the length of the paper among all submissions. 

The second reason is that the paper targets a problem in random matrix theory, which would fit well to a conference like ALT or COLT or a mathematical journal. In order to submit this paper to ICLR, I would expect at least one longer section highlighting the connections to machine learning and demonstrate how these bounds help us to arrive at non-trivial novel insights directly relevant for machine learning.
weaknesses: -

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 3
questions: N/A
soundness: 3
strengths: - The paper is easy to read. 
- The problem considered is important and has wide applications to many machine learning problems.
summary: This paper considers estimation of the right singular subspace of a matrix $A\in\mathbb{R}^{m\times d}$ when the matrix is perturbed by a Gaussian random matrix. The authors focused on the case $d>m$ and derived a perturbation Frobenius bound independent of $m$.
weaknesses: The main weakness of this paper is that the question posed in the Introduction has already been addressed in the existing literature. The prior works have already proposed minimax optimal subspace estimators that attain tighter bounds than the one derived in this paper. Moreover, the required signal-to-noise condition in this paper is also more stringent than those in the prior works.

In [1,2,3], the authors proposed left singular subspace estimators of a matrix $A\in\mathbb{R}^{d_1\times d_2}$, which achieve the statistically optimal estimation bounds (in both spectral norm and $({2,\infty})$ bound) that only depend on $d_1$ when the noise variance $\sigma^2$ is small. In addition, it has been shown that when $\sigma^2$ is large, it is information-theoretically impossible to obtain an estimation bound that is independent of $d_2$.

By transposing the target matrix and converting an $({2,\infty})$ bound to a Frobiuns bound (multiplying by $\sqrt{d}$), the estimation guarantee for the right singular subspace in terms of the Frobenius norm follows directly from these prior results. Further, the signal-to-noise ratio condition in this paper $\sqrt{T}/(\sigma_1-\sigma_{i+1}) = \tilde{O}(1/\sqrt{m})$ (Assumption 2.1) is much stringent than the conditions required in these existing works ($\sqrt{T}/(\sigma_1-\sigma_{i+1}) = \tilde{O}(1/\sqrt{d} \wedge 1/(md)^{1/4})$).  Moreover, the estimation guarantees in the prior work are established in high probability while this paper only establishes it in expectation.

In short, under less stringent signal-to-noise ratio conditions, prior works have already achieved statistically better bounds (which are indeed minimax optimal up to log factors) for the singular subspace than the bound obtained in this paper.

Therefore, the intellectual contribution of this paper is limited. Given the estimation error in the existing works is already minimax optimal and the required SNR condition therein is shown to be necessary to ensure consistent estimation, one approach to improve the contribution might be removing the log factors in the error bounds.


[1] "Subspace Estimation from Unbalanced and Incomplete Data Matrices: $\ell_{2,\infty}$ Statistical Guarantees," Annals of Statistics, 944-967, 2021
[2] "Inference for heteroskedastic PCA with missing data," Annals of Statistics, 729-756, 2024
[3] "Deflated HeteroPCA: Overcoming the Curse of Ill-Conditioning in Heteroskedastic PCA," Annals of Statistics, to appear

Meta-review: This paper provides new matrix perturbation bounds for the top singular vectors of a matrix A under Gaussian perturbations. The authors improve prior results in the setting when the matrix is much taller than it is wide (a common setting in data applications). Most of the reviewers (besides one outlier) felt that the work was interesting and addresses a fundamental question. There was a broad concern about fit to ICLR given the lack of applications -- the work might find a better home in a theory-focused conference. To their credit, the authors added a section during the rebuttal phase on an application to differential privacy (basically a direct corollary of their result is they can bound the accuracy of the top subspace of a data matrix perturbed using the common Gaussian mechanism. Nevertheless, on balance, this paper seems like a nice contribution to include in ICLR.

Decision: Accept (Poster)