Perturbation Bounds for Low-Rank Inverse Approximations under Noise

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.