Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers
<|reference_start|>Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers: 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 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.<|reference_end|>
@article{epperly2024fast,
    title={Fast randomized least-squares solvers can be just as accurate and stable
  as classical direct solvers},
    author={Ethan N. Epperly, Maike Meier, Yuji Nakatsukasa},
    journal={arXiv preprint arXiv:2406.03468},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.03468},
    primaryClass={math.NA cs.NA}
}