  Sketch-and-precondition techniques are efficient and popular for solving
large least squares (LS) problems of the form $Ax=b$ with
$A\in\mathbb{R}^{m\times n}$ and $m\gg n$. This is where $A$ is ``sketched" to
a smaller matrix $SA$ with $S\in\mathbb{R}^{\lceil cn\rceil\times 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.
