Are sketch-and-precondition least squares solvers numerically stable?

DOI10.1137/23M1551973MaRDI QIDQ6426449zbMATH OpenFDO

Authors Maike Meier, Yuji Nakatsukasa, Alex Townsend, Marcus Webb

Publication date 14 February 2023

Full work available at URL https://doi.org/10.1137/23M1551973

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Abstract: Sketch-and-precondition techniques are popular for solving large least squares (LS) problems of the form $Ax=b$ with $Ainmathbb{R}^{mimesn}$ and $mggn$. This is where $A$ is ``sketched" to a smaller matrix $SA$ with $Sinmathbb{R}^{lceilcnceilimesm}$ 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.

Recommendations

• Fast and forward stable randomized algorithms for linear least-squares problems
• M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
• A statistical perspective on randomized sketching for ordinary least-squares
• Preconditioning linear least-squares problems by identifying a basis matrix
• LSRN: A parallel iterative solver for strongly over- or underdetermined systems

Cited in

(10)

• Fast and forward stable randomized algorithms for linear least-squares problems
• Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers
• TT-LSQR for tensor least squares problems and application to data mining
• Randomized and inner-product free Krylov methods for large-scale inverse problems
• Two-sided preconditioned CGLS for the solution of factorized linear systems
• Optimal backward error of a total least squares and its randomized algorithms
• Mixed precision sketching for least-squares problems and its application in GMRES-based iterative refinement
• Sparse linear least-squares problems
• Stable algorithms for general linear systems by preconditioning the normal equations
• Robust, randomized preconditioning for kernel ridge regression

This page was built for publication: Are sketch-and-precondition least squares solvers numerically stable?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426449)