Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy

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.

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\\| < \\|(A+E)_p -A_p\\| + \\|A_p -A\\|$ .)

Thank 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.

This 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.

Moreover, as you noted, the triangle inequality gives:

so bounding $\\| (A+E)_p - A_p \\|$ also gives insight into how well $(A+E)_p$ approximates $A$ overall.

We are happy to discuss this point further in the final version if clarification would be helpful.

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.

Comments:

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.

Thank you for the intriguing comment and for pointing us to this interesting work.

While 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.

Extending 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.

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.

Thank 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.

That 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.

We will revise our presentation to clarify the applicability and limitations of this assumption.

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.

Thank you for the helpful comment and the opportunity to clarify.

Since the matrix $\tilde{A}_p - A_p$ has rank at most $2p$, we have the standard inequality:

Thus, our spectral norm bound (Theorem 2.1) directly implies the Frobenius-norm bound in Mangoubi-Vishnoi [arXiv:2211.06418]:

with high probability.

However, the reverse direction does not hold in general: one only has

so 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

whereas our result gives a high-probability spectral norm bound of

We will add this clarification to the final version of the paper.

The results in Figures 1-2 should also consider the aforementioned bound from norm equivalence for comparison.

Thank 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.

We will add a remark explaining this in the final version.

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.

Thank 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.

The 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:

• $A = \sum_{i=1}^n \sigma_i u_i u_i^\top$,
• $E = \sum_{i \neq p+1} \varepsilon u_i u_i^\top + \mu u_{p+1} u_{p+1}^\top$,

where $\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}$. In this case, we have:

In 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:

• $\sigma_p - \sigma_{p+1} = 4\sqrt{n}$,
• $\delta = 1/10$, $\epsilon = 1/2$.

Then, with high probability, $\\|E\\| > \delta_p / 4$, and the above construction implies $\\|\tilde{A}_p - A_p\\| > \sigma_p$.

We will include this example in the final version to illustrate the importance of the spectral gap condition and its relevance to practical DP settings.

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.

Thank 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.

Provide a reference (e.g., "High-Dimensional Statistics: A Non-Asymptotic View-point" by M. J. Wainwright) for lines 151-154.

Thank you for pointing us to this reference. We will include a citation to Wainwright’s book in the final version.

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.

Questions:

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.

Thank you for the question. Yes, our techniques can be used to obtain a high-probability bound in Frobenius norm.

The most direct approach is to use the inequality

since $\tilde{A}_p - A_p$ has rank at most $2p$. Applying our spectral norm bound (Theorem 2.1 or Corollary 2.4), we obtain:

with high probability.

Alternatively, 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.

We will expand our discussion to include a comparison with the bounds presented in the COLT 2023 paper to clarify our improvements.

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.

Questions:

How do your results for DP-PCA compare to those you can achieve with the power method or other iterative methods?

Thank you for this important question. We appreciate the opportunity to clarify the comparison.

Since 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.

Both 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:

In contrast, our algorithm directly perturbs $A$ and then computes a rank-$p$ approximation $\tilde{A}_p$. We obtain the following high-probability bounds:

• By Theorem 2.1 and Corollary 2.4:

  $$\\|\tilde{A}_p - A_p\\| = O \left( \frac{\sqrt{n \log(1/\delta)}}{\varepsilon} \cdot \frac{\sigma_p}{\delta_p} \right).$$

• By Theorem 2.2:

  $$\\|\tilde{A}_p - A_p\\| = \tilde{O} \left( \frac{\sqrt{n \log(1/\delta)}}{\varepsilon} + \frac{r^2 \sigma_p}{\delta_p} \right),$$

  where $r \geq p$ is the smallest index such that $\sigma_r \leq \sigma_p / 2$.

These bounds highlight two performance regimes:

• 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.

• Our Theorem 2.2 is advantageous when $r^2 \ll \tilde O ( \sqrt{n} \cdot \max_{i} \\|u_i\\|_\infty )$.

This 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}$.

We will include this comparison in the final version to clarify the trade-offs between the two approaches.

[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).

As 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.

Our 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.

Do your proof techniques give results in the overparameterized regime, where we try to capture the top $p$ eigenvectors with $k > p$ dimensions?

Thank you for the interesting question. Our proof techniques do not directly yield bounds on $\\|\tilde{A}_k - A_p\\|$ for $k > p$.

While it is possible to obtain a bound via the triangle inequality,

this 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$.

We view extending our framework to handle overparameterization as a promising direction for future work.

Other comments:

It would be interesting to see additional experiments on a larger datasets and in cases where the assumptions may not hold exactly.

Thank you for the helpful suggestion. We agree that including examples and simulations illustrating behavior when the assumptions do not hold could strengthen the paper.

Indeed, 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:

• $A = \sum_{i=1}^n \sigma_i u_i u_i^\top$,
• $E = \sum_{i \neq p+1} \varepsilon u_i u_i^\top + \mu u_{p+1} u_{p+1}^\top$,

where $\varepsilon > 0$ is a small constant and $\mu > \sigma_p - \sigma_{p+1}$. In this case,

From 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$.

The simulation setup:

• Compute $\delta_p$.
• 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\}$.
• For each $\alpha$, compute:
  • true error: $\|\tilde{A}_p - A_p\|$,
  • classical bound: $2(\\|E\\| + \sigma_{p+1})$,
  • our bound: $7\\|E\\| \cdot \frac{\lambda_p}{\delta_p}$,
  • and the ratios:
    • $\frac{\text{our bound}}{\text{true error}}$,
    • $\frac{\text{our bound}}{\text{classical bound}}$.

The results are summarized below:

These results are particularly interesting:

• The ratio $\frac{\text{our bound}}{\text{true error}}$ remains stable even beyond the regime where $4\\|E\\| < \delta_p$.
• Our bound outperforms the classical bound exactly when $4\\|E\\| < \delta_p$.

We will consider including this example and simulation in the final version of the paper.

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.

Questions:

Is it possible to state the bound in Theorem 2.3 with explicit constants?

Thank 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.

In the “Empirical Results” section, the authors claim the bound $7\\|E\\| \lambda_p/\delta_p$. Where does the constant 7 come from?

We appreciate the opportunity to clarify. The 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.

We will add this clarification in Section 4 of the final version.

Does the bound apply to any submultiplicative norm, or is there something special about the operator norm?

Thank you for the question. Our bound is specifically tailored to the operator norm, and does not directly extend to general submultiplicative norms.

The 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:

and

which are sharp in the operator norm but do not hold analogously for other submultiplicative norms such as the Frobenius norm or Schatten-$p$ norms.

That 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.

Other comments:

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.

Thank 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.

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.

Thank 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.

Our 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.

We 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.