LSMR: AN ITERATIVE ALGORITHM FOR SPARSE LEAST-SQUARES PROBLEMS∗

Abstract. 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 ATAx = ATb, so that the quantities ‖ATrk ‖ are monotonically decreasing (where rk = b−Axk is the residual for the current iterate xk). We observe in practice that ‖rk ‖ also decreases monotonically, so that compared to LSQR (for which only ‖rk ‖ is monotonic) it is safer to terminate LSMR early. We also report some experiments with reorthogonalization