2023/02/14 by Meier, Maike, Nakatsukasa, Yuji, Townsend, Alex +1 · 4 citations
#FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2302.07202
Sketch-and-precondition techniques are efficient and popular for solving large least squares (LS) problems of the form Ax=b with A∈ℝm× n and m≫ n. This is where A is ``sketched" to a smaller matrix SA with S∈ℝ\lceil cn\rceil× m for some constant c>1 before an iterative LS solver computes the solution to Ax=b with a right preconditioner P, where P is constructed from SA. 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 (AP)z=b with x=Pz. Provided the condition number of A is smaller than the reciprocal of the unit round-off, 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.