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 |