# Perturbation Bounds for Low-Rank Inverse Approximations under Noise

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

## Key facts

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

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Deep Learning with Limited Numerical Precision](https://mlsanity.com/paper/1502.02551/) (2015)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [Practical sketching algorithms for low-rank matrix approximation](https://mlsanity.com/paper/1609.00048/) (2016)
- [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)
- [Low-Rank Updates of Matrix Square Roots](https://mlsanity.com/paper/2201.13156/) (2022)
- [A Preconditioned Iterative Interior Point Approach to the Conic Bundle Subproblem](https://mlsanity.com/paper/2110.11496/) (2021)

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

- [Improved Guarantees for Heterogeneous Treatment-Effect Estimation via Matrix Completion](https://mlsanity.com/paper/2605.30319/) (2026)

## Abstract (arXiv)

Low-rank pseudoinverses are widely used to approximate matrix inverses in scalable machine learning, optimization, and scientific computing. However, real-world matrices are often observed with noise, arising from sampling, sketching, and quantization. The spectral-norm robustness of low-rank inverse approximations remains poorly understood. We systematically study the spectral-norm error | (tildeA-1)p - Ap-1 | for an n× n symmetric matrix A, where Ap-1 denotes the best rank-(p) approximation of A-1, and tildeA = A + E is a noisy observation. Under mild assumptions on the noise, we derive sharp non-asymptotic perturbation bounds that reveal how the error scales with the eigengap, spectral decay, and noise alignment with low-curvature directions of A. Our analysis introduces a novel application of contour integral techniques to the non-entire function f(z) = 1/z, yielding bounds that improve over naive adaptations of classical full-inverse bounds by up to a factor of √n. Empirically, our bounds closely track the true perturbation error across a variety of real-world and synthetic matrices, while estimates based on classical results tend to significantly overpredict. These findings offer practical, spectrum-aware guarantees for low-rank inverse approximations in noisy computational environments.