×

LSMR: an iterative algorithm for sparse least-squares problems. (English) Zbl 1232.65052

Summary: An iterative method LSMR is presented for solving linear systems \(Ax=b\) and least-squares problems \(\min \|Ax-b\|_2\), with \(A\) being sparse or a fast linear operator. LSMR is based on the Golub-Kahan bidiagonalization process. It is analytically equivalent to the MINRES method applied to the normal equation \(A^T\! Ax = A^T\! b\), so that the quantities \(\|A^T\! r_k\|\) are monotonically decreasing (where \(r_k = b - Ax_k\) is the residual for the current iterate \(x_k\)). We observe in practice that \(\|r_k\|\) also decreases monotonically, so that compared to LSQR (for which only \(\|r_k\|\) is monotonic) it is safer to terminate LSMR early. We also report some experiments with reorthogonalization.

MSC:

65F10 Iterative numerical methods for linear systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
15A06 Linear equations (linear algebraic aspects)
65F22 Ill-posedness and regularization problems in numerical linear algebra
65F25 Orthogonalization in numerical linear algebra
65F35 Numerical computation of matrix norms, conditioning, scaling
65F50 Computational methods for sparse matrices
93E24 Least squares and related methods for stochastic control systems
PDFBibTeX XMLCite
Full Text: DOI arXiv