The Farrell–Vershynin conjecture: optimal $O(\sqrt n)$ smoothed bound for $\|(D+R)^{-1}\|$ with bounded-density symmetric noise

How large can the operator norm of the inverse of a symmetric matrix become after random noise is added? Farrell and Vershynin (2016) proved that if an arbitrary deterministic symmetric matrix $D$ is perturbed by a symmetric random matrix $R$ whose independent entries have continuous distributions with densities bounded by $K$ — with no moment, centering, or variance assumptions — then $\|(D+R)^{-1}\|=O(n^2)$ with high probability, uniformly in $D$, and they conjectured that the optimal bound is $O(\sqrt n)$ with a $1/t$ tail, by analogy with Sankar–Spielman–Teng's result for non-symmetric Gaussian noise. The Gaussian case of the conjecture is settled: Bourgain's chapter settled it for GOE perturbations of an arbitrary symmetric matrix, and Aizenman, Peled, Schenker, Shamis and Sodin independently proved the full optimal GOE/GUE statement with sharp Wegner- and Minami-type eigenvalue-counting estimates and $1/t$ tails. The surviving open core is therefore: prove or refute $\mathbb{P}\{\|(D+R)^{-1}\|\ge t\sqrt n\}\le C(K)/t$ for general non-Gaussian bounded-density symmetric noise, uniformly over the deterministic part. The best known uniform bound for this case remains $O(n^2)$; noise with atoms is known to violate any such uniform bound, so the density hypothesis is essential.

Background

Smoothed analysis, introduced in the program of Spielman and Teng, studies the performance of algorithms on a worst-case input after a small amount of random noise is added. For matrix computations the relevant quantity is the condition number $\kappa(A)=\|A\|\,\|A^{-1}\|$, governed by the smallest singular value $s_n(A)=1/\|A^{-1}\|$ (for a symmetric matrix, $s_n$ is the smallest absolute value of an eigenvalue; $\|\cdot\|$ denotes the operator norm). The model problem is: given an arbitrary deterministic matrix $D$, possibly nearly singular, bound the typical size of $\|(D+R)^{-1}\|$ when $R$ is random noise, uniformly in $D$.

For non-symmetric Gaussian noise — $R$ a real Ginibre matrix, i.e. with independent $N(0,1)$ entries — Sankar, Spielman, and Teng proved that $\mathbb{P}\{\|(D+R)^{-1}\|\ge t\sqrt n\}\le 2.35/t$ for every deterministic $D$ and every $t>0$. The $\sqrt n$ scale is sharp already for $D=0$, so $O(\sqrt n)$ with a $1/t$ tail is the optimal form of such a uniform bound. For general non-symmetric noise the situation is subtler: with discrete entries the uniform bound can genuinely deteriorate as $\|D\|$ grows (Farrell and Vershynin quote an unpublished example of Rudelson with $\pm1$/0 entries and a diagonal $D$ for which $\|(D+R)^{-1}\|$ far exceeds $\sqrt n$ with constant probability), while polynomial bounds depending on $\|D\|$ were known from work in the circular-law literature (the circular law is the theorem that the eigenvalues of a large non-symmetric random matrix with independent entries of variance $1/n$ spread uniformly over the unit disk in the complex plane).

Farrell and Vershynin then studied the symmetric model, the one relevant for symmetric eigenvalue problems: $D$ an arbitrary deterministic real symmetric $n\times n$ matrix, and $R$ a random real symmetric matrix whose entries on and above the diagonal are independent with continuous distributions whose densities are bounded by a constant $K$. No moment, centering, or variance assumptions are made (since $R$ need not be centered, the deterministic part can be absorbed into the entry means, so the model is exactly 'symmetric random matrix with bounded-density entries'). They proved $\mathbb{P}\{\|(D+R)^{-1}\|\ge n^2t\}\le 8K/t$ — the first bound completely independent of $D$ in the symmetric case. The proof computes the influence of a single entry $A_{ij}$ on one entry of $A^{-1}$: by the Jacobi formula for the derivative of a determinant, each entry of $A^{-1}$ is a rational function of degree at most two in $A_{ij}$, and the density bound controls how close its poles and zeros can be, yielding a weak-$L^1$ bound per entry (a tail bound of the form $\mathbb{P}\{|X|\ge t\}\le c/t$ for a single entry of $A^{-1}$); summing the $n^2$ entries is what costs the factor $n^2$. They conjectured that the truth is the Gaussian scale: $\|(D+R)^{-1}\|=O(\sqrt n)$ with a Sankar–Spielman–Teng-type tail, uniformly in $D$.

The Gaussian case of this conjecture is now settled. Bourgain's chapter announced the settlement for perturbation by a GOE element (the Gaussian Orthogonal Ensemble: the probability distribution on real symmetric matrices with independent Gaussian entries on and above the diagonal, invariant under orthogonal conjugation). Independently, Aizenman, Peled, Schenker, Shamis, and Sodin proved the complete optimal statement for GOE and GUE (the complex Hermitian analogue): for $H=A+V$ with $V$ a normalized GOE/GUE matrix and $A$ an arbitrary deterministic symmetric (Hermitian) matrix, $\mathbb{P}\{\|H^{-1}\|_{op}\ge tN\}\le C/t$ uniformly in $A$ and $N$, together with a Wegner-type estimate $\mathbb{E}N(I)\le CN|I|$ on the mean number of eigenvalues in an interval (a Wegner estimate, named after the random-Schrödinger-operator literature, bounds eigenvalue counts in intervals and here plays the role of a density-of-states bound), Minami-type bounds on multiple eigenvalues in an interval (a Minami estimate controls the probability that several eigenvalues fall in one short interval), and matching examples showing all bounds are saturated up to multiplicative constants. In the normalization of Farrell and Vershynin this is exactly the conjectured $\mathbb{P}\{\|(D+R)^{-1}\|\ge t\sqrt n\}\le C/t$, with the optimal rate and the optimal tail exponent. The non-symmetric analogue for general continuous noise is also known (Tikhomirov: $\mathbb{P}\{s_n(A+M)\le t\,n^{-1/2}\}\le C't$ for any fixed $A$ and noise with independent rows and sufficiently regular continuous distributions).

What remains open is the general non-Gaussian symmetric case. The obstacles are structural: symmetry couples rows and columns, so the distance-to-subspace arguments of the non-symmetric theory do not apply; the Gaussian resolutions rest on orthogonal/unitary invariance and explicit formulas for invariant ensembles, unavailable for general densities; the required uniformity in $D$ with no norm bound, and the absence of moment assumptions (entries may be arbitrarily heavy-tailed), block local-law and resolvent methods for deformed Wigner matrices (a Wigner matrix is the standard random-matrix model of symmetric noise: a symmetric random matrix whose entries on and above the diagonal are independent centered random variables; a deformed Wigner matrix is a Wigner matrix plus a deterministic shift; a local law is a statement that the resolvent $(A-zI)^{-1}$ of the random matrix is, with high probability, uniformly close to a deterministic limit, and it is the standard tool for locating eigenvalues); and the entrywise influence argument of Farrell and Vershynin loses a factor of order $n^{3/2}$ when the entrywise bounds are combined. Equivalently, what is missing is an optimal-scale single-eigenvalue ($k=1$) counting (Wegner) estimate for deformed Wigner matrices with merely bounded-density entries; the known repulsion estimates of Nguyen for Wigner matrices under arbitrary deterministic perturbation are vacuous at $k=1$, the only case that governs the inverse norm.

Problem Statement

Let $K<\infty$ be fixed. For each $n\ge1$, let $D$ be an arbitrary deterministic real symmetric $n\times n$ matrix (with no bound on $\|D\|$), and let $R$ be a random real symmetric $n\times n$ matrix whose entries $\{R_{ij}:1\le i\le j\le n\}$ are independent random variables with continuous distributions whose densities are bounded by $K$; no moment, centering, or variance assumptions are made on the entries (the Hermitian analogue is immediate). Prove or disprove the conjecture of Farrell and Vershynin: there exists a constant $C=C(K)$, depending on nothing but $K$, such that for all $n$, all such $D$ and $R$, and all $t>0$,

$$\mathbb{P}\bigl\{\|(D+R)^{-1}\|\ge t\sqrt n\bigr\}\le\frac{C}{t},$$

where $\|\cdot\|$ is the operator norm. Equivalently, $\mathbb{P}\{s_n(D+R)\le\varepsilon/\sqrt n\}\le C\varepsilon$ for every $\varepsilon>0$, where $s_n$ denotes the smallest singular value; in particular the conjecture asserts that $\|(D+R)^{-1}\|=O(\sqrt n)$ with high probability, uniformly over the deterministic part and over all ensembles with density bound $K$. The Gaussian case of this statement ($R$ drawn, up to scaling, from the Gaussian Orthogonal Ensemble or its complex Hermitian analogue, the Gaussian Unitary Ensemble — the orthogonally and unitarily invariant Gaussian ensembles of real symmetric and complex Hermitian matrices) is already settled — by Bourgain's chapter for GOE perturbations and, in full optimal form with $1/t$ tails and sharp constants, by Aizenman–Peled–Schenker–Shamis–Sodin — so the open content is precisely non-Gaussian bounded-density noise; noise with atoms is known to violate any such uniform bound, so a regularity hypothesis of this type is necessary, and a refutation must exhibit a bounded-density ensemble (and deterministic matrices $D_n$) for which the conjectured inequality fails.

References

1. Jean Bourgain, "On a Problem of Farrell and Vershynin in Random Matrix Theory", in Bo'az Klartag and Emanuel Milman (eds.), Geometric Aspects of Functional Analysis, Israel Seminar (GAFA 2014–2016), Lecture Notes in Mathematics 2169, Springer, Cham, 2017, pp. 65–69. DOI: 10.1007/978-3-319-45282-1_5, https://doi.org/10.1007/978-3-319-45282-1_5.
2. Brendan Farrell and Roman Vershynin, "Smoothed analysis of symmetric random matrices with continuous distributions", Proceedings of the American Mathematical Society 144 (2016), no. 5, 2257–2261. DOI: 10.1090/proc/12844, https://doi.org/10.1090/proc/12844; preprint arXiv:1212.3531, https://arxiv.org/abs/1212.3531.
3. Michael Aizenman, Ron Peled, Jeffrey Schenker, Mira Shamis, and Sasha Sodin, "Matrix regularizing effects of Gaussian perturbations", Communications in Contemporary Mathematics 19 (2017), no. 3, 1750028. DOI: 10.1142/S0219199717500286, https://doi.org/10.1142/S0219199717500286; preprint arXiv:1509.01799, https://arxiv.org/abs/1509.01799.
4. Arvind Sankar, Daniel A. Spielman, and Shang-Hua Teng, "Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices", SIAM Journal on Matrix Analysis and Applications 28 (2006), no. 2, 446–476. DOI: 10.1137/S0895479803436202, https://doi.org/10.1137/S0895479803436202.
5. Daniel A. Spielman and Shang-Hua Teng, "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time", Journal of the ACM 51 (2004), no. 3, 385–463. DOI: 10.1145/990308.990310, https://doi.org/10.1145/990308.990310.
6. 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 (2022), no. 2, 369–388. DOI: 10.1112/blms.12561, https://doi.org/10.1112/blms.12561; preprint arXiv:2009.01699, https://arxiv.org/abs/2009.01699.
7. Hoi H. Nguyen, "Random matrices: Overcrowding estimates for the spectrum", Journal of Functional Analysis 275 (2018), no. 8, 2197–2224. DOI: 10.1016/j.jfa.2018.06.010, https://doi.org/10.1016/j.jfa.2018.06.010; preprint arXiv:1709.06682, https://arxiv.org/abs/1709.06682.
8. Rowan Killip and Monica Vişan, "Sonin's argument, the shape of solitons, and the most stably singular matrix", 2018. arXiv:1811.01836, https://arxiv.org/abs/1811.01836.
9. Konstantin Tikhomirov, "Invertibility via distance for noncentered random matrices with continuous distributions", Random Structures & Algorithms 57 (2020), no. 2, 526–562. DOI: 10.1002/rsa.20920, https://doi.org/10.1002/rsa.20920; preprint arXiv:1707.09656, https://arxiv.org/abs/1707.09656, whose preprint title is spelled "Invertibility via distance for non-centered random matrices with continuous distributions".
10. Phuc Tran and Van Vu, "Eigenvalue stability and new perturbation bounds for the extremal eigenvalues of a matrix", 2026. arXiv:2603.19758, https://arxiv.org/abs/2603.19758, DOI: 10.48550/arXiv.2603.19758.
11. László Erdős and Hong Chang Ji, "Wegner estimate and upper bound on the eigenvalue condition number of non-Hermitian random matrices", Communications on Pure and Applied Mathematics 77 (2024), no. 9, 3785–3840. DOI: 10.1002/cpa.22201, https://doi.org/10.1002/cpa.22201; preprint arXiv:2301.04981, https://arxiv.org/abs/2301.04981.