Fast randomized least‐squares solvers can be just as accurate and stable as classical direct solvers

Authors:

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.
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: