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 $\Omega(n^2)$ 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.
Introduction
In numerical linear algebra, the condition number of a matrix measures how sensitive a system is to small changes in input. If a matrix has a high condition number (it's "ill-conditioned"), algorithms like linear solvers become slow or wildly inaccurate. To explain why algorithms often work better in practice than worst-case theory suggests, researchers use smoothed analysis. This framework involves taking a "bad" input and adding a bit of random noise to see if it becomes "good."
Traditionally, this noise is "dense"—meaning every single entry in the matrix is slightly changed. However, dense noise has two major flaws:
- Computational Cost: Storing and processing $n^2$ random numbers is expensive for large matrices.
- Sparsity Destruction: If you have a sparse matrix (mostly zeros), adding dense noise turns it into a dense matrix, destroying the very structure that makes it efficient to work with.
This paper explores whether the same "smoothing" effect can be achieved using low-rank noise. Instead of changing every entry, the authors add a product of two skinny matrices ($UV^T$), which only adds a small amount of structured randomness. This approach promises significant savings in memory and computation—reducing costs from $O(n^2)$ to $O(nk)$—making it a practical tool for stabilizing large-scale sparse linear systems.
Methodology
The authors analyze the perturbation model $M + UV^T$, where $M$ is an $n \times n$ matrix of rank $n-k$, and $U, V$ are $n \times k$ random Gaussian matrices. Their mathematical approach differs significantly from previous work on dense noise:
- Breaking Row Independence: Standard proofs for dense noise rely on the fact that every row is independent. In low-rank noise, the randomness is "shared" across rows, which breaks traditional techniques like the Erdos-Littlewood-Offord inequality.
- Rotational Invariance & Schur Complements: To bypass the lack of independence, the authors use the rotational invariance of Gaussian distributions to reduce the problem to a diagonal matrix. They then use the Schur complement formula to derive an explicit representation of the inverse of the perturbed matrix, allowing them to bound the smallest singular value directly.
- Extension to Complex/Symmetric Cases: They extend these proofs to complex matrices and symmetric settings (where $U=V$).
To validate their findings, the authors use a synthetic family of sparse matrices ($M_n$) known to be extremely ill-conditioned (their smallest singular values decay exponentially with $n$). These matrices serve as a "worst-case" benchmark to test if low-rank noise can actually rescue them from numerical instability.
Key Results
The study yields several critical findings:
- Theoretical Bound: The authors provide a tail bound on the smallest singular value of the perturbed matrix. Specifically, they show that the probability of the new matrix having a tiny singular value (and thus a huge condition number) is very low, comparable to the bounds found in dense noise models.
- Numerical Validation: In experiments with $M_n$ matrices (where the condition number is $O(C^n)$), adding a rank-1 perturbation improved the condition number to a level nearly identical to that achieved by dense noise.
- Speedup: The time taken for matrix-vector products remained nearly constant (linear scaling) for rank-1 perturbations, whereas dense perturbations caused a quadratic ($n^2$) explosion in computation time.
Discussion and Insights
A surprising finding is that this "smoothing" effect fails if you use discrete noise (like Rademacher $\pm 1$ variables). If the original matrix $M$ has a very sparse structure, discrete noise might not "hit" the right spots to fix the rank deficiency. Continuous Gaussian noise is required to ensure the perturbed matrix is full rank with probability 1.
The results suggest a "Free Lunch" of stability: you don't need to perturb $n^2$ entries to stabilize a system. Perturbing just enough entries to match the "rank gap" ($k$) is sufficient. For a sparse matrix $M$, computing $(M + UV^T)x$ can be done in $Time(Mx) + O(nk)$. If $k$ is small, the overhead is negligible, but the stability gains are massive.
Limitations and Future Work
While the condition number problem was successfully addressed, the authors admit that low-rank noise is much harder to apply to other smoothed analysis problems, like the Simplex method or k-means clustering. In those cases, the lack of independence between rows makes it difficult to use standard "union bound" arguments. Future research could explore specific pivoting rules for the Simplex method that run in expected polynomial time under low-rank noise, or extending the proof to a broader class of sub-Gaussian distributions.
Summary updated