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

DOI10.1088/1361-6420/AB9C45MaRDI QIDQ5117399zbMATH OpenOpenAlexFDO

Authors Zhongxiao Jia

Publication date 25 August 2020

Published in Inverse Problems (Search for Journal in Brave)

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

zbMATH Keywords

low-rank approximationsemi-convergenceRitz valuesdiscrete ill-posed problemsmultiple singular values

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Ill-posedness and regularization problems in numerical linear algebra (65F22)

Abstract: For the large-scale linear discrete ill-posed problem $min|Ax-b|$ or $Ax=b$ with $b$ contaminated by white noise, the Golub-Kahan bidiagonalization based LSQR method and its mathematically equivalent CGLS, the Conjugate Gradient (CG) method applied to $A^{T}Ax=A^{T}b$, are most commonly used. They have intrinsic regularizing effects, where the iteration number $k$ plays the role of regularization parameter. The long-standing fundamental question is: {em Can LSQR and CGLS find 2-norm filtering best possible regularized solutions}? The author has given definitive answers to this question for severely and moderately ill-posed problems when the singular values of $A$ are simple. This paper extends the results to the multiple singular value case, and studies the approximation accuracy of Krylov subspaces, the quality of low rank approximations generated by Golub-Kahan bidiagonalization and the convergence properties of Ritz values. For the two kinds of problems, we prove that LSQR finds 2-norm filtering best possible regularized solutions at semi-convergence. Particularly, we consider some important and untouched issues on best, near best and general rank $k$ approximations to $A$ for the ill-posed problems with the singular values $sigm{a}_k=mathcalO(k^{-alpha})$ with $alpha>0$, and the relationships between them and their nonzero singular values. Numerical experiments confirm our theory. The results on general rank $k$ approximations and the properties of their nonzero singular values apply to several Krylov solvers, including LSQR, CGME, MINRES, MR-II, GMRES and RRGMRES.

Recommendations

• 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
• Old and new parameter choice rules for discrete ill-posed problems
• A framework for studying the regularizing properties of Krylov subspace methods
• Regularization properties of Krylov iterative solvers CGME and LSMR for linear discrete ill-posed problems with an application to truncated randomized SVDs

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 783550 (Why is no real title available?)
• scientific article; zbMATH DE number 852536 (Why is no real title available?)
• scientific article; zbMATH DE number 1409641 (Why is no real title available?)
• A Bidiagonalization-Regularization Procedure for Large Scale Discretizations of Ill-Posed Problems
• A Practical Examination of Some Numerical Methods for Linear Discrete Ill-Posed Problems
• A bidiagonalization algorithm for solving large and sparse ill-posed systems of linear equations
• A framework for regularization via operator approximation
• A joint bidiagonalization based iterative algorithm for large scale general-form Tikhonov regularization
• A weighted-GCV method for Lanczos-hybrid regularization
• An implicit shift bidiagonalization algorithm for ill-posed systems
• 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
• Core Problems in Linear Algebraic Systems
• Discrete inverse problems. Insight and algorithms.
• Hybrid and iteratively reweighted regularization by unbiased predictive risk and weighted GCV for projected systems
• IR tools: a MATLAB package of iterative regularization methods and large-scale test problems
• Inheritance of the discrete Picard condition in Krylov subspace methods
• Iterative Regularization and MINRES
• Iterative regularization with minimum-residual methods
• LSMR: An Iterative Algorithm for Sparse Least-Squares Problems
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
• Linear and nonlinear inverse problems with practical applications
• Matrix algorithms. Vol. 2: Eigensystems
• 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
• On regularizing effects of MINRES and MR-II for large scale symmetric discrete ill-posed problems
• Rank-Deficient and Discrete Ill-Posed Problems
• Regularization by Truncated Total Least Squares
• Regularization methods for large-scale problems
• Regularization methods for the stable solution of inverse problems
• Regularization properties of Krylov iterative solvers CGME and LSMR for linear discrete ill-posed problems with an application to truncated randomized SVDs
• Regularization tools version \(4.0\) for matlab \(7.3\)
• Restoration of atmospherically blurred images by symmetric indefinite conjugate gradient techniques
• Robust methods in inverse theory
• Solving or resolving inadequate and noisy tomographic systems
• 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 low rank approximations and Ritz values in LSQR for linear discrete ill-posed problem
• The mathematics of computerized tomography
• The rate of convergence of conjugate gradients
• 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

(9)

• Regularization properties of Krylov iterative solvers CGME and LSMR for linear discrete ill-posed problems with an application to truncated randomized SVDs
• A skew-symmetric Lanczos bidiagonalization method for computing several extremal eigenpairs of a large skew-symmetric matrix
• Convergence analysis of LSQR for compact operator equations
• Admissible subspaces and the subspace iteration method
• Some results on the regularization of LSQR for large-scale discrete ill-posed problems
• A joint bidiagonalization based iterative algorithm for large scale general-form Tikhonov regularization
• The Joint Bidiagonalization Method for Large GSVD Computations in Finite Precision
• Double precision is not necessary for LSQR for solving discrete linear ill-posed problems
• Iterative hybrid regularization for extremely noisy full models in single particle analysis

Describes a project that uses

Uses Software

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

This page was built for publication: 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

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