English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Sketch-and-precondition techniques are efficient and popular for solvinglarge 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" toa smaller matrix $SA$ with $S\in\mathbb{R}^{\lceil cn\rceil\times m}$ for someconstant $c>1$ before an iterative LS solver computes the solution to $Ax=b$with a right preconditioner $P$, where $P$ is constructed from $SA$. Prominentsketch-and-precondition LS solvers are Blendenpik and LSRN. We show that thesketch-and-precondition technique in its most commonly used form is notnumerically stable for ill-conditioned LS problems. For provable and practicalbackward stability and optimal residuals, we suggest using an unpreconditionediterative 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 thismodification ensures that the computed solution has a backward error comparableto the iterative LS solver applied to a well-conditioned matrix. Using smoothedanalysis, we model floating-point rounding errors to argue that ourmodification is expected to compute a backward stable solution even forarbitrarily ill-conditioned LS problems. Additionally, we provide experimentalevidence that using the sketch-and-solve solution as a starting vector insketch-and-precondition algorithms (as suggested by Rokhlin and Tygert in 2008)should be highly preferred over the zero vector. The initialization oftenresults in much more accurate solutions -- albeit not always backward stableones.

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