Perturbation Bounds for Low-Rank Inverse Approximations under Noise Phuc Tran VinUniversity Nisheeth K. Vishnoi Yale University

Low-rank pseudoinverses are widely used to approximate matrix inverses in scalable machine learning, optimization, and scientific computing. However, realworld 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 ( A 1)p A 1p for an n n symmetric matrix A, where A 1p denotes the best rank-papproximation of A 1, and A = 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.