LSMR: An Iterative Algorithm for Sparse Least-Squares Problems

DOI10.1137/10079687XMaRDI QIDQ3116469zbMATH OpenOpenAlexFDO

Authors David Chin-Lung Fong, Michael A. Saunders

Publication date 23 February 2012

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.0758

zbMATH Keywords

conjugate-gradient methodgolub-kahan processiterative methodKrylov subspace methodleast-squares problemLSQRminimum-residual methodMINRESsparse matrix

Mathematics Subject Classification ID

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

Abstract: An iterative method LSMR is presented for solving linear systems $Ax=b$ and least-squares problem $minorm{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 $ormAT{r}_k$ are monotonically decreasing (where $r_k=b-A{x}_k$ is the residual for the current iterate $x_k$). In practice we observe that $orm{r}_k$ also decreases monotonically. Compared to LSQR, for which only $orm{r}_k$ is monotonic, it is safer to terminate LSMR early. Improvements for the new iterative method in the presence of extra available memory are also explored.

Recommendations

• scientific article; zbMATH DE number 1222467
• An iteratively reweighted least squares algorithm for sparse regularization
• Some properties of LSQR for large sparse linear least squares problems
• An algorithm for solving sparse nonlinear least squares problems
• Iteratively reweighted least squares minimization for sparse recovery
• scientific article; zbMATH DE number 1953446
• Application of a new accelerating Bregman iterative algorithm in the sparse least squares problems
• SIRT- and CG-type methods for the iterative solution of sparse linear least-squares problems
• LSLQ: an iterative method for linear least-squares with an error minimization property
• LU-decomposition with iterative refinement for solving sparse linear systems

Cited in

(only showing first 100 items - show all)

• A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows
• Dual-loop iterative optimal control for the finite horizon LQR problem with unknown dynamics
• An evaluation of linear and non-linear models of expressive dynamics in classical piano and symphonic music
• Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework
• A pairwise-relaxing incompressible smoothed particle hydrodynamics scheme
• Vector extrapolation based Landweber method for discrete ill-posed problems
• Two new efficient iterative regularization methods for image restoration problems
• A flow perspective on nonlinear least-squares problems
• Structure in loss of orthogonality
• A least squares approach for saddle point problems
• A stabilized GMRES method for singular and severely ill-conditioned systems of linear equations
• GMRES methods for tomographic reconstruction with an unmatched back projector
• Hierarchical orthogonal factorization: sparse least squares problems
• Estimating the backward error for the least-squares problem with multiple right-hand sides
• An ALE pairwise-relaxing meshless method for compressible flows
• Flexible GMRES for total variation regularization
• A new iterative model updating technique based on least squares minimal residual method using measured modal data
• Error bounds for computed least squares estimators
• Global least squares methods based on tensor form to solve a class of generalized Sylvester tensor equations
• Preconditioners for rank deficient least squares problems
• Approximation accuracy of the Krylov subspaces for linear discrete ill-posed problems
• LSMR iterative method for solving one- and two-dimensional linear Fredholm integral equations
• LSMR iterative method for general coupled matrix equations
• Multidirectional subspace expansion for one-parameter and multiparameter Tikhonov regularization
• Global LSMR(Gl-LSMR) method for solving general linear systems with several right-hand sides
• Noise representation in residuals of LSQR, LSMR, and CRAIG regularization
• Weighted conjugate gradient-type methods for solving quadrature discretization of Fredholm integral equations of the first kind
• LSMR
• Implicitly restarting the LSQR algorithm
• Discrete vector calculus and Helmholtz Hodge decomposition for classical finite difference summation by parts operators
• A variational discrete element method for the computation of Cosserat elasticity
• A penalty method for PDE-constrained optimization in inverse problems
• Incremental regularized least squares for dimensionality reduction of large-scale data
• Numerical equivalences among Krylov subspace algorithms for skew-symmetric matrices
• Testing matrix function algorithms using identities
• Matrix-free convex optimization modeling
• Hybrid and iteratively reweighted regularization by unbiased predictive risk and weighted GCV for projected systems
• LSLQ: an iterative method for linear least-squares with an error minimization property
• Projection method for eigenvalue problems of linear nonsquare matrix pencils
• A hybrid LSMR algorithm for large-scale Tikhonov regularization
• A matching pursuit approach to solenoidal filtering of three-dimensional velocity measurements
• An augmented LSQR method
• Simple backward error bounds for linear least-squares problems
• SPMR: A family of saddle-point minimum residual solvers
• The attenuated geodesic x-ray transform
• A new implementation of LSMR algorithm for the quaternionic least squares problem
• LSMB: minimizing the backward error for least-squares problems
• Solving mixed sparse-dense linear least-squares problems by preconditioned iterative methods
• Preconditioning and Iterative Solution of All-at-Once Systems for Evolutionary Partial Differential Equations
• An iteratively reweighted least squares algorithm for sparse regularization
• A regularized factorization-free method for equality-constrained optimization
• A collaborative neighbor representation based face recognition algorithm
• <scp>TriCG</scp> and <scp>TriMR</scp>: Two Iterative Methods for Symmetric Quasi-definite Systems
• Large-Scale Optimization with Linear Equality Constraints Using Reduced Compact Representation
• A block preconditioner for the Gl-LSMR algorithm
• Approximate Generalized Inverses with Iterative Refinement for \epsilon-Accurate Preconditioning of Singular Systems
• scientific article; zbMATH DE number 7625175 (Why is no real title available?)
• A Computational Study of Using Black-box QR Solvers for Large-scale Sparse-dense Linear Least Squares Problems
• Semi-Infinite Linear Regression and Its Applications
• Block conjugate gradient algorithms for least squares problems
• An alternative method for SPP with full rank (2,1)-block matrix and nonzero right-hand side vector
• Random walks on simplicial complexes and the normalized Hodge 1-Laplacian
• Regularization properties of LSQR for linear discrete ill-posed problems in the multiple singular value case and best, near best and general low rank approximations
• Iterative algorithms for least-squares solutions of a quaternion matrix equation
• An inner-outer iterative method for edge preservation in image restoration and reconstruction
• Sharp 2-norm error bounds for LSQR and the conjugate gradient method
• The AZ algorithm for least squares systems with a known incomplete generalized inverse
• A robust algorithm for semidefinite programming
• Accuracy of the Lanczos process for the eigenproblem and solution of equations
• The Conjugate Residual Method in Linesearch and Trust-Region Methods
• Flexible Krylov methods for \(\ell_p\) regularization
• A tridiagonalization method for symmetric saddle-point systems
• Convergence of inner-iteration GMRES methods for rank-deficient least squares problems
• A framework for regularization via operator approximation
• An Active-Set Method for Quadratic Programming Based On Sequential Hot-Starts
• On Using Cholesky-Based Factorizations and Regularization for Solving Rank-Deficient Sparse Linear Least-Squares Problems
• Generalized Hybrid Iterative Methods for Large-Scale Bayesian Inverse Problems
• Goal-oriented optimal approximations of Bayesian linear inverse problems
• Proximal distance algorithms: theory and practice
• Algorithm 937: MINRES-QLP for symmetric and Hermitian linear equations and least-squares problems
• A block bidiagonalization method for fixed-accuracy low-rank matrix approximation
• PLSS: A Projected Linear Systems Solver
• Space‐local reduced‐order bases for accelerating reduced‐order models through sparsity
• Properties of semi-conjugate gradient methods for solving unsymmetric positive definite linear systems
• Alternating cyclic vector extrapolation technique for accelerating nonlinear optimization algorithms and fixed-point mapping applications
• Preconditioners for Krylov subspace methods: An overview
• Quantifying the structural stability of simplicial homology
• Analyzing vector orthogonalization algorithms
• Predicting chaotic statistics with unstable invariant tori
• Robust linear algebra
• Optimization of random feature method in the high-precision regime
• Estimating error norms in CG-like algorithms for least-squares and least-norm problems
• Scalable adaptive cubic regularization methods
• On Krylov subspace methods for skew-symmetric and shifted skew-symmetric linear systems
• High-dimensional multivariate geostatistics: a Bayesian matrix-normal approach
• The regularized global GMERR method for solving large-scale linear discrete ill-posed problems
• Developing LSQR method for Sylvester quaternion tensor equations
• The least squares solution of inconsistent discretized elliptic problems using the FETI method.
• High-precision randomized preconditioned iterative methods for the random feature method
• Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers

Describes a project that uses

Uses Software

• mctoolbox
• PROPACK
• SparseMatrix
• LSQR

This page was built for publication: LSMR: An Iterative Algorithm for Sparse Least-Squares Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3116469)