Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy
Authors: Phuc Tran
Van Vu
Nisheeth K. Vishnoi
Venue: NeurIPS 2025 oral ()
Keywords: Spectral norm
low-rank approximation
differentially private PCA
contour integration
matrix analysis
Primary area: theory
TL;DR: We derive sharp spectral-norm bounds for noisy low-rank approximation, improving prior results by up to $\sqrt{n}$. Applied to DP-PCA, our method resolves an open problem and matches empirical error via a novel contour bootstrapping technique.

Abstract: A central challenge in machine learning is to understand how noise or measurement errors affect low-rank approximations, particularly in the spectral norm. This question is especially important in differentially private low-rank approximation, where one aims to preserve the top-$p$ structure of a data-derived matrix while ensuring privacy. Prior work often analyzes Frobenius norm error or changes in reconstruction quality, but these metrics can over- or under-estimate true subspace distortion. The spectral norm, by contrast, captures worst-case directional error and provides the strongest utility guarantees. We establish new high-probability spectral-norm perturbation bounds for symmetric matrices that refine the classical Eckart--Young--Mirsky theorem and explicitly capture interactions between a matrix $A \in \mathbb{R}^{n \times n}$ and an arbitrary symmetric perturbation $E$. Under mild eigengap and norm conditions, our bounds yield sharp estimates for $\| (A + E)_p - A_p \|$, where $A_p$ is the best rank-$p$ approximation of $A$, with improvements of up to a factor of $\sqrt{n}$. As an application, we derive improved utility guarantees for differentially private PCA, resolving an open problem in the literature. Our analysis relies on a novel contour bootstrapping method from complex analysis and extends it to a broad class of spectral functionals, including polynomials and matrix exponentials. Empirical results on real-world datasets confirm that our bounds closely track the actual spectral error under diverse perturbation regimes.

Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy
Phuc Tran VinUniversity
Nisheeth K. Vishnoi" Yale University
Van Vu Yale University
Abstract
A central challenge in machine learning is to understand how noise or measure- ment errors affect low-rank approximations- particullal in the spectral norm. This question is especially important in differentially private low-rank approxima- tion, where one aims to preserve the top-p structure of data-derived matrix while ensuring privacy. Prior work often analyzes Frobenius norm error or changes in reconstruction quality, but these metrics can over- or under-estimate true subspace distortion. The spectral norm, by contrast, captures worst-case directional error and provides the strongest utility guarantees. We establish new high-probabilliy spectral-norm perturbation bounds for symmetric matrices that refine the classical Eckart- Youngt-Young--irrkky theorem and explicitly capture interactions between a ma- trix A E _=x= and arbitrary symmetric perturbation E. Under mild eigengap and norm conditions, our bounds yield sharp estimates for [[(A + E)p Apll- where Ap is the best rank-p approximation of A, with improvements of up to factor of vn. As an application, we derive improved utility guarantees for dif- ferentially private PCA, resolving an open problem in the literature. Our analysis relies on a novel contour bootstrapping method from complex analysis and ex- tends broad class of spectral functionals, including polynomials and matrix exponentials. Empirical results on real-world datasets confirm that our bounds closely track the actual spectral error under diverse perturbation regimes.
Introduction
Low-rank approximation is a foundational technique in machine learning, data science, and nu- merical linear algebra, with applications ranging from dimensionality reduction and clustering to recommendation systems and privacy-preserving data analysis [1, 4, 5, 14, 21, 23, 24, 42, 45). A common setting involves real symmetric matrix A Raan, such
sample covariance matrix derived from high-dimensional data. Let X 2 ... > An denote the eigenvalues of A, with corresponding orthonormal eigenvectors U1,...; Un. The best rank-p approximation of A is denoted by Ap := Σi, A,u;4 This approximation solves the optimization problem Ap = arg min ||A- Bi}, where the norm be any unitarily invariant norm 10]. In particular, Ap minimizes both the spectral norm ||. measuring worst-case error, and the Frobenius norm || [|r, measuring average deviation.
In many applications, the matrix A is not directly available-it may be corrupted by noise, com- pressed for efficiency, or randomized to preserve privacy. A standard model introduces a symmetric perturbation E, yielding the observed matrix A = A + E. The approximation Åp. computed from A, is often used in downstream learning and inference. This leads to a central question: How does the perturbation E affect the top-p approximation A,? Understanding the deviation || - Apll is critical for ensuring the reliability and robustness of low-rank methods under noise.
Alphabetical order. Correspondence nisheeth. vishnoi@gmail.com com.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Motivating application: differential privacy. The stability under perturbations is especially im- portant when the matrix encodes sensitive information, such as user behavior or medical data. In such settings, even low-rank approximations of A can inadvertently leak private information [6]. To address this risk, differential privacy (DP) [14] has become the standard framework for designing wrivacy-preservee algorithms. Several mechanisms have been developed to release private low-rank approximations while satisfying DP guarantees [8. 9, 15, 25, 29, 31, 34, 39J. A canonical method, introduced in [15], adds a symmetric noise matrix E' with i.i.d. Gaussian entries to the input matrix A, yielding the perturbed matrix Ā A + E. The algorithm then releases A, as the privatized out- put. The utility of such mechanisms is typically assessed by comparing A, to the ideal (non-private) approximation Ap- Two standard metrics are: (1) the Frobenius norm error || - ApllF, and (2) the change in reconstruction error ||| Ap 4p1
||A 1 Apll-I. ll- which measures how much the quality of low-rank approximation degrades due noise, for norm || || [3. 11, 15, 29]. These metrics offer insight into the effect of noise on overall variance or total reconstruction error. However, as we explain next, they may fail to capture worst-case directional misalignment, which is often critical for downstream tasks and algorithmic guarantees.
I Limitations of existing utility metrics. The Frobenius norm error and reconstruction error may not be appropriate in applications that rely on the geometry of the top-p eigenspace. In particular, the Frobenius norm may overestimate the impact of noise by up to factor of vp when the perturba- tion E lies largely in directions orthogonal to the top-p subspace. The reconstruction error metric can underestimate subspace deviation- sometimes dramatically. In some cases, it remains small (or even zero) despite substantial rotation in the top-p eigenspace. (See Sections B for concrete illustrations.) These limitations motivate the use of the spectral norm || - Apll. which captures the worst-case directional deviation between the two low-rank approximations. The spectral norm also governs algorithmic robustness in many downstream applications, such as PCA-based learning, private clustering, and subspace tracking.
A classical spectral norm bound, derived from the Eckart-Young-Minn theorem [7, 16], states that || - Apl S 2(Ap+1 + +I ||),, which holds for arbitrary matrices and noise. However, such bounds are often pessimistic and fail to exploit the structure of A and E. More refined bounds exist in the Frobenius norm setting. For example, recent work [29, 30] shows that when A is positive semidefinite and has nontrivial eigengap óp == Ap Xp+1 2 ElI and when E is drawn from
complex Gaussian ensemble, one obtains: A - bounds of [15] by a factor of vp. However, these bounds have important limitations: They hold only in expectation and do not yield high-probability guarantees; They often assume Gaussian noise distributions; They are not spectral norm bounds and therefore do not directly quantify the worst-case impact on the eigenspace. These limitations prompt the following open question, raised in [29, Remark 5.3]: Can one obtain siobbbrrbbbbiitty spectral norm bounds for A Apll under natural structural assumptions on A and realistic noise models?
Ö ||]|| ) which improves on
the earlier reconstrutioon-errr-basss
Our contributions. We resolve the open question posed in [29, Remark 5.3), proving new high- probability spectral norm bounds for low-rank approximation under symmetric perturbations. Our results rely on natural structural assumptions on A and E and yield the first such guarantees for differentially private PCA (DP-PCA).
Two higb-probability spectral norm bounds. Under the same eigengap condition as [29], 8p Ap-Ap= 2 El, we prove || |Ap-Appl = O (1E1) 2x) and A A, || = Ō ( [ + r"x
Ag
8p
where r is the halving distance (a measure of spectral decay) and x == jax |u, Euyl quan- tifies noise-eigenspace alignment (Theorems 1-122. In addition, our contour-based framework extends to a broader class of spectral functionals ((A) (beyond f(A) = A), encompassing matrix powers, exponentials, and trigonometric transforms; see Theorem 2.3.
Spectral utility bounds for DP-PCA. Our first bound yields high-probability spectral norm utility guarantee for differentially private PCA under sub-Gaussian noise, improving existing Frobenius norm bounds by up to factor of vp (Corollary 2.4). While prior work has achieved spectral norm guarantees iterative or multi-pass settings [17, 18], our contribution concerns the direct noise-addition model, where this appears to be the first such result. For matrices with low stable rank and weak eigenspace-noise interaction, our second bound further improves by up to Vn.
2

---

Novel analytical technique: contour bootstrapping. Our proof relies on contour bootstrap- ping argument (Lemma 3.1). which provides new way analyze the contour representation of perturbations [19, 26, 35], enabling analysis of a broader class of spectral functionals (The- orem 2.3). The bootstrapping argument here is generalization of the argument used handle eigenspaces perturbation introduced in [37].
Empirical validation. We benchmark our bounds on real covariance matrices under both Gaus- sian and Rademacher noise. Across datasets and noise regimes, the predicted error closely matches empirical behavior and consistently surpasses classical baselines, confirming the sharpness and robustness of our theoretical results (Section 4).
2
Main results
Main spectral norm bound. For clarity, we state our main bounds assuming A E R=**" positive semi-definite (PSD); extensions to symmetric matrices appear in Section D. Let À 2 ... 2 An 2 0 be the eigenvalues of A, with corresponding orthonormal eigenvectors #1, Uny and define the eigengap 6% := > A Given a real symmetric perturbation matrix E, we let A := A + E, and define Ap and A, as the best rank-p approximations of A and Å, respectively. Our goal is to bound the spectral error || Apll-
Theorem 2.1 (Main spectral bound PSD). If |f S 6p. then: 1| - Apll S SO(EE) 2.)
The (() notation here hides small universal constant (less than 7), which we have not opti- mized; see Section D.1 for the proof of the generalization to the symmetric setting, of which this theorem is a special case. For Wigner noise-iee. a symmetric matrix E with i.i.d. sub-Gaussian entries of mean 0 and variance l-we have |E (2 + o(l)) with high probability [41, 43), so Theorem 2.1 reduces to ||Ap- Apll = (v
dependent, addressing a key limitation of the classical The right-hand side is explicitly noise-
Yount--uug--iiinn bound. Moreover, in many widely studied structured models (e.g., spiked covariance, stochastic block, and graph Lapla- cian models), one typically has A, = ((p)), yielding the clean bound O[] This rate theoret- ically tight: for instance, when A is PSD diagonal matrix and E = μIn for some μ > O, we have ||Ap- Apll P ||]]
Gap condition. Our assumption E||||| 6p aligns with standard conditions in prior work, in- cluding [29, 30], and is satisfied in many well-studied matrix sudc as spiked covariance (Wishart) models, deformed Wigner ensembles. stochastic block models, and kernel matrices for clustering. It also arises naturally in classical perturbation theory [12, 26, 28). Empirical analy- ses [29, Section B] further show that this condition holds for real-world datasets commonly used in private matrix approximation (e.g., the 1990 U.S. Census and the UCI Adult dataset [3, 11]). Hence, Theorem 2. operates under a mild and broadly applicable assumption, satisfied across both theoretical models and practical benchmarks.
Comparison the Eckart- Yokartt-oung-Miskk bound. Using >pp 5, + >pp11 Theorem 2.1 rewrites as || - Apll = O(1E) + Ap+1
[ This improves on the E-Y-M bound O[] + Ap+1)
bp
when Ap+1 > ||]] by a factor of mine Apt1 TET
For example, consider matrix with spectrum (10n, 9n. n, n/2, 1....,,, 1} and p = 10. For Gaussian noise with ||]|| = (Vv)), E-Y-M yields
5n ]
(n)) error, while our bound gives ((v /n-factor gain.
Comparison to Mangoubi-Vishhe Vishnoi bounds [29, 30]. Our bound also improves upon the Frobe- nius norm bounds of [29, 30], which under the same gap assumption yield: E| A, Apllr O( ). We eliminate the vp factor, upgrade from expectation to high probability. and support real-valued, non non-Gaussian noise models. A more detailed comparison appears later in this section (Corollary 2.4), where we analyze implications for differentially private PCA.
Proof technique: contour bootstrapping. Unlike prior analyses [29, 30], which rely on Dyson Brownian motion and tools from random matrix theory (see Section A, our proof of Theorem 2.1 uses contour-integral representation of the rank-p projector. This approach, which we call contour bootstrupping. isolates the top-2 eigenspace via complex-analyte techniques and avoids power- series or Davis- Kahan-type expansions. It enables tighter, structure-aware spectral bounds and ex-
3

---

tends naturally to refined perturbation results (Theorem 2.2) and general spectral functionals (Theo- rem 2.3). Full details uppear in Section 3.
Refined bound via eigenspace interaction. To sharpen our analysis, we incorporate fine-grained structure of the eigenspace and its interaction with the noise. Inspired by the recent works [33, 38), we start with the observation that the rank-p perturbation is primarily influenced by the cluster of eigenvalues near Ay, and the interaction between L and the corresponding eigenvectors. To control these factors, we define the halving distance (w.r. the index p) as the smallest integer such that Ay+1 S X2/ and interaction term = maxigijsr |u, Euyl. measuring the alignment between the noise E' and the top-7 eigenvectors of A. This yields a refined spectral norm bound:
Theorem 2.2 (Interaction-wware bound). If [|| S 6p. then | Apll = Ō([ + +r 2.)
See Section D.2 for the proof and its generalization to the symmetric setting. This bound improves upon the basic eigengap bound O (I + when the interaction term r²x is small. This oc- curs, for instance, when (i) A has low stable rank or clustered eigenvalues (e.g., spiked models, multi-cluster Laplacians), (ii) the noise E is random and approximately orthogonal to the leading eigenspace, or (iii) /p large but r = Ô() and Ó(). In such regimes, the bound simplifies to Ô [|EI| + ) ). yielding up /n-factor improvement over Theorem 2.1. This highlights the benefit of explicitly incorporating spectral decay and noise-cigenspace alignment when analyzing noise-robust low-rank approximations.
In practice, many public DP datasets (e.g.. Census, Adult, KDD) have small dimensions and modest eigenspace decay, the simple bound is more effective. However, the refined bound becomes espe- cially informative in large-scale or synthetically structured settings. Thus, the two bounds are best viewed as complementary: the first is robust and broadly applicable, while the second highlights structural regimes where stronger stability is provable.
Extension to spectral functionals. Beyond approximating A itself, many applications involve low- rank approximations of spectral functions fA), such as A exp(A), or cos(A); see [7, 44]. Our contour-bass based analysis extends naturally to this broader setting. Let (A) := Σ f )u,) denote the best rank-p approximation of (A). We obtain the following general perturbation bound.
Theorem 2.3 (Perturbation bounds for general functions). If |f S 6p. then
(A)) fĄ(A))l S O (max,er, [1f(
|
6p
where 11 is the rectangle with vertices (zo, T", (I1, T", (x1, -2), -T) with
zo = Ap
8 2 2 2\1; := 2A1-
The O()) notation hides a small universal constant (less than 4), which we have not attempted to optimize; see Section F for details. For example, let f(2) = 23, so that (A) and fp( correspond to the best rank-p approximations of A and A respectively. Since max,er, [[f(=)] < 64||A|3 Theorem 2.3 yields ||-43 A3ll O (I|-)13 || ||)))/))) This result applies to many important classes of functions c.g.. polynomials, exponentials, and trigonometric functions- and hence we expect it to be broadly useful. However, Theorem 2.3 does not apply to non-entire functions such as f(=) = z for non-integer c, where singularities obstruct the contour representation (1). In particular, when e 0, the expression (A) is no longer the best rank-p approximation to f(A). so the conclusion of Theorem 2.3 is not meaningful in that setting. We note that in a related work (36), the first two authors present an extension of the setting f(z) =1
-an
differentially private low-rank approximation. We now apply our spectral norm bound to analyze a standard differentially private (DP) mechanism for releasing low-rank approx- imation of a sensitive matrix A, commonly assumed to be a sample covariance matrix and hence PSD. Under (e, 8D [14], the Gaussian mechanism releases == A + E, where E is a symmetric matrix with i.i.d. Gaussian entries scaled to sensitivity A = =
Application:
A common post- processing step is to compute Ap. the best rank-p approximation of Á. Prior analyses [3, 15, 30] focused primarily on Frobenius norm or reconstruction error. For instance, [30] showed that under complex Wigner noise and moderate eigengap. ElIApp ApllF < >pu>p
up to lower-order terms.
6p

---

Since 1|Ap - AAll I 1|Ap Aplls, the above inequality implies expected spectral norm error of Ö (vmm pp 2.) In contrast, our bound yields the following bigh-probbbility spectral norm guarantee:
Corollary 2.4 (Application differential privacy). Let be PSD and E be a real or complex Wigner matrix. 6p 2 8.01vn, then with probubility - o(1), 1| - Apll S O( (.)
This follows directly from Theorem 2.1, using the fact that E = O(yn) with high probability for Wigner matrices [40, 43]. Compared [30], this result provides spectral norm (rather than Frobenius) guarantee, holds with high probability instead of in expectation, applies to both real and complex Wigner noise, removes the log!os log n factor, and eliminates restrictive assumptions such as X1 I 50 It also improves the dependence on p by a factor of vp, thereby resolving the open question posed in [30, Remark 5.3].
The spectral norm better captures subspace distortion, which is critical in applications like private PCA. Unlike Frobenius reconstruction error both of which may remain small even when Ap de- viates significantly from the true top-p eigenspace the spectral norm reflects worst-case directional error and is thus more reliable utility metric. This distinction is empirically validated in Figure 3. Moreover, Corollary 2.4 further yields high-probability Frobenius norm and reconstruction error bounds on the perturbation of low-rank approximations:
A ApllF S ( 2)), and 1| All || - All S <O(V 2n)
Finally, while Corollary 2.4 is stated for sub-Gaussian noise, Theorem 2.1 extends any symmetric perturbation satisfying the norm and gap conditions, including subsampled or quantized Gaussians and Laplace noise. We leave the detailed analysis of these settings future work.
Table 1: Summary table of perturbation bounds on A, AA for noise E.
Bound type
Norm
Noise model
Assumption
Extra factor vs |
EYM bound
High-probabiliity
Spectral
Real and Complex
None
+
Apt T
M. bound [29)
Expectation
Frobenius
GOF (real)
8. > VI
du vThe
M-V bound [30]
Expoctation
Frobenius
GUE (complex)
6. > 2|| A1 A1 n0
Thm. 2.1
high-probbbiiity
Spectral
Real and Complex
6p > 1|
Thm. 2.2
ligh probabiiiyy
Spectral
sub Gaussian
6 4|| rankA 6(1)
(1+ 111
"EYM" and "M-V" denote the Eckart-Young and [29, 30] bounds, respectively.
Alternative methods for approximating Ap. Hardt and Price [17, 18] proposed a random iterative method which, under the condition 6, >> Vol n. produces rank-k approximation A' of A, with
A p O()), satisfying the trade-off bound ||A' Appl Ō /n d maxisiso [|u:)lo)) [|u:ll/) where u, denotes the eigenvectors of A.
If at least one eigenvector u; is localized (i.e., maxigign || x 1/O(1)). this simplifies to
ò ( A1 In this regime, Theorem 2.1 achieves smaller bound by factor of Ó(Ai/Ap)-up (m)) and Ap @(vn). Furthermore, Theorem 2.2 provides an additional
v when improvement by factor of O (min| v 2 }). which can reach vn when Ô(1) and 8, @(vn) common regime in high-dimensional data.
If all eigenvectors u, delocalized (i.c., maxisign || O(1)/ the Hardt-Price bound reduces (())) Theorem 2.1 achieves comparable rate when ai O(n) and A, c6 O(yn), while Theorem 2.2 yields an improvement by a factor of \1/X, whenever r = Õ(1), i.e. when A is approximately low-rank.
5

---

3
Proof outline
In the preceding section, we stated our main results- Theorems 2.1, 2.2, and 2.3, Here, we first sketch the key ideas behind the proof of Theorem 2.1, then adapt the same framework, with minor refinements, to derive Theorems 2.2 and 2.3.
The proof of Theorem 2.1 proceeds in three main steps. First, using the contour method, we obtain the contour-based bound of our perturbation || - A,ll = F(z) == I Jr = A)- (z1 A) I]|dz. Here I' is a contour on the complex plane, isolating the p-leading eigenvalues of A and A. This contour step captures the A-E' interaction that the Eckart-Young Young-uungg-sa
bound omits (see Appendix A). Secondly, we develop the contour bootstrapping technique (Lemma 3.1), which under the gap assumption 4 Eلl I 8p. yields F(z) < 2F (z) with Fz) == Jr || - A) E(zl
Aldd) This technique (valid for any entire function f) replaces the traditional series expansions and the heavy analysis of the matrix-derivative operator (the limitation of the Mangoubi-Vishnnn approach 30), Appendix A) with computable quantity. Third, we construct bespoke contour one specifically tailored so that the top-p eigenvalues of A and À lie at prescribed distances from its sides. This precise alignment makes the integral defining Fi (z) both tractable and essentially optimal, yielding a tight perturbation bound.
Step 1: Representing fl (A) via the classical contour method. Let A1 2
An be the eigenvalues of with the corresponding cigenvectors {u. We now present the contour method to bound matrix perturbations in the spectral norm. Let I' be a contour in C that encloses λ1. .2.,2...... . and excludes Ap+1 Ap An- Let f be any entire function and recall fA(A) E (Ap)u,,u, Since f analytic on the whole plane C, the well-known contour integral representation [19, 26, 35] gives us:
1 2मi fr f())(=1 - A)
= fAAA).
Let λ₁ 2 .... Än denote the eigenvalue of Á with the corresponding eigenvectors ū1 ūg ug...... Un. The construction of I' (presented later) and the gap assumption 4/ Ea| < 6p ensure that the eigenval- ues À for 1 < < p lie inside r, while all N7 for j > remain outside. Then, similarly, we have I f())(1l - A)-'dz = E.= f(,)ū, == fA). Thus, we obtain the following contour
identity for the perturbation:
Sr Sr [+)]((]] - - íĄ( - Sx(A) = 2
Now we bound the perturbation by the corresponding integral
(lf fa(A))l s f [1f=))((1-AA - - (zI A) "IIldz F(f)..
(2)
This inequality makes the interaction of A and E explicit and is widely used in functional perturba- tion analysis, e.g., [19, 26, 28, 32, 33, 37J. However, obtaining a sharp bound on its right-hand side remains a formidable analytical challenge.
Step 2: Bounding F < 2.F via the contour bootstrapping method. Attempts control F(f), the right-hand side of (2), often use series expansion and analytical tools. By repeatedly applying the resolvent formula, one can expand f())[(2I - A) - (zl - A) into Em f()
A) AE - A) This yields the bound:
F,(J), where Fs(S) = + Jr [[ (F(=) 1) Idz).
One needs to estimate (f) for each s. For example, when f(z) = 1, [26, Part 2] bounds (1)
by O
Idal || fr minee(") 12 --) O ((IE")16,,)) where I' is union of vertical lines isolating (relevant for
{),, i E p}. yielding the Davis- Kahan bound O (11)))//6)). However, for f()) low-rank perturbations), this approach fails as |^| + Do. These estimates are highly nontrivial and rely on deep analytical techniques, making generalization arbitrary challenging.
Moreover, for f(z) 1, under certain conditions, the dominant term is Fi(S), i.e. F()) = O(Fi (f)); see, e.g., [22, 27, 32, 33, 37). In particular, using contour-bootsraapping technique, the authors in [37] proved F([(=) = 1) s (f(=) = 1). Inspired by this technique, we prove that F(f) < 2F) for any entire function

---

Lemma 3.1 (Contour bootstrapping for entire function f). f 2 21) then
F(f) S (f)()), where Fi(f) == 2x ([)=)(()))))===-->))))))())))))) -)- A)-1E(2I A)- ||
[dz].
Our contour bootstrapping argument is designed to prove Lemma 3.1. Our argument concise and novel, avoiding the need for series expansion and convergence analysis. In the context of standard low-rank approximations, where f(z) and fp(A) Ap- we write F(z) and Fi (2) instead of F(J) and (f) respectively.
Step 3: Construction of I, Fi (=)-estimattinn and proof completion of Thm. 2.1. Given Lemma 3.1, we now need to carefully choose the contour I' and estimate Fi (f). Constructing I' (so that the perturbation analysis via contour integration provides a sharp bound) is delicate; for example, the classical pick of two vertically parallel lines and any I placed too near any X can blow up Fi (z) to infinity. Indeed, we tailor I' w.r.t Fi()) as follows. First, we choose I' be rectangular as this simplifies integration. To control the factor (2I - A)- in the expression of (f(.). we need to ensure that the distance
A for any E r and E [n] are relatively large. Since separates Ap and Ap+1, this minimal distance min 2 - > cannot exceed ((6,). Thus, we simply
construct I through the midpoint 2g = A Finally, by setting the contour sufficiently high in the complex plane (while avoiding excessive height to prevent [f(=)] from diverging),
2
ensure that the primary contribution to the integral is from the vertical segments of r. This is because the distance X, is minimized on these segments. Note that, under the assumption 4|| < 6p. this construction ensures that the p-leading eigenvalues of and À are well aligned inside the contour.
Now, in particular, to prove Theorem 2.1, we will estimate
2 (2) Jr || A) -(=T
A)- |d2),
in which the contour r is set
to
be
a rectangle with vertices
(ro, T). (#1,T), (#1. -T), (zg: T), where Fy :=
Ap
6p 22 11 == 2 T := 2)j. Then,
we split I into four segments: P1 == { t)l - T < t <
T}; I2 = {(,,T) xo S x - x
T3 = (T 1 2 -T; T4 = (1 -T) 2 x 2 mo).
3
Xp+1
Xp
X
T4
Given the construction of I', we have 2T = Ebent My. where
M₁ := Jry. || - B''' - A) [dz].
Intuitively, set T, large (= A|] that the main term is the integral along I,, i.e., M,-
Indeed, factoring our E and using the fact that |z A₂1 2 1a Apl 6 +2 for all 1 < i S
and 2 E 11 = {T +)1 - T s t < T}, we have M1 - Sr, || min.e
| - |dz| S ||
LT Va dz dt. Directly compute the integral 1"
V /
15, 40 dl (see Section E.3), we obtain:
Mi S | O (ma/5,) O Ap)p))
By a similar manner, replace I; by F3 := ((11, t) - T st we have
M3 < E|| Jr, minge()
|=|
1 - dz) I E Jr, x++1" dt,
y /at+
where the last inequality follows the fact that min;e |2 A,a = |a - -1l (1) -m
V X +2 Directly compute the integral 1
v X/++2 dt (see Section E.3), we obtain:
Ms < | O =
Similarly, M2, M4 = OII ( Section E.2). These estimates on Mi, M2, M3. Ma imply F1(2) = O (IEE) 2x) which together with Lemma 3.1 proves Theorem 2.1.
7

---

Second upper bound of M1 and proof of Theorem 2.2. The key idea of the second bound a.u? =-xi Hence, M1 is rewritten as Proving the contour bootstrapping lemma (Lemma 3.1). The first observation is that using the
Aherman-Morrisee Woodbury formula M -MM+ (M N) NM [20] and the fact
Morisoo-Wooddury
that A+ + E, we obtain
(=l -=1- -
-)-
Using this, we can rewrite
F(f) 2x Je [ A) 1| |dz| as
2F Jr (1(=))221 A(= A)
A) [=( - A) - (zl - [d]
Using triangle inequality, we first see that F(f) is at most
fr 1 + fr [(llee -(1 !]||ds
2
2x
Next the key observation that the second term in the equation above can be rearranged and upper- bounded follows that the original perturbation appears again:
max er (2) - - æll
[[] - A) (=l - A)- |dz/.
2x
Thus, we have
F()) S (i( + maxzer [| A)- F(J).
(3)
Now we need our gap assumption that F|| 6p and the construction of T, which imply minger, 1z - Aa 2 5,/2 E|| Therefore, we have
maxzer [| - =|| & max:er (I(=T - A)- || minger,ee -- Aa
|
E
E
2
Together with (3), follows that F(f) S Fi(f) + 2 F(f.. Therefore, 1) S Fi(f, S). This proves Lemma 3.1.2
Remark 3.2. Using a similar strategy, one can prove that
2n Fi(f) S max [l]( 1 Sr - 1 - 1)|dl] s maxzer [If())]
2|
6y
see Appendix F. Together, this estimate and Lemma 3. prove Theorem 2.3.
is to replace (zT A)-1 by its spectral expansion Σ Sr, Eisissn (a-x,)(a-x.) u.ui Fuyu,] ||dz.
There are n² terms in the expression, and the direct use of the triangle inequality cannot provide good estimate. The next key trick is grouping up the r-top eigenvectors {u:)== Formally, M, is at most
Jr, ll Eisiose (=-xoĪ==X,) u T Eujuy |||dz| Sr, |I (=-1,)(2-2,5) ind Euju, [||da|
+ Sr. Eeery (=-x)(-X))) ind EujuJ111 |||dz|. Gr2)
To estimate the first term, we apply the triangle inequality. For each term, factor out components independent of and carefully evaluate the integral. Specifically, by the triangle inequality, the first term is at most
[u. Fu, Ilucc |1:12| (dz|- 1(2 (,) X,
Eigussr Sr. (1--x u.u, Euju, |||da| = EEssssr Jr.
Since maxigujr ! Fuyl S x. |u || = 1, and D1 = {=|2 Do + it, T S T).
the r.h.s.
is at most
Eiser x T V( A.) X,) 1, < Eijsr x S V( - 4(=
+
|20|=11
dt.
"The gap assumption 4 bلll < 6, and Weyl's inequality ensure that A is inside the contour I' if and only if
1 < i p.
8

---

By the construction of 11, we have |mo - x,1 2 2 for all E [n]. Thus, the r.h.s. is bounded by dt, which by direct computation (see Appendix E.1 for full details) is less than rax _- ( (+ (2) or equals
|solt|4|
,2x 2xza + 2 log 8
3T (x))) Ô (122z²
by
To estimate the second term, we apply matrix-norm inequalities to factor out E from the integral: Sr, Dij=r (=-x.i(= x,) tns! Eugu] [I|da]
Sr, |=| Emzisr --x 11 2- |||d]), which is most | Jr, min. lel - |dz
||
Ii and the definition of Iru - >,1 = 10pp + 2p+1)/2- Xel 2 1(Ap + Ap+1)/2 - Ar+1/ 2 A--Ar-1 2 Ap where the first inequality follows the fact i > r. Thus, the second term is at most
||||| [ min, 2:22 (20g (20- A. dt. Moreover, by the construction
1
|
V e (A,/aa di - (((E)));
see Section E. for the detailed estimation.
Similar to estimating the second term, the last term also O(I Combining the estimates on three parts of Mi, we obtain Mi s Ô ( || Consequently, by Lemma 3.1, finally have
(() ò (1 + r22 2xgg) as desired.
4 Empirical results
In this section, we empirically evaluate the sharpness of our spectral-gap bound (Theorem 2.1) in real-world settings central to privacy-preserving low-rank approximation. We compare: (1) the actual spectral error A| Apll. (2) our theoretical bound F| 2.- (3)
(3) and the classical Yokart-Young-Mirky (EYM) bound 2([] F|| + Ap-1). Each quantity computed over 100 trials and 20 noise levels. Because prior bounds [15, 29, 30] apply only to Gaussian noise and involve unspecified constants, we exclude them from this evaluation.
Setting. We study three covariance matrices A from the UCI Machine Learning Repository [13]: the 1990 US Census (n 69), the 1998 KDD-Cup network-intrusion data (n 416), and the Adult dataset (n = 6). These matrices henceefrth Census, KDD, and Adult- are standard benchmarks in DP PCA [3, 11, 29]. The low-rank parameter p is chosen so that the Frobenius norm of Ap contains > 99% of the Frobenius norm of A, giving p 10 for A Census, 2 for A = KDD, and p = for A Adult [29, Section BJ.
Each matrix is perturbed with either GOE noise En or Rademacher noise Eg scaled by twenty evenly spaced factors ranging from 0 1. Note that with high probability [41,43]] 43), F2 = |2
(2 + o(1) so the gap condition 4 Ex]l < 6p simplifies to 8yn < 6p- For Census (n = 69, 10), we have 8p 2 1433.99 > 8v69 69 R 66.45. For KDD (n 416,p = 2), we get 6p R 351.3 > 8/416 ~ 163.2. For Adult (n = 6. 4), we find 6, ~ 37.02 8v6 19.6.
Hence 4|| | < 6, holds in all tested configurations.
Evaluation. Each data matrix is preprocessed as follows: non nom-nue entries are replaced with 0; rows shorter than the maximum length are padded with zeros; each row scaled unit Euclidean norm; and each column is centered to have zero mean. We compute the covariance matrix A == M M, where M is the processed data matrix. For each configuration (A, Ex, p). we run 100 independent trials. In each trial, we perturb A with noise Es E [Ei, E2} to form À A + Ex. compute its best rank-p approximation Az. and measure the spectral error [ - Apll. We compare this with bound E&| Xp and the classical EYM bound 2[| E + 1)+1). Following standard practice, all reported values are averaged over 100 trials, with error bars shown for Actual Error and Our Bound (cap width 3pt).
'The O(-) in Theorem 2.1 hides small universal constant factor (< 7): see Section D.I for details.

---

Result and conclusion. Across all experiments the 69 x 69 US Census, the 416 X 416 KDD- Cup, and the 6 Adult matrix- bound closely matches the empirical error for both Gaussian and Rademacher noise (Figs. 1-2), consistently outperforming the classical EYM estimate. (Note: the error bars for Census and KDD) are too small to see.) Over all three benchmark datasets, two distinct noise models, and twenty escalation levels per model, our spectral-gap estimate never de- viates from the observed error by more than a single order of magnitude. This uniform tightness, achieved without any datasct-specific tuning, demonstrates that the bound of Theorem 2.1 is not merely sufficient but practically sharp across matrix sizes spanning two orders of magnitude and arivacy-motivatee perturbations spanning the entire operational range. Consequently, the bound can serve as a reliable, ooplication-agnosee error certificate for low-rank covariance approximation in both differential -erievccil-pivvacy pipelines and more general motri-matrix workflows.
Oaras Cannse Nouee
MDC Conuse Plaa
CoNtt Gesoer Nax
Figure From Left to Right: perturbation of the Census, KDD and Adult covariance matrices by Gaussian noise. Each panel plots the actual error, our bound, and the EYM bound; error bars indicate standard deviation over 100 trials.
Detan
Figure 2: Low-rank approximation errors under Rademacher perturbations. From left to right: the Census, KDD and Adult covariance matrices.
Conclusion and future work
We established new spectral norm perturbation bounds for low-rank approximations that explic- itly account for the interaction between a matrix A and its perturbation E. Our results extend the Eckart- YYung-Mirss theorem, improving upon prior Frobenius-nome norm-based analyses. A key tribution novel application the contour bootstrapping technique, which simplifies spectral perturbation arguments and enables refined estimates. Our bounds provide sharper guarantees for differentially private low-rank approximations with high probability spectral norm bounds that im- prove upon prior results. We also extended approach to general spectral functionals, broadening its applicability.
Several limitations and open questions remain. While spectral norm error bounds are standard and widely used in both theoretical and applied settings, can we extend our analysis to other structured metrics such as Schatten-p norm, the Ky Fan norm, subspace affinity norm? Can our bounds be further refined for matrices with specific spectral structures, such as polynomial or exponential de- cay? What be the threshold for the gap assumption that one still obtains meaningful bound beyond the Eckart-Youur Young-Mirsky theorem? Additionally, real-world noise often exhibits struc- tured dependencies
our techniques be adapted to handle sparse or correlated perturbations?
'For an empirical comparison between our new bound and the Eckart gap condition 4||| < 8p. see Section C.
Eckart-Young- Young -iig-kyikky bound beyond the
10

---

Acknowledgments
This work was funded in part by NSF Award CCF-2112665, Simons Foundation Award SFI-MPS- SFM-00006506, and NSF Grant AWD 0010308.
References
[1] Dimitris Achlioptas and Frank McSherry. Fast computation of low-rank matrix approxima- tions. Journal of the ACM (JACM), 54(2):9-es, 2007.
[2] U. Alon, N. Barkai, D. A. Notterman, K. Gish, S. Ybarra, D. Mack, and A. J. Levine. Broad patterns of gene expression revealed by clustering analysis tumor and normal colon tissues probed by oligonucleotide arrays. Proceedings of the National Academy of Sciences of the United States of America, 96(1 06(12):6745-6750, 1999.
[3] Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz, and Sergei Vassilvitskii. Differen- tially private covariance estimation. Advances in Neural Information Processing Systems, 32, 2019.
[4] Y. Azar, A. Flat, A. Karlin, F. McSherry, and J. Saia. Spectral analysis of data. In Proceedings of the thirty-third annual ACM symposium Theory of computing, pages 619-626, 2001.
[5] Zhidong Bai and Jack William Silverstein. Spectral analysis of large dimensional random matrices. Springer, 2009.
[6] James Bennett and Stan Lanning. The Netflix Prize. In Proceedings of KDD cup and workshop, volume 2007, page 35. New York, NY, USA., 2007.
[7] Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
[8] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson-LLindenstrauss transform itself preserves differential privacy. In 2012 IEEE 53rd Annual Symposium on Foun- dations of Computer Science, pages 410-419. IEEE, 2012.
[9] Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. In Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGAN symposium on Principles of database systems, pages 128-138, 2005.
[10] Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of data science, Cambridge University Press. 2020.
[11] Kamalika Chaudhuri, Anand Sarwate, and Kaushik Sinha. Near-optimal differentially private principal components. Advances in neural information processing systems, 25:989 9000999777000 2012.
[12] C. Davis and W. M. Kahan. The rotation of cigenvectors by perturbation. SIAM Journal on Numerical Analysis, 7:1-46, 1970.
[13] Dheeru Dua and Casey Graff. UCI machine learning repository. https://archive ics. uci. edu/ml, 2017.
[14] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensi- tivity in private data analysis. In Theory of cryptography conference, pages 265-2844 Springer, 2006.
[15] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Zhang. Analyze Gauss: Optimal bounds for annual ACM symposium on Theory of computing, pages 11-20, 2014.
principal component analysis. In Proceedings of the forty-sixth
[16] G. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psy- chometrika 1, pages 21 211-218, 1936.
[17] Moritz Hardt. Robust subspace iteration and privacy-preserving spectral analysis. In 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1624-1626. IEFF, 2013.

---

[18] Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications. Advances in neural information processing systems. 27, 2014.
[19] Nicholas Higham. Functions of Matrices: Theory and Computation. SIAM, 2008. See $1.3 and $7.6 for the Cauchy-Dunford integral.
[20] R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 2012.
[21] M. Ivanovs, R. Kadikis, and K. Ozols. Perturbation-based methods for explaining deep neural
networks: A survey, Pattern Recognition Letters, 150:228-2335 2021.
[22] M. Jirak and M. Wahl. Perturbation bounds for eigenspaces under a relative gap condition. Proceedings of the American Mathematical Sociery, 148(2):479-49) 2020.
[23] R. Kannan, H. Salmasian, and S. Vempala. The spectral method for general mixture models. SIAM Journal on Computing, (8(3):1141-133 2008
[24] R. Kannan and S. Vempala. Spectral algorithms. Foundations and Trends in Theoretical Computer Science, 4(3-4):157-288, 2009.
[25] Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In Proceedings of the twenly-forth annual ACM-SIAM symposium on Discrete algorithms, pages 1395-1414. SIAM, 2013.
[26] Tosio Kato. Perturbation Theory for Linear Operators. Classics in Mathematics. Springer, New York, NY, 1980.
[27] V. Koltchinskii and K. Lounici. Concentration inequalities and moment bounds for sample covariance operators. Bernoulli, 23:1 10-133, 2017.
[28] Vladimir Koltchinskii and Dong Xia. Perturbation of linear forms of singular vectors under Gaussian noise. In High Dimensional Probability VII: The Cargèse Volume, pages 397-423. Springer, 2016.
[29] Oren Mangoubi and Nisheeth Vishnoi. Re-analyze Gauss: Bounds for private matrix approxi- mation via Dyson Brownian motion. In Advances in Neural Information Processing Systems, volume 35, pages 38585-38599, 2022.
[30] Oren Mangoubi and Nisheeth K. Vishnoi. Private low-rank approximation for covariance ma- trices, Dyson Brownian Motion, and eigenvalue-gap bounds for Gaussian perturbations. J. ACM, 72(2), March 2025.
[31] Oren Mangoubi, Yikai Wu, Satyen Kale, Abhradeep Thakurta, and Nisheeth K Vishnoi. Private matrix approximation and geometry of unitary orbits. In Conference Learning Theory, pages 3547-3588. PMLR, 2022.
[32] Sean O' 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.
[33] Sean O'Rourke, Van Vu, and Ke Wang. Matrices with Gaussian noise: Optimal estimates for singular subspace perturbation. JEEE Transactions on Information Theory, 2023.
[34] Or Sheffet. Old techniques in differentially private linear regression. In Algorithmic Learning Theory, pages 789-827. PMLR, 2019.
[35] G. W. Stewart and Ji Guang Sun. Matrix Perturbation Theory. Academic Press, 1990. See Chap. III, $3.
[36] Phuc Tran and Nisheeth K. Vishnoi. Perturbation bounds for low-rank inverse approximations under noise. In Proceedings of the 39th Conference on Neural Information Processing Systems (NeurIPS 2025), 2025.
[37] Phuc Tran and Van Vu. Davis-Kahan theorem under a moderate gap condi- tion. Communications in Contemporary Mathematics, 2025. World Scientific, doi: 10.1 1011122/022911977550535
12

---

[38] Phuc Tran and Van Vu. New matrix perturbation bounds with relative norm: Perturbation of eigenspaces. ArXiv preprint: 2409.20207, 2026.
[39] Jalaj Upadhyay. The price privacy for low-rank factorization. Advances in Neural Informa- lion Processing Systems, 31, 2018.
[40] Ramon Van Handel. On the spectral norm of Gaussian random matrices. Transactions of the American Mathematical Society,
2017.
[41] Sabine Van Huffel and Joos Vandewalle. On the accuracy of total least squares and least squares techniques in the presence of errors on all data. Automatica, 25(5):665-76,, 1989.
[42] Roman Vershynin. High--imennsooaa probability: An introduction with applications data science, volume 47. Cambridge university press, 2018.
[43] Van Vu. Spectral norm of random matrices. Combinatorica, 27(6):721-736, 2007.
[44] Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[45] M.J. Wainwright. High-Dimensional Statistics: A Non-Asymplotic view point. Cambridge Series in Statistical and Probabilistic Mathematics, 2019.
[46] Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differ- entialgleichungen. Mathematische Annalen, 71(4):441-479, 1912.
13

---

Contents
Introduction
2 Main results
3 Proof outline
4 Empirical results
5 Conclusion and future work
10
A Limitations of prior approaches
15
Comparison error metries
16
Empirical evaluation beyond gap assumption
17
Extensions Theorem and Theorem 2.2 to the symmetric matrices
18
D.I Extension of Theorem 2.1 to the symmetric matrices
18
D.2 Extension of Theorem 2.2 to the symmetric matrices
20
Estimating integrals over segments
E.1 Estimating integrals over vertical segments for interaction-depeeddent bound
21
E.2 Estimating integrals over horizontal segments
24
E.3 Estimating integrals over vertical segments for non-interaction bound
24
F
Perturbation of matrix functionals Theorem 2.3
24
Some classical perturbation bounds
26
Notation
26
14

---

A Limitations of prior approaches
This section explains why existing perturbation methods fail to yield spectral norm bounds of the form || - Apll that incorporate interaction between and the perturbation E.
Eckart- Young- Mirssy:: lack of interaction sensitivity. Let 01 2 02 2 ... 2 on 2 0 denote the singular values of A. The Eckart- Eckart-Young Young-Mirsky theorem gives ||A - Apll 0p+1. and by the triangle inequality:
|| Apl = | Apll || All + J S 0p- | S 2 p+1 + ||B)),
where the final step uses Weyl's inequality [46]. While this bound is assumption-fret free, it is uninfor- mative in regimes where xp+1 || which are common in practice. The key limitation is that the triangle inequality treats A and independently, failing to capture how structure or spectral gaps in A might mitigate the effect of E.
Mangoubi-Vishnol Frobenius only, spectral norm intractable. els noise as a continuous-tin
The strategy of [29, 30] mod-
Brownian motion:
A(t) == +E = A+ B(t),
with cigen-decomposiition
A(t) = ((t)
(n))
where (()) [u)(()) and A (() 2 ... 2 An((). The rank-p approximation time /
(1 = (()) Diag (1), (1),), ",00000000000000000) T
The total perturbation is then expressed as an integral:
Åp Ap = S." dAp(().
Using properties of Dyson Brownian motion and Itô calculus, they derive a Frobenius norm identity:
E I dAp(t)
Σ
E Σ JimE
A -
+
Σ
A - X (A, (2)1)2 Jite
dt.
Bounding these expressions depends repulsion properties of the eigenvalues; for GOE matrices, Weyl's inequality suffices, while for GUE matrices, stronger gap estimates are used.
Although this method captures the spectral structure of A and interaction with E, it only yields Frobenius-norm bounds. Extending it to the spectral norm would require controlling
|| A Apll - 111, dAp(0)
which entails bounding the operator norm of the full stochastic process. This requires detailed control over the dynamics of (L) and X(I), including their correlations none of which are tractable with current techniques.
Moreover, for generalized functionals such (ī)) ff()]],, the problem becomes even harder: one must analyze l (A(())))), which involves matrix-valued analytic functions under random per- turbation, setting far beyond existing random matrix tools.
In contrast, our approach bypasses these limitations by using complex-analytie representation of spectral projectors that directly captures interaction between A and F,, yielding sharp spectral norm bounds under broad assumptions.
15

---

300
040 4.5
325 475
620
1.00
370 350
Figure 3: Comparison of error metries under Gaussian perturbation. Left: Synthetic PSD matrix with exponentially decaying spectrum (n 50, p = 5); Center: 1990 US Census covariance matrix (n 69, p = 5); Right: 1998 KDD-Cup covariance matrix (n 416, p 5). Each plot reports the spectral norm error ||4 Apll. Frobenius norm error I|-Ap Aplle: and change-in-
error || Apll || Apll as functions Gaussian noise level a. Error bars reflect standard deviation over 20 trials.
B Comparison of error metrics
This section studies three common metrics for low-rank approximation under perturbation the spectral-norm error A - Apll. the Frobenius-nomm error |A,, - ApplF, and the "change- Apll - ||4 - Apll
in-error" ||A
We compare these metrics both empirically (through Monte Carlo simulations) and thcoretically. Empirically, we examine how the metrics behave under Gaussian noise applied to both synthetic and real-world matrices (Figure 3). Theoretically, we analyze their interpretability and limitations, high- lighting that while Frobenius norms capture aggregate error and change-in-erve quantifies residual shifts, only the spectral norm controls worst-case subspace distortion.
simple x 2 example (Example B. further illustrates how residual-based measures can com- pletely mask subspace drift, underscoring the robustness and interpretability of the spectral norm for tasks such as private low-rank approximation.
Empirical comparison of utility metrics. We perform three Monte Carlo experiments under ad- ditive Gaussian perturbations. The first uses synthetic PSD matrix A E 500050 with exponentially decaying eigenvalues A = 0.8*, and sets = 5. The second and third use real-world covari- ance matrices derived from: the 1990 US Census dataset (n = 69), the 1998 KDD-Cup dataset (n 416).
All datasets drawn from the UCI Machine Learning Repository [13] and have been widely used in private matrix approximation and PCA [30, 29, 11].
In each setting, compute the best rank-p approximation Ap. perturb A with symmetric Gaussian noise of varying standard deviation a, and measure:
Spectral norm deviation: || Apll-
2. Frobenius norm deviation:
||4 Aplle,
3. Change-in-error: ||IAA 11l-A,1l
||A Apll
As shown in Figure Frobenius norm error grows fastest, reflecting total energy deviation. The change-in-error metric remains much smaller and, in the real-world cases, nearly flat, suggesting may fail to capture meaningful distortion. Notably, in the synthetic case (left), the spectral norm error closely tracks the change-in-error- desip their differing intent-whicl may result from near- alignment the top subspaces. However, such behavior is not guaranteed in general.
Theoretical distinction between utility metrics. Frobenius norm bounds of the form A Apll= S aggregate squared deviations across all directions, but may hide large emror in in-
16

---

dividual components, Spectral norm bounds || - Apll I directly constrain the worst-case deviation and are thus more reliable in sensitive applications such as differentially private PCA.
In contrast, residual-error metries such ||A Apll A Apll commonly used for their analytical convenience. However, they reflect only changes residual energy and are insensitive to subspace movement. In particular, this metric can be nearly zero even when the top-p eigenspaces have shifted significantly.
Given the spectral decompositions
Ap = Un Diag(A), App O, O).....)U Ap=U, Diag .,. .,77
the change-ing enrorror vanishes whenever UPU 2 Ug and Ap+1 is large. Such conditions are typical when noise E is small and S sr(A) = Ei=1 \1/A1- Moreover, standard perturbation results imply
|
1
IUU - -1, =
+
[33, 38).
Ap
8p
Example B.1 (Rank-1 rotation in R2?. Let
A (0
0 0):
1,
so that Ap = A. Define the rotated matrix
A= = Rg ARg where
Ro
cos 0
- -sin 0
sin
cos
Then Åp = Å, and although the top eigenspace has rotated by 0, the change-in-error is zero:
|| Apl = | Apll =.
Yet the true subspace drift is visible in:
|| Apll sin 0).
|| Appl = v2 sin 0).
This example highlights the limitations of residual- utility metries and illustrates why spectral norm deviation provides more reliable and interpretable signal of approximation quality under perturbation.
In summary, both our analysis and experiments support the use of the spectral norm the most informative and robust emror metric for evaluating private low-rank approximations. Unlike Frobe- nius and residual metrics, it captures the worst-case directional distortion and provides tighter connection to subspace stability.
C Empirical evaluation beyond gap assumption
In this section, empirically compare (1) the actual spectral error [| Apll. (2) our theoretical bound E|| 2 (3) and the classical BokkrrtYoung-Miisee (EYM) bound E[] + Ap+1) in the setting beyond the gap assumption that E|| < 6p.
Setup. We conducted simulation covariance matrix A with 2000, derived from the Alon colon-cancer microarray dataset [2]. The low-rank parameter is chosen so that the Frobenius norm of Ap contains 95% of the Frobenius norm of A, giving p with A, 46.29. We first computed oy. Gaussian noise was then added in the form E (O, In), with a chosen over 11 evenly spaced values such that
E
E {0.05, 0.10, 0.50J.
8,
For each a, we computed the following quantities:
the true error: || Apll.
the classical EYM bound: 2|I + apt1).
our bound: E||
> 6p
the ratios bound and our bound
classacal bound
17

---

Results. Table summarizes the results. The ratio our bound remains remarkably stable even beyond the regime 4|| < 6p (i.e,, ||E|| < 25),, and our bound outperforms the classical bound precisely when 4|| < 6p (i.e., Lell
6p
6p < 225.
Table 2: Comparison of bounds under increasing noise levels.
|
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40
0.45
0.50
our bound True error
90.17
88.27
87.02
89.83
89.44
87.81
88.39
89.29
87.08
87.26
our bound
0.20
0.40
0.60
0.79
0.98
1.17
1.36
1.53
1.70
1.88
classical hound
D Extensions of Theorem 2.1 and Theorem 2.2 to the symmetric matrices
In this section, extend Theorem 2.1 and Theorem 2.2 to the setting where A is a symmetric matrix. These extensions are naturally important since the data real-world applications is often arbitrary, making it natural for the eigenvalues of A to span both signs. While singular value de- composition (SVD) could be used to apply Theorem 2.1 or Theorem 2.2, singular value gaps are typically small. By working directly with eigenvalues,
exploit the fact that the eigenvalue gap
6%. A A is significantly large when dς- Ak+1 < 0.
D.1 Extension of Theorem 2.1 to the symmetric matrices
To simplify the presentation, we assume that the eigenvalues (singular values) are different, so the eigenvectors (singular vectors) are well-defined (up to signs). However, our results hold for matrices with multiple eigenvalues. Let A, E be the rank of approximation. Let As be the kth largest eigenvalue of A and uy be the corresponding orthonormal eigenvector. Let Ā == A + E. Let Ap: Ap denote the best rank-p approximations of
denote real symmetric matrices, and let 1 S
A and respectively. Define 1 $ I p such that the set of the top p singular values corresponds {A.(1)..... ) = {Ai,.... A > 0 2 (n-(p-k)+1...... ). In other words, the pth singular value of A is either Å (f,-(p-k) +) Let 8, == X A411. for [n 1]. Theorem 2.1 is extended to the following result.
Theorem D.1 (Extension of Theorem 2.1 to the symmetric matrices). If 4|| < min(ōr. 8n (n-(p-)) and 2/ E < op ppt1, then
| Ap 6|| log
6 du
+
Au
6. + log (n-(p- de
+
An- On- (x-
Note that when A is not PSD, (1A1h.-.,
1 (2- 15 may not correspond to the p
leading singular values of Á. This issue is resolved by enforcing the singular value gap condition
Op -pp11 ElI Indeed, by Weyl's inequality, given op Opt1 2| ElI, we have
d z A - | N op - ||l|| = Opt1 + |E|
2 (p= + 8 - ||||| 2 15n- l + 5 E|| > 1Âm An-(p-k)l-
here 8 Op -pt1. By similar argument, also have 15n- x)+1| det1. Therefore,
()m(1)) ) )m( = {Am 2 Ao 2 2 d > 0 7n- 2 >n-(p- 2... An.
want. Note that the gap condition of eigenvalues cannot guarantee this fact. For example, consider the following matrices
A /
0 28 28
(-2/T 22/7 0
then À (28
(288/
0
E
-2vn)
30
Here, clearly, S = (1), 5 {1} and [val is the largest singular value of A, but |r1 is not the largest singular value of À ()1 is still the largest eigenvalue).
18

---

Proof of Theorem D.1 Let S k S be natural number such that
(T((1)) ( Am()) = {11, ,.,.... AR > 02 An (p- 11 An Thus, we can split Ap as Ax + Bp-k. in which
Ant.
Bp-k= Em2-zn Aoury..
Similarly, Ap = A4 + Bp-k. Therefore,
|| | Ap1l As Bp-k A Bp Bp-b s $1 Ae
Bp- Bp-k
Applying the contour bootstrapping argument on
| - A with contour [ and on
|| B Bp-k with another contour r (we define these contours later), we obtain
- Az-Aull 12tt 1
2n Frm ||===l-
||| da|;
| - Bp-k < F( = 2x
1
SNee
- |dl
2
(4)
and hence,
| - A 2
2FFF1") [F| + FP!)
We set P(N and [[2] to be rectangles, whose vertices
TWu (oo, T), (a1, 7), (a1, -T), (ao, -T) with ag = 7== 05/22,11 20,, T 2211
and
T (bo: T), (b,, T), -b); (bo, - 7) with bo = An (n-(p- k)+1 + (p- b=:1= -201, T = 20
Now, going to bound P(!. First, split [(4] into four segments:
Pí == {(ao, f) - T < k
-2 == ((x,T) (ao $ x a1).
Ts == ( 2t -T}
14 = (Z),-))(ar 2 2 mo)
T2
Ti
T3
Ak+1
X
Re (2) 0
T
Therefore,
F(1 = Eim ||= A) A A)- |dz).
Notice that
A) -)=I-A) A) < E
min.eta 3
we further obtain
2T < ||| E Ni),
in which
Ni = Jr, min: o |d] for 1, 2, 3,4 We use the following lemmas, whose proofs are delayed to the next section.
19

---

Lemma D.2. Under the assumption of Theorem D.I,
N1 <
2
+ 4 log
37
Lemma D.3. Under the assumption of Theorem D.I.
N33 -
761 [0 -11l
+ 4 +log
01-A1
Lemma D.4. Under the assumption
of T'hhorem 1.1,
N2, N4 S
Since p < n, then + > n (p h) + and hence & (T,) It means
[AR+1] S Ap. Thus 0 S d0 I dε, and hence
N1 <
4 log
6
By the setting that 01 = =T==2 201
N2, N4 < T
221
22
N3 S
25 + log
37
2 + +llog
+ log
201 A1
Thus, using above estimates, obtain
P
2T
log
+ 2/2 + 20de An
+ log
604
2t
|
15 log
G.r
2mdu
(5)
2
6
82
< 3||
E||
Ga (log)
Ak
8,
Applying a similar argument on contour
[
obtain
F Pl S 3
E||
log
Go
Ae v012l
(6)
8n-(p-k)
Combining (4), (5) and (6), we complete our proof.
D.2 Extension of Theorem 2.2 to the symmetric matrices
Let A be symmetric matrix with eigenvalues A A2 ... 2 An. in which An is nec- essarily positive. Recall the setting from the previous section that 1 < k S is the positive integer such that the of the top p singular values is (>x())...., >
(AI,...,A) d > 0 - -,,]-- To extend Theorem 2.2, first generalize the definition of the halv- ing distance r and interaction term I as follows. Let F1, respectively be the smallest pos- itive integer satisfying 3
A X >rt+,, and DAn (v kiill < An-rz+1 fine the "halving distance" r = max(ri, r2]. Next, let Φ1 = maxigi.sn |u, Euyl and F2 == maxigiJ5rz [u Eun-st1l- Define the interaction parameter == xxx(x11.22)
(n-(p-))+1- De-
Theorem D.5 (Extension of Theorem 2.2 to the symmetric matrices). Assume that B|| < min(5 8n-(o-)) and E|| <op-
Optl. then
A Apl < 12 (| + +2x) (log Gez
+ log ( ))) 30/2 Au +
6a
on-to-
Proof of Theorem D.5 First, we still split (Ap, Ap) into (As, By As, By-k) and apply the
contour bootstrapping argument As Av By-k Bp- x
We also obtain
Åp - Ap S [r(11] + r1(3)
20

---

However, we will treat F/", F| bit differently, Indeed,
FT S Mi + | (N2 + No + Na),
in which
Mi = Sr, || ( A)- A) |=z Sr. Eisuisn (=-A.)(2- 2, uil, B ldz).
and
| N fr, min : x,,² |dz for I (2,3,4).
We additionally use the following lemma (its proof will be delayed in the next section).
Lemma D.6. Under the assumption of Theorem D.5,
Mi S x
2500 + 2 log
+ (20 4 (10) log
10mr
Ax
Together with the estimates for N2, No. N₂ from the previous section, we obtain
2T F/ [1]
S
Am 5x
+ 2 log
37 5w
+ (20 +
log
4m
E|
log
57 0%
+
|| (2V2+ + 2nr + 4 log 6)
2nds 6n
+ 2 log
Gar )
(20 + log 10
An
||
log
10e: 6N
+
2v 25 logg
E log
10a1 8x
log
Thus,
F|" < (IE)) log
1001 8n
+ x2 An
100z )) + fr2llog log
Similarly,
n 56 6 (IE)) log
Ao A
100 Jn On-(o--)
+ 22
2 log o (p-
100
(8)
(n-(o-
Therefore, combining (4), (7), and (8), we finally obtain
|| A 164-Ap/1 - 12
[ log
3607
+ r2 du
de + 22 An 10--0-11211 >²
bn-(p-
8 b66n-(p-
3607
E Estimating integrals over segments
In this section, we present in detail the integral estimations mentioned in the previous section: Lemma D.2, Lemma D.3, Lemma D.6 (integration vertical segments); and Lemma D.4 (in- tegration over horizontal segments). We first present technical lemma, which is used several times in the upcoming sections.
Lemma E.1. Let a, T be positive numbers such that S T. Then,
1 J dt <
Proof of Lemma E.1
We have
1 + = 2 マt
Barctan(T/a)
E.1 Estimating integrals over vertical segments for interaction-dependenl bound
In this Section, we now estimate M1 integral over the left vertical segment (prove Lemma D.6) and estimate N3- the integral over the right vertical segment (prove Lemma D.3). First, we estimate Mj as follows.
Using the spectral decomposition (=I (=T-A)-1- En
aaa X,)
we can rewrite Mj as
M1 = -r, Enzise (E- u. Euju, |dzl.
21

---

Define 21 = maxigi |u Euyl-
By the triangle inequality, M1 is at most
Jr, Eisissh (=-Aa](=-2,)) ini Fuguy
|al Sr. Enzison (s-x)((=x))) Unu! Enjuy |dzl
Sr, Eisney (ー-メ) und Eugu] 13112
_
|dz].
Consider the first term, by the triangle inequality, have
Sr, Eisuson (E-A))(= ins! Euguy [dz| S E Eiswssn Sr, (=->>i(=>))) un Eujuy ddz
Eisiss Jn "1 Rayl 11 1.12|
|dz|
12 (e)(=-)3)) A3)
S Eijsn 21 S"T V ((000) dt
Važte3
(since maxisi.jsn |n Euyl 1 T1 |/ || = 1, and r3 = f=|2= au + it, -T -T st
S Eisen 21 21STT ((ca--)))++(((oo>>)))++++-- dt.
|
By the construction of ,, we have
8% I00 112 2
for all isisn
(9)
Thus, the r.h.s. is most
rizu S 2 (6222
loul+||| dt = rsaı (I-r
lao (8. 23 dt + So #4166/23211
2t
(10)
By Lemma E.1, have
T
lool 22) di < 27|aol 2xag (since do 2 0).
The second integral is estimated by what follows.
21 7 /2/22
dt
+6)2 1du (u= f2 + (8x/2)²) [(6x/2)²
(T9+ (6L/2)²
log
(11)
log
4TT +62 6%
< 2 log 31'
Therefore,
Sr, E (z-x)](=x;) 23) i Euju {
|dz| S o
(2500 6x
2 log
3T
(12)
3x
Next, we bound the second term as follows
Jr: Σ m2ijer (2- (=-A)]==-0 A,J
unu Eujuy |dzl
24a = Jr. 1 Σ En z-
E Enzioo. 2- |dz
< Jr, |2|
u.u. x
x ||l||| x
Enzior -
[dz]
|| Sr. min 2- 2 d2z
| 1T minng
+0 (100
[, dl.
Moreover, by the construction of I2 and the definition rT.
lag Arl A++A 2/ 2
A 2Ar+1
b 1- da
(13)
2
22

---

where the second inequality follows the fact i > r1. Thus, the r.h.s. is at most
Vapte2 #4 de S |EIST
| f2
P (A+/11) dt.
got
Similar to (10) and (11), also have
S T (-
T #gtldl
dl
Araa Ak
+ log
(Ae//2)))
(Az/T)"
4000 A
+ log
22
(14)
%
$ + 2 2log
27'
(since ag S Az).
hk
follows that
Jn Enzison (F-x)(E-X,)44 ii Euju,
|dz| S |E'l| 4 + 2 2log
x )))
(15)
Now we consider the last term:
Sr, E Eisney (=-x) uau! Eugu] |dz| 2 Jr, minis-eelll-Al11-- |dz/.
|2|
13722
By (13) and (9), the r.h.s. is at most
1| T
v (6,, (6, 1100 )m11)a) dt -1| So (6e)) 1. dt
(16)
I <| lo" (1==+ (00- Ar41)3) dl.
anti
Moreover, fo'
(6x+ (12 (as Art1 }a) equals
of
S
andt 112+(0//29)1 A
((12(662/2)2) tao Ar 11)
andi
1 log
(12+160 (2) An++1)
((8+(66/22))((24 {m11)²)
(I"+ -ro0-11111) Ar+1) 1002/2
T+y T2+minn 22110)
(6 2) -ao 11)
Og max( Ant1J X log
+ 2 log
min(6e/2,00 (:000/00/.-11111
(T +(2+ A 12
Note that ao Art1 2 6k/2 and ag
Ar+1 + 5x/2 = A - Art1 2
d 2 aut!
Therefore, ap Art1
max (6./2,00 - \r+1} 2 dv We further obtain that 1o'
dl is at most
v 222) A1
6o X,/4
log
5T log
6,
+
27 8
< log
8x
(17)
The estimates (16) and (17) together imply that the last term is at most
18||
57
(18)
Combining (12), (15) and (18), we finally obtain that Mi is at most
2ndg de
+ 2 log
3T
+ |||
4T + log
2T dc
+
18
E|| log
57
0%
2 1 <
2mag
+ log
6.
)) + (20 + 4- / (o) 10)
E log
10m du
(since log
10mm
> log 10)
<
2
+ 2 log
6d:
)) (20 +
log
10oz
(19)
This proves Lemma D.6.
23

---

Next, we estimate N3. Notice that
N3- Sr, 1=1
dz)
di (since :3 {a 2 ai + +11, - -7 -TST)T))
(i) (a1 +4)
+af+
(41 - dt
|011 dt
14 p (ai A1 dt
(a1 A1)
ma
+ 2 log
+1)
(by Lemma E.1)
20
+ 4 log
37
A1
This proves Lemma D.3.
E.2 Estimating integrals over horizontal segments
We are going to bound N2, N4- integral over top horizontal segment (prove Lemma D.4). We have
N₂ Sr2 min;g[[] 2 1 da)
son minieta (12 ((=- dr (since T2 == {2| 2= x 17, au S x S a1))
+77+72
San 7
VēT dr (since x S a1 T)
-ool T
By similar arguments, also obtain
N4 < V2 ago
These estimates on N2, N4 prove Lemma D.4.
E.3 Estimating integrals over vertical segments for non-interaction bound
In this Section, we estimate Ni, proving Lemma D.2. The estimation of Ng follows the case of the interaction-dependent bound the end of Section E.1.
Ni
Sr. min,
T min.e (rs) (00 2. dt (since F1 == 22 ao + -T
+
/ +2
(++ (6x (2)/22 dt (by (9))
dt + [ 24 dt
J-T 7 (+2
2x00
+ 2 log
2T de
2
+1)
(by Lemma E.1)
6%
2x0a 6%
+ 4 4lg
3T
5x
This proves Lemma D.2.
F Perturbation of matrix functionals Theorem 2.3
In this section, we complete the delayed proof of Theorem 2.3. By Remark 3.2, to prove Theorem 2.3, we need to show that
|
2xt = -F
11|dz]
4m
8,
24

---

in which the contour I is set to be rectangle with vertices
(Io, T), (11, 7), (I1, -T), (xo, -T); where 20 = Ap 6p/2, = 2A1, = 2A1
We split I into four segments:
F1 (1z0, t)] - = (x, > m1);
T3 = ((x1. 2 (1= - == ((x, (c.-7) x 2 mo).
Therefore,
J (|=l--)- E -( |||dz |||dl Σ M
(20)
which
M4 = / A)-1- A) |||d for E (,,,,344)
By similar strategy from previous section, bound M₁ as follows. Notice that
((=-A)- A) < min; m]
E
Therefore, Mi is at most
1
||
12 2x |z]
min
S.. 12 2p1 |dz| (since Ap is closest I'1 among all eigenvalues of A)
||
['
|||||
dt (by definition Iı = {( t)] - sts and 100 Apl = 6p/2)
(6p/2)2 t2
2T 111
(by Lemma E.I).
8p
Next, we bound M3 as what follows.
M3 < || Sr, minsetm ==- 1 dz|
| 5 min:g|n] (1) (n] 4e2 dt (since I3s = f2|2 21 + -T
1
= | 5 2+(21 A1 dt
S [m] -xal
E||
(by Lemma E.
E|
(since F1 2A1)-
A1
Next, we estimate M2 as
M2 S Jr, minse 2, [2][dz = [E]lSr, minse 1= [dz].
Moreover, since T2 = {= | = x + 17, S Sx S 01}.
Sra minigta 22- 1, [dz] f
minueta ((x X, TT de S S + dr
|x
Therefore, M2 < | (x mpl
[
E Similarly, also obtain that [
M4
These
72
4x7
estimates on M1, M2, My, M4 and Equation 20 imply
[1(c1- - A E(zl - A) -)-'(|| = 2T
ET E
1
1
E
E
+ (T +
<
4T
6p
6p
The last inequality follows the trivial fact that X > 5p for any PSD matrix A. We complete the proof.
25

---

G Some classical perturbation bounds
This section recalls standard results referenced in Section 2, Section 3, and Section
Theorem G.1 YYckart-Young-Mirsky bound [16]). Let À TR and let Ap. A, denote their respective best rank-p approximations. Set == Á A. Then,
| - Apll - (a + |[]]),
where ppt1 the (p+ + 1)st singular value of A.
Theorem G.2 (Weyl's inequality [46]). Let A, E' E Rux= be symmetric, and define À == A E.
Then, for any S n
1 \ S |l
and 1o, oil s ||),
where Xo, di are the ith eigenvalues of A and Å, and o; o₁ are the corresponding singular values.
H
Notation
This section summarizes the key notations used throughout the paper. Let A, E be symmetric n x n matrices, and define the perturbed matrix := A + E. Let be an entire function, and let e N.
Table 3: Summary of notation
Symbol
Definition
Dimension of A, Á
P
Target rank parameter
Ap
rank p approximation
Ap
Best rank-p approximation of Á
A 2 ... An
Ligenvalues of A in descending order Eigenvalues of in descending order 2 ... An
2 ...
Singular values of A in descending order 8th eigengap:
É 1]
X Ai41 Eigenvector of correponning A;
for
i for E [n]
Eigenvector of Á corresponding A.
(T())
Stable rank: sr( || (p. 22)
Halving distance
Smallest integer such Ap/2 2 Ar+1 (p. Thm. 2.2)
Interaction term
maxisi.jr |u," Euyl (p. Thm.
Thm. 2.2)
(a(A)
fx(A) Ma))aa (p. 2.3)
(((A)
fo(A) E ((:))aa (p.4, 2.3.
P
Contour enclosing (AI...., ........., Ap (p:5)
F())
[1(()))(= -) -1 (=f A) 11l |d=] (p. Eq (2))
25
[I(())= - A) 'E
A) -) ()
F1()
| [[[(=)(=T - -A)- F(2] A)=1 ( 3.
F(s)
|=|[=T A) (21- A) "111 [2
2x
Fi(2)
||=[=] A) E(2l A) (p
2x
||-
Spectral
|| ][F
Frobenius norm
EYM bound
Eckart- Young-Mirsky bound
M. V hound
Mangoubi Vishnoi bound
PSD
Positive semi definite
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction state that the paper provides new high- probability spectral norm bounds for low-rank approximation under symmetric perturba- tions, resolving key limitations of classical worst-case bounds and prior DP utility analyses, and the body of the paper rigorously proves and empirically validates this claim (Sections 2 2-4).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Section 5 (Conclusion, Limitations, and Future Work) discusses the reliance on spectral quantities, the limitations of our results beyond the gap threshold, and the open questions of extending the framework to structured perturbations, including data matrices with specific spectral patterns or correlated noise.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
27

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Justification: All main theorems (e.g., Theorem 2.1) include clear assump- tions, and full proofs are provided in Sections 3, Appendix D, Appendix E, and Appendix F.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yss]
Justification: Section 4 details the matrices used, noise models, parameter settings, evalua- tion metrics, and empirical setup to enable reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., g.g in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
28

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The data (e.g., Census and 1998 KDD-Cup are publicly available and cited appropriately. Code and instructions are provided in the supplemental material.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://niis. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips.co.mc wttpccpppppccccccccccccccccccccc heoollic/guideee guwgeeee///eee /tt.ddddeeeeeeeueeeeeeeeee Cat////deeeeeiiiicccece ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ye]]
Justification: Section 4 and Section B describe matrix dimensions, truncation ranks, noise scales, trial counts, and the methods used compute bounds.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Ys]]
Justification: Section and Section B report error bars across 100 trials as mean standard deviation, with clear plots and captions.
Guidelines:
29

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments are lightweight and run on standard CPU machines; resource requirements are described in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: attpp:///eurrre http:////eursppeeeeeeeee cttpiiss.cppuuuu wwtppppcc//eeeeeeeeeeeeeeeeeeeet httpaa//eeeiieeciieeeeeeeeeeeee
Answer: [Yes]
Justification: The research is theoretical and empirical, uses only publicly available datasets, and conforms ethical standards.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
30

---

Justification:
This is theoretical paper on spectral norm perturbation bounds with no direct societal or ethical impact pathways.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release models or datasets with any risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All datasets (e.g., Census, 1998 KDD-Cup, Adult) are properly cited (e.g., [29], [11], [3]) and are in the public domain or released under open academic licenses.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
31

---

The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode thcode com/ dataseta has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper does not introduce new datasets, models, or other assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve any human subjects crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The research does not involve human subjects and thus does not require IRB approval.
Guidelines:
32

---

The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The research does not use LLMs for any component of the core methodology.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttts::/naet /ttpss////eeups/eeeeeeeeee htt.:////caeeeennnn////////1.1. for what should or should not be described.
33


Reviews:
[{"review_id": "THfuiR2iJ7", "reviewer": "Reviewer_DQsb", "summary": "This paper develops general perturbation bounds for spectral functions of a matrix. Specifically, for a matrix $A$, with eigenvalues and eigenvectors $\\{(\\lambda_i, u_i): i = 1,2, \\dots N\\}$, let $f_p(A)$ denote the matrix $\\sum_{i=1}^p f(\\lambda_i) u_i u_i^\\top$. The main result of the paper provides a general purpose bound on $|| f(A+E) - f(A)||$ in terms $||E||$, where $E$ denotes a perturbation in the matrix. \n\nAs a primary application of their result, the authors analyze the utility (as measured by the operator norm error between the privatized best rank-$p$ approximation and the actual best rank-$p$ approximation)  for the Gaussian mechanism in differentially private PCA, improving existing results.", "questions": "Questions and Comments:\n— I think the authors should discuss prior work on deriving perturbation bounds using the contour integral representation more prominently. Currently, those citations are easy to miss (in step 1 of the proof outline) and this sends the misleading impression that this technique is developed in this paper. It would be ideal to discuss these prior works as early as possible and in some detail.\n\n— Is it possible to state the bound in Theorem 2.3 with explicit constants? This would make the result user-friendly. Currently, it might not be very obvious to a reader what the constants hidden in the big-O notation depend on (without carefully reading the proof).\n\n— In the “Empirical Results” section the authors claim the bound $7 ||E|| \\cdot \\tfrac{\\lambda_p}{\\delta_p}$.  Where does the constant $7$ come from? (The results in the main paper are stated in big-O notation). \n\n— Does the bound apply to any submultiplicative norm, or is there something special about the operator norm? If the bound is general, it would be good to state it generally.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n— The paper is well-written and the authors have made a good effort to present their proofs in an accessible and systematic fashion.\n— The bound appears to be quite general, and could have many potential applications.  \n—The authors use a contour integral representation of spectral functions in terms of the resolvent to obtain their perturbation bound. This technique is well-known and classical in matrix perturbation theory. The primary contribution of this paper is to exploit this technique to develop a general-purpose bound which can be readily applied without a case-by-case analysis of the contour integral representation. To the best of my knowledge, I am not aware of a similar general purpose bound, so this contribution appears novel, although the contour integral technique is quite standard.\n\nWeaknesses:\n— The authors consider a single application of their bound, and moreover, the improvement in the application is not very significant (an operator norm bound rather than the Frobenius norm bound). Some additional applications could have improved the paper.", "was_revised": true, "final_justification": "This paper develops perturbation bounds for spectral functions of a matrix using a contour integral representation of spectral functions. The bounds are very general and can have many potential applications. Because of this reason, I think the paper definitely meets the bar of acceptance.\n\nDuring the discussion period, the authors addressed all of my suggestions, including stating the bounds with explicit constants so that it is easy to apply.", "rebuttal": "Thank you for your valuable comments and suggestions. We are glad that you appreciate our new bounds, the novelty of the contour bootstrapping argument, and the potential applications of our work. We address your specific questions and concerns below.\n### Questions:\n>Is it possible to state the bound in Theorem 2.3 with explicit constants?\n\nThank you for the question. The constant in Theorem 2.3 is 4. This value can be further optimized by examining the detailed computation in Appendix E. We will update Theorem 2.3 accordingly in the final version.\n\n>In the “Empirical Results” section, the authors claim the bound $7\\\\|E\\\\| \\lambda_p/\\delta_p$. Where does the constant 7 come from? \n\nWe appreciate the opportunity to clarify. \nThe constant $7$ comes from the exact r.h.s of Theorem 2.1, which is $6 \\\\|E\\\\| ( \\log (6\\frac{\\lambda_p}{\\delta_p}) + \\frac{\\lambda_p}{\\delta_p})$. Since the logarithmic term is negligible compared to $\\frac{\\lambda_p}{\\delta_p}$ in our real-world datasets (as considered in this section), we opted to simplify the bound by replacing the constant 6 with the slightly larger integer 7. \n\nWe will add this clarification in Section 4 of the final version.\n\n> Does the bound apply to any submultiplicative norm, or is there something special about the operator norm? \n\nThank you for the question. Our bound is specifically tailored to the operator norm, and does not directly extend to general submultiplicative norms.\n\nThe key step in estimating the term $F_1$ (see lines 247–265) crucially relies on properties that are specific to the operator norm. In particular, we use the identity:\n$$\n\\left\\\\| (zI - A)^{-1} \\right\\\\| = \\left\\\\| \\sum_{i=1}^n \\frac{u_i u_i^\\top}{z - \\lambda_i} \\right\\\\| \\leq \\max_{1 \\leq i \\leq n} \\frac{1}{|z - \\lambda_i|},\n$$\nand\n$$\n\\left\\\\| \\sum_{i > r} \\frac{u_i u_i^\\top}{z - \\lambda_i} \\right\\\\| \\leq \\max_{i > r} \\frac{1}{|z - \\lambda_i|},\n$$\nwhich are sharp in the operator norm but do not hold analogously for other submultiplicative norms such as the Frobenius norm or Schatten-$p$ norms.\n\nThat said, the contour bootstrapping framework itself can, in principle, be adapted to other norms. However, obtaining sharp analogues of our bounds in those settings would require new norm-specific estimates of resolvent decay and perturbation alignment. We view this as a promising direction for future work and will include a brief remark in the final version to clarify this scope.\n\n### Other comments:\n\n>The authors consider a single application of their bound, and moreover, the improvement in the application is not very significant (an operator norm bound rather than the Frobenius norm bound). Some additional applications could have improved the paper.\n\nThank you for the comment. While our method has broader applicability, we chose to focus on a single motivating application—differentially private PCA—to present the technique and its implications with greater clarity. We will consider highlighting potential extensions more explicitly in the revision.\n\n>I think the authors should discuss prior work on deriving perturbation bounds using the contour integral representation more prominently.  ... It would be ideal to discuss these prior works as early as possible and in some detail.\n\nThank you for these valuable comments. We fully acknowledge that the contour integral representation is a classical tool, widely used in prior work on functional perturbation analysis.\n\nOur contribution does not lie in introducing this technique, but in using it as the foundation for a novel and general-purpose bootstrapping strategy that applies broadly to spectral-norm perturbation bounds.\n\nWe will revise the introduction and related work sections to include a more prominent and timely discussion of classical uses of the contour method. In particular, we will clarify this distinction in Steps 1 and 2 of the “Outline of Proof.” To our knowledge, most prior applications of contour methods focus on eigenvalue or eigenspace perturbations (e.g., Davis–Kahan-type results), which differ from our setting of low-rank approximation under spectral norm."}, {"review_id": "if1yBcU8er", "reviewer": "Reviewer_aeeH", "summary": "The work provides new perturbation bounds for low rank approximations in the spectral norm, improving over classical results that follow from the Eckart-Young-Mirsky theorem. \n\nThe main feature of the bounds is that they are sensitive to the misalignment between the perturbation and the top singular vectors. This is important for applications in differential privacy, where the perturbation is typically Gaussian noise, and hence has small projection in the direction of any fixed eigenvector. The authors discuss the applications of their work to differentially private PCA.", "questions": "1. How do your results for DP-PCA compare to those you can achieve with the power method or other iterative methods?\n2. Do your proof techniques give results in the overparameterized regime, where we try to capture the top p eigenvectors with k > p dimensions?\n3. It would be interesting to see additional experiments on a larger datasets and in cases where the assumptions may not hold exactly.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper is well written and provides helpful discussion throughout. The main results are elegant and natural, providing interesting extensions to classical results from numerical analysis and matrix theory. The proof technique sounds intriguing. Apparently, the authors have a new technique that avoids some of the classical tools like Davis-Kahan expansions. This sounds great, although I did not have time to dig into the details.\n\nUsing the new perturbation bounds, the authors give some improvements for one particular way of achieving differentially private PCA: Add noise to the original matrix and compute a low rank approximation on top of the noisy matrix. Whereas most previous results applied only to Frobenius norm, the new results apply to spectral norm. I agree with the authors that this is the much more meaningful guarantee in realistic settings.\n\nNote, though, that this is just one way of achieving differentially private PCA. It's a well studied problem and there are numerous ways of doing it. \n\nThe authors claim that they give the first high probability bounds for differentially private PCA in the spectral norm. This is, however, not true. High probability bounds in the spectral norm already follow from the work by Hardt and Price (NeurIPS 2015) and Hardt and Roth (STOC 2013). Thos papers analyze noisy subspace iteration. The bounds are sensitive to the misalignment between the noise (gaussian) and the spectrum of the matrix. In addition, they give results for overparameterization: approximating rank p by rank k > p matrices. It's worth discussing these classical results. In which ways do the new tools give improvements over these results?\n\nIn particular, in the empirical results it would be good to compare to these methods.", "was_revised": true, "final_justification": "The authors have adequately answered my first question about the comparison with the noisy power method. The discussion convinced me me that the bounds are often significantly stronger than would follow from the noisy power method for the low-rank approximation objective. This gave me a better appreciation for the significance of the results, which is why I raised my score.", "rebuttal": "Thank you for your valuable comments and suggestions. We are glad that you appreciate our main results as natural and elegant improvements over classical bounds, and that you find our new contour bootstrapping technique of interest. We address your specific questions and concerns below.\n\n### Questions:\n> How do your results for DP-PCA compare to those you can achieve with the power method or other iterative methods?\n\n\nThank you for this important question. We appreciate the opportunity to clarify the comparison.\n\nSince Hardt and Price (NeurIPS 2015) is a refined and improved version of Hardt and Roth (STOC 2013), we focus on Theorem 1.4 and Corollary 4.3 from Hardt and Price.\n\nBoth their work and ours aim to construct an $(\\varepsilon, \\delta)$-differentially private matrix that approximates $A_p$. Their approach, the Noisy Power Method (NPM), produces a rank-$k$ approximation $A'$ with $k = p + \\Omega(p)$, serving as a private surrogate for $A_p$. Under the assumption $\\sigma_p - \\sigma_{p+1} > C \\sqrt{n} \\log n$ (for some constant $C$), they show that with high probability:\n\n$$\n\\\\|A' - A_p\\\\| = \\tilde{O} \\left( \\frac{\\sqrt{n \\log(1/\\delta)}}{\\varepsilon} \\cdot \\frac{\\sigma_1}{\\delta_p} \\cdot \\max_{1 \\leq i \\leq n} \\\\|u_i\\\\|_\\infty \\right).\n$$\n\nIn contrast, our algorithm directly perturbs $A$ and then computes a rank-$p$ approximation $\\tilde{A}_p$. We obtain the following high-probability bounds:\n\n- By Theorem 2.1 and Corollary 2.4:\n  $$\n  \\\\|\\tilde{A}_p - A_p\\\\| = O \\left( \\frac{\\sqrt{n \\log(1/\\delta)}}{\\varepsilon} \\cdot \\frac{\\sigma_p}{\\delta_p} \\right).\n  $$\n  \n- By Theorem 2.2:\n  $$\n  \\\\|\\tilde{A}_p - A_p\\\\| = \\tilde{O} \\left( \\frac{\\sqrt{n \\log(1/\\delta)}}{\\varepsilon} + \\frac{r^2 \\sigma_p}{\\delta_p} \\right),\n  $$\n  where $r \\geq p$ is the smallest index such that $\\sigma_r \\leq \\sigma_p / 2$.\n\nThese bounds highlight two performance regimes:\n\n- Our Theorem 2.1 and Corollary 2.4 offer improved trade-offs when at least one eigenvector $u_i$ is localized. In such cases, our gain factor can be up to $\\tilde{O}(\\sigma_1 / \\sigma_p)$ compared to NPM.\n\n- Our Theorem 2.2 is advantageous when $r^2 \\ll \\tilde O ( \\sqrt{n} \\cdot \\max_{i}  \\\\|u_i\\\\|_\\infty )$. \n\nThis occurs, for instance, when $A$ has low stable rank—i.e., $r = \\tilde O(1)$—since $\\max_{i} \\\\|u_i \\\\|_\\infty \\geq 1/\\sqrt{n}$.\n\nWe will include this comparison in the final version to clarify the trade-offs between the two approaches.\n\n\n\n\n>[Related comment] The authors claim that they give the first high probability bounds for differentially private PCA in the spectral norm. This is, however, not true. High probability bounds in the spectral norm already follow from the work by Hardt and Price (NeurIPS 2015) and Hardt and Roth (STOC 2013). \n\nAs noted above, prior work such as Hardt and Price (NeurIPS 2015) provides high-probability spectral norm bounds for iterative methods. We thank the reviewer for pointing this out and apologize for the oversight.\n\nOur contribution focuses on a different setting—adding noise directly to the data matrix—where, to our knowledge, our result gives the first such bound. We will qualify our claims accordingly and include proper citations and discussion in the final version.\n\n\n\n\n> Do your proof techniques give results in the overparameterized regime, where we try to capture the top $p$ eigenvectors with $k > p$ dimensions?\n \nThank you for the interesting question. Our proof techniques do not directly yield bounds on $\\\\|\\tilde{A}_k - A_p\\\\|$ for $k > p$.\n\nWhile it is possible to obtain a bound via the triangle inequality,\n$$\\\\|\\tilde{A}_k - A_p\\\\| \\leq \\\\|\\tilde{A}_k - \\tilde{A}_p\\\\| + \\\\|\\tilde{A}_p - A_p\\\\|,\n$$\nthis is not directly controlled by our main results. The limitation arises from the contour-integral argument, which is tailored to bounding $\\tilde{A}_p - A_p$ using a contour $\\Gamma$ that encloses only the eigenvalues $\\lambda_i$ and $\\tilde{\\lambda}_i$ for $1 \\leq i \\leq p$.\n\nWe view extending our framework to handle overparameterization as a promising direction for future work.\n\n ### Other comments:\n \n\n >It would be interesting to see additional experiments on a larger datasets and in cases where the assumptions may not hold exactly.\n\nThank you for the helpful suggestion. We agree that including examples and simulations illustrating behavior when the assumptions do not hold could strengthen the paper.\n\nIndeed, it is well known—and we have also observed—that the error $\\\\|\\tilde{A}_p - A_p\\\\|$ may blow up when $\\\\|E\\\\| > \\delta_p$. For instance, consider PSD matrices $A$ and $E$ with the following spectral decompositions:\n- $A = \\sum_{i=1}^n \\sigma_i u_i u_i^\\top$,\n- $E = \\sum_{i \\neq p+1} \\varepsilon u_i u_i^\\top + \\mu u_{p+1} u_{p+1}^\\top$,\n\nwhere $\\varepsilon > 0$ is a small constant and $\\mu > \\sigma_p - \\sigma_{p+1}$. In this case,\n$$\n\\\\|\\tilde A_p - A_p\\\\| = \\left\\\\| (\\mu + \\sigma_{p+1}) u_{p+1} u_{p+1}^\\top - \\sigma_p u_p u_p^\\top \\right\\\\| > \\sigma_p.\n$$\n\nFrom an empirical perspective, we also conducted a simulation on a larger dataset. We used a covariance matrix $A$ (with $n=2000$) derived from the Alon colon-cancer microarray dataset. We selected $p = 9$ such that $A_p$ captures 95% of $A$ in Frobenius norm, and $\\lambda_p \\approx 46.29$.\n\nThe simulation setup:\n- Compute $\\delta_p$.\n- Add Gaussian noise $E = \\alpha \\cdot \\mathcal{N}(0, I_n)$, where $\\alpha$ ranges over 11 evenly spaced values such that $\\\\|E\\\\| / \\delta_p \\in \\{0.05, 0.1, \\ldots, 0.5\\}$.\n- For each $\\alpha$, compute:\n  - true error: $\\|\\tilde{A}_p - A_p\\|$,\n  - classical bound: $2(\\\\|E\\\\| + \\sigma_{p+1})$,\n  - our bound: $7\\\\|E\\\\| \\cdot \\frac{\\lambda_p}{\\delta_p}$,\n  - and the ratios:\n    - $\\frac{\\text{our bound}}{\\text{true error}}$,\n    - $\\frac{\\text{our bound}}{\\text{classical bound}}$.\n\nThe results are summarized below:\n\n| $\\|E\\|/\\delta_p$                          | 0.05  | 0.10  | 0.15  | 0.20  | 0.25  | 0.30  | 0.35  | 0.40  | 0.45  | 0.50  |\n|:-----------------------------------------|------:|------:|------:|------:|------:|------:|------:|------:|------:|------:|\n| $\\frac{\\text{our bound}}{\\text{true error}}$     | 90.17 | 88.27 | 87.02 | 89.83 | 89.44 | 87.81 | 88.39 | 89.29 | 87.08 | 87.26 |\n| $\\frac{\\text{our bound}}{\\text{classical bound}}$| 0.20  | 0.40  | 0.60  | 0.79  | 0.98  | 1.17  | 1.36  | 1.53  | 1.70  | 1.88  |\n\nThese results are particularly interesting:  \n- The ratio $\\frac{\\text{our bound}}{\\text{true error}}$ remains stable even beyond the regime where $4\\\\|E\\\\| < \\delta_p$.  \n- Our bound outperforms the classical bound exactly when $4\\\\|E\\\\| < \\delta_p$.\n\nWe will consider including this example and simulation in the final version of the paper."}, {"review_id": "4gf5SgsWuP", "reviewer": "Reviewer_HKv5", "summary": "The paper studies rank-$k$ approximation under spectral norm. They give really great results and something that was definitely lacking in previous works.", "questions": "I have one quick question: can we use the techniques in this paper to also give high probability bound in COLT 2023 paper where the authors study the Frobenius norm metric? In my opinion, that was the weak point of the paper. I do not see that using Dyson Brownian motion based method can be used to get a high probability bound (having extensively thought on this problem since the NeurIPS 2022 paper came out).", "limitations": "None.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Beautiful paper and amazing result! \n\nI do not see any weakness in the paper. The writing is good. I am ready to champion the paper and do not have much to say. I would have accepted the paper just with one set of results (the bound on spectral norm error). I have thought about this problem for over three years, so I understand the limitations of previous approaches used when it comes to bound the spectral norm metric and get the high probability bound (instead of expected bound in the complex Dyson Brownian based analysis).\n\nThe weakness, if I can say, is that I was not able to read the proof, but I am looking forward to completely understanding the paper and engaging with the authors during the rebuttal phase with any questions I will have.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and suggestions. We are glad that you appreciate our results and are interested in a deeper understanding of our work. We answer your specific question below.\n### Questions:\n> Can we use the techniques in this paper to also give high probability bound in COLT 2023 paper where the authors study the Frobenius norm metric? In my opinion, that was the weak point of the paper.\n\nThank you for the question. Yes, our techniques can be used to obtain a high-probability bound in Frobenius norm.\n\nThe most direct approach is to use the inequality\n$$\n\\\\|\\tilde{A}_p - A_p\\\\|_F \\leq \\sqrt{2p} \\cdot \\\\|\\tilde{A}_p - A_p\\\\|,\n$$\nsince $\\tilde{A}_p - A_p$ has rank at most $2p$. Applying our spectral norm bound (Theorem 2.1 or Corollary 2.4), we obtain:\n$$\n\\\\|\\tilde{A}_p - A_p\\\\|_F \\leq O \\left( \\sqrt{p} \\cdot \\\\|E\\\\| \\cdot \\frac{\\lambda_p}{\\delta_p} \\right)\n= O\\left( \\sqrt{p n} \\cdot \\frac{\\lambda_p}{\\delta_p} \\right)\n$$\nwith high probability.\n\nAlternatively, one could revisit the contour bootstrapping argument and estimate $F_1$ directly in Frobenius norm. This may require additional technical refinements to preserve sharpness, but the framework extends naturally.\n\nWe will expand our discussion to include a comparison with the bounds presented in the COLT 2023 paper to clarify our improvements."}, {"review_id": "iQCjqoAF7Y", "reviewer": "Reviewer_oLme", "summary": "The paper presents the error bound (in terms of the spectral norm) for the rank-$p$ approximation of a symmetric matrix perturbed with a symmetric noise. The paper is written nicely with a clear motivation and description. The mathematical tools used to solve this hard problem namely contour bootstrapping are interesting in their own right and the authors seem to have found a novel application for this tool in this work. The simulation results also seem to highlight the utility of the derived bound when compared to classical baselines.", "questions": "Major comments:\n1. It is important to clarify the following: How different is the derived bound from that obtained by applying norm equivalence to the Frobenius error bound in https://arxiv.org/abs/2211.06418? Particularly, the $\\sqrt{p}$ improvement, as outlined in lines 119-123,  strongly suggests this.\n2. The results in Figures 1-2 should also consider the aforementioned bound from norm equivalence for comparison.\n3. Given that the result is presented with DP as the primary application, in light of the second weakness stated in the strength and weakness section, it is desirable to have an illustrative example showing where the condition $\\Vert E \\Vert \\leq \\delta_p/4$ would fail and where it will hold (especially with the increasing dimension $n$ for different values of DP parameters, $(\\epsilon,\\delta)$) along with an illustration on how $\\lambda_p$ and $\\lambda_{p+1}$ behave in such conditions.\n\nMinor comments:\n1. It has to be clearly indicated when the asymptotic bounds are probabilistic (e.g.,  $O_{\\texttt{p}}$ and $O_{\\texttt{p}}$) - please see https://arxiv.org/abs/2103.08721 and https://arxiv.org/abs/1108.3924.\n2. Provide a reference (e.g., \"High-Dimensional Statistics: A Non-Asymptotic View-point\" by M. J. Wainwright) for lines 151-154.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. The derived bound is tighter than the EYM bound and leverages the symmetry of data and noise matrices. Also, the presented bounds are high probability asymptotic bounds, which are preferable over the bounds on expectation. \n2. The paper adopts a new analytical approach, contour bootstrapping. \n\nWeaknesses:\n1. The paper highlights the importance of the spectral norm error bounds over the Frobenius norm error or reconstruction error. However, the spectral norm still does not present a complete picture. In my opinion, the more appropriate metric for the low-rank approximation problem would be the affinity between true and estimated subspaces (as defined in https://arxiv.org/abs/1301.2603) or, say, the Ky Fan norm.\n2. The technical assumption in line 66 for the bound to hold is too restrictive in DP since DP mechanisms usually add excessive noise that also scales with the dimension", "was_revised": true, "final_justification": "The authors have addressed all my comments/queries well. They have given a convincing reasons for the points which cannot be addressed easily. Further they have also provided an example in response to my question 3 which seems correct. Since I have already given a rating of 5, I continue to retain the rating and commend the authors on the excellent work and rebuttal", "rebuttal": "Thank you for your valuable comments and suggestions. We are glad that you appreciate our new high-probability bound and the novel contour bootstrapping technique. We answer your specific comments and suggestions below.\n### Comments:\n>The paper highlights the importance of the spectral norm error bounds over the Frobenius norm error or reconstruction error. However, the spectral norm still does not present a complete picture. In my opinion, the more appropriate metric for the low-rank approximation problem would be the affinity between true and estimated subspaces (as defined in https://arxiv.org/abs/1301.2603) or, say, the Ky Fan norm.\n\nThank you for the intriguing comment and for pointing us to this interesting work.\n\nWhile spectral norm error bounds are standard and widely used in both theoretical and applied settings, we agree that metrics such as subspace affinity and the Ky Fan norm offer complementary insights—particularly when evaluating subspace structure or alignment.\n\nExtending our framework to these metrics would require new technical ideas, especially to control perturbations of projection operators or spectral sums. We view this as an important direction for future work and will mention this in the final version.\n\n\n\n>The technical assumption in line 66 for the bound to hold is too restrictive in DP since DP mechanisms usually add excessive noise that also scales with the dimension. \n\nThank you for the comment. We acknowledge that the condition $4\\\\|E\\\\| < \\delta_p$ may be restrictive in some settings, and we believe future work may extend our results beyond this threshold—especially for matrices with favorable spectral structure.\n\nThat said, this type of gap condition has been widely adopted in the DP literature. For example, it appears in both theoretical and empirical work, including Dwork et al. (STOC 2014, Main Result 2) and Mangoubi–Vishnoi (JACM 2025, Remark 5.3). Mangoubi–Vishnoi (NeurIPS 2022, Appendix J) also provide empirical evidence that the condition holds on standard datasets such as Census and Adult—commonly used benchmarks in DP.\n\nWe will revise our presentation to clarify the applicability and limitations of this assumption.\n\n\n\n\n> It is important to clarify the following: How different is the derived bound from that obtained by applying norm equivalence to the Frobenius error bound in https://arxiv.org/abs/2211.06418? Particularly, the \\sqrt{p}- improvement, as outlined in lines 119-123, strongly suggests this.\n\nThank you for the helpful comment and the opportunity to clarify.\n\nSince the matrix $\\tilde{A}_p - A_p$ has rank at most $2p$, we have the standard inequality:\n$$\n\\\\|\\tilde{A}_p - A_p\\\\|_F \\leq \\sqrt{2p} \\cdot \\\\|\\tilde{A}_p - A_p\\\\|.\n$$\nThus, our spectral norm bound (Theorem 2.1) directly implies the Frobenius-norm bound in Mangoubi-Vishnoi [arXiv:2211.06418]:\n$$\n\\\\|\\tilde{A}_p - A_p\\\\|_F \\leq O\\left( \\sqrt{p} \\cdot \\\\|E\\\\| \\cdot \\frac{\\lambda_p}{\\delta_p} \\right)\n$$\nwith high probability.\n\nHowever, the reverse direction does not hold in general: one only has\n$$\n\\\\|\\tilde{A}_p - A_p\\\\| \\leq \\\\|\\tilde{A}_p - A_p\\\\|_F,\n$$\nso Frobenius-norm bounds alone do not yield spectral norm bounds. In particular, the result in [arXiv:2211.06418] only establishes an *expected* spectral norm bound of\n$$\n\\mathbb{E} \\\\|\\tilde{A}_p - A_p\\\\| \\leq \\tilde{O}\\left( \\sqrt{p} \\cdot \\\\|E\\\\| \\cdot \\frac{\\lambda_p}{\\delta_p} \\right),\n$$\nwhereas our result gives a high-probability spectral norm bound of\n$$\n\\\\|\\tilde{A}_p - A_p\\\\| \\leq O\\left( \\\\|E\\\\| \\cdot \\frac{\\lambda_p}{\\delta_p} \\right).\n$$\nWe will add this clarification to the final version of the paper.\n\n\n\n\n>The results in Figures 1-2 should also consider the aforementioned bound from norm equivalence for comparison.\n\nThank you for the valuable suggestion. Bounds derived via norm equivalence—such as Theorem 9 from Dwork et al. (STOC 2014) for reconstruction error and the Frobenius-norm bounds from Mangoubi–Vishnoi (JACM 2025)—are expressed using $O$ or $\\tilde{O}$ notation with unspecified constants. This makes it difficult to include them meaningfully in quantitative plots without making arbitrary choices.\n\nWe will add a remark explaining this in the final version.\n\n\n\n\n> Given that the result is presented with DP as the primary application, in light of the second weakness stated in the strength and weakness section, it is desirable to have an illustrative example showing where the condition $||E||< \\delta_p/4$  would fail and where it will hold (especially with the increasing dimension n  for different values of DP parameters, $(\\varepsilon, \\delta)$ ) along with an illustration on how $\\lambda_p$  and $\\lambda_{p+1}$  behave in such conditions.\n\nThank you for the thoughtful suggestion. We agree that including an example illustrating when the assumptions fail or hold would strengthen the paper, and we have indeed kept this threshold in mind throughout.\n\nThe phenomenon that $\\\\|\\tilde{A}_p - A_p\\\\|$ can blow up when $\\\\|E\\\\| > \\delta_p$ has been observed frequently. For a concrete example, consider PSD matrices $A$ and $E$ with spectral decompositions:\n- $A = \\sum_{i=1}^n \\sigma_i u_i u_i^\\top$,\n- $E = \\sum_{i \\neq p+1} \\varepsilon u_i u_i^\\top + \\mu u_{p+1} u_{p+1}^\\top$,\n\nwhere $\\sigma_1 > \\sigma_2 > \\cdots > \\sigma_n > 0$, $\\varepsilon > 0$ is small (e.g., $\\varepsilon < \\delta_i$ for all $1 \\leq i \\leq p$), and $\\mu > \\sigma_p - \\sigma_{p+1}$.\nIn this case, we have:\n$$\n\\\\|\\tilde A_p - A_p\\\\| = \\\\| (\\mu + \\sigma_{p+1}) u_{p+1} u_{p+1}^\\top - \\sigma_p u_p u_p^\\top \\\\| > \\sigma_p.\n$$\n\nIn the specific context of $(\\epsilon, \\delta)$-differential privacy, where $E \\sim \\mathcal{N}(0, \\sigma^2 I_n)$ with $\\sigma = \\frac{\\sqrt{\\log(1/\\delta)}}{\\epsilon}$, we can set, for instance:\n- $\\sigma_p - \\sigma_{p+1} = 4\\sqrt{n}$,\n- $\\delta = 1/10$, $\\epsilon = 1/2$.\n\nThen, with high probability, $\\\\|E\\\\| > \\delta_p / 4$, and the above construction implies $\\\\|\\tilde{A}_p - A_p\\\\| > \\sigma_p$.\n\nWe will include this example in the final version to illustrate the importance of the spectral gap condition and its relevance to practical DP settings.\n\n\n\n\n>It has to be clearly indicated when the asymptotic bounds are probabilistic (e.g., O_p and O_p ) - please see https://arxiv.org/abs/2103.08721 and https://arxiv.org/abs/1108.3924.\n\nThank you for the comment and suggestion. We will carefully review our use of $O$ and $\\tilde{O}$ throughout the paper and correct any inconsistencies. We will also include a brief clarification of our notation to distinguish high-probability bounds where appropriate.\n\n> Provide a reference (e.g., \"High-Dimensional Statistics: A Non-Asymptotic View-point\" by M. J. Wainwright) for lines 151-154.\n\nThank you for pointing us to this reference. We will include a citation to Wainwright’s book in the final version."}, {"review_id": "Ag0qLDSyyX", "reviewer": "Reviewer_swEV", "summary": "This paper studies how an additive noise matrix affects low-rank approximation. In particular, given a symmetric $n$-by-$n$ matrix $A$ and a symmetric noise matrix $E$, the goal is to bound $\\|(A+E)_p - A_p\\|$ for some norm $\\|\\cdot\\|$. (Given a symmetric matrix $M$, let $M_p$ denote its best rank-$p$ approximation.)\nPrevious works have studied error metrics such as the Frobenius norm $\\|(A+E)_p - A_p\\|_F$ and the change in reconstruction error $| \\|(A+E)_p - A\\| - \\|A_p - A\\| |$.\nThis paper studies the spectral norm error $\\|(A+E)_p - A_p\\|_2$, which is more suitable in certain cases. This is validated both theoretically and in experiments in the paper.\nThe main result of this paper is, assuming $A$ is PSD, if $\\|E\\| \\le (\\lambda_p - \\lambda_{p+1}) / 4$, then $\\| (A+E)_p - A_p \\| \\lesssim \\| E \\| \\cdot \\frac{\\lambda_p}{\\lambda_p - \\lambda_{p+1}}$, where $\\lambda_1 \\ge \\cdots \\ge \\lambda_n \\ge 0$ are the eigenvalues of $A$. (They also extend the result to general symmetric matrices. The bound is less clean than the PSD case.)\nTheir result is better than the Eckart–Young–Mirsky bound than a factor of $\\min\\{\\frac{\\lambda_{p+1}}{\\|E\\|}, \\frac{\\lambda_{p} - \\lambda_{p+1}}{\\|E\\|}\\}$, which is a meaningful improvement when $\\lambda_{p+1} \\gg \\|E\\|$ and $\\lambda_{p} - \\lambda_{p+1} \\gg \\|E\\|$.\nWhen translating the previous Frobenius norm bound by Mangoubi and Vishnoi to the spectral norm bound, it will be worse than the error bound in this paper by a factor of $\\sqrt{p}$. Moreover, the previous Frobenius norm bound by Mangoubi and Vishnoi only holds in expectation, while this paper obtains high probability bounds.\nOne important application of their main result is differentially private PCA. \nThis paper also gets two more results: a more fine-grained bound that takes into account a measure of spectral decay of $A$ and the alignment between the noise $E$ and the top eigenvectors of $A$; a perturbation bound for general matrix functions.\nThe authors prove these results by using a novel contour bootstrapping method from complex analysis and extends it to a broad class of spectral functionals, including polynomials and matrix exponentials.", "questions": "Why consider $\\|(A+E)_p - A_p\\|$ instead of $\\|(A+E)_p - A\\|$? It seems to me a more natural goal is to approximate $A$ instead of $A_p$. (Of course, $\\|(A+E)_p - A\\| \\le \\|(A+E)_p - A_p\\| + \\|A_p - A\\|$.)", "limitations": "no", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "I think the nice results obtained in this paper would be interesting at least for the filed of differential privacy and matrix perturbation theory. The spectral norm error bound is not only of interest itself, but also is more preferable in some applications. This paper is also very well-written. It motivates the spectral norm error bound well, presents a clear proof outline, and gives a good explanation of why previous techniques fail.", "was_revised": true, "final_justification": "The authors have addressed my questions and I keep my positive rating.", "rebuttal": "Thank you for your valuable comments and questions. We are glad that you find our new spectral norm bound and the contour bootstrapping technique both interesting and valuable for theoretical studies and applications. We answer your specific question below.\n### Questions:\n> Why consider $\\\\|(A+E)_p -A_p\\\\|$  instead of $\\\\|(A+E)_p -A\\\\|$ ? It seems to me a more natural goal is to approximate A  instead of $A_p$ . (Of course, $\\\\|(A+E)_p - A\\\\| < \\\\|(A+E)_p -A_p\\\\| + \\\\|A_p -A\\\\|$ .)\n\n\nThank you for this interesting question. We agree that in some contexts one might aim to approximate $A$ directly. However, in the setting of low-rank approximation, it is standard to treat $A_p$—the best rank-$p$ approximation to $A$—as the target.\n\nThis is because any rank-$p$ matrix, including $(A + E)_p$, must incur an irreducible error of $\\\\|A - A_p\\\\|$ when approximating $A$. That component is inherent to the low-rank constraint and cannot be improved. The quantity $\\\\| (A+E)_p - A_p \\\\|$ captures the *additional* error introduced by the perturbation $E$—and thus represents the part we can meaningfully analyze and minimize.\n\nMoreover, as you noted, the triangle inequality gives:\n$$\n\\\\| (A+E)_p - A \\\\| \\leq \\\\| (A+E)_p - A_p \\\\| + \\\\| A_p - A \\\\|,\n$$\nso bounding $\\\\| (A+E)_p - A_p \\\\|$ also gives insight into how well $(A+E)_p$ approximates $A$ overall.\n\nWe are happy to discuss this point further in the final version if clarification would be helpful."}]

Author rebuttal:

Meta-review: The paper introduce a new perturbation bounds for low rank approximations in the spectral norm, improving the Eckart-Young-Mirsky theorem. Then it presents a practical application to differentially private PCA.

From a technical perspective the paper is novel and interesting. More specifically, the authors have a new technique that avoids some of the classical tools like Davis-Kahan expansions in the proof of Eckart-Young-Mirsky theorem and do they are able to obtain tighter extensions to classical results from numerical analysis and matrix theory.

From a practical perspective, the authors shows how these new results can be applied to very practical problems as differentially private PCA.

From exposition perspective, the paper is very accessible and easy to read.

Overall, the reviewers appreciate the novelty and the strength of the new result and its applicability in differential privacy, overall the paper is strong and should be accepted.
Decision: Accept (oral)