Sketch-and-precondition techniques are popular for solving large overdetermined least squares (LS) problems. This is when a right preconditioner is constructed from a randomized 'sketch' of the matrix. In this talk, we will see that the sketch-and-precondition technique is not numerically stable for ill-conditioned LS problems. We propose a modifciation: using an unpreconditioned iterative LS solver on the preconditioned matrix. 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.
