Perturbation Bounds for Low-Rank Inverse Approximations under Noise
Authors: Phuc Tran
Nisheeth K. Vishnoi
Venue: NeurIPS 2025 poster ()
Keywords: Low-rank approximation
Pseudoinverse
Robustness  Numerical linear algebra
Noisy matrices
Primary area: optimization
TL;DR: We derive sharp spectral-norm bounds for low-rank inverse approximations of noisy matrices, improving classical estimates by up to  \sqrt{n} and offering spectrum-aware robustness guarantees validated on real and synthetic data.

Abstract: 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 $\| \tilde{A}_p^{-1} - A_p^{-1} \|$ for an $n\times n$ symmetric matrix $A$, where $A_p^{-1}$ denotes the best rank-\(p\) approximation of $A^{-1}$, and $\tilde{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 \emph{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 $\sqrt{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.

Perturbation Bounds for Low-Rank Inverse Approximations under Noise
Phue Tran
Nisheeth K. Vishnoi"
VinUniversity
Yale University
Abstract
Low-rank pseudoinverses are widely used to approximate matrix inverses scal- able 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 approxima- tions remains poorly understood. We systematically study the spectral-norm error [((A-), A,' 'I for an n x n symmetric matrix A, where A,, denotes the best rank-p approximaton of A and À A E noisy observation. Under mild assumptions on the noise, we derive sharp non-asymptotic perturbation bounds that reveal how the eтrоr scales with the eigengap, spectral decay, and noise align- ment with low-curvature directions of A. Our analysis introduces novel applica- tion of contour integral techniques to the non-entire function ((=) = 1/z, yielding bounds that improve over naive adaptations of classical full-inverse bounds by up to a factor Vn. Empirically, our bounds closely track the true perturbation er- ror across 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 compu- tational environments.
1 Introduction
Low-rank matrix approximations are foundational tools in machine learning, optimization, and sci- entific computing. They enable scalable algorithms by reducing memory and computation while preserving the dominant structure in high-dimensional data [24, 57]. A recurring task is to apply or approximate the inverse of large symmetric (often positive semidefinite) matrix A Rexn, Such inverse computations arise in kernel methods [19, 63]. Gaussian processes [44], covariance- inference [21, 33), and solvers for structured systems and graph Laplacians.
For large n, computing or storing the full inverse A often infeasible. A common alternative is to approximate 1-1 with low-rank surrogate. Let A Σ A,u;u be the eigendecomposition of A, with eigenvalues À1 2 An and orthonormal eigenvectors u, E R.. Then A-1 Σn x- " and the best rank-p approximation of A- in spectral norm is given by
A. arg minn)ann(()s5n || - XI| Ei u,u,"
These directions capture the flattest (low-curvature) subspace, which dominates the condition num- ber and affects stability in inverse- based algorithms. Such approximations are integral to fast solvers, adaptive preconditioners, and randomized linear algebra [13, 18], well optimization [43].
In many applications, however, one does not observe A exactly but rather noisy version = A+ E, where may arise from sampling error, sketching, quantization [3, 23), or deliberate perturbation
Alphabetical order. Correspondence nisheeth. vishnoi@gmail
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

for differential privacy [1, 61]. This naturally raises a basic question: How robust is the rank-p pseudoinverse to noise-how large is II(A-);; Ap
This question is fundamental for assessing the stability of approximate solvers, Hessian- based pre- conditioners, and downstream learning or optimization pipelines that rely on noisy second-order information.
Classical matrix perturbation theory provides worst-case bounds for the full inverse:
| - - 1
1- A |8
under the condition ||A- < 1, or the first-order expansion
-- = - -------A---- +
see [26, 47]. Such perturbation bounds apply to arbitrary symmetric matrices and perturbations E, but they address the full inverse A and do not account for truncation to rank p. Moreover, they ignore the interaction between the noise and the eigengap. and scale poorly with n, often yield- ing overly pessimistic estimates. Structured identities such as the formula apply only to specific low-rank updates, and recent results on low-rank perturbations un- der Schatten norms [35, 46, 57] do not provide spectral-norm guarantees for pseudoinverses under general noise.
Our contributions. We derive explicit, non-asymptotic spectral-norm perturbation bounds for the error [((Á--), A, where A,1 is the best rank-p approximation of A-1 and Å = A + E noisy observation. While certain bounds can obtained from classical perturbation theory, analysis yields sharper, ppectrum-adaptivv guarantees that depend explicitly on the eigengap 6p:= := An-p-An- -n-p+11. the spectral decay of A, and the alignment of the perturbation with its low- curvature subspace. The main technical contribution is novel application of contour bootstrapping to the non-entire function fz) 1/z, enabling localized resolvent expansions around the smallest eigenvalues and precise control over the perturbation of associated Riesz projectors [14, 27, 56].
Under the condition 4 E|| S min(An, 5n-p), our main theorem establishes the bound
((A--),, )) A," 1
E A
An 6n-p)
for pesitive-definite A (Theorem 2.1); an extension to arbitrary real symmetric matrices appears in Section A. Our approach also applics to matrices with rank deficiency via their pseudoinverses (see Remark A.7). This result provides: (1) explicit and interpretable spectral-norm guarantee; (2) up to a vn improvement over classical inverse bounds in realistic regimes; and (3) a quantitative criterion for robustness of low-rank inverse approximations under general noise.
We empirically evaluate (i) the true perturbation error, (ii) our theoretical bound, and (iii) the esti- mate implied by classical Neumann-series and Eckart-YouggMirrkk analyses. Tests on both real and synthetic matrices-includinn
sample covariance matrices, discretized elliptic operators, and sparse structural stiffness matrices (e.g., BCSSTK09) that our bound tracks the actual error within a small constant factor, whereas classical estimates often overpredict by one to two orders of magnitude (see Figures 1-2). These results provide robust, interpretable certificate for the stability of noisy low-rank inverse approximations.
In Section 4.1, we evaluate the admissibility of the noise condition E|| < min >n, 8n-p) on standard datasets such as the 1990 US Census covariance and the BCSSTK09 stiffness matrices, showing that the resulting safety margins comfortably exceed noise levels common in differential- privacy and structural-engginerring applications.
Section B presents an asymptotically refined bound for large-scale or synthetically structured ma- trices. Section demonstrates concrete application: we apply our framework to improve the theoretical convergence rate of the preconditioned conjugate-gradien (PCG) method. Using wtw--raak-puu-euuullaae
preconditioner, our bound yields tighter condition-number estimates and a provable n 1/4 improvement in the guaranteed iteration count compared with the classical Moaa---oooug---s----euum
analysis.
To the best of our knowledge, this is the first work to provide non-asymptotic spectral-norm bounds for (Āā-)), A-11 under general additive noise. Our analysis addresses fundamental robustness

---

question in noisy inverse computation and complements existing algorithmic approaches by offering structural, spectrum- aware guarantees for when a low-rank inverse remains reliable.
Related work. Classical perturbation theory provides tools for analyzing the inverse of a perturbed matrix, but these focus on the full inverse and do not account for low-rank truncation or spectral structure [26, 47J. While the literature on low-rank approximation is dilensive-spanniig random- ized SVD, projection methods, and sketching techniques [18. 24, 42, 57] primarily addresses approximation of A itself or f(A) when f is a monotone-operator function", rather than inverse computations.
Several recent works study perturbations of low-rank approximations under Schatten or Frobenius norms [16. 35, 36, 37, 46], often in structured sparse settings. However, these results do not apply to the spectral-norm error of low-rank inverse approximations. Similarly, while the Sherman- Morrison-Woodble
identity yields exact formulas for structured updates, it does not extend to bitrary noise. Approximate Hessian inversion has been studied in the context of sketching [43], privacy [1, 61], and distributed optimization, but those works focus on convergence rather than the spectral stability of low-rank pseudoinverses.
Our technical approach builds the contour integral representation of matrix functions, a classical tool in numerical analysis [27, 56]. While contour- contour-based arguments have been used to analyze perturbations of spectral functionals associated with entire functions such as the matrix exponential
(w..t. fz) = exp(2)) [39, 59] or the eigenspace-prat prresppace-pooecction (w.x.t f(z) = 1) [31, 41, 53), they have rarely been applied to non-entire functions like the inverse. We adapt these techniques in non-trivial way to f(z = 1/2, localizing the resolvent expansion around small eigenvalues and
bounding the impact of noise the associated spectral projectors.
2 Theoretical results
For clarity, we present our main results in the case where positive definite (PD). Extensions to general symmetric matrices are provided in Section A.
Setup. Let A E |= be real symmetric PD matrix with eigenvalues A1 2 de 2 A,
and corresponding orthonormal eigenvectors u1,... Up. For each 1 < k S n 1, define the eigenvalue gap
8x = A AR+1-
Then 1 is also a real symmetric PD matrix, with eigenvalues X 2 A=1 and the same eigenvectors Un,..., 41 (in reverse order).
2 x 0.
Let E Rax= be a symmetric perturbation (error) matrix, and define the perturbed matrix as Ā A+ F. For a given rank 1 S S let A and (A-1), denote the best rank-p apprxxmation of A and A-1, respectively.
Goal and classical baseline. Our objective is to derive a spectral-norm bound on the difference between the best rank-p approximations of A and A-1:
II(A-)), A,
While no prior results directly analyze this quantity, one can obtain a baseline estimate using classi- cal tools: the Neumann expansion and the Eckart- Young- Mirsky (EYM) theorem [20]. Specifically, defining E' : A-1 A-! and applying a low-rank approximation argument yields:
8|
2
I(A-)),- 2[[] + +
322
An-p'
valid when E|| < An; see Section D. This condition is needed for the application of Neumann expansion, and we refer to this bound as the EYM-N bound. This bound degrades when Xn-p
\ and fails to capture the limit ((A-)), -, + 0 as | + 0.
Main result. We now present a sharper, spectrum-adaptivee bound based on contour bootstrapping.
For clarity, we assume the eigenvalues of A are ordered as: +oo = > > \ 2 A2 2 ... 2 An > 0.
'A matrix function f is monotone-operee implies f(A) - (B) is sositive-semi definite. For example, f(z) = 2" with 0 < t < is monotone-operator, whereas f(z) 2². f(z) = c², and f(z) 1/z are not.
if, for all Hermitian A, B. A B is positive semi-definite
3

---

Theorem 2.1 (Main perturbation bound for PD matrices). Let A be real symmetric PD matrix and = A+ + E with E' symmetric. 4 |لله < min(An An Sn-ph then
||AA1); - A
EEl 5|
An-pOn-p
This bound consists of two interpretable components: the first term, || reflects classical perturbation scaling for the full inverse, while the second term, (Anl//An-ppn-- captures the additional sensitivity introduced by projecting onto the subspace spanned by the smallest eigenvalues of A.
When the eigengap 8n-p- An-p An-pt) p+1 is well-separated and An-p p is not too small, the low- rank approximation remains stable under noise, and the bound remains tight. Compared classical bounds, this result explicitly accounts for spectral structure and subspace alignment, providing more accurate estimate of the low-rank inverse perturbation.
Note that for p n,, we recover the full inverse case: (A-t), A-1 and A, AA-1, In this setting, 6n-p À = +oc, so the second term vanishes and the bound simplifies to ((1) recovering the Neumann bound.
The gap condition. The first assumption, ||]| < An. ensures that Á is invertible and À is well-defined. This matches the classical Neumann expansion, which fails when [|] 1.
The second assumption, E'l & 6n-p. which we call the gap assumption, ensures that the spectral ordering of eigenvalues is preserved under perturbation. By Weyl's inequality [62], this guarantees that the eigenvectors associated with the smallest eigenvalues of Á remain aligned with those of A, thereby preserving the low-rank inverse structure. When this assumption fails-i.e., when ōn-p < the the eigenvalues of A can reorder, leading to instability in the low-rank approximation; see Section I.1 for concrete example.
Our bound for a random matrix noise model. If E is a Wigner matrix (i.e., symmetric with i..d. sub- Gaussian entries), then || = (2 + o(1)) /n with high probability. Substituting this into Theorem 2.1 yields:
I( -, =
+ Am pó.,
In contrast, the EYM-N bound gives ( + 1/2n-p), which is larger when vn & 8n-pp
Comparison to the EYM-N bound. The EYM-N and bootstrapped bounds coincide in order of magnitude when ||]]] > /2/An-p- In contrast, when | < X >n our bound smaller by factor of
This "gain regime" arises naturally whenever either sT ( Σラ= An/ or on On-pAn-p < X2 i.e., min(Am, An, }n-p] < /n assuming the conditions Theorem 2.1 are met. Notably, our bound becomes increasingly sharp as the noise level decreases.
In favorable cases, result yields up v fi-cto improvement. For example, consider matrix A with spectrum {n, 2n.2n.... 10n, 20n, 20m, 20m} and 10. E is standard Gaussian noise,
the EYM-N bound evaluates to O R + 1 = O(L/n). while our bound gives O(Vn/ni =
Onn -3/2), demonstrating the expected / Veleeel gain. Section 4.2 empirically confirms that our bound consistently tracks the error within a small constant (typically below 10), and outperforms the EYM-N estimate across both synthetic and real datasets.
Applicability of assumptions. Unlike the EYM-N bound, Theorem 2.1 additionally requires the gap condition 4|| < 8n-p- This assumption holds across a range of practically relevant matrix classes. For example, suppose = M M is a sample covariance matrix, where M E mxx (m 2 n. ensuring that A is well-defined), and E is symmetric matrix with i.i.d. sub- Gabssan entries mean zero and variance 2 || [[? 2 m log n and m > Cp.3/2A for some constant
log
C > 0, then both the spectral and gap conditions of Theorem 1. hold with high probability.
In Section 4.1, we compute Xx and 6n-p for several real-world matrices A, and determine the maximum noise level ||] for which the assumptions remain valid. Our findings show that both conditions-44] X., and EEl < 6n-p" are satisfied robustly across many datasets.

---

In practice exact verification of these assumptions is often unnecessary: as long as the estimation errors in An and 6p-p are within | our bound remains valid up to constant factor (Step 3, Sec- tion 3). Thus, the assumptions are robust to moderate misestimation and allow scalable application large-scale settings.
Remark 2.2 (A stronger but more technical bound). In the intermediate regime where / < [|] < &min min((nnps An). ; the bound in Theorem B.2 (Section B) offers an asymp- totic improvement over both the simple bound of Theorem 2.1 and EYM-N bound. This refinement more technical and depends on additional structural quantities, such as the alignment of E with the low-curvature eigenspace. While we do not empirically evaluate this bound, may provide tighter guarantees in settings where noise is moderate and the spectral decay of A-1 is slow.
3
Proof overview
This section delineates the proof framework for Theorem 2.1, organized into three core stages. First, employing contour integration, we bound the perturbation by
|( - 4 24 =
(=I - -2]
Here I' is a contour on the complex plane, encireling the p-bottom eigenvalues of A and A. Unlike the Eckart Bekkart-Yuun-Miing Moimg--Mrsk---eeumaae
(EYM-N) bound (see Section D), this formulation preserves the delicate A E interaction. Secondly, we develop the contour bootstrapping technique (Lemma 3.1) which under the assumption 4 F|| S min An. 8n-p), yields s 2F; with
R := f1 - A 1 ([=I--A)-11 1|122]
This bootstrapping argument, crafted specifically for the non-entire function f(2) = 1/2, replaces classical series expansions by a quantity that can be computed directly. Third, we construct be- spoke contour r- one specifically tailored so that the bottom-p cigenvalues of and Á lic at prescribed distances from its sides. This tailored geometry renders the integral defining F1 tractable and essentially tight, culminating in a sharp perturbation bound.
Step 1: Representing the perturbation || (A--)), -A
A via classical contour method. Let A 2 ... 2 A, > be the eigenvalues of A with eigenvectors u,- Then, A-1 is well-defined, with cigenvalues X,- > X
\ > 0. Let λι 2 2 An > 0 denote the eigenvalue of Á.
By Weyl's inequality [62].
E 2 An Anl 2 An An
Under the assumption E|| S An of Theorem 2.1, we obtain
d 2 An | D i| 0. Hence À is also positive definite, and À is well-defined with eigenvalues A 2-1 2 x-1 0.
We now present the contour method to bound the perturbation of low-rank approximations in- verses in the spectral norm. Let I be contour in C that encloses X, An-1.... An-p+1 and ex- cludes and Å1 .2...., Ån-p- Thus, f(z) = 1/2 is analytic on the whole interior and boundary of T, and hence the contour integral representation [27, 30. 47] gives us:
2r fr 2 (2T A) -dz - En- Xo uuu A
Here and later, denotes V The assumption E|| min ( (5n-p- An and the construction of (see later this section) ensure that the cigenvalues Ả; for n 2 i 2 n - + + 1 lie within I, while and all Xy for j < n - p remain outside. We obtain the similar contour identity for A:
- f - - Enzizn-pii A " (A-1))
Thus, we obtain the contour inequality:
((A-)), 100--5-'1 $ + 1 A) - (zl A) |dz).
5

---

This inequality makes the A - E interaction explicit, but obtaining a sharp bound on its right-hand side remains a formidable analytical challenge.
Step 2: Bounding F < 2 via contour bootstrapping method for non-entire function f() =
1/2. By repeatedly applying the resolvent formula, one can expand
-=1 - A (z1 - (=
(2T AF=1 A)-1)
This yields the bound:
F E. Fs. where F. = 2x (1T () ---((((I-A)-111)
- 1)-1)" |dz|-
The traditional approach [30] attempted to estimate Fg for each s. One can bound F, by
o (1 Jr min
M 6++2
in which 8 mingeT, [|=1, /z > and Mr is the total length r. This traditional approach, with appropriate choices of r, can only provide a bound of O (1) |
Moreover, when f() 1 in [53] when is entire function as in [52], the dominant contribution to F arises from the term F1, i.e., F = O(F). We show that this relationship continues to hold for the rational case [(z) 1/2 under the assumption 4|| min min(An, 8n 8n-p3.
Lemma 3.1 (Contour Bootstrapping) 4f min 5n-p]: p. then
A) - E(=I - A) |dz|. 1= 1=1 F 2F 2F π
1
For entire functions f. the perturbation depends only on the top p singular values of A, and the contour r is chosen to isolate the leading eigenvalues (Ap In contrast, the rational func- tion f(z) = 1/2 requires the contour to enclose the smallest eigenvalues of A while avoiding the singularity at = = 0.
This non-entire setting introduces two significant technical challenges. First, the relevant spectral components lie in the smallest p eigenvalues of A. which are much more sensitive perturbation. Indeed, when Á is a deformed Wigner matrix, || = O(n) with high probability for any fixed real A; see [29, 45, 48]. In such cases, the smallest singular values of A are effectively destroyed by noise, illustrating the instability of low-curvature directions. Moreover, the perturbation of the low-rank approximation ||Ap- Apll does control the inverse approximations; see Section I.2 for concrete counterexample. Second, constructing I' to isolate these low-lying eigenvalues while maintaining analyticity of fz) 1/2 requires additional care in bounding the associated resolvent terms.
Step 3: Construction of r, F1 estimmatio and proof completion of Theorem 2.1. Now we show how Lemma 3.1, along with a careful choice of a contour T can be used to prove Theorem 2.1. We need to construct the contour I so that (i) the lowest p-cigenvalues of and Á lie inside and remain aligned, (ii) every point E I is at least? 8n-p/2 or Xn,/ from the spectrum of A, and (iii) the integral with respect to the resulting geometry is finite and computationally tractable. Indeed, the contour I' is set rectangle with vertices (zo, T), (x1, T), (I1, -T), (ra, -T), where xp
An/2 2,, := An-pt1 + 6n=p. T = 2\1 Then, we split into four segments:
2
Vertical segments: Fi = [1 1) - <1 = ((11, 2 12 -T).
Horizontal segments: Io2 ((x, ()) S x : = (Tx,-) 2 x 2 ro
Given the construction of I, we have
FT = Ei= Mr. where Mr : Sry. En x i.d EujuJ |||dz|.
'The factor 1/2 may be replaced by any fixed constant c E (0, 1) by adjusting the contour 1', and the estimate changes only up to constant. This flexibility makes the bound robust to moderate misestimation of An and 8n-p in practice.

---

T
An
Au-p
Re (2)
Note that the setting of the height T = 2 ensures that the integral does not blow and at the same time, the main contributions are the integrals along the vertical edges F 3, i.e. M1, M3." We now estimate Mi. Using the submultiplicative property of the spectral norm and factoring out E, have
M1 S Sr, गि
-1-1 (I A) = Sr. || Talmmin giga 1=-A,12 dz/.
Here, we use the standard identity that
[|(2T 1) min gign Au-
The key observation is that |z Arl 2 |a - Am for any 2 2 Ii and isis n. Hence, the r.h.s is at most
Jr. || E |=|-|=-A,, A., |d)..
1
T S 1 T). parameterize xo for [-T, Then |=| v J + 12 and |z >, (>,, - xo)² + 12 since A, is real. Moreover, on this segment, |dz| = dt. Therefore, the integral becomes
By the definition of i {(z0 1)
||
Vog+t ((g (ooo)))) = | S (A., (2 dt.
By Lemma C.2,
4 (Aa/2)² X
Therefore, M1 <
In similar manner, replace r by r3 = (( 1) - S.S.. we also obtain
M3 S Jr, H mimiggss 1= 2 S S ( +2-2))
| dde
|| dt
By Lemma C.2 and the fact that (a An-pl 8n 8n-p/2 p/2 M3 most
El (An x + 1)
El|
4T| An An-pón- por
01 12
Arguing similarly, also obtain that M2, M4 S ((X}) These estimates imply
[E|
(Section C.2), and hence M2 + MA
12
S 1 (M1 M2 + M3 M4) S
2||
2.5| A., S
Aa
The last inequality follows the facts that X,, I An-p: An-pt1, and max Am A X21 AP. This Fi 's upper bound and Lemma 3.1 prove Theorem 2.1.
Proving the contour bootstrapping lemma (Lemma 3.1). The first observation is that using the therman-Morrison -ww.rrrooo--ooobbrrrry Woodbury formula M- 10-----+-0 -M N [28] and the fact
that A + E, we obtain
(<I - A)- - (zI A) (>I A)-1 A)-
Using this, we can rewrite
F
1 2 S || (zI E(22
E(2l 1)-111
as -
(al --) A)-11 dz).
*In [53]. the contour construction was free to extend rightward, making the primary contribution to the integral only come from the left vertical segment. In contrast, our contour has to be more restrictive, and both vertical segments play equally essential role in the analysis.
7

---

Using the triangle inequality. we first see that F is at most
2 fr 1== F)=1 - -)-
II ( A)-1 (=T A) da
Next the key observation that the second term in the equation above can be rearranged and upper- bounded as follows, that the original perturbation appears again:
max.er (2) - Ay
Sr 1| [(z] - A)- (=l - I[||dz
2T
Thus, have
E F. FSP + maxzer || - E
Furthermore, our assumption that F| I onin(ón- An} and the definition of imply
max,er [[=1 B < ||x|-maxzerr ||(=1 A)- min,cr --
||
min
Equivalently, F S Fi + F/2, and hence F S 2 We thus complete the proof overview of Lemma 3,1 and, consequently, Theorem 2.1.
Empirical results
We empirically validate the perturbation bound in Theorem 2.1, demonstrating that it (i) holds on real datasets, and
(ii) yields significantly tighter estimates than the EYM-N bound.
4.1 Assumption of Theorem 2.1 on real-world datasets
Theorem 2.1 requires the spectral condition E|| < min(An, 6n-p], where An is the smallest eigenvalue the matrix A, and ón-p := An-p An-p+1 denotes the eigengap near the truncation threshold. We translate this requirement into a data-dependent upper bound on the noise variance for two real-world matrices.
We perform this analysis on two matrices: the 1990 US Census covariance matrix (n = 69) and the BCSSTX09 stiffness matrix (n 1083). Specifically, we first compute X and 8n-p for the smallest such that the spectral tail satisfies
IA- 0.05,
ensuring that at least 95% of the inverse spectral mass is retained. We then translate these spec- tral quantities into the maximum permissible noise level ||E]], and derive the corresponding sub- Gaussian variance threshold
A max
min Aa 8 m1
8/n
Datasets. We use two widely studied matrices: the 69 x 69 US Census covariance matrix from the UCI MI. repository [5], commonly used in studies on differentially private PCA [4, 12, 36), and the 1083 x 1083 BCSSTK09 matrix [15], stiffness matrix arising from a finite-element model of clamped plate [6, 9, 11, 17, 50].
Noise model and variance threshold. We consider symmetric noise matrices E with i.i.d. sub-Gaussian entries (mean zero, variance proxy A With high probability, | (2 + (T, as established in [58, 60). Thus, Theorem 2.1 is valid whenever 4(2 + (1))) n < min An, 8p-p). equivalently, A< max
Results and conclusion. For the US Census matrix with p = 17, we compute A Mmx x 47.8; for BCSSTK09 with p 8, we find A max 26.9. These thresholds comfortably exceed the noise levels commonly used practice. For instance, in differential privacy, Laplacian noise with scale b satisfies
| < 22. Since e-DP corresponds to b = 1/e, Theorem 2.1 applies as long as > within the commonly accepted range for strong privacy [40]. Similarly, prior work using BCSSTK09 applies noise at the level ||]|| < 10-511 || z= 6.7 x 10?, which translates to A 10.2 < A max
Section F (Table 1) confirms that this safety margin persists for range of values. We conclude that the assumptions of Theorem 2.1 are satisfied in several practical settings, making broadly applicable to workflows in differential privacy, structural engineering, and numerical linear algebra.
8

---

4.2 Empirical sharpness of Theorem 2.1
To gauge the practical sharpness of our new low-rank riverse-perturaation bound, we benchmark on three markedly different matrices- dense covariance matrix from the 1990 US Census, large sparse stiffness matrix (BCSSTK09), and synthetic discretized Hamiltonian with an almost linear spectrum. By injecting both Gaussian Orthogonal Ensemble and Rademacher noise at ten escalating levels that respect the stability requirement of Theorem 2.1, we create a broad test bed that spans dense, sparse, and near-Toeplitz spectra as well as moderate to severe perturbations. The goal is to compare
(i) the true error, (ïi) our bound, and
(iii) the
Young-Mirsky- Neumann (EYM-N) bound under the same conditions.
Setting. In this subsection, we consider three different matrices A:
(i) real matrices: the 69 x 69 covariance of the 1990 US Census (A == Census, n 69),
(ii) the 1083 1083 BCSSTK09 stiffness matrix (A BCSSTK09, n 1083), and
(iii) synthetic matrix: the approximately linear spectrum A (A == Discretized Hamiltonian) de- rived by discretizing the 1-D quantum harmonic oscillator on E (500, 1000) grid points (see Appendix G for the detailed construction).
We set the low-rank parameter satisfies ||A-1 - 1,711/11A~111 < 0.05. This yields 17 for = Census, p = for A BCSSTK09, and p = 10 for A Discretized Hamiltonian.
We perturb each by either Gaussian Orthogonal Ensemble (GOE) noise ES or Rademacher noise E2. Each Eg is scaled by ten equally spaced factors CA so that 4 spans up to 6) for A = Census, CA E {1.2, 1.4,............. 3] for A = BCSSTK09, and CA E {10-4, 10 3.67 10-1} for A = Discretized Hamiltonian; see Table and Appendix G. This scaling range ensures that the assumption of Theorem 2.1 is satisfied.
min An i.c., CA E {1.5, 2.0,
Evaluation. For each configuration (A, Eg, n, p), we report:
(i) the empirical error
[I(A-))p
(100 trials).
(ii) our bound
4| 1| An-ponpp"
and
X
(iii) the EYM-N bound
8| 3A
2 An-Pp
For the 1990 US Census, we additionally preprocess the data to ensure all entries are numeric: discard the header row and the indexing column, then replace every non-numeric field with We bound
record the ratio actual error" As is standard, all numerical results are reported mean + standard deviation in 4e format, and the curves for Actual Error, Our Bound, and EYM-N Bound are plotted with error bars (cap width 3pt) and logarithmic y-axis.
Results and conclusion. For every matrix tested- the 69 x 69 US US-Census covariance, the 1083 x 1083 BCSSTK09 stiffness matrix, and the discretised Hamiltonians with {500, 1000) our low-rank inverse bound consistently outperforms the EYM-N estimate and closely follows the measured error for all noise models Σş and scaling factors CAs see Figures 1-2. (The error bars for Our Bound and our hound
the EYM-N Bound are too small to discern.) In every experiment actuol error < 10, whereas the M- N bound is typically looser by more than order of magnitude; see Tables 2-9. This improvement is uniform across matrix sizes n E {69, 500, 1000, 1083). demonstrating that our estimate captures the leading error term in practice and is therefore reliable error certificate for low-rank inverse approximations.
'The inverse harmonic oscillator and its discretized version are central many studies in spectral perturba- tion theory; e.g., implicit time- stepping, preconditioning in quantum simulations, and the design of Gaussian- process covariance kernels [7, 34, 49, 51]. Low-rank approximations of these inverses enable fast On log n) solvers and reduced-order models [24, 38. 55J.

---

Figure Four panels show (1) Actual Error, (ii) Our Bound, and (iii EYM-N Bound, over 100 trials for real-world matrices A = Census (n 69, p 17) and A BCSSTK09 (n 1083, p 8),
perturbed by
noise.
Cestror
Figure 2: Four panels show (i) Actual Error, (ii) Our Bound, and (iii) EYM-N Bound, over 100 trials for Hamiltonian (p 10, (500, 1000)) perturbed by Gaussian/Rademachon noise.
Conclusion, limitations, and future work
We present first non-asymptotic spectral-norm perturbation bounds for low-rank approxima- tions of matrix inverses under general additive noise. Our results characterize how the error [[(A-),, A depends spectral quantities such as the smallest eigenvalue An. the eigengap 5n-p: and the alignment of noise with low-curvature eigenspaces. In regimes where these quan- bound improves upon classical Neumann- based estimates by up
tities are bell-behaved, /n-factor. This analysis introduces new application contour bootstrapping to the non-entire isolate and control the impact of perturbations inverse
function f(=) 1/z, allowing approximations projected onto the smallest eigencomponents of A.
We validate bounds on diverse matrix classes-including stiffiness matrices, and discretized quantum Hamiltonians noise. Across all settings, bound tracks the empirical error within small constant factor and consistently outperforms the Eckart- Young-uung-Maa Mirnky-irs---euuee magnitude. These findings yield robust, spectrum- aware guarantees for low-rank inverse estimation in noisy numerical pipelines.
including dense covariance matrices, sparse
both Gaussian and Rademacher
baseline, often by over an order of
Despite these contributions, several limitations remain. Our guarantees depend on spectral quantities that may be difficult to estimate efficiently, especially black-box or data-driven scenarios. In particular, verifying the gap condition 5n-p > El] requires accurate access to the tail of the spectrum, which can be computationally demanding. Moreover, our results are tailored to static matrices and do not directly extend to adaptive iterative settings where the matrix evolves over time.
Nonetheless, our framework provides a principled tool for certifying the stability of inverse-based methods the presence of noise. optimization and machine learning, it can inform the use of low-rank Hessian approximations, preconditioners, or trust-region updates under noisy curvature in- formation. Future directions include analyzing structured or time-varying noise, developing adaptive gap estimators, obtaining the sharp perturbation bounds of low-rank inverse approximation for other structured metrics such as Schatten-p norm or the Ky Fan norm, and extending contour techniques to other non-entire matrix functions such resolvents matrix roots.
10

---

Acknowledgments
This work was funded in part by NSF Award CCF-2112665, Simons Foundation Award SFI-MPS- SFM-00006506, and NSF Grant AWD 0010308.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings the 20/6 ACM SIGSAC Conference on Computer and Communications Security, pages 308-318, 2016.
[2] Sadhan K Adhikari and Paulsamy Muruganandam, Dosse-Einstciicondensttiiin dynamics from the numerical solution of the Gross-Pitaevskii equation. Journal of Physics B: Atomic, Molec- ular and Optical Physics, (5(12)2831, 2002.
[3] Dan Alistarh, Danijela Grubic, Jerry Li, Rémi Tomioka, and Milan Vojnović. QSGD: Communication--ffiieen stochastic gradient descent via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, pages 1709-
1720, 2017.
[4] Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz, and Sergei Vassilvitskii. Differen- tially private covariance estimation. Advances in Neural Information Processing Systems, 32, 2019.
[5] Arthur Asuncion, David Newman, al. UCI machine learning repository, 2007.
[6] Peter H Beckman. The harwell-boeing sparse matrix collection. 1991.
[7] Michele Benzi. Preconditioning techniques for large linear systems: survey, Journal of computational Physics, 182(2):418-47) 2002.
[8] Luca Bergamaschi, José Marín, and Angeles Martinez. Compact Quasi-Newton precondition- ers for SPD linear systems. arXiv preprint:2001.00062 2020.
[9] Jörg Berns-Müller, Ivan G Graham, and Alastair Spence. Inexact inverse iteration for symmet- ric matrices. Linear Algebra and its Applications, 4 416(2-3):389-413 2006.
[10] Andreas A Bock and Martin Andersen. A new matrix truncation method for improv- ing approximate factorization preconditioners. Numerical Linear Algebra with Applications, 3202): 2025.
[11] Elena Caraba. Preconditioned conjugate gradient algorithm. 2008
[12] Kamalika Chaudhuri, Anand Sarwate, and Kaushik Sinha. Near-optimal differentially private principal components. Advances in neural information processing systems, 25:989-997, 2012.
[13] Kenneth Clarkson and David P. Woodruff. Low-rank approximation and regression input sparsity time. In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC), pages 81-90. ACM, 2013.
[14] Chandler Davis and William Morton Kahan. The rotation of eigenvectors by a perturbation. III. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
[15] Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. https://sparse: tamu, edu/HB/bcsstkk9, 2011. SuiteSparse Matrix Collection, Matrix: HB/bcsstk09.
[16) Michal Derezinski, Rajiv Khanna, and Michael W Mahoney. Improved guarantees and multiple-descent curve for column subset selection and the nystrom method. Advances in Neural Information Processing Systems, 33:4953 4964, 2020.
[17] Jack Dongarra, Michael A Heroux, and Piotr Luszczek. High- bigg-perffrmance conjugate-gradient benchmark: new metric for ranking nigh-performance computing systems. The International Journal of High Performance Computing Applications, 30(1) 1:300, 2016.

---

[18] Petros Drineas, Ravi Kannan, and Michael W. Mahoney. Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. Proceedings of the 39th ACM SIGMOD- SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 200-210. ACM, 2012.
[19] Petros Drineas and Michael W. Mahoney. On the Nyström method for approximating a gram matrix for improved kernel-based learning. In Journal of Machine Learning Research (JMLR), Workshop and Conference Proceedings, volume 6, pages 167-174, 2005.
[20] G. Eckart and G. Young. The approximation one matrix by another lower rank. Psy- chometrika I, pages 211-218, 1936.
[21] Jianqing Fan, Yuan Liao, and Marianna Mincheva. High-dimensional covariance matrix esti- mation approximate factor models. The Annals of Statistics, 46(1):259-22) 2018.
[22] Zachary Frangella, Joel A Tropp, and Madeleine Udell. Randomized Nyström preconditioning. SIAM Journal on Matrix Analysis and Applications, 44(2):718-752, 2023.
[23] Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and P. Narayanan. Deep learning with limited numerical precision. In International Conference on Machine Learning (ICML), pages 1737-1746. JMLR.org, 2015.
[24] Nathan Halko, Per-Gunnar Martinsson, and Joel Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM review, 53(2):217-288, 2011.
[25] Christoph Helmberg. A preconditioned iterative interior point approach to the conic bundle subproblem. Mathematical Programming, 205(1):559-615 615, 2024.
[26] Nicholas J. Higham. Accuracy and Stability of Numerical Algorithms. SIAM, 2002.
[27] Nicholas Higham. Functions of Matrices: Theory and Computation. SIAM, 2008.
[28] R. A. Horn and R. Johnson. Matrix Analysis. Cambridge University Press, 2012.
[29] Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney. On the smoothed analysis of the smallest singular value with discrete noise. Bulletin of the London Mathematical Society, 54(2):369- 388, 2022.
[30] T. Kato. Perturbation Theory for Linear Operators. Classics in Mathematics. Springer, New York, NY, 1980.
[31] V. Koltchinskii and D. Xia. Perturbation of linear forms of singular vectors under Gaussian noise, volume 71. Springer, 2016.
[32] Lev Davidovich Landau and Evgenii Mikhailovich Lifshitz. Quantum mechanics: non- relativistic theory, volume 3. Elsevier, 2013.
[33] Olivier Ledoit and Michael Wolf. Honey, shrunk the sample covariance matrix. The Journal of Portfolio Management, 30(4): 10-119, 2004.
[34] Finn Lindgren, Håvard Rue, and Johan Lindström. An explicit link between Gaussian fields and Gaussian Markov random fields: the stochastic partial differential equation approach. Journal of the Royal Statistical Society Series B: Statistical Methodology, 73(4):423 2011.
[35] Ming Luo, Yue Han, and Yujia Zhang, Perturbation bounds for low-rank matrix approxima- tions. arXiv preprint:2008.011 011111 2021.
[36] Oren Mangoubi and Nisheeth Vishnoi. Re-analyze Gauss: Bounds for private matrix approxi- mation via Dyson Brownian motion. Advances in Neural Information Processing Systems, volume 35, pages 38585-38500 2022.
12

---

[37] Oren Mangoubi and Nisheeth K. Vishnoi. Private low-rank approximation for covariance ma- trices, Dyson Brownian Motion, and eigenvalue- bounds for Gaussian perturbations. J. ACM, 72(2), March 2025.
[38] Paulsamy Muruganandam and Sadhan K Adhikari. Bose einstein condensation dynamics in three dimensions by the pseudospectraland fimiteddifference methods. Journal of Physics B: Atomic, Molecular and Optical Physics, 36(12):2 2):2501, 2003.
[39] Igor Najfeld and Timothy Havel. Derivatives of the matrix exponential and their computation. Advances in applied mathematics, 16(3):321-375, 1995.
[40] Joseph P Near, David Darais, Naomi Lefkovitz, Gary Howarth, et al. Guidelines for evaluating differential privacy guarantees. National Institute of Standards and Technology, Tech. Rep, pages 800-226, 2023.
[41] Sean O'Rourke, Van Vu, and Ke Wang. Matrices with Gaussian noise: Optimal estimates for singular subspace perturbation. IEEE Transactions on Information Theory, 2023.
[42] D. Persson and D. Kressner. Randomized low-rank approximation of monotone matrix func- tions. SIAM Journal on Matrix Analysis and Applications, (44)):8949918 2023.
[43] Mert Pilanci and Martin J. Wainwright. Newton sketch: A linear-time optimization algorithm with high-dimensional statistical guarantees. In Proceedings of the 28th Annual Conference on Learning Theory (COLT), pages 1046-1079, 2015.
[44] Carl Edward Rasmussen and Christopher K.I. Williams. Gaussian Processes for Machine Learning. MIT Press, 2006.
[45] Arvind Sankar, Daniel A Spielman, and Shang Mhang-Hua Teng. Smoothed analysis of the condition numbers and growth factors of matrices. SIAM Journal on Matrix Analysis and Applications, 28(2):446-476, 2006.
[46] Dror Shumeli, Petros Drineas, and Haim Avron. Low-rank updates of matrix square roots and their applications. arXiv preprint:220..13355 2022.
[47] G. W. Stewart and Ji Guang Sun. Matrix Perturbation Theory. Academic Press, 1990.
[48] Terence Tao and Van Vu. Smooth analysis of the condition number and the least singular value. Mathematics of computation, 79(272):2333-236 2352, 2010.
[49] Mechthild Thalhammer. High-order exponential operator splitting methods for dependenn schrödinger equations. SIAM Journal on Numerical Analysis, 46(4):2022-2033: 2008
[50] Petr Tichy, Gérard Mcurant, and Dorota vSimonová. Block CG algorithms revisited. Numeri- cal Algorithms, pages 1-27, 2025.
[51] Michalis K. Titsias Variational learning of inducing variables in sparse Gaussian processes. In Proceedings of AISTATS, pages 567-574, 2009.
[52] Phuc Tran, Nisheeth K. Vishnoi, and Van H. Vu. Spectral perturbation bounds for low-rank approximation with applications to privacy. In Proceedings of the 39th Conference on Neural Information Processing Systems (NeurIPS 2025), 2025.
[53] Phuc Tran and Van Vu. Davis-Kahan theorem under a moderate gap condi- tion. Communications in Contemporary Mathematics, 2025. World Scientific, doi: 10. 101114//02211997550033x
[54] Phuc Tran and Van Vu. New matrix perturbation bounds with relative norm: Perturbation of eigenspaces, arXiv preprint:2409.200 2026.
[55] Lloyd N. Trefethen. Spectral methods in MATLAB. SIAM, 2000.
[56] Lloyd N. Trefethen and Mark Embree. Spectra and Pseudospectra: The Behavior of Nonnor- mal Matrices and Operators. Princeton University Press, 2005.
13

---

[57] Joel A. Tropp. Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Practical sketch- ing algorithms for low-rank matrix approximation. Proceedings of the Royal Society A, 473(2197):00100415, 2017.
[58] Ramon Van Handel. On the spectral norm of Gaussian random matrices. Transactions of the American Mathematical Sociery, 369(1 1):8161--8888 8178, 2017.
[59] Charles Van Loan. The sensitivity of the matrix exponential. SIAM Journal on Numerical Analysis, 14(6):971-99)))) 9-11, 1977.
[60] Van Vu. Spectral norm of random matrices. Combinatorica,, 27(6) 2007.
[61] Yu-Xiang Wang. Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differ- ential privacy and analytical moments accountant. Journal of Privacy and Confidentiality, 9(2):1-41, 2019.
[62] Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differ- entialgleichungen. Mathematische Annalen, 71(4):441-779, 1912.
[63] Christopher K. I. Williams and Matthias Seeger. Using the Nyström method speed up kernel machines. Advances in Neural Information Processing Systems (NeurIPS), volume 13, pages 682-688, 2001.
14

---

Contents
Introduction
2 Theoretical results
3
3 Proof overview
4 Empirical results
4.1 Assumption of Theorem 2.1 real-world datasets
4.2 Empirical sharpness of Theorem 2.1
5
Conclusion, limitations, and future work
10
Extension of Theorem 2.1 for an arbitrary symmetric matrix
16
B Refinements of Theorem 2.1 and Theorem A.1
18
Contour integral estimations
19
C.1 Estimating integrals over vertical segments
20
C.2 Estimating integrals over horizontal segments
21
C,3 Estimating integrals over segment
D Perturbation bound for inverse low-rank approximations via classical methods
22
Application:
Improving the convergence rate of preconditioned conjugate gradient
F Maximal allowable variance proxy
24
Discretized synthetic Hamiltonian
25
H Empirical sharpness of Theorem 2.1 -numerical results
26
Examples illustrating limitations of low-rank inverse approximation
27
L.1 Eigenvalue reordering due to small eigengaps
27
I.2 Failure of direct low-rank approximation error predict inverse error
28
J Some classical perturbation bounds
28
K Notation
28
15

---

A Extension of Theorem 2.1 for an arbitrary symmetric matrix A
In this section, we extend Theorem 2.1 the perturbation of the best rank-p approximation of the inverse when A is a symmetric matrix. To simplify the presentation, we assume that the eigenvalues (singular values) are different, so the eigenvectors (singular vectors) are well-defined (up to signs). However, our results hold for matrices with multiple eigenvalues.
For general symmetrie matrix A, interpret its collection of p-least singular values as follows.
Since -1 < 0, to make the perturbation well-defined, there exists a natural number s A S n such that
A A2 > ................................ Ak > 0> ARt1 >
An-
Hence, there an integer number 1 such that {ān, nn 1........ Fn-p+1] {Aa..i S} for . + (p k1)}.
S = (k- (k1 1). k - (k1 .).............................. k. k + 1, + 2....
In general, there is a permutation æ of [n] such that on-p = |Ampp) for all 0 S p S n 1. We have the following extension of Theorem 2.1
Theorem A.1. If 1/4| < min (dx Ōktp- onh, and Øn-p - on on-p+1 > 2 Bll then
4 El
E|
4||E||
E|
II ( A,'1l
+ AR k1 +1 11 1kkp-k
X
AK-R
|
Note that when A is not PD, Á with the cigenvalues dι 2 X2 2 .... 2 Ån not necessarily PD. And hence, the set ((
|A+tIl...., Ax-p-ku 13 may not correspond to the
least singular values of Á. This issue resolved by enforcing the singular-value gap condition
On-p On-p+1 E|I
Remark A.2. This extension is important when A has both positive and negalive eigenvalues. In real-world applications where data is often arbitrary, natural for the eigenvalues of A to span both signs. While singular value decomposition (SVD) could be used apply Theorem 2.1, sin- gular value gaps are typically small. By working directly with eigenvalues, we exploit the fact that the eigenvalue gaps Ōk-ki Nk-ki - and (p+(p-k1) Aktp-ki -Ai+p-ki+H are significantly larger than On-p - On-pt1 when An(p) Ax(x+1) < 0. For example, if >>(n--))
- -vn + log n, Az(a- p+1) /n, > (m(n-pt2) = -2v A p+3) = 2//n + log n, then
min{ōx-ki 5k } = O(vn) while On-p On-pt! = log n.
Proof of Theorem A.1
Since the spectrum of A is
A 2 A2 ... 2 A > 0> d 2... .... An
the spectrum of A is
xp 2 X k-1 2 ... 2.. >
2 - 2 ... 2 4+1'
We construct the contour follows:
r= [1] 12 UL,
in which [(u] and | are rectangles, whose vertices
rM), (co. T), (a,, (a1,-T), -T) with ap 22/ = At- to == =201;
and
ril (bo, T), (b,, T), -T), (T) -T) with = Aut1 12 = ARtP-Ri A1 - -ktp- /2, T =- 2013
and I, is segment, connecting (bo: T) and (T)
I2
piu
F2
Aetp-Artt
Avep-
Ant1
0
Ap
(z)
F4
16

---

Applying the contour bootstrapping argument, we obtain
((A-1);
4,
= 2F = 1
π / 11= (2I
A) E(2I A) A)
(3)
22(
F| + P
in which
1
F1
1 1 (=l
A) E(zl A) ||
2T T1
F
|| (2I A) - E(2I A) 1)
2π
J
1
1 A A) dz).
2T
L
Now, we going bound P. First, we split [|4] into four segments:
. Tı == {(a0. t) - T Tts
T2 == {(x,T)/oo S x - a.j.
.
TT == ((a1, 2 -T}.
14 = ((x,-7)(a 2 2 4n)
Therefore,
T.ll = - -)- A)- |d//
Notice that
111 A)- A) -1 < الا | 22
we further obtain
2TF [1]
M1 + || (N₂ + N4) + M3.
in which
M1 = Jr, | - A) F(2l - A) A)- I| |dl.
M3 == Jry || (2I - A) E - A) || |dl.
and
N = Jr. la xmi I l |d. for 1 E (2. 4).
We use the following lemmas (their proofs are delayed to Section C.I and Section C.2). Lemma A.3. Under assumptions of Theorem A.I,
Mi S 4T
X
Lemma A.4. Under assumptions of Theorem A.I,
4- My < min d 66-
Lemma A.5. Under assumptions of Theorem A.
1 N2, N4 S TE.
Together Lemma A.3, Lemma A.4, and Lemma A.5 imply
Ff1
Mi
+
My
E N2
Fl
2 F3
E 4nd
Au-
By similar manner, we also obtain
2
|
De 1k-
4
For bounding F we use the following lemma, whose proof is also delayed to Section C.3.
17

---

Lemma A.6. Under assumptions of Theorem A.I,
F <
1
00
bp
E
2x
7
Since 100 bol - |oo|
+ lbol S 201 = T, we further obtain Fl s
| a
Combining above
estimates for 1:!h! 192) and F1 finally obtain
4 EI
1
4| ++
F 2P <
X A Rn Kk-
DRRtD k1+1 1k-
which is less than the r.h.s of Theorem A.1. We complete the proof.
Remark A.7. Our approach directly extends to the case where is a symmetric PSD of rank r n (rfni-deficient). In this setting, one replaces A A and Å,1 with At (the pseudoin- verse of A), Al. and the projection of At onto the subspace corresponding to the nonzero eigen- respectively. The contour can then constructed with respect to (Dy, Ar-pt1, 0r-1) and the analysis proceeds similarly.
values Xp Ap-11....,App
B Refinements of Theorem 2.1 and Theorem A.1
By looking at the finer structure of Mj and M3, one can obtain a more nuanced bound. The key idea is to control the spectral decay of A and to take into account the interaction between E and the p-bottom eigenvectors of A. Recall the notations from the previous section. Given the eigenvalues Xn, there is an integer number ką such that
of A, A1 A2 > > 0 > 0 > Ax+1
(on, On 1, In. 0nptt1 = | E S) for
S: (k (k) 1), - (k1 2), ... k. + 1,k 2.... A (p-kk)))-
In general, there is a permutation of [n] such that .--p = |dmpp) for all 0 s
To characterize how quickly the singular values of A grow, define the doubling distance 2 (with respect to the index p) as follows. Let k - (A1 - 1) S rı S k r2 I K be the smallest integer such that 2 2/ S D4str+t1l- Set r == min F1, }2) if < k I n 1 and r == max(ri, r2] if k E {0,n), n). Define the important subset = (i k r2 2 i --ri + 1} and the interaction parameter x maxijer, |u, Euyl- The asymptotic refinement of Theorem A.1 is
the smallest integer such
that 2d, Ak-r, and let
Theorem B.1. | E|| < 8 == minndōk-kr 0k+p-k1:00m and On-p On-pt1 11 > E|, then pe
[( -.0-1-111 A,11 S OaOa-r +
|
r²x x Xe- bu- 1
x²x + |e 1bb-p-
In particular, when A is PD. the doubling distance 2 p is simply the smallest positive integer satisfying 2An-2+1 Σ An-ry and the interaction term is x == maxn-r+1s.Jsu ue Euyl The refinement of Theorem 2.1
Theorem B.2 (Refinement of Theorem 2.1). 1f4| < min (an An), then
[((Ā-)) A,-1 S
||l|| An
+
x ,3
X2
An
x² X
Comparison to EYM-N bound in the intermediate regime min 5n-p3 E When A is PD and the noise E is in the intermediate regime, our result improves upon the clas- sical bound by a factor of min A
2z }) When a Wigner random noise, with high [
A.
probability, E = (2 + o(1) n and x = O n) [60, 41, 54], this gaining factor simplifies to min O(A.)) Dor logn) yielding up to a fn-factor improvement. This achievable when the
stable rank Sr(AA (T(A-1) is ~ Ô(1) and E' is a Wigner random noise [41, 54]. As concrete example, - 40,72, 8 4/n), perturbed by the standard
consider A with spectrum {(1 Jn................... (1 (1--- -
Gaussian noise E ~ (000 I). For 6 ( (rp 11), the EYM-N bound gives O(n 01/2), whereas Theorem 2.1 yields Ö(n-1) clear levell gain.
' hides poly-log factors
18

---

Proof of Theorem B.1 This proof follows exactly the proof of Theorem A.1, except the following asymptotically finer estimates of M1 and M3- Lemma B.3. Under the assumption of Theorem B.I,
Mi
AgPa-r
Lemma B.4. Under the assumption of Theorem B.I,
M3 S 0
E
Au
Ane
Ax
Kr.
The proof's of these lemmas will be delayed the next section. Combining the estimates of N2, N₂ from Lemma A.5 with Lemma B.3 and Lemma B.4, we obtain P. at most
0
F AND Au- Pe-r
F
22 66-61
E
0
| Ca Onan-r
X
In similar manner, we also obtain
P
Onoa-r
Ell
Me+1l
Pr
+
A 1
gr
Combining these estimates with Lemma A.6 that A.l O (11F11/of),
finally obtain
F < 2F
0
F
2
+ AR+1
Ondn-r
x
anOn-r
which simplifies to
E1 Onan-r
2xx +
2 A k1 Okto
+
Nu Ak- 0k
We complete the proof.
C Contour integral estimations
In this section, we present the contour integral estimations used in the previous section: Lemma A.3, Lemma B.3, Lemma A.4, Lemma B.4 (integration over vertical segments); Lemma A.5 (integration over horizontal segments), and Lemma A.6 (integration over L-segment). We first present two technical lemmas, which are used several times the upcoming sections.
Lemma C.1. Let a, T be positive numbers such that a < Then,
S 1 dt I a.
Proof of Lemma C.1
We have
ST # dt 2 ア
Zarctan
<
Lemma C.2. Let a, b, c, T be positive numbers such that a, b, c S T. Then,
V10+a)(04~))14+) di S max(a.b.c) xmibea,
Proof of Lemma C.2 Without the loss of generality, assume that <bsc5 T. We have
ST (00044)1)))000022) dl S V1e409) di
S
(by Lemma C.I).
19

---

C.1 Estimating integrals over vertical segments
In this section, we are going estimate M1 integral over the left vertical segment (prove Lemma A.3 and Lemma B.3), and then by similar argument, we obtain the upper bound for M3 integral over the right vertical segment of I (Lemma A.4 and Lemma B.4). First, we estimate M1 as follows.
Using the spectral decomposition (zI - A) 1 = Ei=1 1==1
we can rewrite M1 as
Mi = Jr. En2i/21 z(2 (,)(2 Ay) Uiuh Eujuj |dz].
Define a set of indices
I, == k t2 212 k 1}.
and denote its complement is := [m] I,. By the triangle inequality, M, is at most
Sr. Eiser, =(e->)(e>>)) un Eujuy _
|dzl Sr. | ((=-a)te-x) ini Eujuy |dzl
+ fr, Eist,der 3(=-AM(s-X,) ind F |dz|. iELS,ET,
Consider the first term, by the triangle inequality, we have
Jr. Eijer, s(x s(x-As)(s-2)) u Eujuy us |dzl
< Enjer, Sr, -(=-Ao((=xx)) unu Eujuy dzz
|u, Blug--llu,a,
Eises, Jr.
12 1= Ay3 dz)
S Eijer, x TL V(ag-1)((an ())( - 2.)2+1)(((a 2,)3 dt.
The last inequality follows the facts that || 1, = {=1 = ao + it, -T 7T S155)) and
= jax |u] Euyl. By the construction of 11, we have
l00- A1 A
2 ag for all 1 15 i n
(4)
Thus, by Lemma C.2, the r.h.s. is at most
2x
4xr² x
equivalently,
Sr, [Ener z(2 ()=-))==2 un Eujuy Next, we bound the second term as follows
4mr2 |dzl s
(5)
X2
Sr, Eijjers a(=-A)(e- uau Euguy
|dzl
Sr. EiEr-pe u.n. z-h1
E
uiM. E Eiers
|dzl
x-
unu S fr. | EiEle x->1
w.u. || Eiere
(6)
=-x,
< | Jr, 1= minigi 1=- 2, dd)
| V /ag+12 seloueeeeellloo1111 dt.
Moreover, by the construction of I2 and the definition of r,
A |} 2 minf An-m 2 |0n - x 2 min(|a- - > I, lap
Matee
}
(7)
2
where the second inequality follows the fact & I,. Thus, by Lemma C,2, the r.h.s. most
[ x
4x Bl
20

---

It follows that
Jr. [nnee (=-Aa)(a-,,) indn Euju,
|d
1 on
An
Now we consider the last term:
fr, Eie.,.err z(s->)te- und Eu,u] [dz] 2 Jr. | mi A.)(a ddz. VEiiEE,
By (7) and (4), the r...s is
2|[i11 40 dt S E1|
(by Lemma C.2)
(9)
8
Au
It implies
Sr. EiEr,jErs ((=-,))(=X,,) Uaul E iEL,.EL,
|dz| S
BT|| on-rAk
(10)
Combining (5), (8) and (10), we finally obtain
4mr2x 12x Ell
M1 S
(11)
xE AN
This proves Lemma B.3. For Lemma A.3, directly have
Mi <
|B||
Sr, [|mmluee - |dz| S |1 8 (io+-e)x((3+e)) dl
x F 4m Ell (by Lemma C.2).
%
By similar argument, by replacing 111 by L'3 == {2 a1 it, -T S ST and replacing do by we have
M3 S
2 ardc-by
G
aion-r
Te- Ox-ba
A On-r
and
M3 <
4x [
4x [
02,,2 (AR- - 10k-A1
XR- Oz-A1
This proves Lemma B.4 and Lemma A.4.
C.2 Estimating integrals over horizontal segments
We are going to bound M2 integral over the top horizontal segment T; (prove Lemma A.5). The treatment of M4 follows similar manner. We have
N2 Jra [e] min.e(m)
1 |dl
V==+1" f ((= (17-))))777 dz (since 12 = {212 iT, S {
[ dr dx
Σ T
By similar arguments, we can prove
N4 S T2
These estimates prove Lemma A.5.
C.3 Estimating integrals over segment L
In this section, we estimate F|44, proving Lemma A.6. Recall that
F14| = 2T / 12 1xT (2T E -) |dz|,
21

---

in which L = it, bo S au). Arguing similarly to the previous sections, we also have
1 11- -)- -02l -| |dz| S
||
mills|]]] |a - >111 -2,12 dz
|a
000
||
dl
V12 T x ((t 2,)2 + T2)
bo
50g
1
S
|
7 dt
hg
100
bol
EE
T
This proves Lemma A.6.
D Perturbation bound for inverse low-rank approximations via classical methods
In this section, we present and prove the Eckart- Moounn-Mrssky--- Neumann (EYM-N) bound, as stated in Equation 2 in Section 2. Let A be symmetric positive definite (PD) matrix with eigenval- ues A 2 2 ... An 0, and let E be symmetric perturbation matrix. Define Á == A + E, and let λι 2 ... 2 A, be the eigenvalues of Á. For each 1 S S n, denote by A,, and (A-1), p the best rank-p approximations (in spectral norm) of A-1 and Å Å-1, respectively. Theorem D.1 (Eckart-Young- Moouugg-iisky--euuaaae bound). If S Xn, then
I(AA-),, - A, 8 E
2
3X An-p
Proof. Since A is PD matrix, A-1 is well-defined with the eigenvalues A, 2 An-1 2
XT > 0. Thus, by the Youutt-Yuug---aa theorem [20], we have
||A Ap A.=
By Weyl's inequality [62], we have
| 2 i\n -m 2 An In.
Together with the assumption that E < Am. this implies
in 2 A, | 2 || |-| = 31 0.
Hence, Å also a positive definite matrix. As result, A is well-defined with the eigenvalues x=1 > Xلo 2 2 - > 0. Thus, similarly, we also have
A (À (A'''))))
1 = A
Combining the above equalities with the triangle inequality, we obtain:
II(A 1
) - 1 S ( ), - A || + - - A '1 + + A7'll
(12)
+| - -- - +
Applying Weyl's inequality again, we further have
| - A 2 -| XmLpp 2 t-11 X
equivalently
3 S + - A-
(13)
Together (12) and (13) imply
[I(A-)), A 1| s 2
( + ا - -A-11)
22

---

To bound ||A-1 -A- AA
we use a Neumann series expansion. Under the assumption ||,
||
S Xn/4,
we have:
E
E
1
4||
< X
1-
/
X
1/4
3
Substituting this bound into the earlier inequality yields:
4 41
8| |ل|
2 An-p
II(A-), Ap 22
3X
An
3
E Application: Improving the convergence rate of preconditioned conjugate gradient
In this section, we analyze the convergence rate of the preconditioned conjugate gradient (PCG) method for solving Ax = b using an approximately low-rank preconditioner M. Without loss of generality, let A E R be symmetric positive definite and E R.
An effective preconditioner should (i) approximate A-1 closely and (ii) accelerate computation. In practice, the exact matrix A is rarely available; instead, one typically works with approximate version Å, obtained via rounding or sketching. Although one could in principle set M Ä-1, computing with a dense inverse is computationally expensive. A more practical choice is therefore
M +
for some small >> O, where ULUI denotes the projection onto the orthogonal complement of the subspace spanned by (A-))p- This low-rank paank-pluu-regularzaattt preconditioner has been widely adopted in various schemes, including randomized Nyström preconditioners [22], low-rank correc- tion and deflation methods [8, 10), and low-rank updates for interior-point preconditioners [25].
Let ((k) denote the PCG iterate after l steps using M, and let x* = 6 be the exact solution. A central question is: for a prescribed accuracy 0, how many iterations are required guarantee
|| (k)
x²1 <
Let E = A A, and write A - Anu where A1 2 ... Ap > 0 and {u are orthonor-
mal cigenvectors. For each 1 <iisn 1, define the spectral gap 8, := X A441. Combining the spectral perturbation bound from Theorem 2.1 with the standard PCG residual estimate yields the following result.
Corollary F.1. Under the above setting, for any given 0, if Ell < min (An 5n-p). then
=0(v
[[((k) A- <e after k k=
||ll|
Fl
|
TAT)
1og((/e)) iterations.
8n
An-
Proof. Let r%k denote the residual the je-th iteration. To achieve (+( A A-'bl < 8, we require
| ll
Se,
where | Vxl Ar.
rol
Using the standard CG residual bound,
Iirk la Polla
< 2
ReMMAj- )b we require
Vx(MA)+1>
*
Va(MA) VK(MA)
Σ 2
equivalently,
k: >
(((MA)
log(2/s).
(14)
Here, <(MA) ||MA|| -|(MA))=1| is the condition number of MA.
23

---

Analyzing k( x(MA). Given the decomposition A Ei=1 A and since M = (A-1)p +
rULUI, we can write
"
MA= = -
Σ
i.su +TULUT
Thus,
<(MA) = ((A-)))
Σ 1t-
un, -ULUIA
Since M acts as an approximate inverse on the dominant subspace and scales the complement by the smallest eigenvalue of MA is approximately TAn, while the largest is dominated by 1 + [I((A=))p AlI Hence,
), (A~1))) 1
1 + 1((((A))))
<(MA) SO
(15)
TAn
In practice, we set 7 S. A/I which ensures the complement contribution rλ1 S 1; with this choice, the bound in (15) holds up absolute constants. Equality holds approximately when the eigenvectors of (Á-1) align closely with {un {un-ptl:.... Un which is typical since A approximates A.
By Theorem 2.1, under F|| & min Anx 8n-p).
E
|((A-t) A 0
X2
on Ón-pAn-p
Substituting into (15) yields
|All
E
E
1
s RMMA) & 0
Tmn
6 p---p--pp
|||]]
Substituting this bound into (14) completes the proof.
Remark E.2. By a similar argument, the classical Eckart- Young- -e---MMis--emaaae bound (2) yields
8 E
2
-
3X2
An-p
leading to the weaker estimate
|||||
E
<(MA) S
Thn
X2
An-p
Consequently,
|A|
E
1
(1)(()) - A < after k k=
log(2/E)
iterations.
T>n
An--p
As discussed in Section 2, Theorem 2.1 improves upon the classical Eckart- Eckart-Young -Neumann bound by up a factor of nn. Consequently, Corollary E.1 improves the condition number estimate by up to the same factor, corresponding to improvement of order n2-4 in the guaranteed iteration count.
Maximal allowable variance proxy
Recall from Section 4.1 that, given matrix A. aim to report the maximal allowable variance proxy A max for the noise matrix E, such that the assumption of Theorem 2.1 holds.
We consider two real-world matrices: the 1990 US Census covariance matrix and the BCSSTK09 stiffness matrix. Fach perturbed by a random matrix E with independent, mean-zero, sub- Gaussian entries and variance proxy 2 It is well known that, with high probability, ||]]|

---

(2 + ( [58. 60]. Thus, for each matrix A and chosen integer the noise level prescribed by Theorem 2.1 valid whenever
4(2 + o(1)) min 8n-p3
which implies the variance proxy must satisfy
min An. 5n-pp
max
8V
Table reports max for each p E [1. PA.. where PA is the smallest integer such that
(A 1)p - '1 < 0.05.
||-11|
For BCSSTK09 and E {2, the eigengaps 0n-p are extremely small (below 10-9), rendering the corresponding low-rank approximations numerically unstable. We omit Amax in these positions avoid reporting unreliable values. All numerical values are presented in scientific notation. In each sub-table, we boldface the smallest reported value of A max
Table 1: Maximal allowable variance proxy max min An, 8n-p1/(Vnn) for the 1990 US Cen- (n 69, 17) and BCSSTK09 (n 1083, I ps 8). Entries are reported in scientific notation. Missing entries correspond to unstable eigengaps.
1990 US Census (n 69, $ < 17)
(b) BCSSTKO9 (n 1083, < S
P
P
1
2.18
10
4.78
10¹
2.70 X 10'
2
4.78
x 10'
11
4.78
X
101
3
4.33
x
2.37
10
10
4.43
10'
2.70
10a
4.78 x 10
10
5
3.83 x 10
6
4.37
x 10
15
2.60
10a
6
2.70 x 10*
7
4.78 x
2.79
x 10a
8
1.55
x
4.78
10
2.70 10
10"
G Discretized synthetic Hamiltonian
In this section, we describe the construction of the discretized synthetic Hamiltonian matrix used in Section 4.2. We begin with the one-dimensional quantum harmonic oscillator:
h
d²
1
mw
2m
da?
whose natural length scale is l ;== //h/mm/ Following standard knite-differenc benchmarks [55, 38], we truncate the domain to (-L, L) with homogeneous Dirichlet boundary conditions and set L Sc.
Let iL+ for 1,.... n, with step size Ar 2T./ + 1), and define the dimensionless grid points & = 2:/l and mesh size h Ar/E.
A second-order differdiffeeecce discretization of f yields an x real symmetric tridiagonal matrix H with entries
2 H 12
1
5? H
h2 (1sisn)
[2, 32]. For h - 0, the eigenvalues of H converge to the exact oscillator levels 4i + O(h?) for i [55, Program 8), so the discrete spectrum approximately linear.
Scaling, As is standard, we set h
and w 4, that - -1/4= 12,
Finally, to produce the matrix A, whose smallest eigenvalue X, and gap 5n-p are compatible with either standard Gaussian Rademacher noise, apply the scaling
A := 2/
25

---

H Empirical sharpness of Theorem 2.1 - numerical results
We numerically report the two scale-free ratios discussed in Section 4.2:
EYM-N bound
empirical error our bound
and
our bound
across various configurations (A, Fg, n. P): see Tables 2-9. These ratios reflect the comparative tightness of bounds and are invariant scaling or normalization. We omit the standard deviations here as they uniformly small and do not affect interpretation. In all experiments, the ratio EYM-N Ours
exceeds across all CΛ, while Empirical Ours
remains consistently around 0.3 0.4.
Table Relative tightness of the EYM-N bound and the empirical emoor compared to our bound on Census (n 69, p- 17) under Gaussian noise.
1.5
2.0
2.5
3.0
3.5
4.0
4.5
EYLN
5.69
3.08
3.16
266
2.33
2.10
1.92
1.78
1.67
1.32
1.50
0.433
0.395
0.454
0.473
0.401
0.461
0.443
0.427
0.455
0,402
0.446
Table Relative tightness of the EYM-N bound and the empirical error compared to our bound on Census (n2 69, 17) under Rademacher noise.
2.5
3.0
3.5
EYL-
4.26
3.07
2.47
2.11
1.87
1.69
1.57
1.47
1.39
1.32
1.27
Bnriicel
0.398
0.395
0.415
0.407
0.401
0.404
0.403
0.397
0.424
0.402
0,410
Ows
Table 4: Relative tightness of the EYM-N bound and the empirical error compared to our bound on BCSSTX09 (n 1083, p = 8) under Gaussian noise.
C
1.2
2.6
2.8
3.0
RYM-N
3.23
2.87
2.59
2.37
2.20
2,06
1.95
1.85
1.76
1.69
0.320
0.325
0.353
0,372
0.334
0.347
0.318
0.348
0.306
0.354
Ons
Table 5: Relative tightness of the EYM-N bound and the empirical error compared to our bound on BCSSTK09 (n 1083, p = 8) under Rademacher noise.
CA
1.2
1.4
2.0
2.2
2.4
2.6
2.8
3.0
2.48
2.22
2.03
1.88
1.75
1.66
1.57
1,50
1.44
1.39
Chis
Dam
0.317
0.324
0,332
0.341
0.326
0.379
0.337
0.325
0.314
0.349
Table 6: Relative tightness of the EYM-N bound and the empirical error compared to our bound on Discretized Hamiltonian (n 500, p = 10) under Gaussian noise.
Ca
10-4.00
10
10-
10
3.67
10-3.33
10
10 10-3.00
10 2.67
10- 2.33
10-2.00
10
2.00
10-1.67
10-1.33
10-1.00
RYM-N
618.2
287.9
133.8
62.53
29.38
6.84
1.99
0.301
0.326
0.331
0.346
0.321
0.318
0.339
0.338
0.309
0.371
Table Relative tightness of the EYM-N bound and the empirical error compared to our bound on Discretized Hamiltonian (n = 500, 10) under Rademacher noise.
Ca 10-1.00
10-3.67
10-3.33
10-3.00
10-2.67
1032:33
1002.00
10-1.87
10-1:33
10-1.00
EYM-N
946.6
439.6
204.0
95.06
44.54
21.04
10.10
5.05
2.69
1.60
ChEL
0.315
0.327
0.326
0.310
0.331
0.317
0.308
0.340
0.307
0.309
Own
26

---

Table Relative tightness of the EYM-N bound and the empirical error compared to our bound on Discretized Hamiltonian (n = 1000, p = 10) under Gaussian noise.
Ca 10
10-4.00
10
3.07
10-3.33
10-3.00 00
2:67
10-2.35
10-2.00
10-1.67
10-1.33
10-1.00
BYM-N
1330
617.8
287.3
133.6
62.39
29.33
13.96
6.83
3.52
1.99
Inpiised
0.317
0.334
0.373
0,336
0.347
0,310
0.322
0.314
0,330
0.349
Table 9: Relative tightness of the EYM-N bound and the empirical error compared to our bound on
Discretized Hamiltonian (n 1000, p = 10) under Rademacher noise.
CA 10
10
3.67
10 3.33
10
10
2.67
10
10
2.00
10"
10"
10
1.00
RYM-N
942.0
438.0
204.0
94.80
44.30
20.90
10.10
5.03
2.69
1.60
0.341
0.331
0.328
0.362
0.321
0.301
0.340
0.353
0.332
0.322
I Examples illustrating limitations of low-rank inverse approximation
This section presents two illustrative examples demonstrating subtle failure modes in low-rank in- verse approximation.
I.1 Eigenvalue reordering due to small eigengaps
We construct an example where a small eigenvalue gap 6n-p causes the eigenvalues of Á to reorder, making the low-rank error (|(A-)), ) A poor proxy for the global error || A 1| In fact, the ratio
|I(Ā-1), ), A '1
||-11 - A-11| - 0C
as n + co.
We illustrate this for p = 1 (the construction generalizes). Let Diagla a,) denote the diagonal matrix with entries d1,,... On- Define:
A = Diag[ (4K [alag((4<>)
1) AKV n, nl.. E Diag| Vn, 3 O, O,..., 0]. Ā A + E Diag (4K + 2), (4K + 3) n, n....,n.
Then,
The inverses are:
A Diag
(4K + 1)
4K n n n2
1
Ā Diag
(4K 3n n (4K + 2)
The best rank-1 approximations retain the top eigenvalue:
(Ā-'), Diag
(4K + 2) 0, O,.... 0
A
Diag
0, .....,0
4K /n'""
Hence,
((ā-))--A0) max
= 0
(AK + 2n 4K Anvn
4K 4K
while
- = 0
K2
Choosing K=nf. we find the ratio
||
O(n)) xc
A 14-1-A-11 A-11
27

---

1.2 Failure of direct low-rank approximation error to predict inverse error
We now give an example where the low-rank approximation error ||Ap - Appl is zero, but the inverse approximation error (A(A)))p Ap'll grows with n.
Let
= Diag
n1
2/n'
Vn"
Diag
0, 2/n"
n2
Then,
2
Ā A+ E Diag
n,
The best rank-l approximations retain the largest diagonal entry:
A = A = Diag/n, 0, ..,....) 0,.
Hence, || - A = Now consider the inverses:
vn...., n...... Vnl --1= Diag vn, vn
vn
A Diag 2/n, Vn,
2
The rank-l inverse approximations retain the largest entries:
AT = Diag(0, (0, 2/n, 0, o,....o,, (A-1); = Diag(0, vn, 0, .,....0 0).
Hence, [[(Ā-1) AT Vr. This example shows that even when the direct approximation error || Apll vanishes, the inverse approximation eтror can diverge. Consequently, bounding ||4p Apll alone is insufficient to understand the behavior of low-rank inverse approximations.
J Some classical perturbation bounds
This section recalls standard classical results referenced Section 2, Section 3, and Section D.
(Eekart-Young-Mirsk. Young-Mirsky bound [20]). Let Á E Æax", and let Ap. Ap denote their respective best rank-p approximations. Set = A A. Then,
Theorem J.1 (Eckart-
|Á Apll < 2 (o + ||]])
where ppt1 is the (p + 1)st singular value of A.
Theorem J.2 (Weyl's inequality [62]). Let A, E E paxx be symmetric, and define Ā == A E.
Then, for any < i < n,
1N. 1 X |El and |ă, oil S |
where De, de are the ith eigenvalues of and c, and o;, ā; are the corresponding singular values.
K Notation
This section collects key notations used throughout the paper. Let A, E be symmetric x matrices, and define the perturbed matrix Á == A E.
28

---

Table 10: Summary of notation used in the paper
Symbal
Definition
Dimension of A. Á
Target rank parameter
A
Best rank-p appreximation to A rank-p appreximation Á Eigenvalaes in descending order Eigenvalues of Á in descending order Singular values of in descending order 1-th eigengap: 6; A; A141 Eigenvector of A coresponding to A
(A
1)p
A1
2
An
d1 2
A.
01
0n
M4
Eigenvector of Å correpoonding X;
enclosing (An-pt1.... (p. 5)
F
|= [1=] A) (=1 4) (p.
F,
12 (2l A) [B(=] A) 11 (p.
Fi
Ix > (=l A) B(sl - A) (p.) Lem. 3.1)
min min, 6n = (Sec. 4.1)
max
Max. allowable variance:
8yR
Stable rank of A ||A-11|
sr(A !)
(p. 23)
I|A 211
Doubling distance
Smallest s.t. 2Am-p+1 2 Am-r (p. 16, B)
Interaction term
max Ju. Euyl (p. 16, Sec. B)
n-r-1151.55
||-II
Spectral
I| 1|
Frobenius norn
EYM-N bound
Eckart- Sikart-Young-BBe Toung-Mirsky-Norn bound
PD
Positive semi-definite
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction state that the paper provides the first non- asymptotic spectral-norm bounds for low-rank inverse approximations under additive noise, and the body of the paper rigorously proves and empirically validates this claim (Sections 2-4).
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings. is fine to include aspirational goals motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Section 5 (Conclusion, limitations, and future work) discusses the reliance on spectral quantities like eigengaps, the static matrix assumption, and the practical difficulty of verifying the gap condition.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed penalize honesty concerning limitations.
3. Theory assumptions and proofs
30

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All main theorems (e.g., Theorem 2.1) include clear assumptions, and full proof' are provided in Sections 3, Appendix A, Appendix and Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section 4 details the matrices used, noise models, parameter settings, evalua- tion metrics, and empirical setup to enable reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all sub- reasonable avenue for reproducibility, which may depend
missions to provide on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibiliiy. In the case of closed-source models, it may be that access to the model is limited in
31

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The data (e.g., Census and BCSSTK09) are publicly available and cited appro- priately. Code and instructions are provided in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
public/guide Sallee///ooSSSumiiiieiieee
aerionnPoicyy olicy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //iips wttpcc/pppbba.. wwwpic/gggg///iiee SodeeSummmomeemii wwwibbmmssiiooo asionPolicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Subsection 4.1 and Subsection 4.2 describe matrix dimensions, truncation ranks, noise scales, trial counts, and the methods used compute bounds.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should presented in the core the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Section 4.2 reports error bars across 100 trials as mean + standard deviation, with clear plots and captions.
Guidelines:
The answer NA means that the paper does not include experiments.
32

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors verified.
For asymmetric distributions, the authors should be careful not to show tables or fig- ures symmetric error bars that would yield results that are out of range (e.g., negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments are lightweight and run on standard CPU machines; resource requirements are described in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: :
Answer: [Yes]
Justification: The research is theoretical and empirical, uses only publicly available datasets, and conforms ethical standards.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Question:
Answer: [NA]
33

---

Justification:
This is theoretical paper on spectral norm perturbation bounds with no direct societal or ethical impact pathways.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release models or datasets with any risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All datasets (e.g., Census, BCSSTKO9) are properly cited (e.g.. [15], [36]) and are in the public domain or released under open academic licenses.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
34

---

The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode thcode com/ dataseta has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper does not introduce new datasets, models, or other assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve any human subjects crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The research does not involve human subjects and thus does not require IRB approval.
Guidelines:
35

---

The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The research does not use LLMs for any component of the core methodology.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: petts://naaee /ttpss////eeupppeeeeeeeeee http:////Caeeeennne////////1.1. for what should or should not be described.
36


Reviews:
[{"review_id": "OTGp8nWnD0", "reviewer": "Reviewer_GAri", "summary": "This paper studies perturbation bounds for low-rank matrix inverse approximation under noise. Specifically, given a symmetric matrix $A$, and noise $E$, this work studies the spectral-norm of the matrix $\\tilde{A} - A$, where $\\tilde{A} = A+E$. The goal here is to derive sharp asymptotic error bounds that scales appropriately with the eigengap, spectral decay, and noise alignment for even the smallest non-zero eigenvalues of A. The main paper studies this problem when $A$ is positive-definite, and in the appendix the authors study the general symmetric case.  The core of the analysis is the novel use of contour integral representations of matrix functions and how these are used to provide tighter error bounds. The theoretical results are complemented with empirical analysis of 2 real and one synthetic matrix, which demonstrates how well the error bounds here mimic the true error outperforming Eckart-et al-Neumann bound.", "questions": "Please refer to the Weakness section above. Given those are resolved, I would like to understand what the authors think would this result mean for problems like the Schatten-1 norm or the spectral density estimation under noisy environments.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I should preface by saying that I am not an expert in the field of random matrix theory. \n### Strengths\n- I believe the application of contour integrals for finding the smallest eigenvalues is novel, and opens the door for using this technique across other applications including but not limited to approximation of the Schatten-norms, spectral density estimation, among others.\n\n### Weaknesses\n- Equation (2) is derived in Section F. upon checking I noticed that the authors are using Weyl's inequality to bound the eigengap between $||\\tilde{A}^{-1} - \\tilde{A}||$ as $$||\\tilde{A}^{-1} - \\tilde{A}|| \\geq \\tilde{\\lambda}^{-1}_{n-p} - {\\lambda}\\_{n-p}^{-1}.$$ \n\nHowever, as far as I know Weyl's is $\\max_{i \\in [n]} |\\lambda_i^A - {\\lambda}_i^B| \\leq ||A-B||$. Are the authors using some specific Weyl's inequality? If yes, please cite it accordingly, or if there is any assumption to this statement, it should be stated in the theorem statement and not assumed in the proofs.\n\n- While the authors state the bounds are for PSDs in the main paper, the first line in Setup (line 95) assumes for $A \\in \\mathbb{R}^{n\\times n}$ that $\\lambda_1 \\geq \\ldots \\geq \\lambda_n > 0$ which is PD matrix. While $E$ is assumed to be symmetric, in Step 1 within Proof overview, eigenvalues of $\\tilde{A}$ are also assumed to be positive, which confused a bit. What is the point when $E$ cannot perturb the eigenvalues of $A$ to result in indefinite $\\tilde{A}$?\n\n- In the same line in Step 1 of Proof overview, the authors use this nice trick to swap the norm and the integrals. However $dz$ should be $|dz|$, which complicates the whole proof (I am unsure if the proof breaks though). The same issue exists in appendix $A$. Is $dz$ and $|dz|$ interchangable in this context? Surely not, right, as one has to hand two cases $\\geq 0$ and $< 0$ separately?\n\n- In line 803, the authors state that there exists some permutation of $[n]$ such that $\\sigma_{n-p} = \\lambda_{\\pi(p)}$. The $\\lambda$ here should be an absolute value, as otherwise, yes there is some perturbation when this is true, but such perturbation might not lead to consecutive values be guaranteed to be $> 2||E||$, which is a required assumption in Theorem A.1", "was_revised": true, "final_justification": "Based on the discussion I had with the authors I am willing to upgrade the score of the paper.", "rebuttal": "Thank you for your valuable comments and suggestions. We are glad that you appreciate our novel technique related to the smallest eigenvalues and that you find interested in some potential extensions of our work. Below, we address your specific question and concerns.\n### Questions:\n> Equation (2) is derived in Section F. Upon checking, I noticed that the authors are using Weyl's inequality to bound the eigengap between $\\\\| \\tilde A^{-1}-A^{-1} \\\\|$ as $\\\\|\\tilde A^{-1} -A^{-1}\\\\| \\ge\\tilde\\lambda_{n-p}^{-1} - \\lambda_{n-p}^{-1}$ . However, as far as I know Weyl's is $|\\lambda_i^{A} -\\lambda_{i}^B| \\leq \\\\|A -B\\\\|$. Are the authors using some specific Weyl's inequality? If yes, please cite it accordingly, or if there is any assumption to this statement, it should be stated in the theorem statement and not assumed in the proofs.\n\nThank you for this question and the careful reading. We apologize if the presentation was unclear and appreciate the opportunity to clarify. In Section F, we use the standard version of Weyl’s inequality as you stated. The inequality\n                             $ \\\\|\\tilde A^{-1} -A^{-1}\\\\| \\geq |\\tilde\\lambda_{n-p}^{-1} - \\lambda_{n-p}^{-1}|$\nis a direct consequence of applying Weyl's inequality to the matrices $\\tilde{A}^{-1}$ and $A^{-1}$.\n\nSince $4\\\\|E\\\\| < \\lambda_n$ and $A$ is positive definite, $\\tilde{A}$ remains positive definite as well. Therefore, $\\tilde\\lambda_{n-p}^{-1}$ and $\\lambda_{n-p}^{-1}$ are the $(p+1)^{th}$ eigenvalues of $\\tilde{A}^{-1}$ and $A^{-1}$, and Weyl's inequality applies. We will add this clarification in the proof of Section F in the final version.\n\n\n> While the authors state the bounds are for PSDs in the main paper, the first line in Setup (line 95) assumes for $A \\in \\mathbb{R}^{n \\times n}$ that $\\lambda_1 \\geq \\lambda_2 \\geq \\dots \\geq \\lambda_n > 0$, which defines a PD matrix.\n\nThank you for pointing this out. You are correct—the setup assumes that $A$ is positive definite. Indeed, when $A$ is PSD, its inverse $A^{-1}$ is well-defined only when $\\lambda_n > 0$. We will clarify this in the final version.\n\nWe would also like to note that our approach naturally extends to the case where $A$ is symmetric PSD of rank $r < n$. In this setting, we replace $A^{-1}, A_p^{-1}$, and $\\tilde A_p^{-1}$ with the pseudoinverse of $A$ and the projection of $\\tilde A^{\\dagger}$ onto the subspace corresponding to the nonzero eigenvalues $\\tilde\\lambda_r, \\tilde\\lambda_{r-1}, \\dots, \\tilde\\lambda_{r-p+1}$. The contour $\\Gamma$ can then be constructed with respect to $(\\lambda_r, \\lambda_{r-p+1}, \\delta_{r-p})$, and the analysis proceeds similarly.\n\n\n> While $\\tilde{A}$ is assumed to be symmetric, in Step 1 of the Proof Overview, its eigenvalues are also assumed to be positive. This was confusing—can $E$ not perturb the eigenvalues of $A$ to make $\\tilde{A}$ indefinite?\n\nThank you for this helpful question—we appreciate the opportunity to clarify. The assumption in Theorem 2.1 implicitly ensures that $\\tilde{A}$ remains positive definite, though we should have stated this more explicitly.\n\nIndeed, under the condition $4\\\\|E\\\\| < \\lambda_n$ from Theorem 2.1, Weyl’s inequality guarantees that all eigenvalues of $\\tilde{A}$ are at least $\\lambda_n - \\\\|E\\\\| > 3\\\\|E\\\\| > 0$, which ensures that $\\tilde{A}$ remains positive definite. We will include this clarification in the final version of the paper.\n\n\n>In the same line in Step 1 of Proof overview, the authors use this nice trick to swap the norm and the integrals. However  $dz$ should be $|dz|$ , which complicates the whole proof (I am unsure if the proof breaks though). The same issue exists in appendix . Is $dz$  and $|dz|$  interchangable in this context? Surely not, right, as one has to hand two cases $\\geq 0$  and  $< 0$ separately?\n\nThank you for catching this—we appreciate the opportunity to clarify and correct the notation.\n\nYou are absolutely right: the correct form of the inequality should use $|dz|$, in line with the standard bound  \n$$\n\\left\\\\|  \\int_{\\Gamma} f(z) \\hspace{1mm} dz \\right\\\\|  \\leq \\int_{\\Gamma} \\\\|f(z)\\\\| \\hspace{1mm} |dz|.\n$$  \nIn Step 1, we mistakenly wrote $dz$ instead of $|dz|$. Starting from line 178, the derivation should indeed switch to $|dz|$, and this is what we intended throughout. Later, in Step 3, where the rectangular contour $\\Gamma$ is explicitly constructed, we estimate each integral segment using $dt$ in place of $|dz|$, as appropriate for real-line integrals.\n\nWe will correct the notation in both the main text and the appendix in the final version. Thank you again for pointing this out.\n\n\n\n\n\n>In line 803, the authors state that there exists some permutation of $\\pi$  such that $\\sigma_{n-p}=\\lambda_{\\pi(p)}$ . The $\\lambda$  here should be an absolute value, as otherwise, yes there is some perturbation when this is true, but such perturbation might not lead to consecutive values be $> 2||E||$ guaranteed to be $> 2||E||$, which is a required assumption in Theorem A.1\n\nThank you for the question. As you correctly noted, the proper statement is $\\sigma_{n-p} = |\\lambda_{\\pi(p)}|$. We apologize for the typo and any confusion it caused. \n\nWe will fix it in the final version. \n\n### Other comments:\n> Given those are resolved, I would like to understand what the authors think this result would mean for problems like the Schatten-1 norm or spectral density estimation under noisy environments.\n\nThank you for the insightful question and suggestion. We are happy to discuss possible implications of our work in these directions.\n\n1. **Schatten-1 Norm Error**: Suppose the goal is to estimate $\\\\| \\tilde A_p^{-1} - A_p^{-1}\\\\|^{S_1}$.  Our contour-based approach can be extended to this setting. Note that\n   $$\n   \\\\|\\tilde A_p^{-1} - A_p^{-1}\\\\|^{S_1} = \\left| \\sum_{i=1}^n e_i^\\top (\\tilde A_p^{-1} - A_p^{-1}) e_i \\right| = \\left| \\int_{\\Gamma}  \\frac{1}{2\\pi i z} \\sum_{i=1}^n e_i^\\top \\left[ (zI - \\tilde{A})^{-1} - (zI - A)^{-1} \\right] e_i \\hspace{1mm} dz \\right|.$$\n\n   We can apply our contour bootstrapping technique to this integral, reducing the problem to bounding a term of the form\n\n   $$\n   F_1 = \\int_{\\Gamma} \\left|  \\frac{1}{z} \\sum_{i=1}^n e_i^\\top (zI - A)^{-1} E (zI - A)^{-1} e_i \\right| \\hspace{1mm} |dz|.\n   $$\n   While obtaining a sharp bound for this trace term may require additional assumptions or techniques, our framework provides a natural starting point for extending spectral-norm results to Schatten-1 norms. We would be happy to explore this further if there is a particular application or setting you have in mind.\n\n2. **Spectral Density Estimation**: We are not yet certain which specific formulation or model for spectral density estimation under noise you are referring to. However, our contour-based analysis and sensitivity bounds could potentially inform error guarantees in estimators that rely on smoothed spectral traces (e.g., via Chebyshev expansions or resolvent averaging). We would welcome the opportunity to discuss this direction further."}, {"review_id": "6coSKFRbP1", "reviewer": "Reviewer_Rwak", "summary": "This paper prove new perturbation bounds for $\\left\\| \\tilde{A}_p^{-1} - A_p^{-1} \\right\\|$, where $A_p$ is the best rank $p$ approximation of $A$, and $\\tilde{A} = A + E$ is a noisy version of $A$. Based on techniques involving contour integrals, the authors prove a new bound that is spectral-gap dependent and sharper than previous versions. Previously, using basic classical techniques such as the Neumann expansion and the Eckart–Young–Mirsky theorem, one can prove that \n$$\\left\\|\\left(\\tilde{A}^{-1}\\right)_p-A_p^{-1}\\right\\| \\leq 8\\|E\\|/3\\lambda\\_n^2 + 2/\\lambda\\_{n-p}$$\nUnder the additional assumption that $4\\|E\\|\\leq \\delta\\_{n-p} = \\lambda\\_{n-p} - \\lambda\\_{n-p+1}$,  the authors improve the bound to \n$$\\left\\|\\left(\\tilde{A}^{-1}\\right)_p-A_p^{-1}\\right\\| \\leq \\frac{4\\|E\\|}{\\lambda\\_n^2}+\\frac{5\\|E\\|}{\\lambda\\_{n-p} \\delta\\_{n-p}} $$\nThe key improvement is that as $\\|E\\|\\to 0$, the upper bound also goes to zero.", "questions": "n/a", "limitations": "n/a", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This paper is a pretty easy read: both the results and the proof are clearly presented. The authors basically prove a sharper perturbation bound using techniques in complex analysis. These techniques are fairly common in the numerical linear algebra literature.  However, I do think the main results presented in this work are some what expected: the new bound on the error takes into account the spectral gap, spectral decay, so it is naturally \"sharper\", because it is more specific. This is also my view of the experimental section, which shows that the author's bound is tighter that classical ones. \n\nOne other concern I have is that this is one of the only papers I've reviewed at this conference that derives a purely theoretical result for numerical linear algebra.  If judged as a applied math paper, I think the theoretical results are a bit incremental, since the baseline result here can be derived in just 3 or 4 lines, based on very classic ideas. In fact, there is not really a baseline paper to compare to, other than the bound that one can derive by using standard techniques. But on the other hand, it is also hard to view this as a machine learning paper, because the lack of direct connections to applications. Therefore, I would not recommend accepting this paper.", "was_revised": true, "final_justification": "After reading the rebuttal and other reviews, I have the updated view that applying the contour technique to a non-analytic function is indeed a novelty in this paper, and I appreciate the theoretical results more. But I still feel there is a real lack of connections to ML or any applications. A tighter bound, simply as a plug in result, can perhaps lead to a tighter analysis for some ML algorithms, but I do not see such an example in this paper. Furthermore, I would be much more positive about this result if the authors are able to demonstrate an example where this new bound can lead to new insights about either an application or an algorithm.", "rebuttal": "Thank you for the valuable comments. We address your specific points below.\n### Comments:\n> The authors basically prove a sharper perturbation bound using techniques in complex analysis. [...] the new bound on the error takes into account the spectral gap, spectral decay, so it is naturally \"sharper\", because it is more specific. This is also my view of the experimental section, which shows that the author's bound is tighter than classical ones.\n\n\n\nWe appreciate this perspective. While we fully acknowledge that the contour integral representation is a well-established tool in functional perturbation theory, our contribution lies in how we *extend and apply* this tool in a new regime.\n\nTo the best of our knowledge, our work is the first to (1) apply the contour method to a **non-analytic** function like $f(x) = 1/x$ (which lacks a convergent power series around $x = 0$), and (2) develop a **contour bootstrapping argument** that directly targets the low-curvature part of the spectrum — where classical bounds are typically loose. These aspects are central to our technique and not found in prior literature.\n\nMoreover, the improvement over classical bounds (such as those derived from the Eckart–Young–Neumann theorem or Neumann expansions) can reach up to a $\\sqrt{n}$ factor in relevant regimes. We believe this is a meaningful gain, particularly for applications in high-dimensional settings or with structured noise.\n\nThat said, we appreciate that the novelty may not have been sufficiently emphasized in the current version, and we will revise the introduction and related work sections to highlight these contributions more clearly.\n\n\n\n>[...] a purely theoretical result for numerical linear algebra. [...] the baseline result here can be derived in just 3 or 4 lines, based on very classic ideas. [...] But on the other hand, it is also hard to view this as a machine learning paper, because the lack of direct connections to applications.\n\nWe appreciate the comment and the concerns about positioning. However, we believe the contribution is both conceptually and technically novel, and relevant for ML-adjacent problems, as we outline below.\n\nWhile classical techniques can yield rough upper bounds in a few lines, they do not offer sharp, spectrum-aware guarantees in the spectral norm—particularly in the regime where the inverse is most sensitive (i.e., near small eigenvalues). To our knowledge, no prior work provides non-asymptotic, low-rank inverse perturbation bounds of the kind we establish.\n\nIn particular, the problem of approximating $A_p^{-1}$ via $\\tilde{A}_p^{-1}$ presents several distinct and nontrivial challenges:\n\n1. **Controlling the smallest singular values is delicate**, as they are highly sensitive to noise. Even small Gaussian perturbations can significantly shift or destroy the least singular value. For instance, when $E$ is a standard GOE, it is well-known that $||\\tilde{A}^{-1}|| = O(n)$ with high probability for any fixed real $n \\times n$ matrix $A$.\n\n2. **The error $||\\tilde{A}_p^{-1} - A_p^{-1}||$ is not scale-invariant**, unlike many standard perturbation measures. Determining tolerable noise levels while preserving utility is a meaningful and technically subtle question, especially in systems involving sketching, quantization, or privacy.\n\n3. **The transition from spectral gaps in $A$ to bounds on the inverse error is analytically subtle**, particularly near the tail of the spectrum, where eigengaps are narrow and easily erased by noise.\n\nOur contour bootstrapping technique was developed to address these issues directly. To the best of our knowledge, this is the first work to provide sharp, non-asymptotic spectral-norm bounds for low-rank inverse approximations—with up to a $\\sqrt{n}$ improvement over classical estimates in structured regimes.\n\nAs for application relevance: although the paper focuses on foundational results, these are directly motivated by practical challenges in ML pipelines—such as preconditioned solvers, private optimization, and low-rank kernel methods. We will add a brief discussion of such connections in the final version to make this link more explicit.\n\nWe focused this paper on resolving the core theoretical question clearly and precisely, as this problem had not previously been addressed at this level of generality. We believe this kind of rigorous, broadly applicable contribution is well aligned with NeurIPS."}, {"review_id": "R4rHr9jWvu", "reviewer": "Reviewer_Twdi", "summary": "This work provides perturbation bounds for the low-rank inverse approximation of noisy matrices, which is non-asymptotic and spectrum-adaptive. It is demonstrated that the two assumptions required for the conclusion, that the noise needs to be bounded by the smallest eigenvalue and the $(n-p)$th eigengaps, should be applicable for many real-world scenarios. The proof is accomplished by first bounding the perturbation with a contour integration, and then applying a developed contour bootstrapping and designing a bespoke counter. Empirical study shows the results are validated by some real-world cases, and are tighter than the EY–N bound.", "questions": "None.", "limitations": "The authors mentioned several limitations in the manuscript, including the spectral quality dependencies and limitation on static matrices.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This paper studies a foundamental problem with potentially wide downstream applications, including optimization, scientific computing, signal processing, etc.\n- The theoretical results are claimed to be the first non-asymptotic spectral-norm perturbation bounds for low-rank approximations of noizy matrix inversion, which provide a $sqrt(n)$-level gain compared to the previous EY-N bound.\n- Empirical results validate that the proposed bound is tighter than the previous EY-N bound.\n\nWeaknesses:\n- In the main theoretical results, besides that the noise matrix bounded by the spectrum, the matrix $A$ is required to be real symmetric and positive semi-definite, and the noise matrix $E$ is required to be symmetric. These requirements will also limit the application of the results.\n- Only several specific matrices are checked in the empirical study, including the 69-by-69 1990 US Census covariance matrix, the 1083-by-1083 BCSSTK09 stiffness matrix, and synthetic matrices from discretised Hamiltonians. Some examples with real-world applications will better demonstrate the value of this work.\n\n==========update after rebuttal============\n\nThe theoretical results are extended to general symmetric matrices in the Appendices.", "was_revised": true, "final_justification": "During the rebuttal phase, I think the solidness of the proof is further validated by rounds of discussions between authors and different reviewers. On the other hand, whether this work fits the venue well is indeed debatable. It would be nice to see some application demonstrations in machine learning, algorithm design, etc.", "rebuttal": "Thank you for your valuable comments. We are glad that you recognize the importance of the fundamental problem we study and appreciate the improvements our work provides over classical results. We address your specific remarks below.\n\n### Comments:\n>In the main theoretical results, besides that the noise matrix bounded by the spectrum, the matrix $A$ is required to be real symmetric and positive semi-definite, and the noise matrix $E$  is required to be symmetric. These requirements will also limit the application of the results.\n\nThank you for the comment. We apologize if our presentation caused any confusion. We would like to clarify that the main result in Theorem 2.1 assumes $A$ is symmetric positive definite, but the extensions provided in Appendices A and B apply to **general symmetric matrices**, without requiring $A$ to be positive semidefinite.\n\nRegarding the boundedness of the noise, the condition that $||E||$ is small relative to the spectrum of $A$ is natural and necessary: without such control, the perturbation can overwhelm the small eigenvalues or singular values of $A$, making any spectral-norm guarantee for the inverse ill-posed.\n\nWe also note that our approach extends naturally to the case where $A$ is symmetric but rank-deficient (i.e., $\\operatorname{rank}(A) = r < n$). In that setting, we work with the pseudoinverse $A^\\dagger$ and project onto the subspace corresponding to the nonzero eigenvalues $\\tilde\\lambda_r, \\tilde\\lambda_{r-1}, \\dots, \\tilde\\lambda_{r-p+1}$. The contour $\\Gamma$ is then reconstructed accordingly using $(\\lambda_r, \\lambda_{r-p+1}, \\delta_{r-p})$.\n\nWe will revise the paper to more clearly state these extensions and their assumptions in the final version.\n\n\n\n\n\n>Only several specific matrices are checked in the empirical study, including the 69-by-69 1990 US Census covariance matrix, the 1083-by-1083 BCSSTK09 stiffness matrix, and synthetic matrices from discretised Hamiltonians. Some examples with real-world applications will better demonstrate the value of this work.\n\nThank you for this helpful comment. We agree that additional real-world application examples could further illustrate the value of our results.\n\nIn this paper, our primary goal was to introduce the problem of low-rank inverse approximation under noise, address its key theoretical challenges, and present a clean and general analysis framework. We deliberately selected datasets that are diverse in structure and origin—including real-world matrices from scientific computing and statistics—to provide meaningful validation while keeping the focus on the underlying mathematical phenomena.\n\nThat said, we fully agree that exploring richer applications (e.g., in private optimization, kernel methods, or compressed solvers) is a natural next step, and we plan to pursue these directions in future work. We will revise the manuscript to clarify this motivation and scope."}, {"review_id": "l4NwzcR4N5", "reviewer": "Reviewer_oQAG", "summary": "This paper studies the spectral‐norm error between the best rank-$p$ approximations of the inverse of a symmetric matrix $A$ and its noisy observation $\\widetilde A = A + E$. The authors introduce a novel “contour bootstrapping” technique applying contour‐integral methods to the non-entire function $f(z)=1/z$ to localize resolvent expansions around the smallest eigenvalues. Under the written condition, they prove the bound which improves classical full-inverse estimates by up to a $\\sqrt n$ factor in regimes of fast spectral decay.", "questions": "- Can you propose a low-cost procedure (e.g., randomized sketch) to approximate $\\delta_{n-p}$ and $\\lambda_n$ sufficiently well to certify the gap condition without full eigendecomposition?\n- How sensitive is the bound to slight misestimation of $\\lambda_1$ or $\\delta_{n-p}$ when constructing $\\Gamma$? Have you observed any numerical instabilities?\n-  Is there a practical way to measure or bound $\\|E\\|$ within the low-curvature eigenspace to tighten the bound further in specific applications (e.g., quantization noise)?\n- Section A mentions general symmetric $A$; can your approach handle non-square or non-Hermitian matrices (e.g., via pseudospectrum)?", "limitations": "See Weaknesses", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n- The adaptation of contour‐integral (Riesz projector) methods to $f(z)=1/z$ under noise is non-trivial and addresses a gap in perturbation theory for low-rank pseudoinverses.\n- The paper connects the theory to applications (e.g., differential privacy, structural engineering) by analyzing real-world matrices and demonstrating that typical noise levels satisfy the gap condition for safe usage.\n\n**Weaknesses:**\n - The requirement $4\\|E\\| < \\delta_{n-p}$ may be hard to check in black-box or data-streaming settings, as estimating tail eigengaps can be as expensive as the inverse itself .\n- The analysis assumes a fixed matrix $A$; extensions to time-varying or adaptive contexts (e.g., iterative solvers) are not addressed.\n- While theoretically elegant, the custom rectangular contour $\\Gamma$ (Section 3) depends on spectral extremal values ($\\lambda_1,\\lambda_n,\\delta_{n-p}$); practical implementation may require careful numerical tuning and stability analysis.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and questions. We are glad that you recognize our contributions to perturbation theory for low-rank pseudoinverses and appreciate your interest in the potential connections between our theoretical results and practical applications. We address your specific points below.\n### Questions:\n> Can you propose a low-cost procedure (e.g., randomized sketch) to approximate $\\delta_{n-p}$ and $\\lambda_n$ sufficiently well to certify the gap condition without full eigendecomposition?  \n> [Related comment] The requirement $4\\\\|E\\\\| < \\delta_{n-p}$ may be hard to check in black-box or data-streaming settings, as estimating tail eigengaps can be as expensive as the inverse itself.\n\n\nThank you for this thoughtful question. We agree that efficiently estimating $\\delta_{n-p}$ and $\\lambda_n$ is important for practical use, particularly in large-scale, streaming, or black-box settings where full eigendecomposition is infeasible.\n\nFortunately, randomized Krylov subspace or Lanczos methods offer scalable ways to approximate extremal eigenvalues. For symmetric PSD matrices, applying Lanczos with a modest number of iterations can yield reliable estimates of $\\lambda_n$ and $\\lambda_{n-p}$, and hence of the eigengap $\\delta_{n-p} = \\lambda_{n-p} - \\lambda_{n-p+1}$. These methods require only matrix-vector products and scale as $O(km)$, where $k$ is the number of iterations and $m$ is the cost of a matrix-vector multiplication.\n\nWe also note that **exact evaluation of the gap condition is not always necessary**. In many practical settings—especially when the spectrum exhibits decay or separation—**coarse estimates or structural priors** (e.g., from known physical models or sketch-based spectrum summaries) are sufficient to verify the condition approximately. For example, it is often possible to use a small number of random projections or polynomial filters to check whether the tail spectrum is well-separated without resolving every eigenvalue.\n\nWe will add a brief discussion of these practical considerations in the final version.\n\n\n\n\n> How sensitive is the bound to slight misestimation of $\\delta_{n-p}$ or $\\lambda_1$ when constructing $\\Gamma$? \n> [Related comment] While theoretically elegant, the custom rectangular contour $\\Gamma$ (Section 3) depends on spectral extremal values $(\\lambda_1, \\lambda_n, \\delta_{n-p})$; practical implementation may require careful numerical tuning and stability analysis.\n\nThank you for this insightful question. As you noted, our bound and the construction of $\\Gamma$ depend on controlling $(\\lambda_n, \\lambda_{n-p}, \\delta_{n-p})$, and we agree that understanding the impact of misestimation is an important direction.\n\nOur method is robust to moderate misestimation: as long as the error in estimating $\\lambda_n$ or $\\delta_{n-p}$ is no greater than $\\\\|E\\\\|$, the bound remains valid up to a constant factor. The key condition is that the contour $\\Gamma$ must enclose exactly the eigenvalues $\\tilde\\lambda_n, \\tilde\\lambda_{n-1}, \\dots, \\tilde\\lambda_{n-p+1}$ while staying sufficiently away from all perturbed eigenvalues. This can be ensured by adjusting $\\Gamma$—e.g., shifting its left edge closer to 0 or expanding the right edge toward $\\lambda_{n-p}$. Specifically, it suffices that the distance from $\\Gamma$ to $\\lambda_n$ is at least $\\min \\\\{c \\lambda_n, \\\\|E\\\\| \\\\}$ and to $\\lambda_{n-p}$ or $\\lambda_{n-p+1}$ is at least $\\min \\\\{c \\delta_{n-p}, \\\\|E\\\\| \\\\}$ for some constant $0 < c < 1$.\n\nIf the misestimation greatly exceeds $\\\\|E\\\\|$, however, key eigenvalues such as $\\tilde\\lambda_n$ or $\\tilde\\lambda_{n-p+1}$ may approach $0$ or $\\lambda_{n-p}$ respectively, forcing $\\Gamma$ too close to these points. This can cause the bound to deteriorate due to a potential blow-up in $\\\\|(zI - A)^{-1}\\\\|$.\n\nWe will consider including a brief discussion of this stability condition in the final version and agree that further analysis of numerical tuning and adaptive contour selection is a promising direction for future work.\n\n\n\n\n> Section A mentions general symmetric $A$; can your approach handle non-square or non-Hermitian matrices (e.g., via pseudospectrum)?\n\nThank you for this thoughtful question. Yes, our approach can be extended beyond the symmetric full-rank setting in two directions:\n\n1. **Symmetric but rank-deficient matrices**:  \n   Our method extends naturally to symmetric matrices $A$ of rank $r < n$. In this setting, we use the pseudoinverse $A^\\dagger$ and work within the subspace corresponding to the nonzero eigenvalues $\\lambda_r, \\lambda_{r-1}, \\dots, \\lambda_{r-p+1}$. The contour $\\Gamma$ is then redefined in terms of $(\\lambda_r, \\lambda_{r-p+1}, \\delta_{r-p})$, and the same analysis applies by projecting $\\tilde{A}^{-1}$ accordingly.\n\n2. **Non-square or non-Hermitian matrices**:  \n   For general rectangular or non-Hermitian matrices $A$, one can embed $A$ into a symmetric matrix\n   $$\n   A' = \\begin{bmatrix} 0 & A \\\\\\ A^\\top & 0 \\end{bmatrix},\n   $$\n   which is symmetric (and Hermitian if $A$ is complex) but typically rank-deficient. Our contour-based framework then applies to $A'$, and one can recover information about $A^\\dagger$ via its singular value decomposition. This connection may also be viewed through the lens of the pseudospectrum, and we believe further exploration in this direction would be interesting.\n\nWe will add a brief note about these extensions in the final version.\n\n\n\n> Is there a practical way to measure or bound $\\\\|E\\\\|$ within the low-curvature eigenspace to tighten the bound further in specific applications (e.g., quantization noise)?\n\nThis is an excellent observation. In many applications—particularly those involving quantization or structured noise—the perturbation $E$ tends to have low energy in the low-curvature (i.e., small-eigenvalue) directions of $A$. This suggests that a refined bound depending on $\\\\|\\Pi_{>p} E \\Pi_{>p}\\\\|$, where $\\Pi_{>p}$ denotes the projection onto the tail eigenspace, could offer a tighter and more informative alternative to the global spectral norm bound. In practice, this quantity can often be estimated using a small number of random projections or empirical measurements when the noise model is known (e.g., isotropic or bounded quantization noise). We agree that incorporating such direction-sensitive refinements is a promising direction and will include a brief discussion in the future work section of the final version.\n\n### Other comments:\n> The gap $\\delta_{n-p}$ is sometimes denoted $\\delta_{n-p}$ and elsewhere $\\delta_{n-p+1}$ — please standardize.\n\nThank you for pointing out this inconsistency. We will carefully review our notation and ensure that it is used consistently throughout the paper in the final version.\n\n\n>The analysis assumes a fixed matrix $A$ ; extensions to time-varying or adaptive contexts (e.g., iterative solvers) are not addressed.\n\nThank you for the insightful comment. You are correct that our current analysis focuses on a fixed matrix $A$ and does not directly address time-varying or adaptive settings. Such extensions would indeed require leveraging additional structure specific to each application—for example, spectral stability over iterations or control over update noise in optimization routines.\n\nThat said, we believe the tools developed in this work—particularly our contour-based approach and spectrum-sensitive bounds—could serve as a foundation for analyzing robustness in iterative solvers and other adaptive contexts. We view this as a promising direction for future research and will include a note to this effect in the final version."}, {"review_id": "C5IysHAk1f", "reviewer": "Reviewer_oXWK", "summary": "This work explores the problem of bounding the error for low rank approximation of inverse of a noisy matrix. Specifically, for PSD matrix $A$ and observed noisy matrix $\\tilde{A} = A + E$, with noise matrix $E$, let $\\tilde{A_p}^{-1}$ and $A_p^{-1}$  be the best rank-$p$ approximation to $\\tilde{A}$ and $A$ respectively; the work provides an upper bound on $||\\tilde{A_p}^{-1} - A_p^{-1}||$ in terms of $||E||$, smallest eigenvalue $\\lambda_n$ and the gap in eigenvalues $\\delta_p = \\lambda_{n-p} - \\lambda_{n-p+1}$ of matrix $A$. The bounds obtained in this work are data dependent, and for certain regimes provides tighter results than previously known, under the assumption that the norm of noise matrix $||E|| \\leq \\min (\\lambda_n, \\delta_{n-p} )$. \nTo prove the bound, following up on the recent line of work, they apply contour bootstrapping to the function $f(x) = 1/x$. This involves bounding the error term by an integral over the contour that contains $p$ smallest eigenvalues of matrix $A$. The authors then bound this integral.\nThey also discuss extensions to symmetric matrices (can have negative eigenvalues) and also provide bounds for this case.\nEmpirical evidence on synthetic and real-world datasets is provided by comparing their bound and previously known bound, showing that their bounds provide better characterization of actual error.", "questions": "Please refer the previous section for discussion. No specific questions for the authors.", "limitations": "The scope of work is limited to analyzing the function $f(x) = 1/x$ and the bounds offer improved characterizations of error for certain parameter regime.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The bound obtained in this work for $||\\tilde{A_p}^{-1} - A_p^{-1}||$ is $5 \\Big( \\frac{||E||}{\\lambda_n^2} + \\frac{||E||}{\\lambda_{n-p} \\delta_{n-p}} \\Big)$ whereas the previous known bound is $ \\Big( \\frac{8||E||}{3\\lambda_n^2} + \\frac{2}{\\lambda_{n-p}} \\Big)$. As a result, their bound is better whenever $||E|| << \\delta_{n-p}$. Essentially, for small noise and large eigenvalue separation, the bound obtained in this work is better.\n\n\nThough, for instances where gap can be of the order $O(\\log{n})$, the bound obtained seems worse compared to the EY-N bound.\nFor justifying the assumption of $||E|| < \\delta_{n-p}$, the authors provide discussion assuming sub-Gaussian noise, on the variance of noise that ensures this condition w.h.p which is fine as long as $m >> n$, otherwise the permissible noise scale can be much smaller - $\\tilde{O}(1/\\sqrt{n})$. This also potentially limits the applicability of the bound for high-dimensional data, which is typically the case for modern machine learning applications.", "was_revised": true, "final_justification": "Based on the reply from authors, I am happy to upgrade the score.", "rebuttal": "Thank you for your valuable comments and suggestions. We are glad that you recognize our improvements over classical results. We address your specific questions and comments below.\n### Comments:\n>Though, for instances where gap can be of the order $O(\\log n)$  , the bound obtained seems worse compared to the EY-N bound. \n\nThank you for the comment. We fully acknowledge that our bounds do not apply in regimes where $\\delta_{n-p} < \\\\|E\\\\|$. In such cases—particularly when the gap is as small as $O(\\log n) \\ll \\Theta(\\sqrt{n}) = \\\\|E\\\\|$—our bound may indeed be weaker than the classical EY–N bound.\n\nWe would also like to note that when $\\delta_{n-p}$ is too small relative to the noise level $\\\\|E\\\\|$, the low-rank inverse $A_p^{-1}$ itself may cease to be a stable or meaningful approximation to $A^{-1}$. This behavior is illustrated in Appendix J.1, where we provide a concrete example showing that the spectral instability of small eigenvalues fundamentally limits robustness in this regime.\n\nWe will revise the manuscript to clarify this limitation more explicitly.\n\n\n\n>For justifying the assumption of $||E|| \\ll \\delta_{n-p}$ , the authors provide discussion assuming sub-Gaussian noise, on the variance of noise that ensures this condition w.h.p which is fine as long as $m \\gg n$ , otherwise the permissible noise scale can be much smaller - $\\tilde{O}(1/\\sqrt{n})$ . This also potentially limits the applicability of the bound for high-dimensional data, which is typically the case for modern machine learning applications.\n\nThank you for this helpful comment. We apologize if our presentation was unclear, and we appreciate the opportunity to clarify.\n\nIn the example discussed, we implicitly assume $m \\geq n$ so that $A^{-1}$ and $A_p^{-1}$ are well-defined. Otherwise, when $m < n$, the matrix $A = M^\\top M$ becomes rank-deficient and both $\\lambda_n$ and $\\lambda_{n-p}$ are zero for small $p$.\n\nIn such cases, one should instead consider the pseudoinverses $A^\\dagger$ and $A_p^\\dagger$. Our framework and techniques still apply, with $\\lambda_m$ and $\\delta_{m-p}$ replacing $\\lambda_n$ and $\\delta_{n-p}$, and the roles of $m$ and $n$ adjusted accordingly. In particular, under sub-Gaussian noise, when $\\\\|M\\\\|_F^2 \\gg n \\log m$, the permissible noise scale becomes $\\tilde{O}(1/\\sqrt{m})$—which is often reasonable even in high-dimensional settings.\n\nMore broadly, we note that this noise tolerance is especially relevant in sparse or structured data scenarios, where the effective energy of $M$ is concentrated. When entries of $M$ are $\\Theta(1)$ and $M$ is dense, one should expect a significantly larger permissible noise scale. The assumption remains meaningful and the bound applicable.\n\nWe will include a clarification of this point in the final version."}]

Author rebuttal:

Meta-review: This paper develops new perturbation bounds for low-rank inverse approximation under noise, using contour-integral techniques (“contour bootstrapping”) to localize resolvent expansions around the smallest eigenvalues. The main results (PSD case in the paper; general symmetric in the appendix) yield spectrum-adaptive, eigengap-dependent bounds that improve over classical Neumann/EY–N estimates in regimes of small noise and fast spectral decay, with empirical evidence on two real matrices and one synthetic example. Reviewers highlighted the conceptual novelty of applying contour methods to a non-analytic function and the potential breadth of impact (optimization, scientific computing, DP, kernel/Nyström pipelines). 

After the rebuttal and reviewers’ discussion, remaining technical questions were resolved to a satisfactory degree and the overall stance shifted to cautious support. I therefore recommend accept (likely on the weaker side). To strengthen the camera-ready, please (i) expand the practical angle: include worked examples where the new bound tightens analyses or informs algorithms (e.g., CG/MINRES, preconditioned solvers, DP, low-rank kernels), and add small-scale experiments; (ii) clarify assumptions and presentation (PSD vs. PD, symmetric/noisy cases, explicit statement of gap/noise conditions, and the norm–integral interchange), with improved figures/intuition; and (iii) address practicality questions raised by R4/R5: low-cost certification of eigengaps via randomized sketches, sensitivity to misestimation when constructing contours, and guidance on regimes where the new bounds beat EY–N vs. where they may not.
Decision: Accept (poster)