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-WzbMATH Open1455.65062arXiv1812.04762OpenAlexW3008416987MaRDI QIDQ827077FDOQ827077

Authors: Zhongxiao Jia 

Publication date: 6 January 2021

Published in: Numerical Algorithms (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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

Uses Software

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

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)