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

arXiv: https://arxiv.org/abs/2510.25670 · HTML: https://mlsanity.com/paper/2510.25670/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 45 references that are in the map.
- First posted on arXiv 29 Oct 2025.

## Builds on (most cited first, 5 of 5)

- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion](https://mlsanity.com/paper/2211.06418/) (2022)
- [Matrices with Gaussian noise: optimal estimates for singular subspace perturbation](https://mlsanity.com/paper/1803.00679/) (2018)
- [Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations](https://mlsanity.com/paper/2502.07657/) (2025)
- [Private Matrix Approximation and Geometry of Unitary Orbits](https://mlsanity.com/paper/2207.02794/) (2022)

## Built on by (most cited first, 3 of 3)

- [Adaptive Power Iteration Method for Differentially Private PCA](https://mlsanity.com/paper/2602.11454/) (2026)
- [Expectation Error Bounds for Transfer Learning in Linear Regression and Linear Neural Networks](https://mlsanity.com/paper/2603.28739/) (2026)
- [Stochastic Rounding Increases Small Singular Values](https://mlsanity.com/paper/2606.00312/) (2026)

## Abstract (arXiv)

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 ∈ ℝn × n and an arbitrary symmetric perturbation E. Under mild eigengap and norm conditions, our bounds yield sharp estimates for |(A + E)p - Ap|, where Ap is the best rank-p approximation of A, with improvements of up to a factor of √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.