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

sparse matrixiterative methodKrylov subspace methodLSQRMINRESleast-squares problemconjugate-gradient methodminimum-residual methodgolub-kahan process

Mathematics Subject Classification ID

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

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)

• Weighted conjugate gradient-type methods for solving quadrature discretization of Fredholm integral equations of the first kind
• Multidirectional subspace expansion for one-parameter and multiparameter Tikhonov regularization
• Estimating the backward error for the least-squares problem with multiple right-hand sides
• Analyzing vector orthogonalization algorithms
• Convergence of inner-iteration GMRES methods for rank-deficient least squares problems
• Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework
• Algorithm 937: MINRES-QLP for symmetric and Hermitian linear equations and least-squares problems
• Simple backward error bounds for linear least-squares problems
• An inner-outer iterative method for edge preservation in image restoration and reconstruction
• Reduced biquaternion elastic net and its application
• Obtaining pseudoinverse solutions with MINRES
• A pairwise-relaxing incompressible smoothed particle hydrodynamics scheme
• A Computational Study of Using Black-box QR Solvers for Large-scale Sparse-dense Linear Least Squares Problems
• Predicting chaotic statistics with unstable invariant tori
• Testing matrix function algorithms using identities
• Linear constrained Rayleigh quotient optimization: theory and algorithms
• Hierarchical orthogonal factorization: sparse least squares problems
• Regularization properties of Krylov iterative solvers CGME and LSMR for linear discrete ill-posed problems with an application to truncated randomized SVDs
• Error bounds for computed least squares estimators
• Alternating cyclic vector extrapolation technique for accelerating nonlinear optimization algorithms and fixed-point mapping applications
• On Using Cholesky-Based Factorizations and Regularization for Solving Rank-Deficient Sparse Linear Least-Squares Problems
• A least squares approach for saddle point problems
• Robust linear algebra
• A robust algorithm for semidefinite programming
• The Conjugate Residual Method in Linesearch and Trust-Region Methods
• Vector extrapolation based Landweber method for discrete ill-posed problems
• An ALE pairwise-relaxing meshless method for compressible flows
• Approximate Generalized Inverses with Iterative Refinement for $\epsilon$-Accurate Preconditioning of Singular Systems
• Sparse linear least-squares problems
• Global least squares methods based on tensor form to solve a class of generalized Sylvester tensor equations
• LSMR iterative method for solving one- and two-dimensional linear Fredholm integral equations
• An alternative method for SPP with full rank (2,1)-block matrix and nonzero right-hand side vector
• Sharp 2-norm error bounds for LSQR and the conjugate gradient method
• A block preconditioner for the Gl-LSMR algorithm
• A block bidiagonalization method for fixed-accuracy low-rank matrix approximation
• Iterative method for rank-deficient (2,1)-block KKT systems
• Optimization of random feature method in the high-precision regime
• A penalty method for PDE-constrained optimization in inverse problems
• Hybrid and iteratively reweighted regularization by unbiased predictive risk and weighted GCV for projected systems
• Quantifying the structural stability of simplicial homology
• Local convergence analysis of a variable projection method for regularized separable nonlinear inverse problems
• A hybrid LSMR algorithm for large-scale Tikhonov regularization
• PLSS: A Projected Linear Systems Solver
• Large-Scale Optimization with Linear Equality Constraints Using Reduced Compact Representation
• A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows
• Random walks on simplicial complexes and the normalized Hodge 1-Laplacian
• Incremental regularized least squares for dimensionality reduction of large-scale data
• LSMR iterative method for general coupled matrix equations
• Estimating error norms in CG-like algorithms for least-squares and least-norm problems
• Matrix-free convex optimization modeling
• An iteratively reweighted least squares algorithm for sparse regularization
• A new iterative model updating technique based on least squares minimal residual method using measured modal data
• \textsc{MinAres}: an iterative solver for symmetric linear systems
• Solving mixed sparse-dense linear least-squares problems by preconditioned iterative methods
• Generalized Golub-Kahan bidiagonalization for nonsymmetric saddle-point systems
• Approximation accuracy of the Krylov subspaces for linear discrete ill-posed problems
• LSMB: minimizing the backward error for least-squares problems
• Scalable adaptive cubic regularization methods
• Noise representation in residuals of LSQR, LSMR, and CRAIG regularization
• A regularized factorization-free method for equality-constrained optimization
• Global LSMR(Gl-LSMR) method for solving general linear systems with several right-hand sides
• Accuracy of the Lanczos process for the eigenproblem and solution of equations
• The AZ algorithm for least squares systems with a known incomplete generalized inverse
• Structure in loss of orthogonality
• A new implementation of LSMR algorithm for the quaternionic least squares problem
• LSLQ: an iterative method for linear least-squares with an error minimization property
• Flexible Krylov methods for \(\ell_p\) regularization
• GMRES methods for tomographic reconstruction with an unmatched back projector
• On Krylov subspace methods for skew-symmetric and shifted skew-symmetric linear systems
• GP-CMRH: an inner product free iterative method for block two-by-two nonsymmetric linear systems
• Fitting multiple Bell curves stably and accurately to a time series as applied to Hubbert cycles or other phenomena
• LSMR
• A variable dimension sketching strategy for nonlinear least-squares
• A tridiagonalization method for symmetric saddle-point systems
• Preconditioning and Iterative Solution of All-at-Once Systems for Evolutionary Partial Differential Equations
• Space‐local reduced‐order bases for accelerating reduced‐order models through sparsity
• High-dimensional multivariate geostatistics: a Bayesian matrix-normal approach
• A stabilized GMRES method for singular and severely ill-conditioned systems of linear equations
• Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers
• 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
• Flexible GMRES for total variation regularization
• Developing LSQR method for Sylvester quaternion tensor equations
• Preconditioners for Krylov subspace methods: An overview
• Proximal distance algorithms: theory and practice
• Goal-oriented optimal approximations of Bayesian linear inverse problems
• The least squares solution of inconsistent discretized elliptic problems using the FETI method.
• Properties of semi-conjugate gradient methods for solving unsymmetric positive definite linear systems
• A collaborative neighbor representation based face recognition algorithm
• The regularized global GMERR method for solving large-scale linear discrete ill-posed problems
• High-precision randomized preconditioned iterative methods for the random feature method
• Preconditioners for rank deficient least squares problems
• A variational discrete element method for the computation of Cosserat elasticity
• An Active-Set Method for Quadratic Programming Based On Sequential Hot-Starts
• SPMR: A family of saddle-point minimum residual solvers
• Generalized Hybrid Iterative Methods for Large-Scale Bayesian Inverse Problems
• Numerical equivalences among Krylov subspace algorithms for skew-symmetric matrices
• A matching pursuit approach to solenoidal filtering of three-dimensional velocity measurements
• Implicitly restarting the LSQR algorithm
• Inexact Gauss-Newton methods with matrix approximation by sampling for nonlinear least-squares and systems
• The attenuated geodesic x-ray transform

Describes a project that uses

Uses Software

• mctoolbox
• SparseMatrix
• PROPACK
• 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)