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

Meier, M; Nakatsukasa, Y; Townsend, A; Webb, M

Journal article

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

Abstract:: Sketch-and-precondition techniques are efficient and popular for solving large least squares (LS) problems of the form 𝐴⁢𝑥=𝑏 with 𝐴∈ℝ𝑚×𝑛 and 𝑚≫𝑛. This is where 𝐴 is “sketched” to a smaller matrix 𝑆⁢𝐴 with 𝑆∈ℝ⌈𝑐⁢𝑛⌉×𝑚 for some constant 𝑐>1 before an iterative LS solver computes the solution to 𝐴⁢𝑥=𝑏 with a right preconditioner 𝑃, where 𝑃 is constructed from 𝑆⁢𝐴. 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 (𝐴⁢𝑃)⁢𝑧=𝑏 with 𝑥=𝑃⁢𝑧. Provided the condition number of 𝐴 is smaller than the reciprocal of the unit roundoff, 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 solutio

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

Meier, M., Nakatsukasa, Y., Townsend, A., & Webb, M. (2024). Are sketch-and-precondition least squares solvers numerically stable? SIAM Journal on Matrix Analysis and Applications, 45(2), 905–929.

MLA Style

Meier, M, et al. “Are Sketch-and-Precondition Least Squares Solvers Numerically Stable?” SIAM Journal on Matrix Analysis and Applications, vol. 45, no. 2, 2024, pp. 905–29.

Chicago Style

Meier, M, Y Nakatsukasa, A Townsend, and M Webb. 2024. “Are Sketch-and-Precondition Least Squares Solvers Numerically Stable?” SIAM Journal on Matrix Analysis and Applications 45 (2): 905–29.
Print