Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Perturbation Bounds for Low-Rank Inverse Approximations under Noise
Authors: Phuc Tran, Nisheeth K. Vishnoi
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We systematically study the spectral-norm error ( A 1)p A 1 p for an n n symmetric matrix A, where A 1 p denotes the best rank-p approximation 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. |
| Researcher Affiliation | Academia | Phuc Tran Vin University Nisheeth K. Vishnoi Yale University |
| Pseudocode | No | The paper describes theoretical proofs and empirical validations but does not present any structured pseudocode or algorithm blocks. |
| Open Source Code | Yes | Code and instructions are provided in the supplemental material. |
| Open Datasets | Yes | We perform this analysis on two matrices: the 1990 US Census covariance matrix (n = 69) and the BCSSTK09 stiffness matrix (n = 1083). Specifically, we first compute λn and δn p for the smallest p such that the spectral tail satisfies A 1 A 1 p A 1 < 0.05, ensuring that at least 95% of the inverse spectral mass is retained. ... [5] Arthur Asuncion, David Newman, et al. UCI machine learning repository, 2007. ... [15] Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. https://sparse.tamu.edu/HB/bcsstk09, 2011. Suite Sparse Matrix Collection, Matrix: HB/bcsstk09. |
| Dataset Splits | No | The paper evaluates perturbation bounds on entire matrices (e.g., US Census covariance matrix, BCSSTK09 stiffness matrix, synthetic discretized Hamiltonian) rather than performing machine learning experiments with explicit training, validation, or test splits. The concept of dataset splits in the conventional sense (e.g., 80/10/10 for ML training) is not applicable or discussed for this type of matrix analysis. |
| Hardware Specification | No | The main body of the paper does not specify any particular hardware details (e.g., CPU or GPU models) used for running the experiments. While the NeurIPS checklist mentions 'standard CPU machines', this is not part of the main text. |
| Software Dependencies | No | The paper does not explicitly list any specific software libraries, frameworks, or their version numbers used for implementing the experiments. |
| Experiment Setup | Yes | We set the low-rank parameter p satisfies A 1 A 1 p / A 1 < 0.05. This yields p = 17 for A = Census, p = 8 for A = BCSSTK09, and p = 10 for A = Discretized Hamiltonian. We perturb each A by either Gaussian Orthogonal Ensemble (GOE) noise E1 or Rademacher noise E2. Each Ek is scaled by ten equally spaced factors CA so that 4CA Ek spans up to min{λn, δn p}, i.e., CA {1.5, 2.0, . . . , 6} for A = Census, CA {1.2, 1.4, . . . , 3} for A = BCSSTK09, and CA {10 4, 10 3.67, . . . , 10 1} for A = Discretized Hamiltonian; see Table 1 and Appendix G. This scaling range ensures that the assumption of Theorem 2.1 is satisfied. For each configuration (A, Ek, n, p), we report: (i) the empirical error ( A 1)p A 1 p (100 trials). |