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

Authors:
  • EEEthan N. Epperly
    Ethan N. Epperly
  • MMMaike Meier
    Maike Meier
  • YNYuji Nakatsukasa
    Yuji Nakatsukasa

Abstract
One of the greatest success stories of randomized algorithms for linear algebra has been the development of fast, randomized algorithms 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 FOSSILS, a fast, provably backward stable randomized least-squares solver. FOSSILS combines iterative refinement with a preconditioned iterative method applied to the normal equations, and it converges 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.