Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy
Phuc Tran, Nisheeth K. Vishnoi, Van H. Vu · 2025
Read Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy by Phuc Tran, Nisheeth K. Vishnoi, Van H. Vu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-25670.txt.
Introduction
Phuc Tran, Nisheeth K Vishnoi, and Van H Vu bound spectral perturbations. Their 2025 paper studies low-rank approximation under noise. Noise effects on low-rank approximations are central in learning. Spectral norm captures worst-case directional error strongly. Differentially private approximation especially needs spectral guarantees. Preserving top form while ensuring privacy is goal.
Prior work often analyzes Frobenius norm instead. They establish high-probability spectral-norm perturbation bounds. Bounds refine the classic Eckart-Young-Mirsky theorem explicitly. Effects between matrix and perturbation are captured. Under eigengap and norm settings, values are sharp. Improvements reach up to square root of dimension factor. Differentially private PCA utility guarantees improve as use. An open problem in literature is resolved there. A novel contour bootstrapping method drives study. It extends to polynomials and matrix exponentials broadly. Empirical results track actual spectral error closely.
Catalog record
| CREATOR | Phuc Tran, Nisheeth K. Vishnoi, Van H. Vu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-25670
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy Phuc Tran, Nisheeth K. Vishnoi, Van H. Vu 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 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 A\in\mathbb{R}^{n\times n} and an arbitrary symmetric perturbation E E . Under mild eigengap and norm conditions, our bounds yield sharp estimates for ‖ ( A + E ) p − A p ‖ \|(A+E)_{p}-A_{p}\| , where A p A_{p} is the best rank- p p approximation of A A , with improvements of up to a factor of n \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. 1 Introduction Low-rank approximation is a foundational technique in machine learning, data science, and numerical linear algebra, with applications ranging from dimensionality reduction and clustering to recommendation systems and privacy-preserving data analysis achlioptas2007fast ; AFKMcS1 ; BS1 ; dwork2006calibrating ; IKO1 ; KSV1 ; KVbook ; vershynin2018high ; WW1 . A common setting involves a real symmetric matrix A\in\mathbb{R}^{n\times n} , such as a sample covariance matrix derived from high-dimensional data. Let \lambda_{1}\geq\cdots\geq\lambda_{n} denote the eigenvalues of A , with corresponding orthonormal eigenvectors u_{1},\ldots,u_{n} . The best rank- p approximation of A is denoted by A_{p}:=\sum_{i=1}^{p}\lambda_{i}u_{i}u_{i}^{\top} . This approximation solves the optimization problem A_{p}=\arg\min_{\text{rank}(B)\leq p}\|A-B\| , where the norm can be any unitarily invariant norm bhatia2013matrix ; blum2020foundations . In particular, A_{p} minimizes both the spectral norm \|\cdot\| , measuring worst-case error, and the Frobenius norm \|\cdot\|_{F} , measuring average deviation. In many applications, the matrix A is not directly available—it may be corrupted by noise, compressed for efficiency, or randomized to preserve privacy. A standard model introduces a symmetric perturbation E , yielding the observed matrix \tilde{A}:=A+E . The approximation \tilde{A}_{p} , computed from \tilde{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_{p} ? Understanding the deviation \|\tilde{A}_{p}-A_{p}\| is critical for ensuring the reliability and robustness of low-rank methods under noise. Motivating application: differential privacy. The stability under perturbations is especially important when the matrix A encodes sensitive information , such as user behavior or medical data. In such settings, even low-rank approximations of A can inadvertently leak private information bennett2007netflix . To address this risk, differential privacy (DP) dwork2006calibrating has become the standard framework for designing privacy-preserving algorithms. Several mechanisms have been developed to release private low-rank approximations while satisfying DP guarantees blocki2012johnson ; blum2005practical ; dwork2014analyze ; kapralov2013differentially ; DBM_Neurips ; mangoubi2022private ; sheffet2019old ; upadhyay2018price . A canonical method, introduced in dwork2014analyze , adds a symmetric noise matrix E with i.i.d. Gaussian entries to the input matrix A , yielding the perturbed matrix \tilde{A}=A+E . The algorithm then releases \tilde{A}_{p} as the privatized output. The utility of such mechanisms is typically assessed by comparing \tilde{A}_{p} to the ideal (non-private) approximation A_{p} . Two standard metrics are: (1) the Frobenius norm error \|\tilde{A}_{p}-A_{p}\|_{F} , and (2) the change in reconstruction error |\|A-A_{p}\|_{\star}-\|A-\tilde{A}_{p}\|_{\star}| , which measures how much the quality of low-rank approximation degrades due to noise, for a norm \|\cdot\|_{\star} amin2019differentially ; chaudhuri2012near ; dwork2014analyze ; DBM_Neurips . 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. 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 a factor of \sqrt{p} when the perturbation 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 C for concrete illustrations.) These limitations motivate the use of the spectral norm \|\tilde{A}_{p}-A_{p}\| , 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–Mirsky theorem bhatia2013matrix ; EY1 , states that \|\tilde{A}_{p}-A_{p}\|\leq 2(\lambda_{p+1}+\|E\|) , 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 DBM_Neurips ; MangoubiVJACM shows that when A is positive semidefinite and has a nontrivial eigengap \delta_{p}:=\lambda_{p}-\lambda_{p+1}\geq 4\|E\| , and when E is drawn from a complex Gaussian ensemble, one obtains: \mathbb{E}\|\tilde{A}_{p}-A_{p}\|_{F}=\tilde{O}(\sqrt{p}\cdot\|E\|\cdot\frac{\lambda_{p}}{\delta_{p}}) , which improves on the earlier reconstruction-error-based bounds of dwork2014analyze by a factor of \sqrt{p} . 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 ( DBM_Neurips , Remark 5.3) : Can one obtain high-probability spectral norm bounds for \|\tilde{A}_{p}-A_{p}\| under natural structural assumptions on A and realistic noise models? Our contributions. We resolve the open question posed in ( DBM_Neurips , 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 high-probability spectral norm bounds. Under the same eigengap condition as DBM_Neurips , \delta_{p}:=\lambda_{p}-\lambda_{p+1}\geq 4\|E\| , we prove \|\tilde{A}_{p}-A_{p}\|=O\!\left(\|E\|\cdot\frac{\lambda_{p}}{\delta_{p}}\right) and \|\tilde{A}_{p}-A_{p}\|=\tilde{O}\!\left(\|E\|+r^{2}x\cdot\frac{\lambda_{p}}{\delta_{p}}\right) , where r is the halving distance (a measure of spectral decay) and x:=\max_{i,j\leq r}|u_{i}^{\top}Eu_{j}| quantifies noise–eigenspace alignment (Theorems 2.1 – 2.2 ). In addition, our contour-based framework extends to a broader class of spectral functionals f(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 a high-probability spectral norm utility guarantee for differentially private PCA under sub-Gaussian noise, improving existing Frobenius-norm bounds by up to a factor of \sqrt{p} (Corollary 2.4 ). While prior work has achieved spectral norm guarantees in iterative or