Fast randomized least‐squares solvers can be just as accurate and stable as classical direct solvers
Authors:
Top Cited Papers
- 30 September 2025
- journal article
- Published by Wiley in Communications on Pure and Applied Mathematics
- Vol. 79 (2) , 293-339
Abstract
One of the greatest success stories of randomized algorithms in linear algebra has been the development of fast, randomized solvers for highly overdetermined linear least‐squares problems. However, none of the existing algorithms is backward stable, preventing them from being deployed as drop‐in replacements for existing QR‐based solvers. This paper introduces sketch‐and‐precondition with iterative refinement (SPIR) and FOSSILS, two provably backward stable randomized least‐squares solvers. SPIR and FOSSILS combine iterative refinement with a preconditioned iterative method applied to the normal equations and converge at the same rate as existing randomized least‐squares solvers. This work offers the promise of incorporating randomized least‐squares solvers into existing software libraries while maintaining the same level of accuracy and stability as classical solvers.Keywords
All Related Versions
Funding Information
- U.S. Department of Energy
- Office of Science
- National Science Foundation (FRG 1952777)
- Office of Naval Research (BRC Award N000142412223)
- Engineering and Physical Sciences Research Council (EP/Y010086/1, EP/Y030990/1)
This publication has 46 references indexed in Scilit:
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositionsAdvances in Computational Mathematics, 2023
- Randomized numerical linear algebra: Foundations and algorithmsActa Numerica, 2020
- Faster least squares approximationNumerische Mathematik, 2010
- Fast linear algebra is stableNumerische Mathematik, 2007
- Estimation of optimal backward perturbation bounds for the linear least squares problemBIT Numerical Mathematics, 1997
- Optimal backward perturbation bounds for the linear least squares problemNumerical Linear Algebra with Applications, 1995
- Perturbation theory for pseudo-inversesBIT Numerical Mathematics, 1973
- Condition numbers and equilibration of matricesNumerische Mathematik, 1969
- Note on the iterative refinement of least squares solutionNumerische Mathematik, 1966
- Some methods of speeding up the convergence of iteration methodsUSSR Computational Mathematics and Mathematical Physics, 1964