# Well-Conditioned Oblivious Perturbations in Linear Space

arXiv: https://arxiv.org/abs/2604.23193 · HTML: https://mlsanity.com/paper/2604.23193/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 48 references that are in the map.
- First posted on arXiv 25 Apr 2026.

## Builds on (most cited first, 8 of 8)

- [Stability of the Lanczos Method for Matrix Function Approximation](https://mlsanity.com/paper/1708.07788/) (2017)
- [Polynomial time guarantees for the Burer-Monteiro method](https://mlsanity.com/paper/1912.01745/) (2019)
- [Solving Sparse Linear Systems Faster than Matrix Multiplication](https://mlsanity.com/paper/2007.10254/) (2020)
- [Smooth Nash Equilibria: Algorithms and Complexity](https://mlsanity.com/paper/2309.12226/) (2023)
- [The matrix-vector complexity of Ax=b](https://mlsanity.com/paper/2602.04842/) (2026)
- [Numerical Linear Algebra in Linear Space](https://mlsanity.com/paper/2507.02433/) (2025)
- [Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop](https://mlsanity.com/paper/2602.05394/) (2026)
- [Towards Universal Convergence of Backward Error in Linear System Solvers](https://mlsanity.com/paper/2604.16075/) (2026)

## Abstract (arXiv)

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 n2 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× 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.