Research map / Learning theory and algorithms / Matrix and tensor methods
Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives high-probability spectral-norm perturbation bounds for top-p low-rank approximations of symmetric matrices under eigengap conditions, using a contour bootstrapping argument, and applies them to improve differentially private PCA utility guarantees.
Problem
How symmetric noise or DP perturbations affect the top-p low-rank approximation in spectral norm; prior bounds were in Frobenius norm, in expectation, or residual-based, and an open question asked for high-probability spectral bounds for DP-PCA.
Approach
A contour-integral representation of the rank-p spectral projector plus a "contour bootstrapping" lemma that bounds the perturbation by a single first-order resolvent term (F ≤ 2F_1) under the gap condition 4||E|| ≤ δ_p, yielding spectral bounds of order ||E||·λ_p/δ_p and an interaction-aware refinement, extended to general entire functions f(A).
Key results
- Proves ||Ã_p - A_p|| = O(||E||·λ_p/δ_p) with high probability under 4||E|| ≤ δ_p, improving on the Frobenius bound of Mangoubi-Vishnoi by a factor of sqrt(p) and giving sqrt(n) gains over Eckart-Young-Mirsky in some regimes.
- Corollary for DP-PCA with Wigner noise: spectral error O(sqrt(n)·λ_p/δ_p) with probability 1-o(1) when δ_p ≥ 8.01 sqrt(n).
- On Census, KDD, and Adult covariance matrices, the bound 7||E||λ_p/δ_p stays within roughly one order of magnitude of actual spectral error (ratio around 88 in the beyond-gap Alon experiment, stable across noise levels).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the spectral-gap bound instead of the classical EYM bound | Low-rank approximation under Gaussian perturbation · Alon colon-cancer | bound tightness (our bound / classical bound): 0.20 to 0.98 for ||E||/δ_p = 0.05 to 0.25 | Helped |
| Use the spectral-gap bound beyond the condition 4||E|| < δ_p | Low-rank approximation under Gaussian perturbation · Alon colon-cancer | bound tightness (our bound / classical bound): 1.17 to 1.88 for ||E||/δ_p = 0.30 to 0.50 | Hurt |
| Use the spectral-gap bound across increasing noise levels | Low-rank approximation under Gaussian perturbation · Alon colon-cancer | our bound / true error: 90.17; 88.27; 87.02; 89.83; 89.44; 87.81; 88.39; 89.29; 87.08; 87.26 | No clear effect |
| Add the interaction-aware term to the basic eigengap bound | Low-rank approximation under symmetric perturbation · Matrices with small noise–eigenspace interaction | spectral error bound: up to a √n-factor improvement | Helped |
| Use the proposed high-probability spectral-norm guarantee instead of prior Frobenius-norm bounds | Differentially private PCA · Wigner noise | dependence on p: √p | Helped |
Surprising findings
- The Frobenius norm can overstate noise impact by sqrt(p), while residual-based change-in-error can be zero even when the top-p subspace rotates substantially.
- In the beyond-gap experiment, the bound-to-true-error ratio stayed roughly constant (~87-90) even past the 4||E|| < δ_p assumption, while the classical EYM bound was tighter beyond that regime.
Limitations
- Main results require the eigengap condition 4||E|| ≤ δ_p and mostly assume PSD A; the symmetric extension needs singular-value gap conditions.
- Empirical 'sharpness' is only up to an order of magnitude (bound ratio around 88 in the beyond-gap experiment), and the bound uses unoptimized constants.
- Sub-Gaussian noise is the stated corollary setting; extension to other noise such as Laplace or subsampled Gaussians is left to future work.
Experimental setup
Datasets: 1990 US Census (UCI) 1998 KDD-Cup (UCI) UCI Adult Alon colon-cancer microarray
Benchmarks: Census covariance matrix KDD-Cup covariance matrix Adult covariance matrix Alon colon-cancer covariance matrix
Metrics: spectral norm error bound tightness ratio Frobenius norm error
Baselines: Eckart-Young-Mirsky bound Mangoubi-Vishnoi bound Hardt-Price iterative method
Builds on: Eckart-Young-Mirsky theorem Mangoubi-Vishnoi Frobenius bounds Davis-Kahan theorem Weyl's inequality
Closest papers by meaning
- Perturbation Bounds for Low-Rank Inverse Approximations under Noise (NeurIPS 2025 · similarity 0.93)
- Entrywise error bounds for low-rank approximations of kernel matrices (NeurIPS 2024 · similarity 0.90)
- Coherence-free Entrywise Estimation of Eigenvectors in Low-rank Signal-plus-noise Matrix Models (NeurIPS 2024 · similarity 0.87)
- An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise (NeurIPS 2025 · similarity 0.86)
- Singular Subspace Perturbation Bounds via Rectangular Random Matrix Diffusions (ICLR 2025 · similarity 0.86)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.