David C.-L. Fong
LSMR: An iterative algorithm for least-squares problems

121 Campus Dr
Apt 1109B
Stanford
CA 94305
clfong@stanford.edu
Michael A. Saunders

An iterative method is presented for solving linear systems $Ax=b$ and $\min \Vert Ax-b\Vert _2$, with $A$ being large and sparse, or a fast linear operator. The method is based on the Golub-Kahan bidiagonalization process. It is analytically equivalent to the standard method of MINRES applied to the normal equation $A^T\!Ax = A^T\!b$, so that the quantities $\Vert A^T\!r_k\Vert$ are monotonically decreasing (where $r_k = b - Ax_k$ is the residual for the current iterate $x_k$). In practice we observe that $\Vert r_k\Vert$ also decreases monotonically. Compared to LSQR, for which only $\Vert r_k\Vert$ is monotonic, it is safer to terminate LSMR early.