Well-Conditioned Oblivious Perturbations in Linear Space

arXiv:2604.23193v1 Announce Type: cross Abstract: 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 nimes 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.

Related

• Random Matrix Theory for Deep Learning: Beyond Eigenvalues of Linear Models
• Learning Curves and Benign Overfitting of Spectral Algorithms in Large Dimensions
• Random Matrix Theory of Early-Stopped Gradient Flow: A Transient BBP Scenario
• Gaussian Approximation for Asynchronous Q-learning

Source: arXiv cs.LG | 2026-04-28