Singular Subspace Perturbation Bounds via Rectangular Random Matrix Diffusions
Authors: Peiyao Lai
Oren Mangoubi
Venue: ICLR 2025 Poster (2025)
Keywords: Matrix Perturbation Bounds
Matrix Diffusions
Low-rank Approximation
Differential Privacy
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)

Abstract: Given a matrix $A \in \mathbb{R}^{m\times d}$ with singular values $\sigma_1\geq \cdots \geq \sigma_d$, and a random matrix $G \in \mathbb{R}^{m\times d}$ with iid $N(0,T)$ entries for some $T>0$, we derive  new bounds on the Frobenius distance between subspaces spanned by the top-$k$ (right) singular vectors of $A$ and $A+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$ where the gaps in the top-$k$ singular values are roughly $\Omega(\sigma_k-\sigma_{k+1})$ the expected Frobenius distance between the subspaces is $\tilde{O}(\frac{\sqrt{d}}{\sigma_k-\sigma_{k+1}} \times \sqrt{T})$, improving on previous bounds by a factor of $\frac{\sqrt{m}}{\sqrt{d}}$. 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$ singular vectors, which may be of independent interest.

Published as a conference paper at ICLR 2025
SINGULAR SUBSPACE PERTURBATION BOUNDS VIA RECTANGULAR RANDOM MATRIX DIFFUSIONS
Peiyao Lai
Oren Mangoubi Worcester Polytechnic Institute Worcester, MA, USA
Worcester Polytechnic Institute Worcester, MA, USA
ABSTRACT
Given matrix A E Rn with singular values 01 2 2 Od, and a random matrix G E Rmxd with iid (0, T)) entries for some T >>>000 0, we derive new bounds on the Frobenius distance between subspaces spanned by the top-k (right) singular vectors of A and A + 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 where the gaps in the top-k singular values roughly [2(
ak+1) the expected Frobenius x /T), improving on previous distance between the subspaces is Ō 0 va
02-0641
bounds by a factor of ym To obtain our bounds we view the perturbation to the v/
singular vectors as a diffusion process- the Jyson-Bessed process- and use tools from stochastic calculus to track the evolution of the subspace spanned by the top-k singular vectors, which may be of independent interest.
INTRODUCTION
Given a matrix E R.xdd with d S m and singular values 01 .... 2 Jd, one oftentimes wishes to approximate the right-singular vectors of A by lower rank matrix of some rank k < dhSihhalie ctt al. (2 Hubert & Engelen (atecn))(000)) (2004); James et al. ); Kishore Kumar & Schneider (2017); Liberty et al. (2007). For instance, one may wish 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 M2 which minimizes the Frobenius distance || A All F to the covariance matrix A T of the data A. Roughly speaking, both of these problems are instances of the following general problem: given a set of numbers 11 2... 2 na and denoting by I := diag(n.... Ya) and by A = UVV a singular value decomposition of A, find a matrix M Orz which minimizes the Frobenius distance ||M V VV22, where Or= == T U E ((d) denotes the orbit of 2 under the orthogonal group. Plugging in 7 for < k and 7/4 = for > 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 7 R o; for i < A and 7 = 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 E Ruxd and one only has access to a perturbed matrix A + F. 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 Wu & Chen (199)); Helstrom (1955); Liu & Lin (2012); DjuriC (1996); Bergmaan (1974). In differential privacy applications, Gaussian noise may be artifiiialyy 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 Dwork (2006); Dwork et al. (2006); see e.g. Dwork et al. (2014); Mangoubi & Vishnoil (2022) 2023 In Press) where symmetric-matrix Gaussian noise is added covariance matrices to guarantee privacy. The addition

---

Published as a conference paper at ICLR 2025
of Gaussian noise to ensure privacy is referred to the Gaussian mechanism, and is known to satisfy (e, differreni privacy guarantees.
1.1
RELATED WORK
Multiple prior works have shown singular subspace perturbation bounds when E E Rmxx may be any (deterministic) matrix. For instance, the Davis- Kahan-Wedin sine-Thete theorem Davis & Kahan (9770): Wedin (1972) implies a bound of roughly
||
V V. III
(1)
Ok 0k+1
where Vi, V2 are, respectively, the matrices whose columns are the top-k right-singular vectors of and Á == A + E, and |II |II is e.g. the Frobenius norm || || or the spectral norm || -1l2. These bounds are tight (for sufficiently small ||| in the general setting where E E R may be any (deterministic) matrix.
When the perturbation E is, e.g., Gaussian random matrix with iid N(0. T) entries for some T >>> 0. one can plug segh-proabiiltyy concentration bounds, which imply that || I O(ym)) w.h.p., to the deterministic bounds in equation to obtain bound of
Vlemm σk okt1
V V.V. 11
V
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 equation[] [ in different settings when E is a random matrix from some known distribution or class of distributions (see e.g. O'Rourke al. (2018); Faan al.) (2018): Abbe et al. (2022); Cai al. (202T). In particular, when their bounds, which are given in terms of the spectral norm, are applied to bounding the Frobenius norm distance, the results mnOORourke al. (2018) imply that if the entries of E satisfy concentration properties which generalize those of Gaussian distributions, and A has rank r S d, then
IV - VAV. lF so
(
Vr
m ox(ax
m
+
ok+1 ok 0k+1
ok+1)
w.h.p. In O'Rourke al. (0023) the authors obtain singular subspace perturbation bounds when E is random matrix with rid standard Gaussian entries. Their results, which are given
as bounds on the spectral norm, imply that max (IÜRÜT - URUTT12, [V - V&VV 1l
S
Mmvk
This in turn implies bounds on the Frobenius norm of ak
max (1ÜRÜT URU VI vaVlle)) so
rvk
k
1
Vmvk
[ ok+1)²
O'Rourke al. 2023) show that their spectral norm bounds are tight with respect the subspace spanned by the top-k middimensional left singular vectors of A E mmd when m 2 d. However, the bounds in equation 3 do not imply tight bounds on the perturbation V.V.T V to the subspace spanned by the top-k d-dimensional right singular vectors. particular, the bound on the peturbation Vi V V. to the subspace spanned by the top-k d-dimensional right singular vectors implied by equation grows proportional to the (square root of) the larger of the matrix dimensions vm.
This leads to the question of whether one obtain improved bounds the perturbation V V. || the subspace spanned by the top-k d-dimensional right singular vectors of x d matrix A with m > d perturbed by Gaussian noise, which do not grow with the larger dimension m.
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. Dwork et al, (2014); [Elridge et al. (2018) : Fan et al. (2018)). For instance. Dwork et al. (014)) obtain perturbation bounds for covariance
2

---

Published as a conference paper at ICLR 2025
matrices perturbed by symmetric Gaussian noise, and apply these perturbation bounds version of the Gaussian mechanism to obtain tighter utility bounds for covariance matrix approximation 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 cigenvectors.
problems under (e, 6) -differeentil privacy. Mangoubi & Vishnoi (2022 2023) improve
1.2 OUR CONTRIBUTIONS
Given any matrix A E R and a set of numbers "n 2 .... .... "d. our main result (Theorem 2.2) bound on the perturbation to the matrix V Orr where A UEV is singular value decomposition of A. We show that, if the matrix A is perturbed by matrix E vTG, where 7' > and G' is Gaussian random matrix with iid N(0, 1) entries, the right-singular vectors V (61, ... ud) of the perturbed matrix A + TG satisfy the bound
h Σ
( 773) (at- - 02
E ITTTV VT P so
Σ j=i+1
VT
where the right-hand-side is a sum-of-squares of the ratios of the eigenvalue gaps of I' and Σ.
Plugging in different values of 7, we obtain as corollaries bounds for the subspace recovery and low-rank covariance matrix approximation problems. In particular, show that V
V. Ilr s o ok 0k+1
VT
whenever the top-k singular value gaps of A are roughly
(mmax(o> - JR41, VIn T)) (Corollary 2.3 This improves (in expectation) on the bounds implied
1972 and O'Rourke al. (2018) by factor of roughly VT. and by a factor of va over the bounds implied by O'Rourke et al. (2023), the above setting where E is a Gaussian random matrix. In particular, our bound replaces those bounds' dependence on lead to large improvement in many
by both Davis & Kahan (1970); Wedin ym ym Vi
the number of rows with the number of columns d. This applications, as one oftentimes has that the number m of rows in the data matrix (corresponding to the number of datapoints) much larger than the number of columns (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 Dyson (9622) Norris et al. (1986); [ru (1989);
Mangoubi Vishnoi (2022) 2023 In Press), we view the perturbation of a matrix A E m by Gaussian noise
Brownian motion the entries of an Rdnxd matrix, (1)) == A + B()) where B(I) is a m matrix whose entries undergo iid standard Brownian motions. This Brownian motion induces stochastic diffusion process on the singular values and singular vectors of (t), referred to as the Dyson- Boon-Bessel process. The evolution of these eigenvalues and eigenvectors is determined by system of stochastic differential equations (see e.g. Dyson (1962);
Norris et al. (986); Guionnet & Huang (02TT). This allows us to use Ito's o lemma from stochastic calculus to track the evolution of the Frobenius distance
stochastic integral of a sum-of- sum-of-square of-squares of perturbations to the (right)-singular vectors of ((). In particular, the stochastic evolution of the eigenvectors allows 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 Brownian motion, due the independence of random noise additions 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.
MAIN RESULTS
For any d> 0, denote by O(d) the group of orthogonal of d x d matrices. For any diagonal matrix A Raxdd denote by O₂ : (UAUT :U (d)) the orbit of A under the orthogonal group.
Given any matrix E mmdd where < m, with singular values σ, 2 2 σa 2 and
corresponding orthonormal right-singular vectors U1, and given any numbers 71 nd
3

---

Published as a conference paper at ICLR 2025
main result (Theorem 2.2 is bound on the perturbation to the matrix V TV E Orz, where V := [01... E Rdxd and == diag(?2.....,
Our main result holds under the following assumption the gaps in the top + 1 singular values
01 2 ... 2 0++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 of & Vishnoi (2022) for examples of datasets with saanenttally-decayiinn singular values).
Assumption 2.1 (A, k To,,0,0 o, (Singular value gaps). The gaps in the top k + singular values σi 2 ... 2 0 of the matrix E Rmxx satisfy 0; 0i+1 2 88T SyTymml log (3) for every [k]. where == 8d x (a)
We now state main result.
Theorem 2.2 (Main result). Let > O. Given rectangular matrix A E R with singular values 01 2 dd 0 and corresponding orthonormal sight-singula vectors Vi...u (and denote V [t1....ul E Bdxd), Let G be matrix with i..dd. (0, 1) entries, and consider the perturbed
matrix A = A + VG E R=xd
Define 0 2 2 dd 2 0 to be the singular values of Å with corresponding orthonormal right- singular vectors ...6 (and denote = [0,,...a)]
Let 71 ... 7 2 0 and & E [d] be any numbers such that 7 for i > k, and define I == diag (7,,., Ya). Then if A satisfies Assumption 2.7 for (A, k. T, a. 7), we have
(7, - 7?32 (ai - ,,)
E -
-V
P 0O
T.
(4)
1=++1
We give an overview of the proof Theorem 2.2 in Section
The full proof is given in Appendix A
2.1 APPLICATION TO SINGULAR SUBSPACE RECOVERY.
To obtain a pertubration bound for the subspace recovery problem, we plug 7 for all i s and 7 = () for all k, into Theorem 2.2
Corollary 2.3 (Subspace recovery). Let Let O. Given a rectangular matrix E mx with singular values 01 2 ... 2 oa 2 0 and corresponding right-singular vectors U.. Let G be matrix with i...d. (0, entries, and consider the perturbed matrix À = A + VTG.
For any l [d] define the l matrices Vv [..k] and Vn [6,] where Ú1, Uk denote the right-singular vectors of Å corresponding to is top-k singular values. Then if satisfies Assumption 2. (.T,A, A, k. T, () where = (1,... 1,0, ... ,00 is the vector with the first k entries equal 1, we have
ld
E LIVAEE V.Vi |F 5o
Tk+l )T)
VT
(5)
Moreover, if we further have that o; oit1 2 2(α - Ok-1) for all i S k, then
5o (- vd E [IvV V - V.VVT |F]
(~ -
VT)
(6)
ak
okt1
The proof of Corollary 2.3 is given in Appendix B Corollary
2.3 improves, in the setting where
the perturbation is Gaussian random matrix, by a factor of Vd (in expectation) on the bound
Vkm
||V V
V. || < 0
T) w.h.p. implied by the Davis-Kahan Wedin sine- Theta
Tk Th+l theorem Davis & Kahan (1970); Wedin (1722), whenever Assumption 2.1 is satisfied. If we also have
that σ; - 0++1 2 2(xx x 1 for all < (as is the case for many worldworld datasets which may
exhibit exponential decay in their singular values), the improvement is v \/m Va
4

---

Published as a conference paper at ICLR 2025
Moreover, Corollary 2.3 also improves, in the setting where the perturbation G is Gaussian random
matrix, by a factor of v
v on the bound of [|V V vi
I| I O /mkk VT) w.h.p. implied by on
Theorem 18 of O'ouukke et al. (0188), and by factor of vm on the bound of [| V V 11 - O VT) w.h.p. implied by Theorem of O'Ruukke et al. (2023), when Assumption 2.1 is satisfied and e.g. ox - xk+1 = (((xx) (as is also the case for many real-world datasets). This can lead to large improvement many applications, as one oftentimes has that the number 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).
va
Finally, Corollary 2.3 also implies the same upper bound on the expected spectral norm, since V -V.V [|a] S BIIVVVV V. [[.] Thus it improves, e-g., by a factor of ymm
(in vdva
expectation) on the spectral norm bound [| VT - VVVV S S0( ym/E <0(>//R vT) w.h.p. implied by Theorem 7 and m > dk:
al. (2023), whenever Assumption 2.1 is satisfied, 0% ok+1 ((xx)
2.2 APPLICATION TO RANK-k COVARIANCE MATRIX APPROXIMATION.
To obtain a perturbation bound for the rank-k covariance matrix approximation problem, we plug in % og for all < k. and % = 0 for all i > k, into Theorem 2.2
Corollary 2.4 (Rank-k covariance matrix approximation). Ler T > O. Given a rectangular matrix A E IR m with singular values d1 2 ... 2 aa 2 0 and with right-singullr vectors Ud. where we define V := [u]l E Rddd Let G be a matrix with i.i.d. N(, 1) entries, and consider the perturbed matrix that outputs = A+ VTG.
For any k [d]. define Σn = diag (oi,..., Tk. O,..)) Define â 2 ... Ga singular values of Å with corresponding orthonormal right-singular vectors 61, where we define V = [al], and define Σn == diag (ō1,... ok, .,... Then if A satisfies Assumption 2.1 for (A, k T,,,)),
be the
(01,'.. 0k, 0,....... ,), we have
d Σ
2
E IIVI - VΣ En
P
s 00
d d|jE +k
Tk
T.
0k oj
j=k+1
The proof of Corollary 2.4 is given in Appendix
C In particular, Corollary 2.4 Himplies that
E | E vT
s So
VTiva 01 + σk 0
VT.
Corollary 2.4 improves, in the setting where the perturbation G Gaussian random matrix, by factor of (in expectation) on the bound of |IVE, VT - -VE E || I O VmyTo, +
of oz deam
w.h.p. implied by the Davis-Kahan--a Wedain sine-Theta theorem Davis Kahan (1970): Wedin 1972) whenever Assumption 2.1 is satisfied (see Appendix D for details). If we also
have that 0₁ x (( the improvement is /m K.
vd
Moreover, Corollary 2.4 also improves, when the perturbation is Gaussian, by a factor of Vm (in expectation) on the bound implied by Theorem 18 of O' OO'Rourke et al. (2018) whenever e.g. Tk 0h+1 = ((xx), as in this setting their bound implies ||VE, E VEJ En || S o (okk/mmTT) w.h.p. (see Appendix D for details).
Va Vh
Remark 2.5 (Tightness in full-rank special case). In the special case where = d, we have II(A+ (TA+ (A+VTG) - AT A = G @([EEa|eeVVVT whh.p Thus Corollary 2.4 is tight in this special case. The last equality above holds whh.p. because A GII2- tr(G" AATG) G) tr(G EgE G) tr(EaE] GG | 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.
A+TG Gl]r
( =
5

---

Published as a conference paper at ICLR 2025
2.3 APPLICATIONS TO DIFFERENTIAL PRIVACY
In many applications, datasets contain sensitive information. For instance, this may be the case for medical applications where datasets may contain sensitive information about individual patients. In such applications, one can add random noise to the dataset (or, more generally, add random noise to machine learning algorithm trained on this dataset) to "hide" private information about individuals.
In high- -ish-iimensional statisties, one oftentimes cares only about the covariance between subset S1 of m "input" features and another (possibly. but not necessarily, disjoint) subset S2 of d features (which may correspond "outpuu" features or labels to be predicted). Differential privacy can be used here to calculate private covariance estimates, especially in settings where the data is too high-dimensional to compute an the full symmetric covariance matrix, as privatizing such high-dimensional matrix may require adding an unnecessarily large amount of noise. For instance, in Biomedical and Genomics datasets which involve gene expression data, covariances between different features may be stored as a rectangular matrix A where rows represent genes and columns represent disease conditions (see e.g. Patnaik et al. (2012)) Applying DP PCA to these matrices enables without exposing sensitive information about individuals.
analysis.
For any e, > 0, randomized mechanism M said to be (e. -iffferrretttllllyy private Dwork (2006) Dwork et al. (2006) if for any two neighboring datasets D, D3 E 'D one has (P) E 5) S e F(M(D') E S) +ô. Datasets D, D' are said to be neighbors if they differ by at most one datapoint. The sensitivity of a function f : 2 > mx is defined as the supremum of II
f(D') over
all neighboring D, D' E D. Following, e.g.. Dwork et al. (2014). we assume the input matrix A is a function of the dataset, A f(D), where f has sensitivity at most (see also e.g. Kapralov & Talwar
(2013) [miin et al. 2019); Mangoubi & Vishnoi| 2022); Mangoubi et al. (2022)) )) To ensure that the sensitivity is < 1, a standard preprocessing step is "clip" the datapoints such that each datapoint x E D has length at most ||a||| < 1. This ensures that, whenever A = J(D) arises from a 1- I-Liischitz function f. the sensitity of this function f will be 1. For instance, if A is a rectangular covariance xd matrix arising from data matrices X E RV xm and Y E IR Nx (whose collumns correpond to subsets of size m and d of the features in dataset, and rows are datapoints), where A = X Y, then A is a function f(XXY) = Y which is 1- 1-Lipschitz in each datapoint.
One of the most popular methods of privatizing a dataset the Gaussian mechanism, a randomized mechanism which adds iid Gaussian noise to each entry of the data matrix Dwork et al. (2006). Prior works (e.g.. Dwork et al. 4y014;; Mangoubi Vishnoi (0022) 2023 In Press)) have provided utility bounds for a version of the Gaussian mechanism in the special case when A is symmetric matrix, and when the noise G added to this matrix is a symmetric Gaussian random matrix. However, in many applications including those mentioned above, it is oftentimes desirable to output privatized version of a rectangular matrix A E mxd
The Gaussian mechanism adds Gaussian noise A VTG to the output of f(D) = A, where each entry of the random matrix G e Rm is i.idd. (0, 1), for some T > 0. If has sensitivity at most
1 (as is the case in the above examples), and one sets T 2oog( 122 can be shown to satisfy (s, dddifferretii privacy Dwork et al. (2006). Our bounds in Corollary 2.3 therefore immediately imply a bound on the Frobenius-norm utility of the subspace spanned by the top-k rinhl-r vectors of the output A + vTG of the Gaussian mechanism, when the Gaussian mechanism is applied to rectangular matrix A E IRmxd In particular, Corollary 2.3 implies utility
then the Gaussian mechanism
bound of E [ VT V [e S
Vd
vT)=
VT
-
Vd
2
for the
Tk - -k+1
8
Fa of Gaussian mechanism with (e. diiffeerrlttaal privacy, whenever the singular values oi
A satisfy Assumption 2.1 e.g. a; - 0141 2 2( - ak+1) for all i S k.
This improves by a factor of V ViVV//a va (in expectation) on the bound VIVE Vkm
V.V FF S
/2log( implied by the Thk 1hal
O
sine-Thete theorem Davis & Ka-
han
19700): Wedin 19722) , and by a factor of VmVF/Vdd on the bound of [ VVV Il
O( Ck
mm 22 log 1.3 1/c) implied by Theorem 7 of O' RoRrre al. (0023)

---

Published as a conference paper at ICLR 2025
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 Φ in Section 3.1 Next, present the stochastic differential equations (SDEs) which govern the evolution of the singular values of right-singular vectors of (() in Section 3.2
3.1 DYSON-BESSE PROCESS
We consider the matrix-valued stochastic motion process, ((t), where, for all 2 0, the entries of (t) evolve as independent standard Brownian motions with initial condition 20)) A. In particular, time T we have (T) N N0,, 1) entries.
vTG where G is an m Gaussian random matrix with iid
Recall that 01 ... 2 ad denote the singular values of A. At every time 0, we denote (with slight abuse of notation) the singular values of ((t) by 0 (t) 2 (2 2 ... 2 da(t). In particular 0, = (0) for all E [d]. and the singular values a (t), ..., ,.((t are distinet every time with probability 1 (see e.g. Guionnet & Huang (2021) ). The matrix-valued Brownian motion Φ(()
induces stochastic diffusion processes on the singular values (1) and singular vectors (t). referred to the Dyson- Dyson-Bessel process. The dynamics of the singular values (t of the Dyson-Besse process are given by the following system of stochastic differential equations (see e.g. Norris et al. (1966) or Theorem in Bru 1989))
(t) d.B((t) +
Σ (EE(d))))
(o.(t) (t)(t)²
dt, -1)0))((00())) (0)(1)) (0,
m -
vIsisd (8)
(1,
where Bu, 1 1si i d is family of independent one-dimensional Brownian motions.
3.2 RIGHT SINGULAR VECTOR SDE
The dynamics of right-singular vectors (t) of the Dyson- Bessel process are governed by the following stochastic differential equations (see e.g. Norris et al. (1986) or Theorem 2 in Bru (1989))
(o)(1)) (o,(1))2 (c,()))
v/(() (o)(1)) (o,(1)) ( (t,
du;(t) = Σ
15(t) fElld
((a,(t))²- (o.(t))3) dB)((t)
v1(() 2 (1)di,
Σ (0));())))
visisd,
((E(d)
where 1
d, is family of independent standard dineeimnnao Brownian motions, and the (t) form a skew-symmetric matrix, i.e. (ty(t) (t)(() for all 2 0. For convenience,
in the above equation, we denote (t) = ((1()()))-(<((()2)))) (ta()) for all í,j E [d].
(o))
3.3 ITO'S LEMMA
We will also use the following result from stochastic Calculus, Ito's Lemma, which generalization of the chain rule in deterministic calculus.
Lemma 3.1 (Ito's Lemma Itō (951)). Let f Rd - IR be second-order differentiable function, and let X(t) be a diffusion process on Idd, Then
df(X,) (VS(X.)) TXX, (dx,) (V2 VI 2 0.
3.4 OTHER PRELIMINARIES
We will use the following deterministic eigenvalue perturbation bound
Lemma 3.2 (Weyl's Inequality Weyl (1912). Let A, E E Ikmxd is matrix. Denote by 0 ... ag the singular values of and by 0i 2 ... 2 δa the singular values of + E. Then |a; -a $ F|
Vi [d].
7

---

Published as a conference paper at ICLR 2025
The following concentration bound, Theorem 4.4.5 of Vershynin (0018) applied to Gaussian random matrices, will allow us to bound the spectral norm of the Gaussian perturbation G (which turn will allow us to apply equation 3.2 to bound the perturbations to eigenvalues).
Lemma 3.3 (Spectral-norm concentration bound for Gaussian matrices Vershynin (2018)) If G E Rmxd is Gaussian random matrix with iid (0, 1) entries, then [( > vm vd+ <
2e-** for all > O.
4 OVERVIEW OF PROOF OF THEOREM 2.2
We present an overview the proof of Theorem 2.2 along with the main technical lemmas used in the proof. In Steps and 2 express the perturbed matrix, and its quantities of interest derived from its right-singular vectors, as matrix-valued diffusions. Steps 3, 4, and present the main technical lemmas, and complete the proof in Step 6. The full proof is given in Appendix A..
4.1 VIEWING THE PERTURBED MATRIX AS A -VLUUD BROWNIAN MOTION.
To obtain our bounds, we begin by definigg the matrix- valued Brownian motion, $ Bt) for all 2 O, where the entries of (t) evolve as independent standard Brownian motions initialized at O. In particular, time O we have ((0 = A, and at time t T we have (TT A + /TG where G is an m x d Gaussian random matrix with iid (0, 1) entries.
4.2 PROJECTING THE MATRIX BROWNIAN MOTION ONTO THE ORTHIOGONAL ORBIT Or2.
Denote by A UEVT and Ā -= -ÜVT singular value decompositions of A and Å, respectively, where U,Ú E O(m). V, V Od)), and Σ, E Rgad are diagonal.
Recall that our goal to bound the quantity BlJiTTTiV VT [r], where A EVT and ÅT = EVT are eigenvalue decompositions of A A and ÅT Å. To ob- tain bound on this quantity, first define stochastic process (t) for which Yi (0) VVT and Ve (T) vrTrv. We then bound the expected Frobenius distance
BJJÍT - TV [|]] = (T) - (()][=)
by integrating the stochastic derivative of (1()) over the time period [0, T).
Towards this, at every time / 2 O, define (() = U()) to be singular value decom-
position of the rectangular matrix (t), where (t) E mmd
dd is a diagonal matrix whose diagonal (t of (t)). (tt) [t). ca(t)] is d x d
entries are the singular values σ (t) 2
orthogonal matrix whose columns U1 (t), (t)()) are the corresponding right-singular vectors of (t). (tt ((m) is
orthogonal matrix whose columns are left-singular vectors of (t)..
At every time, denote by (t) E Ora to be the symmetric matrix with given eigenvalues I and eigenvectors given by the columns of (tt):
== V(t) T Vt E [0.
In other words, (t) Orz is the Frobenius-distance minimizing projection of the matrix Brownian motion (t) onto the orthogonal orbit manifold Ors.
4.3 DERIVING AN EXPRESSION FOR THE STOCHASTIC DERIVATIVE (V)
To bound the expected squared Frobenius distance IE [ (0) we would like express integral in terms of the stochastic derivative of ((t).
Towards this end, we use the stochastic differential equations which govern the evolution of the eigenvectors of the -eson- process equation to derive expression for the stochastic
8

---

Published as a conference paper at ICLR 2025
derivative d of the matrix diffusion (t) (Lemma A.2)
(t)(t)
o (t)) (t)
d
(g(())
Σ
h }3))
(t) (10)
4.4 BOUNDING THE SINGULAR VALUE GAPS.
The above equation (equation 10 for the stochastic derivative (t) includes terms Cij (t), whose
magnitude is proportional to the inverse the gaps in the squared singular values of (t) - (t for each i,j E [d]. In order to bound these terms, we use Weyl's inequality equation 3.2 together with standard concentration bounds for the spectral norm of Gaussian random matrices (I Lemma to show that the gaps (t) (t in the top l + singular values satisfy (Lemma A.3
(t) og (t) 2
- E [0, i
with high probability at least - 8, provided that the initial gaps are sufficiently large to satisfy Assumption [.I[A,, 4 T", o, 7) This implies that, with high probability least the inverse- eigenvalue gap terms in equation T0 satisfy (Lemma A.4
+ S
4
Ciy
V ( 0, 0j
vi te [0,
(11)
4.5 INTEGRATING THE STOCHASTIC DERIVATIVE OF (T) OVER THE TIME INTERVAL [0, T].
Next we express the expected squared Frobenius distance E ||| - (0)) as an integral E [I) [()) E [1 (
Next, we apply Ito's Lemma (Lemma 3.1 to S(V(()) where S(X) = || 23 and plug in our
high-probability bound on the inverse ergenvalue gap terms (I) equation bound for the integral E S (V)))) which gives roughly (Lemma A.5
to derive an upper
E (Z) (0)
27
d
d
dt )
32
E
Σ
M
6 - 2z)
dt + 32T
E
Σ
(1 -3)22((()
0
i=1
27
(?) - 222
h2 - 73
< 32
E
dt + 32T
E
Σ
dt.
(12)
(a - -o,-
0 ,3)}
Noting that the second term on the right-hand side of (12) is at least as small as the first term, and applying the Cauchy-Schward inequality to the second term, we get that (Theorem 2.2).
(0) - 73) (0: - -
E - -T 12 =E [IV((T) v 50
T.
CONCLUSION
In this paper, obtain Frobenius-nome bounds the perturbation to the singular subspace spanned by the top-k singular vectors matrix A e moxd when A is perturbed by an m x Gaussian random matrix. Our bounds improve, in many settings where the perturbation is Gaussian, bounds

---

Published as a conference paper at ICLR 2025
implied by previous works, by a factor of roughly ym 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 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.
Vd This may lead to large improvement in many
On the other hand, we note that our bounds assume that the top-k singular value gaps of A are roughly ((ym); while this assumption may hold in settings where the data matrix has fast-decaying singular values, would be interesting to see 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.
ACKNOWLEDGMENTS
This work was supported in part by OM's Google Research Scholar award.
REFERENCES
Emmanuel Abbe, Jianqing Fan, and Kaizheng Wang. An Ep theory of pea and spectral clustering. The Annals of Statistiics, 50(4):2359- 2022.
Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz, and Sergei Vassilvitskii. Differentially private covariance estimation. In Advances in Neural Information Processing Systems, pp. 14213- 14222, 2019.
Patrick Bergmans. A simple converse for broadcast channels with additive white gaussian noise (corresp.). IEEE Transactions on Information Theory, 20(2):279- 2800 1974.
Marie-France Bru. Diffusions of perturbed principal component analysis. Journal of Multivariate Analysis, 2971):227-136, 1989.
Changxiao Cai, Gen Li, Yuejie Chi, H. Vincent Poor, and Yuxin Chen. Subspace estimation from unbalanced and incomplete data matrices: f2 statistical guarantees. The Annals of Statistics, 49 (2):944 967, 2021.
Chandler Davis and William Morton Kahan. The rotation of eigenvectors by perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
Petar M DjuriC. A model selection rule for sinusoids in white gaussian noise. IEEE Transactions on Signal Processing, 44()):744477 1996.
Cynthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pp. 1-12. Springer, 2006.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Iya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference the Theory and Applications of Cryptographic Techniques, pp. 486-503. Springer, 2006.
Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for
principal component analysis. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 11-20, 2014.
Freeman Dyson. A brownian- model for the eigenvalues of random matrix. Journal of Mathematical Physics, 3(6): 1962.
Justin Eldridge, Mikhail Belkin, and Yusu Wang. Unperturbed: spectral analysis beyond davis- In Algorithmic learning theory, pp. 321-358. PMLR, 2018.
Jianqing Fan. Weichen Wang, and Yiqiao Zhong. An loo cigenvector perturbation bound and its application. Journal of Machine Learning Research, 18(207):1-4) 2018.
Alice Guionnet and Jiaoyang Huang. Large deviations asymptotics of rectangular spherical integral. Journal of Functional Analysis, 285(11), 2021.
10

---

Published as a conference paper at ICLR 2025
Carl W Helstrom. The resolution of signals in white, gaussian noise. Proceedings of the IRE, 43(9):
1111-1118, 1955.
Mia Hubert and Sanne Engelen. Robust pea and classification in biosciences. Bioinformatics, 20(11): 7728-1736, 2004.
Kiyosi Itó. On a formula concerning stochastic differentials, Nagoya Mathematical Journal, 3:55-65, 1951.
Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani, et al. An introduction to statistical learning, volume 122. Springer, 2013.
Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In Proceedings of the nwenty-fourth anmual ACM-SIAM symposium Discrete algorithms, pp. 1395-1416 SIAM, 2013.
N Kishore Kumar and Jan Schneider. Literature survey low rank approximation of matrices. Linear and Multilinear Algebra, 65(11):2212-2244, 2017.
Edo Liberty, Franco Woolfe, Fer-Gunnar Martinsson, Vladimir Rokhlin, and Mark Tygert. Random- ized algorithms for the low-rank approximation of matrices. Proceedings of the National Academy of Sciences, 2011)))011272121111 2007.
Wei Liu and Weisi Lin. Additive white gaussian noise level estimation in svd domain for images. IEEE Transactions on Image processing, 22(3):872-883, 2012.
Oren Mangoubi and Nisheeth Vishnoi. Re-analyze gauss: Bounds for private matrix approximation via dyson brownian motion. Advances Neural Information Processing Systems, 35:38585-338 -38599 2022.
Oren Mangoubi and Nisheeth K Vishnoi. Private covariance approximation and eigenvalue- gap bounds for complex gaussian perturbations. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1522-1587. PMLR, 2023.
Oren Mangoubi and Nisheeth K Vishnoi. Private low-rank approximation for covariance matrices, Dyson Brownian motion, and eigenvalue- gaap bounds for Gaussian perturbations. Journal of the ACM, In Press.
Oren Mangoubi, Yikai Wu, Satyen Kale, Abhradeep Thakurta, and Nisheeth Vishnoi. Private matrix approximation and geometry of unitary orbits. In Conference on Learning Theory, pp. 3547-3588. PMLR, 2022.
JR Norris, LCG Rogers, and David Williams. Brownian motions of ellipsoids. Transactions of the American Mathematical Sociery, 294(2):557-765, 1986.
Sean O'Rourke, Van Vu, and Ke Wang. Random perturbation of low rank matrices: Improving classical bounds. Linear Algebra and its Applications, 540:26-59, 2018.
Sean O' O'Ruurke, Van Vu, and Ke Wang. Matrices with gaussian noise: optimal estimates for singular subspace perturbation. IEEE Transactions Information Theory, 2023.
Santosh Patnaik, Jesper Dahlgaard, Wiktor Mazin, Eric Kannisto, Thomas Jensen, Steen Knudsen, and Sai Yendamuri. Expression of micrornas in the nci-60 cancer cell-lines. PloS one, 7(11): c49918, 2012.
Azer P Shikhaliev, Lee C Potter, and Yuejie Chi. Low-rank structured covariance matrix estimation. IEEE Signal Processing Letters, 26(5):700-704, 2019.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge University Press, 2018
Per-Ake Wedin. Perturbation bounds connection with singular value decomposition. BIT Numerical Mathematics, 12:99-111, 1972.
11

---

Published as a conference paper at ICLR 2025
Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgle- ichungen (mit einer anwendung auf die theorie der hoblraumstrahlung)) Mathematische Annalen, 71(4):441-479, 1912.
Wen-Rong Wu and Po-Cheng Chen. Adaptive ar modeling in white gaussian noise. IEEE Transactions on Signal Processing, 15(5):118441199) 1997.
12

---

Published as a conference paper at ICLR 2025
CONTENTS
Introduction
Related work
12
Our Contributions
2
Main results
2.1
Application to singular subspace recovery.
2.2
Application rank-k covariance matrix approximation.
2.3
Applications to differential privacy
3
Preliminaries
3.1
Dyson-Bessel process
3.2
Right singular vector SDE
3.3
Ito's Lemma
3.4
Other preliminaries
4
Overview of proof of Theorem 2.2
Viewing the perturbed matrix matrix-valued Brownian motion.
Projecting the matrix Brownian motion onto the orthogonal orbit Orz.
8
4.3
Deriving an expression for the stochastic derivative dVv()).
4.4
Bounding the singular value gaps.
4.5
Integrating stochastic derivative (t) over the time interval 0,
Conclusion
Proof Theorem 2.2
15
Proof of LemmalA.
15
Proof of Lemma A.2
16
A.3
Proofs of Lemmas A. and A.4
17
4 Proof of Lemma A.5
18
A.5
Completing the proof of Theorem 2.2
21
B Proof of Corollary 2.3
22
Proof of Corollary 2.4
23
D Additional comparisons for low-rank covariance approximation
25
Numerical Simulations
26
Simulations for rank-k covariance matrix approximation
26
Simulations for subspace recovery
28
13

---

Published as a conference paper at ICLR 2025
E.3 Simulations for rank-k covariance matrix approximation
28
14

---

Published as a conference paper at ICLR 2025
A PROOF THEOREM 2.2
A.1 PROOF OF LEMMA A.
We first decomposite the matrix (t) sum of its right-singular vectors: vi())
E (u(()(())) (I)). Thus we have
(v) Σ dd(; (8)
(13)
We begin by computing the stochastic derivative du, (t)o, (t) for each i [d], by applying the
formula in ( together with Ito's 's Lemma (Lemma 3.1).
Lemma A.1 (Stochastic derivative of v((t) For all [0,
d (e:((t)) (0) Σ jit
(1) 2 (t)(t) Σ Cy(O)..
Proof. The dynamic of right-singular vectors Bru 1989) are the following:
du;(t) Σ 1 2y A.(t)
1 (t) Σ
2y(t) + (.(t)
- x,))) dB 2.,.((
(21(1) - Ax(1)² dt
j7i
sti
Σ (,((),(())))((()) 2nd (t)) Σ (1)dt.
#t
sti
Thus, have (v:(t)u, (t)) = (v. + (t)( (ei(t) + (t) - (t)o (t)
vi(t) + Σ 2s(() (()Bx(())) 2 (t(() Σ Ejdtt
v1(1)== + En)(() (c0(0333331)11 -2:00-20000 21((1)
T
Σ ( - -()())(((1)
x
J#
= (t)
Σ
iy (t)c(())))
2000)00 (t) Σ (t)dt +
1
Σ (t))(((1))))33,((1
0 (T(())
2
jti
jtt
ey
Σ AAI
of (0)0((())3))1))
- (2(()) (1) Σ (t)d
vt)
Σ 2 (()((())))))
Σ (0(0(1(()))1)1))
0 - (t)x, (t)
(t)(t)dt
s7i
jti
Σ
ua (4),
k +#
(TT())=a(00)))) Σ E2s(0an00BB10))) ) 1o - (1))0 (1)
= (1)
Σ 23 (000008811))) +
E ())
ati
Σ>
Uk (1),, (0000))))
k 5サ1
Σ
(00 (1))
3#1
15

---

Published as a conference paper at ICLR 2025
A.2
PROOF OF LEMMA A.2
Recall that
(t) Σ 2=1
( (t)).
We now apply Lemma A.1 to compute the stochastic derivative of (t).
Lemma A.2 (Stochastic derivative of (())). For all i [0, T) we have that
dt
1
%
(0000,, (,)) (1) -0 (t)(((((()))))
jti
Proof.
(t)(t))
(td() (0)
Σ 7
Σ 0000 (t) Σ -0) u,))o (t))
itti
jfi
2i +c (t) Σ
Σ v (t)dtcc))))) (t))] (8)
sti
i=1 jyl
10 (,,0,))0)),,,,,,00,000,0000,0 + (t)e (t))
1
(1 - (000))))000000000000000000000000 -1-
(14)
The last equality in the block of equations 14 holds for the following reason:
Since (t) form a -emmmmymtt matrix, i.e. (t) -Bja(t) for all 2 0, we have that (B:;()) = (1) for all 2 O. Thus, we have that for all j + i, Gy ( (t)) T + v,(t)os(t))) -c))(() (t) (t) + (t)())((()))) (15)
Thus, combining the pairs of terms in the first double summation on the r.h.s. of equation 14 with index (i.j) = (a. b) and (i, = (b, a) for every b + we have by equation 15 that
() (0) m000 (0)
Eg L
(2 + tyt()
(16)
jfi
Moreover, observe that, for every + j.
(x²-77)) ()))) (()) (1)
(17)
Thus, combining the pairs of terms in the second double summation on the r.h.s. of equation 14 with index (i,j) = (a, b) and (i,j) = (b, a) for every b # a, have by equation that
Σ Σ ())
(1) 2
Σ
I
(ne -
(00,
1=1 jyl
E=1 iyy
(18)
16

---

Published as a conference paper at ICLR 2025
Pluggining in equation (otiiionn66aaaa and equation 18 into the second-to-last equality in the block of equations 14 we get that the last equality in the block of equations 14 holds
Thus, have
dv
(r (0000)) ( (t)(t)o(()))
(7)
2 i=1
jfi
ΣΣ
7 (0000030000000000000000000000000
2
1= j4t
A.3 PROOFS OF LEMMAS A.3 AND A.4
Next, we show beg-prrbbbilltyy bounds on the singular gaps (t) oy(t) (Lemma A.3) and coefficients Giy (t) (Lemma A.4).
Lemma A.3 (Bound on singular gaps:). Suppose that Assumption 2.7 for A, 7) is satisfied.
Then for all E [0, T), with probability 1 8 where == "dq7 (m1 2 we have (a,(t) -060--op (t) 2 Viz(0 -o,) for any <
Proof. With probability at least 5, by Lemma 3.3 we have
[B( = lIviG||2 s Vt x 2 max (m, d) log ( V x 2 llgg)
1
where G is a matrix with iid (N, 1) entries.
Thus, by Weyl's inequality (Lemma 3.2
we have that
Lemme
3.2 S
Lemm (12/mlog
(t) ozl
[B(t)l2
(19)
for all i E [d] with probability at least - 5.
Therefore, we have that
(o(t))oo/le
o o. lo,(t) o,l (o,(t) 0,5
Eq 19
03 0j Vi 4 1
1
2 (0, σT)
with probability at least 6, for any i < and any E [0, 7].
The following proposition shows that the symmetric coefficients Ciy (1) are bounded by the reciprocal of the initial singular value gaps.
Lemma A.4 (Bound of coefficients (1)( Suppose that Assumption 2.1 for (A,k, is
satisfied. Then for all E [0,T], with probability 1 - 8 where 8 = 8d
r 2 we have
4 for aarany < j-
ciy(() < 0, oj
17

---

Published as a conference paper at ICLR 2025
Proof. By Lemma A.3
have have with probability at least - 8
(=3(0++00() + +3)(
(1(( 10](1) - ot)(
dy(t) + (t(()
$ 2 (oy(t) (o ott))
(i((t) oz(()] S -jjjj
for any i < j.
oo,(t) (t)
A.4 PROOF OF LEMMA A.5
Next, to bound the quantity E (T)
(O) use Lemma A.2 together with Ito's Lemma
(Lemma 3.1). and then apply Lemma t. to the resulting expression (Lemma A.5
Lemma A.5 (Bound the Frobenius error integral of (t))..
E V (T) [00)
27
T
(0) - 73)2 (o, - 02)3
h - 731
$ 16
E
dt 32T
E
dt.
(20)
(0s o,)²
jzii
Proof.
Let be the event that lo.(t) - o,(1) 2 70, - -o,) for any < and any [0, By
Lemma we have P(E) 2 5.
By Lemma we have
(T) v(0) = l dv)
d
Lemmd 4.2
(0 -00 (1)())))))))
2 it
Σ
h - (0000000000000000000000000000000 (1,0000)0000000000)000000))
(,(00,(1)))
1#1
T
<
W 33000((1433,,0000000000 (t)))))))))
2 2
ittt
+3
Σ
(0 (t)),,((t)
2
1=1
iti
312 +
3Iz
(21)
where the inequality holds by the triangle inequality, and where, for convenience, define
1 d
1 =
(T?
(000000) (t)((((())))
2
1=1
jæt
and
d
1 =
Σ
(n2 - (0) (0))),(()))()
2
i=1
18

---

Published as a conference paper at ICLR 2025
To evaluate the first integral 11, define
I' Σ j
T
x(t)
( (0000000000 +0000(0)))))))))
for all t >> 0. Then we have that
dx((t Σ
( 00000000133,00000000000000000010 (000000000000000000000000000010) = Σ E (t)
where Rf:(t)= = (n - (3) ciy(t) (o,(t) (t)) so its [t, component is
dx [x(0)(11)33;;())
Defining the function f(x) = || : Ei Ei= x² r] and applying Ito's Lemma (Lemma we have
as(x) Σ Σ (1x0
1
ΣΣ
2
1=1
d d
d
d d
d
(x
r| ΣΣ (1
=
i=1 jf
Thus,
B(4 x 18)
((()(((T)) - 1g] 0+ EE
R3,(0),r) x LE]
2
El
(17 (100000000000 + et)(t,,,(t)
[[.r)) dt x 1gl
2
I=
d
d
E
(17 (10=00000000000000000 +0,000 (1) di x 1n]
2
jæL 1=1
d Σ
E
11 (1000 +0,00 I
2
i=1 jt
1 T
E
(r (3 (t)) ()) 1g)
2 J
jtt
1
16(
? 02)²
(?) - 73)
E
4d1) 32
E
(oi σ,) 2 dil,
(22)
2
(a:
The first inequality holds since the term E E
Σ. Ei_ 2x(1)(rr)
E' (t), =
O vanishes because d.3):()) is inedependent of both X x() and Rz((()(,7T) for every i,j,4,r r. The
last inequality holds since, whenever the event E. occurs, we have (o,(1) oy(1) 2 [a 0,) for any < j and any & [0,T].
19

---

Published as a conference paper at ICLR 2025
For the second integral 12, we have
d
1 =
(1 - -0000000000000000000000000000000 dtt
2 0
i=1 jzi
d
( -0-0))00000000000000000000000000 dt
i=1 jfi
F
T
T
Σ
dt x
dt
2
iti
12
T
Σ
100
dt
==1
d
Σ hh - 13)6)(10)
[lu((t)u - (5)),()) 1
= 2
i=1
jpt
2
T d Σ
s 2T
Σ ( (t) Ji
dt
(23)
where the first inequality holds by the Cauchy-Schwee inequality. The third and fourth equalities hold since o, (t)) (t))),, = for all i + j. The last equality holds since [[); (t) uy (t) Il. I [[),(t)o; (t)lle + (t), || I because [t) (f)ll = for all E [d].
4
Whenever the event E occurs we have by the proof of Lemma that (iz(t) < and all E [0.
for all i <<>
a; aj
Thus, equation 23 implies that
2
T
h? 731
12 LE S 32T
Σ
0 03) dt.
(24)
ju
We can express [[]))(()
V [3) as the following sum,
(T) - (0) E|l - x Lel EI])(T) (0)) x 11
(25)
Combining equation 22 and equation
it follows that
E (T) (O)) x ig] < E|] (0))
E[4 1g + I2 x ig]
= E[4 x 1Æ] + EE//
x 1F]
2
(1 - 72 (o: 02)
T
h - 73
S 32
E
dt 327
Σ
Σ
ddt.
(a, - o,
iti
d=1
#
(26)
20

---

Published as a conference paper at ICLR 2025
Moreover, have
B (T) (
1 S P(E))
< [[]10([11++(0000) 1
- 8d9)P(E9)
< 8d77 x 8
フं - 7d
2
(0 0o)²
2
T B
( 72
T
(, 73)
32
dd
+
327
E E
Σ
ldl,
(o: o3) )
(i ,; )3
0
i=1
j+
(27)
where the fifth incquality holds since
<
8dy
(or
Therefore, plugging equation 26 and equation
27 into equation 25
we have
d
(1² 2)
d
h
(T) (0)1 < 32
E
d0
+ 327
E
Σ
ldl.
(0;
02)
[
or)3 )2
i=1
j
iml
jz
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
E
TTT
VT
TV
E [IV(T)- (0)
(1 - 133
d
h - -9
< 32
E
dt + 32T
E
ldt
(0: 02
(a+ o2)²
i=1 jti
(=1
izi
2
d
(1 - 22
T
h/2 731
< 64
E
dt) + 64T
E E
ldt
(a. - 0,)² )2
(a: - ,,)²
j=it1
2
T
d
(1² ??
T
h ?3
64
E
dt + 64T
E
ldt
(0: o,)² )2
(a: o,)²
i=1
j=it1
i=1
2
4
(12 - 7
d
h2 791
64T
+ 6
(0: o2)
(o; - o,
1=
3
(7 ?3
+T Σ
Σ
T.
(28)
(a; o3)² )
(a; - o.) )2
j=i+1
21

---

Published as a conference paper at ICLR 2025
By the Cauchy-Schward inequality, we have that
2
2
6 1
1
1 7j
(a; (o--ū)) o,
=
0 02
X
0 o3
/=++1
/=41
(, - -
1
Σ
x
j=1H1 (0, - o,)3
(o, - o,)3
1
(? - 73
(Vd)²
(as σj)
-=++1
(1 - 73) 72
(0: 03)² )2
jmi+1
Plugging equation 29 into equation 28
we have
d (n) 7732
E
1 0o
Σ
T.
(o: - o,)²
j
B PROOF OF COROLLARY 2.3
Proof of Corollary 2.3 To prove Corollary 2.3 we plug in 7 = 7 1 and 76+1
Ya 0 to Theorem 2.2 There are two cases.
In the first case, where A may be any m x d matrix which satisfies Assumption 2.1
plugging in
71 7k 1 and 76+11
Ja 0 to Theorem 2.2 we get
E
V 1
E
TVT - VT
(1: 7
00
T
(0: oo)
|=#1
1
-0
T
jlj=4 (a: - o,)2
1
0o
T
j1 (ox oxti)?
kd
0
T o ) T
(30)
where the first inequality holds by Theorem 2.2 and the second equality holds in that 7 7h 1 and 7:+1 ... Ta 0.
By Jensen's Inequality, we have that
Vkd
B BIIVE - -vav 1F
S
S
VT
- VA
< <0
VT.
(ox 02+1)
22

---

Published as a conference paper at ICLR 2025
In the second case, where the singular values of A also satisfy o, -0+1 a( -k+1) for all
i S h, we have
IIVE
-
-VV
=
-V
d
(1z -
0
T
(0: ロ3)
j=itl
Σ
Σ
1
T
(a= o,)
- 1=
0
Σ
Σ
1
T
(i k - 1) - ok+1)2
j=1
00
Σ
T
i 1)2(0k - -b++1)
1=1
d
Σ 12
0
T
(o 0x+1)2
i=1
d
0
T
(31)
(ox
xx41)2
where the first inequality holds by Theorem 2.2 and the second equality holds since .... % 1 and 7/++ =
Ya = 0, the second inequality holds since o; 0s+1 2 2( 0k+1) for all i S k and the last inequality holds since Σ a S Di= 2 O()).
1
Thanks to Jensen's 's Inequality, we have that
Vd (ox
E IIVVE - VaVVT [F] $ B
VAV 12:]
00
VT.
ox+1)
C PROOF OF COROLLARY 2.4
Proof of Corollary 2.4
We first bound the quantity E
[ Σn DT - -VE
23

---

Published as a conference paper at ICLR 2025
Set 7/2 o, for i S 16 and 7/4 = 0 for i >>>>> k. Then by Theorem 2.2 we have
(,? 773
E
|IVE E -
0
Σ
Σ
T
(0t - o,)²
jmi+1
(o - - (0i o,)²
0 - 0²)
Σ
T
0: oj
i=1 j=
2 2 0: jj
2
( ,
k
k
T
0
oj
== j=k+1
o
2
00
(ai 0o)+ +
Σ Σ
T
0i oj
i1j=kk
4-1
k d Σ (o: +
2
-0
Σ
Σ Σ
0 0: σk
OF
0 o3)
i= j=k+1
2
00
Σ
Σ
(o, 00) 2 +
Σ Σ
0 + 0k
0k
T
-j
i=ij=k+
k-1
2
0
Σ
Σ
+
Σ Σ
0k σk o,)
T
j=k+1
4
2
00
||E
0k
Tk
T
0k Jj
1=1 j=b+1
00
d|E k(d - -k)
ok 0k 0kt1
T.
(32)
We next bound the quantity [ E VT - VVn Eg V |1.]
Let Ej be the event when ||G]| > v max(m, d) log(1/ (1))). By Lemma 3.3 we have PPEE) 2 1 1-6 8.
Since || I Vkoa and |اام|| F V we can use the bound
1 Ex - ΣJ E < Σ Σx || + | Ealle < kσ + ko?(t) < 4ko?
and hence
E V' Et Ei * LE,1 < 2VKo, * P(Ei) < 4ko 6.
Recall that (from Assumption 2.1 i < ooन Hence,
E EI Ex S * LE,] <
Now consider the event ET, where || < m/x(mm d) log( (/8). From above, we have P(E
1 - P(EE) < 5. For Eÿ we get,
11 E Ei
St
1
Ell( Ei' Ex)lFF * LEy]
BivT|| (|Ex|le+ + [|É 1
B[2VKTo Gx|l * .1gg]
2VKdon log(1 (1/8)
24

---

Published as a conference paper at ICLR 2025
Finally, put the two cases together:
E | ΣN
VE Ex V
[11]] =E|EE> Exll>]
= |B[| Ex EKlLF 1F, + B1IE> - Ex11 1my]
4 2V kidoi 1og(1/5)vT
= OVKkdo log( 16))
(33)
Combining equation 32
and equation
we have
| E
VE E [r]
R
s
VΣ Σx 11
+
|IVE Es PT 1OTT-VX EEVEVVTTI [F)
00
VdjiinlF + Vkld-K -k) k)
oh ok
VT + O(Vkdo, log(1/6))VT
0k+1
0 /ddlEnle+ + Vk(d-H) k)
0h: 0k+1
ok
VT.
(34)
D ADDITIONAL COMPARISONS FOR LOW-RANK COVARIANCE APPROXIMATION
In this section, we present how one can derive high-probability bounds on the quantity [VSI
VE F from the subspace perturbation bounds of Davis & Kahan (1970) Wedin (1922) or O' Rourke et al. (0018).
Towards this end, we note that
VVSSVT - VE V lF
VER + -
+ - -
The first term can be bounded as
VEST - VV 1
E
07 o?
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
V - VV 1e
Σ (o
- -WT) - Vl
Σ
(0 - VV + R - 1l
- (a + - - - VVV - Vl
Viva
Vkvd
Σ
(a, 01+1)
0k oh Tk+1
σ 0
=0
σk
Vivaa
(35)
σk 0k+1
25

---

Published as a conference paper at ICLR 2025
Plugging into equation 35 the bound of ||V.V, V.VV 1| S 0--0441 & Kahan 1970): Wedin
fiym VT w.h.p. implied by Davis
1972. one has
Vivm VT + oh
Vivmm VT
VE V
F
0i 02+1)(0
-0++11 oi -i+1
ok 0k+1
k-1
of o++1) oe Vhvmm VT
S VmvT T
ok - o++1
vkym VT. 2k VIVTTI of on ak+1
One can also instead plug in the bound from Theorem 18 of
al. (2018) (restated here as
equation 2 in Section 1.1 into equation
35 When, e.g., o% 0k++ 2 52[max ( Vm)), equation 2
reduces to V T
V |
S
O
i
VT
for i S k into equation 35 Thus, plugging in
this bound into equation 35
one has
-
-V2
lr S
oo + ++0++1)(( 01+1)i -0;1))
VT
of V VT Ok
0;
00
Σ (o +
0
-oli-ookkyVV+++ ookkm/T
0 (ork/mVT)
E NUMERICAL SIMULATIONS
In this section, we present numerical simulations that illustrate the theoretical results in Theorem 2.2 and investigate the extent to which the bounds in Theorem 2.2 are tight.
E. SIMULATIONS FOR RANK-k COVARIANCE MATRIX APPROXIMATION
In this set of simulations, we compute the squared Frobenius error for the rank-k covariance approx- imation problem, / PT VΣ E, V 11. We take an input "data" matrix A, perturb the matrix by iid Gaussian noise (that is, Å = A + VTG where G has iid (O, 1) entries), and compute the error V Egg V- V Σ2 V. for different values of m, d, In the following simulations we choose the input "data" matrix to be a synthetic data matrix with linearly decaying spectral profile spectral profile a; = /m x (d - i 1) for all E [d.. We note that, since the noise distribution G is invariant multiplication orthogonal matrices, we may assume without loss of generality that A is (rectangular) m x diagonal matrix with diagonal entries o.. Ja and zeros in all other entries.
We then plot the ratio of the error observed in the experiments to the r.h.s. of the bound in Cororlary | S S. -V v Ie for different values of m (Figure 1b, d (Figure 2), and & (Figure 31.
2.4
of )a + <x
keeping the other two variables fixed in each plot.
We observe that, the ratio of the experimentally observed error and our upper bound does not change much (up to a small constant factor) for different values m or d, suggesting that, for matrices A with the above spectral profile, our bound in Corollary 2.4 tight with respect to (Figure 1) and d (Figure 2).
On the other hand, observe (Figure 3) that the ratio of the observed error and our upper bound seems to be smaller for values of which are far from or d, suggesting that Corollary 2.4 may not have tight dependence on l for input matrices of this spectral profile.
26

---

Published as a conference paper at ICLR 2025
Rescaled Rank-k Cov. Approx. Error vs. m
1.8
1.6
1.4
1.2
1
0.8
0.6
0.4
0.2
0
1000
2000
3000
4000
5000
600(
m
Figure 1: Plot of the rescaled error, that the Lhs.. of Corollary 2.4 divided by the r.h.... |VS 8 -V "., 11. for different values of Error bars indicate standard deviation. Here, "
d 15, k: = 5. and the input matrix has spectral profile Ø; m (d ----+-1 1) for all [d]. The rescaled error does not change much, suggesting that, for input matrices of this spectral profile, Corollary 2.4 has tight dependence on m.
Rescaled Rank-k Cov. Approx. Error vs.
2
1.5
0.5
0
200
400
600
800
1000
d
Figure 2: Plot of the rescaled error, that is, the L...s Corollary 2.4 divided by the r.h...
|VVT Sy PT VTTTV for different values of d. Error bars indicate standard deviation. Here.
d| + - of "
m 1000, 7 and the input matrix has spectral profile o, = vm x (d - 1) for all i E [d. The rescaled error does not change much, suggesting that, for input matrices of this spectral profile, Corollary 2.4 has a tight dependence on
27

---

Published as a conference paper at ICLR 2025
Rescaled Rank-k Cov. Approx. Error vs. k
1.5
0
60
100
k
Figure 3: Plot of the rescaled error, that is, the l.h.s. Corollary 2.4 divided by the r.h.s., J 8- -V V for different values of d. Error bars indicate standard deviation. Here, d| + Ef " 1 m 1000, d 5, T and the input matrix has spectral profile o; v x (d i 1) for all i [d]. The rescaled error seems to be smaller for values of k which are far from or d, suggesting that Corollary may not have a tight dependence k input matrices of this spectral profile.
E.2 SIMULATIONS FOR SUBSPACE RECOVERY
In this section, we present numerical simulations that illustrate the theoretical results in Theorem 2.2 and investigate the extent to which the bounds in Theorem 2.2 are tight.
E.3 SIMULATIONS FOR RANK- COVARIANCE MATRIX APPROXIMATION
In this set of simulations, we compute the Frobenius norm error for the subspace recovery problem, [!vVT - VV..EF. We take input "data" matrix A, perturb the matrix by iid Gaussian noise (that is, Å - A VTG where G' has iid (O0, 1) entries), and compute the error VV VV [|,, for different values of m, d, k. As the simulations of Section E. we choose the input "data" matrix to be synthetic data matrix with linearly decaying spectral profile spectral profile a; /m x (1) for all E [d].
We then plot the ratio of the emorr observed in the experiments to the r..s. of the bound in Corollary 2.3
V.V. 1/ |lr for different values of m (Figure 4 d (Figure 5 and k (Figure 6), keeping the vd/(ax=0k11)
other two variables fixed in each plot.
We observe that, the ratio of the experimentally observed error and our upper bound does not change much (up to a small constant factor) for different values m or k, suggesting that, for matrices A with the above spectral profile, bound in Corollary 2.3 is tight with respect to (Figure and (Figure b).
On the other hand, observe (Figure 5) that the ratio of the observed error and our upper bound seems to decrease with d, suggesting that, Corollary 2.3 may not be tight in d for input matrices of this spectral profile..
28

---

Published as a conference paper at ICLR 2025
Rescaled Subspace Recovery error vs.
1.6
1.4
1.2
1
0.8
0.6
0.4
0.2
1000
2000
3000
4000
5000
6000
m
Figure 4: Plot of the rescaled subspace recovery error, that is, the Lh.s. Corollary 2.3 divided by the r.h.s., [| V.T - V, for different values of m. Error bars indicate standard deviation. Here, and the input matrix has spectral profile a; = vm (d - + 1) for E [d].
Va/(ou-0444)
15, h = 5, The rescaled error does not change much, suggesting that, for input matrices of this spectral profile, Corollary 2.3 has a tight dependence on m.
Rescaled Subspace Recovery error vs.
1.6
1.4
1.2
1
0.8
0.6 0
0.4
0.2
0
200
400
600
800
1000
d
Figure 5: Plot of the rescaled subspace recovery error, that is, the L...s. Corollary 2.3 divided by the r.h.s., || P.' VV || for different values of m. Error bars indicate standard deviation. Here,
Vā 7+)1)
and the input matrix has spectral profile o; /m (d + 1) for all E [d]. The rescaled error decreases with d, suggesting that, Corollary 2.3 may not be tight in d for input matrices this spectral profile.
15, k 5,
29

---

Published as a conference paper at ICLR 2025
Rescaled Subspace Recovery error vs. k
1.2
0.8
0.6
0.2
40
100
Figure 6: Plot of the rescaled subspace recovery error, that is, the l.h.s. Corollary 2.3 divided by the r.h.s., 11 v2 - V4 VV ||+ for different values of k. Error bars indicate standard deviation. Here, = 15, k Vāl(ar = The rescaled error does not change much, suggesting that, for input matrices of this spectral profile, Corollary 2.3 has tight dependence on k.
T = and the input matrix has spectral profile o; vm (d (d-ir -i+ 1) for all i [d].
30


Reviews:
[{"review_id": "jk47vmEDXK", "reviewer": "Reviewer_vMhC", "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.", "questions": "1- Could you please motivate the theoretical result with some examples, even simply using toy datasets on differential privacy?\n\n2- 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?\n\n2- Could you further motivate why tall matrices are of interest in this particular setting?\n\n----\nTechnical Comments:\n\n1- 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?\n\n2- Line 191 has no period in the end.\n\n3- In Line 204, should it be $\\gamma_i=0$ for $i>k$?\n\n4- 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.\n\n5- The factor 64 and 32 in Eq. (14) is missing in Eq. (12).\n\n6- 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?\n\n7- In Line 595 please explain why $\\mathrm{d} v_i\\mathrm{d} v_i^T$ is neglected.\n\n8- 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.\n\n9- 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?\n\n10- In Line 698, factor 2 is not needed since $\\sigma_i(t)\\geq 0$ and $\\sqrt{a^2+b^2}\\leq a+b$?\n\n11- In 721 and 725, why there is factor 3? Frobenius is a norm and therefore has triangle inequality.\n\n12- In Line 752, please either stick with the notation AA^T or instead use $\\langle\\rangle$ instead of $<>$.\n\n13- From where does factor 2 in 772 appears?\n\n14- In 775, should we have $4\\mathrm{d}t$?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "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.", "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.\n\nFurthermore, 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. \n\nFinally, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pXs4NQnFxP", "reviewer": "Reviewer_PBwp", "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}}$. \n\nTo 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.", "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?\n\nCan 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.\n\nThough 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.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 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. \n\nThe 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).\n\nThat being said, I have a few concerns about the paper which I list below.", "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?\n\nAlso, 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? \n\nI 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "j1ay2QZ8Zc", "reviewer": "Reviewer_6eUD", "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.", "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?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 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.\n\n1. 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.", "weaknesses": "1. As mentioned in the conclusion, the result needs to assume a reasonable top-k singular value gap of A.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IpeCFBFQz2", "reviewer": "Reviewer_JJsP", "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. \n\nI 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. \n\nThe 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.", "questions": "-", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I find the topic very interesting. Proving these results is non-trivial and insightful.", "weaknesses": "-", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aKGqyNabK8", "reviewer": "Reviewer_Bu3u", "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$.", "questions": "N/A", "limitations": "", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "- The paper is easy to read. \n- The problem considered is important and has wide applications to many machine learning problems.", "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.\n\nIn [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$.\n\nBy 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.\n\nIn 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.\n\nTherefore, 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.\n\n\n[1] \"Subspace Estimation from Unbalanced and Incomplete Data Matrices: $\\ell_{2,\\infty}$ Statistical Guarantees,\" Annals of Statistics, 944-967, 2021\n[2] \"Inference for heteroskedastic PCA with missing data,\" Annals of Statistics, 729-756, 2024\n[3] \"Deflated HeteroPCA: Overcoming the Curse of Ill-Conditioning in Heteroskedastic PCA,\" Annals of Statistics, to appear", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)