Regularization properties of Krylov iterative solvers CGME and LSMR for linear discrete ill-posed problems with an application to truncated randomized SVDs

DOI10.1007/S11075-019-00865-WMaRDI QIDQ827077zbMATH OpenOpenAlexFDO

Authors Zhongxiao Jia

Publication date 6 January 2021

Published in Numerical Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

ill-posed problemssemi-convergenceKrylov methodsregularized solutionlow rank approximations

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Ill-posedness and regularization problems in numerical linear algebra (65F22) Iterative numerical methods for linear systems (65F10) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Abstract: For the large-scale linear discrete ill-posed problem $min|Ax-b|$ or $Ax=b$ with $b$ contaminated by Gaussian white noise, there are four commonly used Krylov solvers: LSQR and its mathematically equivalent CGLS, the Conjugate Gradient (CG) method applied to $A^{T}Ax=A^{T}b$, CGME, the CG method applied to $min|A{A}^{T}y-b|$ or $A{A}^{T}y=b$ with $x=A^{T}y$, and LSMR, the minimal residual (MINRES) method applied to $A^{T}Ax=A^{T}b$. These methods have intrinsic regularizing effects, where the number $k$ of iterations plays the role of the regularization parameter. In this paper, we establish a number of regularization properties of CGME and LSMR, including the filtered SVD expansion of CGME iterates, and prove that the 2-norm filtering best regularized solutions by CGME and LSMR are less accurate than and at least as accurate as those by LSQR, respectively. We also prove that the semi-convergence of CGME and LSMR always occurs no later and sooner than that of LSQR, respectively. As a byproduct, using the analysis approach for CGME, we improve a fundamental result on the accuracy of the truncated rank $k$ approximate SVD of $A$ generated by randomized algorithms, and reveal how the truncation step damages the accuracy. Numerical experiments justify our results on CGME and LSMR.

Recommendations

• Approximation accuracy of the Krylov subspaces for linear discrete ill-posed problems
• 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
• Some results on the regularization of LSQR for large-scale discrete ill-posed problems
• A framework for studying the regularizing properties of Krylov subspace methods
• On regularizing effects of MINRES and MR-II for large scale symmetric discrete ill-posed problems

Cites work

• scientific article; zbMATH DE number 6016067 (Why is no real title available?)
• scientific article; zbMATH DE number 3980383 (Why is no real title available?)
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 1049347 (Why is no real title available?)
• scientific article; zbMATH DE number 1049353 (Why is no real title available?)
• scientific article; zbMATH DE number 783550 (Why is no real title available?)
• scientific article; zbMATH DE number 852536 (Why is no real title available?)
• scientific article; zbMATH DE number 936298 (Why is no real title available?)
• scientific article; zbMATH DE number 1409641 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• A Practical Examination of Some Numerical Methods for Linear Discrete Ill-Posed Problems
• A hybrid LSMR algorithm for large-scale Tikhonov regularization
• AIR tools -- a MATLAB package of algebraic iterative reconstruction methods
• AIR tools II: algebraic iterative reconstruction methods, improved implementation
• An introduction to the mathematical theory of inverse problems
• Approximation accuracy of the Krylov subspaces for linear discrete ill-posed problems
• Computational Methods for Inverse Problems
• Discrete inverse problems. Insight and algorithms.
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• IR tools: a MATLAB package of iterative regularization methods and large-scale test problems
• Inheritance of the discrete Picard condition in Krylov subspace methods
• LSMR: An Iterative Algorithm for Sparse Least-Squares Problems
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
• Methods of conjugate gradients for solving linear systems
• Noise representation in residuals of LSQR, LSMR, and CRAIG regularization
• Numerical methods for inverse problems
• Numerical methods in matrix computations
• Rank-Deficient and Discrete Ill-Posed Problems
• Regularization methods for large-scale problems
• Regularization methods for the stable solution of inverse problems
• Regularization tools version \(4.0\) for matlab \(7.3\)
• Solution of Sparse Indefinite Systems of Linear Equations
• Some History of the Conjugate Gradient and Lanczos Algorithms: 1948–1976
• Some results on the regularization of LSQR for large-scale discrete ill-posed problems
• Statistical and computational inverse problems.
• The N‐Step Iteration Procedures
• The Lanczos and Conjugate Gradient Algorithms
• The discrete Picard condition for discrete ill-posed problems
• The instability of some gradient methods for ill-posed problems
• The mathematics of computerized tomography
• The regularizing effect of the Golub-Kahan iterative bidiagonalization and revealing the noise level in the data
• Truncated Singular Value Decomposition Solutions to Discrete Ill-Posed Problems with Ill-Determined Numerical Rank

Cited in

(5)

• The low rank approximations and Ritz values in LSQR for linear discrete ill-posed problem
• The Joint Bidiagonalization Method for Large GSVD Computations in Finite Precision
• GMRES methods for tomographic reconstruction with an unmatched back projector
• 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
• The regularized global GMERR method for solving large-scale linear discrete ill-posed problems

Describes a project that uses

Uses Software

• CRAIG
• IR Tools
• LSMR
• AIR tools
• UTV
• RestoreTools
• Regularization tools
• LSQR

This page was built for publication: Regularization properties of Krylov iterative solvers CGME and LSMR for linear discrete ill-posed problems with an application to truncated randomized SVDs

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