Smoothed Analysis of the Condition Number Under Low-Rank Perturbations

Rikhav Shah, Sandeep Silwal

TL;DR

Classical smoothed analysis shows that adding dense random noise makes ill-conditioned matrices well-behaved, but this destroys sparsity and demands $\Omega(n^2)$ extra time and memory. This paper proves that perturbing a rank-$(n-k)$ matrix with a low-rank Gaussian perturbation ($UV^T$ of rank $k$) guarantees a well-conditioned matrix with high probability. This requires only $O(nk)$ additional memory and preserves fast matrix-vector products.

What Problem Does This Paper Address?

In numerical linear algebra, the condition number $\kappa(M) = s_1(M) / s_n(M)$ dictates the numerical stability of matrix inversions and the convergence rate of iterative solvers like conjugate gradient descent. When $s_n(M)$ is zero or exponentially small, algorithms can fail or take an intractable number of iterations.

The framework of smoothed analysis explains why algorithms perform well in practice: real-world inputs often contain minor random noise, shifting worst-case instances into well-behaved ones. However, standard smoothed analysis injects independent dense Gaussian noise across all $n^2$ entries. This destroys any existing matrix sparsity, consumes $\Omega(n^2)$ memory to store the perturbation, and blows up the cost of computing matrix-vector products $(M + G)x$.

The authors ask: Can we restore conditioning using structured, low-rank random noise—requiring far less randomness, negligible storage, and minimal computational overhead?

Methods

Prior techniques for lower-bounding the smallest singular value $s_n$ rely heavily on row-independence (e.g., bounding the distance from one row to the hyperplane spanned by the rest via Littlewood–Offord-type anti-concentration). For low-rank perturbations $UV^T$, rows share the underlying random vectors, breaking independence.

To bypass this barrier, the authors take an algebraic route rather than an anti-concentration one:

  1. Rotational Invariance: Using the singular value decomposition $M = L D R^T$ and the rotational invariance of Gaussian matrices $U$ and $V$, the problem reduces to analyzing a non-negative diagonal matrix $D$ perturbed by $UV^T$.
  2. Schur Complement Cancellation: Partitioning $D$ and the perturbation into blocks where $D = \begin{pmatrix} 0 & 0 \\ 0 & M' \end{pmatrix}$, the authors express $(D + UV^T)^{-1}$ using the Schur complement formula. Crucially, the perturbation projection cancels out: $$I - V_{[k]}^T (U_{[k]} V_{[k]}^T)^{-1} U_{[k]} = 0$$ This eliminates the cross-terms and simplifies the Schur complement directly to $(M')^{-1}$, whose norm is simply $1 / s_{n-k}(M)$.

  3. Submatrix Singular Value Bounds: The norm of the inverse matrix is then bounded in terms of $s_{n-k}(M)$ and the extreme singular values of independent rectangular Gaussian submatrices of $U$ and $V$.

Datasets

  • Theoretical Analysis: No empirical training datasets were used.
  • Synthetic Benchmark Matrix: The authors validated their findings on a known family of ill-conditioned, sparse $n \times n$ matrices $M_n$ with ones on the anti-diagonal and the first and third off-diagonals above it. The smallest eigenvalue of $M_n$ decays exponentially as $O(n / 1.47^n)$, while its second smallest eigenvalue remains constant.

Key Insights and Ideas

  • Algebra beats probability: While shared randomness defeats standard probabilistic row-independence arguments, block-matrix algebra (the Schur complement) cancels out the dependencies cleanly.
  • Rademacher perturbations fail: Unlike dense perturbations where Gaussian noise can be replaced by sub-Gaussian distributions (like $\pm 1$ Rademacher variables), low-rank perturbations fundamentally depend on rotational invariance. If $U, V$ have Rademacher entries and $M$ has sparse singular vectors, $M + UV^T$ remains singular with constant probability.
  • Barriers in geometric smoothed analysis: Low-rank noise does not readily generalize to problems like the simplex method or $k$-means. In those settings, smoothed analysis relies on the probability of a perturbed point falling inside an $\varepsilon$-ball scaling as $\varepsilon^d$; with rank-1 noise, this probability scales only as $O(\varepsilon / \sqrt{d})$, destroying the union bounds needed for polynomial runtime proofs.

Key Results

  • Smallest Singular Value Bound (Rank $n-k$ inputs): For $M$ of rank $n-k$ ($1 \le k \le n/2$) and i.i.d. standard Gaussian $U, V \in \mathbb{R}^{n \times k}$: $$\mathbb{P}\left(s_n(M + UV^T) \le \frac{\varepsilon}{nk} s_{n-k}(M)\right) \le C\sqrt{\varepsilon} + \exp(-cn)$$
  • Complex Setting: Replacing real Gaussians with complex Gaussians sharpens the bound's failure probability from $C\sqrt{\varepsilon}$ to $C\varepsilon$.
  • Full-Rank Inputs: For an already full-rank matrix perturbed by rank-$k$ noise, the authors establish a non-singular bound that smoothly depends on $s_n(M)$.
  • Numerical Verification: On the exponential ill-conditioned benchmark ($n \le 70$), adding a rank-1 perturbation increased $s_n$ from $\approx 10^{-16}$ to $\approx 10^{-2}$—closely matching dense Gaussian perturbations while keeping matrix-vector multiply times linear ($O(n)$) instead of dense quadratic ($O(n^2)$).

Limitations and Future Work

  • Dependence on $s_{n-k}(M)$: The bound depends directly on the $(n-k)$-th singular value; if the original matrix has a cluster of near-zero singular values beyond rank $k$, the bound degrades (though the authors show this dependence is mathematically unavoidable).
  • Restricted Distributions: The core result relies strictly on rotationally invariant distributions (Gaussian); extending to discrete or general sub-Gaussian distributions requires strong incoherence/density assumptions on the singular vectors of $M$.
  • Open Problem: Proving whether a pivoting rule exists that solves the simplex method in expected polynomial time under rank-1 random perturbations of the constraint matrix remains an open question.

Summary updated

Abstract

Let M be an arbitrary n by n matrix of rank n-k. We study the condition number of M plus a low-rank perturbation UV^T where U, V are n by k random Gaussian matrices. Under some necessary assumptions, it is shown that M+UV^T is unlikely to have a large condition number. The main advantages of this kind of perturbation over the well-studied dense Gaussian perturbation, where every entry is independently perturbed, is the O(nk) cost to store U,V and the O(nk) increase in time complexity for performing the matrix-vector multiplication (M+UV^T)x. This improves the Ω(n²) space and time complexity increase required by a dense perturbation, which is especially burdensome if M is originally sparse. Our results also extend to the case where U and V have rank larger than k and to symmetric and complex settings. We also give an application to linear systems solving and perform some numerical experiments. Lastly, barriers in applying low-rank noise to other problems studied in the smoothed analysis framework are discussed.
BibTeX
@inproceedings{shah2021smoothed,
  author = {Rikhav Shah and Sandeep Silwal},
  title = {{Smoothed Analysis of the Condition Number Under Low-Rank Perturbations}},
  booktitle = {APPROX-RANDOM},
  year = {2021},
  url = {https://openreview.net/forum?id=kgB0Ac6qwa},
}

Loading related content...

Figure