Are sketch-and-precondition least squares solvers numerically stable?
share
Sketch-and-precondition techniques are 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∈ℝ^⌈ cn⌉× 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. Popular sketch-and-precondition LS solvers are Blendenpik and LSRN. We show that the sketch-and-precondition technique is not numerically stable for ill-conditioned LS problems. Instead, we propose using an unpreconditioned iterative LS solver on (AP)y=b with x=Py when accuracy is a concern. 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 comparable backward error to the iterative LS solver applied to a well-conditioned matrix. Using smoothed analysis, we model floating-point rounding errors to provide a convincing argument that our modification is expected to compute a backward stable solution even for arbitrarily ill-conditioned LS problems.
READ FULL TEXT