Sparse Pseudospectral Shattering

Edward Zeng; Nikhil Srivastava; Rikhav Shah

arxiv: 2411.19926 · v3 · submitted 2024-11-29 · 🧮 math.PR · cs.NA· math.NA

Sparse Pseudospectral Shattering

Rikhav Shah , Nikhil Srivastava , Edward Zeng This is my paper

Pith reviewed 2026-05-23 07:55 UTC · model grok-4.3

classification 🧮 math.PR cs.NAmath.NA

keywords sparse perturbationspseudospectral shatteringeigenvector condition numbereigenvalue gapnonnormal matricesrandom matricesleast singular valuesTao-Vu method

0 comments

The pith

Perturbing O(n log² n) random entries of any matrix suffices to make its eigenvectors and eigenvalue gaps polylog-stable with high probability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that sparse random perturbations achieve the same regularization of eigenvalues and eigenvectors as dense Gaussian noise. For any n by n matrix with polynomially bounded norm, adding i.i.d. complex Gaussians to O(n log² n) randomly chosen entries produces a perturbed matrix whose eigenvector condition number and minimum eigenvalue gap are both bounded by polylog n, with high probability. The same holds with O(n^{1+α}) perturbed entries for any constant α > 0, yielding even tighter O_α(log n) bounds. A reader would care because this means minimal amounts of random noise can stabilize numerical methods for nonnormal matrices.

Core claim

Given any n×n matrix M of polynomially bounded norm, perturbing O(n log²(n)) random entries by i.i.d. complex Gaussians yields log κ_V(A)=O(polylog(n)) and log(1/η(A))=O(polylog(n)) with high probability; perturbing O(n^{1+α}) entries for constant α>0 yields the stronger O_α(log n) bounds. The proof reduces control of the eigenvector condition number to the pseudospectral area and minimum eigenvalue gap, which are further reduced to least singular value estimates on shifts of the perturbed matrix via a streamlined Tao-Vu argument specialized to sparse complex Gaussians.

What carries the argument

Reduction of κ_V(A) to pseudospectral area and minimum eigenvalue gap, controlled via the two smallest singular values of shifts of A, using a streamlined Tao-Vu least singular value argument for sparse perturbations.

If this is right

Numerical eigenvalue algorithms for non-Hermitian problems can rely on sparse noise for regularization instead of dense noise.
Stability results for pseudospectra extend to regimes where only a small fraction of entries can be perturbed.
The Tao-Vu least singular value method adapts directly to sparse complex Gaussian matrices.
For any fixed α>0 the bounds improve from polylog n to O_α(log n) once the number of perturbed entries reaches n^{1+α}.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The result suggests that many practical matrices arising from discretizations may be regularized by noise on only a logarithmic fraction of their entries.
It raises whether even fewer than O(n log² n) perturbations suffice or whether the log² n factor is necessary.
The sparse shattering may connect to the spectral behavior of sparse random matrices themselves.

Load-bearing premise

The reduction from eigenvector condition number to pseudospectral area and singular value estimates continues to hold when only a sparse subset of entries is perturbed.

What would settle it

An explicit n by n matrix of polynomial norm such that, after adding complex Gaussians to O(n log² n) random positions, the eigenvector condition number exceeds any polylog n bound with probability bounded away from zero.

read the original abstract

The eigenvalues and eigenvectors of nonnormal matrices can be unstable under perturbations of their entries. This renders an obstacle to the analysis of numerical algorithms for non-Hermitian eigenvalue problems. A recent technique to handle this issue is pseudospectral shattering [BGVKS23], showing that adding a random perturbation to any matrix has a regularizing effect on the stability of the eigenvalues and eigenvectors. Prior work has analyzed the regularizing effect of dense Gaussian perturbations, where independent noise is added to every entry of a given matrix [BVKS20, BGVKS23, BKMS21, JSS21]. We show that the same effect can be achieved by adding a sparse random perturbation. In particular, we show that given any $n\times n$ matrix $M$ of polynomially bounded norm: (a) perturbing $O(n\log^2(n))$ random entries of $M$ by adding i.i.d. complex Gaussians yields $\log\kappa_V(A)=O(\text{poly}\log(n))$ and $\log (1/\eta(A))=O(\text{poly}\log(n))$ with high probability; (b) perturbing $O(n^{1+\alpha})$ random entries of $M$ for any constant $\alpha>0$ yields $\log\kappa_V(A)=O_\alpha(\log(n))$ and $\log(1/\eta(A))=O_\alpha(\log(n))$ with high probability. Here, $\kappa_V(A)$ denotes the condition number of the eigenvectors of the perturbed matrix $A$ and $\eta(A)$ denotes its minimum eigenvalue gap. A key mechanism of the proof is to reduce the study of $\kappa_V(A)$ to control of the pseudospectral area and minimum eigenvalue gap of $A$, which are further reduced to estimates on the least two singular values of shifts of $A$. We obtain the required least singular value estimates via a streamlining of an argument of Tao and Vu [TV07] specialized to the case of sparse complex Gaussian perturbations. [Rest of abstract in pdf].

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Sparse pseudospectral shattering extends the dense case to O(n log² n) entries but the key reduction step remains uncheckable from the abstract alone.

read the letter

The punchline is that this paper claims sparse random perturbations suffice for the same regularization effect on nonnormal matrices that dense Gaussians provided in earlier work. If the details hold, it gives a cheaper way to control eigenvector condition numbers and eigenvalue gaps down to polylog factors with high probability. That is the actual novelty: prior results needed noise on every entry, while here O(n log² n) or O(n^{1+α}) entries are enough for any polynomially bounded matrix. The approach reduces the eigenvector condition number to pseudospectral area and minimum gap, then to the two smallest singular values of shifts, and handles the singular-value step by adapting Tao-Vu to the sparse complex Gaussian setting. That reduction strategy is the part that looks clean on paper. The work is useful because it directly targets the cost of the perturbation step in numerical algorithms for non-Hermitian eigenproblems. The main limitation right now is that only the abstract is available, so the precise way the Tao-Vu streamlining carries over when most entries stay zero cannot be inspected for hidden assumptions or gaps in the singular-value estimates. If that adaptation is straightforward, the central claim should be fine; if it requires extra conditions on the support or the norm, that would need to be stated clearly. No circularity or invented parameters appear in the stated argument. This is for people who already work with pseudospectral techniques or nonnormal stability and want a lower-density perturbation option. A reader who needs the explicit bounds for algorithm design would get concrete value once the proof is verified. It deserves a serious referee because the result is stated sharply, the reduction path is explicit, and the potential savings are measurable. Send the full paper to review.

Referee Report

0 major / 1 minor

Summary. The manuscript claims that sparse random perturbations suffice for pseudospectral shattering: for any n×n matrix M of polynomially bounded norm, perturbing O(n log²(n)) randomly chosen entries with i.i.d. complex Gaussians yields log κ_V(A) = O(polylog(n)) and log(1/η(A)) = O(polylog(n)) with high probability; perturbing O(n^{1+α}) entries for α>0 yields the stronger O_α(log n) bounds. The argument reduces κ_V(A) and the minimum eigenvalue gap to pseudospectral area and then to the least two singular values of shifts of A, obtained via a streamlining of the Tao-Vu argument specialized to sparse complex Gaussians.

Significance. If the central claims are established, the result would be a modest but useful extension of prior dense-perturbation results (BGVKS23 and related works), showing that far fewer random entries are needed to regularize eigenvector conditioning and eigenvalue gaps for nonnormal matrices. This could have practical value for numerical algorithms, though the significance is tempered by the absence of any explicit comparison to existing sparse-matrix techniques or quantitative constants in the polylog bounds.

minor comments (1)

The abstract states that the reduction to least singular values 'continues to hold' for sparse perturbations, but provides no equation or lemma number where this extension is justified; a reader cannot assess whether the Tao-Vu specialization introduces new error terms that affect the polylog(n) conclusion.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their summary of the manuscript and for noting that the result would be a modest but useful extension of prior dense-perturbation work if the claims hold. We address the two points raised in the significance assessment below.

read point-by-point responses

Referee: the absence of any explicit comparison to existing sparse-matrix techniques

Authors: The manuscript is a theoretical contribution establishing that sparse complex Gaussian perturbations suffice for pseudospectral shattering. We agree that situating the result against existing sparse techniques from numerical linear algebra would provide useful context. We will add a brief discussion of related sparse-matrix methods in the introduction of the revised version. revision: yes
Referee: quantitative constants in the polylog bounds

Authors: The stated bounds use O(polylog(n)) and O_α(log n) notation, which is standard to emphasize the dependence on n. Tracking explicit constants through the reductions to singular-value estimates and the streamlined Tao-Vu argument is feasible but would substantially increase the length of the paper without changing the main conclusions. We are happy to add a remark on constant dependence if the referee considers it necessary. revision: partial

Circularity Check

0 steps flagged

No circularity; relies on external Tao-Vu result

full rationale

Only the abstract is provided. It asserts that κ_V(A) and η(A) reduce to pseudospectral area, eigenvalue gap, and least singular values of shifts, with the singular-value bounds obtained by streamlining Tao-Vu [TV07] for sparse complex Gaussians. No equations, self-citations, or fitted parameters appear in the visible text, and the cited argument is external (not overlapping authors). The derivation is therefore self-contained against an independent benchmark; no step reduces by construction to the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Central claim rests on the applicability of the Tao-Vu least-singular-value technique to the sparse complex-Gaussian case after streamlining; no free parameters, new entities, or additional axioms are visible in the abstract.

axioms (1)

domain assumption Tao-Vu least singular value estimates extend to sparse complex Gaussian perturbations after streamlining
Cited as the key mechanism for obtaining the required singular-value bounds

pith-pipeline@v0.9.0 · 5882 in / 1155 out tokens · 51580 ms · 2026-05-23T07:55:20.762413+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Well-Conditioned Oblivious Perturbations in Linear Space
cs.DS 2026-04 unverdicted novelty 8.0

An O(n)-randomness perturbation combining a dense deterministic pattern matrix with a non-uniform sparse dependent perturbation reduces condition numbers to O(n) for any input matrix.