Well-Conditioned Oblivious Perturbations in Linear Space
For algorithm designers and numerical linear algebra practitioners, this provides a practical, low-cost perturbation that achieves the same worst-case condition number improvement as Gaussian perturbations, enabling efficient smoothed analysis in linear space.
The authors propose a perturbation that requires only O(n) random numbers with O(log n) bits of precision, yet reduces the condition number of any deterministic matrix to O(n), matching Gaussian perturbations. This yields a perturbed conjugate gradient algorithm that solves an n×n linear system in linear space to arbitrarily small constant backward error using O(n) matrix-vector products.
Perturbing a deterministic $n$-dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the condition number of the input to $O(n)$, and with it the complexity of many matrix algorithms. However, when deployed algorithmically, these perturbations are expensive due to the cost of generating and storing $n^2$ Gaussian random variables. We propose a perturbation that requires generating and storing $O(n)$ random numbers in $O(\log n)$ bits of precision, and reduces the condition number of any deterministic matrix to $O(n)$, matching Gaussian perturbations. Our result in particular implies a better complexity for the perturbed conjugate gradient algorithm, showing that we can solve an $n\times n$ linear system in linear space to within an arbitrarily small constant backward error using $O(n)$ matrix-vector products. In our construction, we introduce the concept of a pattern matrix, which is a dense deterministic matrix that maps all sparse vectors into dense vectors, and we combine it with a sparse perturbation whose entries are dependent and located in a non-uniform fashion. In order to analyze this construction, we develop new techniques for lower bounding the smallest singular value of a random matrix with dependent entries.