When Does Sketching Suffice? Backward Stability in Randomized Least Squares

Abstract

Randomized sketching methods for overdetermined least-squares problems can reduce computational cost substantially relative to dense QR, but their numerical reliability is not yet fully understood in practice. This thesis studies when sketch-and-solve alone is sufficient to achieve backward stability and when iterative refinement is necessary. In particular, we compare sketch-and-precondition, sketch-and-precondition with iterative refinement (SPIR), and fast optimal stable sketchy iterative least squares (FOSSILS) across a systematic sweep of condition numbers κ ∈ {10^3 , . . . , 10^14}, aspect ratios m/n ∈ {10, . . . , 250}, residual sizes, and two noise models: one in which only b is perturbed and one in which both A and b are perturbed, for a total of 840 configurations. We complement the synthetic study with targeted follow-up experiments and real-data validation on SuiteSparse and LIBSVM matrices. The central empirical finding is that, within the tested regimes, the noise model is the main factor governing backward stability, while condition number and aspect ratio have little effect on pass rates. When only b is noisy, sketch-and-precondition with a warm start achieves backward stability in 96% of configurations, indicating that expensive iterative refinement is usually unnecessary. However, when A is also noisy, SPIR is the only method that remains reliably backward stable across the tested configurations. FOSSILS fails in about 10% of cases, and sketch-only methods fail throughout. These results provide practical guidance for selecting randomized least-squares solvers when both efficiency and certifiable numerical accuracy matter.