Are Sketch-and-Precondition Least Squares Solvers Numerically Stable?
Maike Meier, Yuji Nakatsukasa, Alex Townsend, Marcus G. T. Webb · SIAM Journal on Matrix Analysis and Applications · 2024
Abstract. Sketch-and-precondition techniques are efficient and popular for solving large least squares (LS) problems of the form [Formula: see text] with [Formula: see text] and [Formula: see text]. This is where [Formula: see text] is “sketched” to a smaller matrix [Formula: see text] with [Formula: see text] for some constant [Formula: see text] before an iterative LS solver computes the solution to [Formula: see text] with a right preconditioner [Formula: see text], where [Formula: see text] is constructed from [Formula: see text]. Prominent sketch-and-precondition LS solvers are Blendenpik and LSRN. We show that the sketch-and-precondition technique in its most commonly used form is not numerically stable for ill-conditioned LS problems. For provable and practical backward stability and optimal residuals, we suggest using an unpreconditioned iterative LS solver on [Formula: see text] with [Formula: see text]. Provided the condition number of [Formula: see text] is smaller than the reciprocal of the unit roundoff, we show that this modification ensures that the computed solution has a backward error comparable to the iterative LS solver applied to a well-conditioned matrix. Using smoothed analysis, we model floating-point rounding errors to argue that our modification is expected to compute a backward stable solution even for arbitrarily ill-conditioned LS problems. Additionally, we provide experimental evidence that using the sketch-and-solve solution as a starting vector in sketch-and-precondition algorithms (as suggested by Rokhlin and Tygert in 2008) should be highly preferred over the zero vector. The initialization often results in much more accurate solutions—albeit not always backward stable ones.