Research map / Learning theory and algorithms / Matrix and tensor methods
Perturbation Bounds for Low-Rank Inverse Approximations under Noise
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives non-asymptotic spectral-norm bounds on the error between rank-p truncated inverses of a symmetric matrix A and its noisy version A+E, using contour bootstrapping for the non-entire function 1/z.
Problem
How robust is the best rank-p pseudoinverse of a symmetric (PD) matrix to additive symmetric noise, measured as the spectral-norm error between truncated inverses of A and A+E?
Approach
Applies contour integral representation with a bootstrapping lemma (F <= 2F_1) to the non-entire function f(z)=1/z, using a tailored rectangular contour, yielding bounds in terms of eigengap delta_{n-p}, lambda_n and lambda_{n-p} that improve on classical Neumann+Eckart-Young-Mirsky bounds.
Key results
- Proposed bound 4||E||/lambda_n^2 + 5||E||/(lambda_{n-p} delta_{n-p}) tracks the empirical error with bound/error ratio below 10 across all tested configurations.
- EYM-N bound is typically 1.3x to over 1000x looser than the proposed bound depending on C_A (e.g., ratio 1334 for Hamiltonian n=500 at smallest noise).
- Empirical error is consistently about 0.3-0.4 times the proposed bound across Census, BCSSTK09, and Hamiltonian experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the spectrum-adaptive contour-bootstrapped bound instead of the EYM--N estimate | Low-rank inverse perturbation bounds · Census, BCSSTK09, and Discretized Hamiltonian under Gaussian and Rademacher noise | bound tightness relative to empirical error: EYM--N bound / proposed bound exceeds 1 across all C_A; empirical error / proposed bound remains around 0.3-0.4 | Helped |
| Use the proposed bound rather than the EYM--N bound for Discretized Hamiltonian n=500 at C_A=10^{-4.00} with Gaussian noise | Low-rank inverse perturbation bounds · Discretized Hamiltonian n=500, Gaussian noise | bound magnitude relative to proposed bound: 1334 | Helped |
| Use the proposed bound rather than the EYM--N bound for BCSSTK09 under Gaussian noise | Low-rank inverse perturbation bounds · BCSSTK09, Gaussian noise | bound magnitude relative to proposed bound: 3.23 | Helped |
| Apply the proposed bound to empirical perturbation errors across tested matrices and noise models | Low-rank inverse perturbation bounds · Census, BCSSTK09, and Discretized Hamiltonian | empirical error / proposed bound: less than 10 | Helped |
| Increase the noise scaling factor C_A | Proposed perturbation bound versus EYM--N · Census, BCSSTK09, and Discretized Hamiltonian | EYM--N bound / proposed bound: Census Gaussian: 5.69 to 1.50; BCSSTK09 Gaussian: 3.23 to 1.69; Hamiltonian n=500 Gaussian: 1334 to 1.99 | Mixed |
| Require the eigengap condition 4||E|| ≤ δ_{n-p} in addition to the noise-size condition | Proposed perturbation bound · Low-rank inverse approximation under additive noise | validity of the perturbation guarantee | Helped |
| Use the EYM--N baseline instead of the proposed bound | PCG convergence analysis with a low-rank-plus-regularization preconditioner · PCG iteration-count guarantee | guaranteed iteration count: n^{1/4} | Hurt |
Surprising findings
- Low-rank approximation error ||A_p - tilde A_p|| can be zero while the low-rank inverse error grows like sqrt(n), showing direct low-rank error does not control inverse error.
- Eigenvalue reordering from small eigengaps can make the low-rank inverse error arbitrarily large relative to the full inverse error.
Limitations
- Guarantees depend on spectral quantities (eigengap, smallest eigenvalue) that may be hard to estimate efficiently.
- Results are for static matrices and do not extend directly to adaptive or time-varying settings.
- Refined bound (doubling-distance version) is not empirically evaluated.
Experimental setup
Datasets: 1990 US Census covariance matrix (UCI) BCSSTK09 stiffness matrix discretized quantum harmonic oscillator Hamiltonian (synthetic)
Benchmarks: 1990 US Census covariance BCSSTK09 discretized Hamiltonian
Metrics: spectral-norm perturbation error ratio of bound to empirical error ratio of EYM-N bound to proposed bound
Baselines: EYM-N bound Neumann series bound
Builds on: Neumann series expansion Eckart-Young-Mirsky theorem Weyl's inequality contour integral representation of matrix functions
Closest papers by meaning
- Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy (NeurIPS 2025 · similarity 0.93)
- Entrywise error bounds for low-rank approximations of kernel matrices (NeurIPS 2024 · similarity 0.88)
- Lower Bounds on Adaptive Sensing for Matrix Recovery (NeurIPS 2023 · similarity 0.87)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.87)
- Fast and Stable Gradient Approximation for Bilinear Forms of Hermitian Matrix Functions (NeurIPS 2026 · similarity 0.85)
- Coherence-free Entrywise Estimation of Eigenvectors in Low-rank Signal-plus-noise Matrix Models (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.