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/AB9C45zbMATH Open1452.65075arXiv2003.09259OpenAlexW3102248732MaRDI QIDQ5117399FDOQ5117399

Zhongxiao Jia

Publication date: 25 August 2020

Published in: Inverse Problems (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 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.

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)

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
• Methods of conjugate gradients for solving linear systems
• Regularization methods for large-scale problems
• The mathematics of computerized tomography
• Matrix algorithms. Vol. 2: Eigensystems
• Title not available (Why is that?)
• Linear and Nonlinear Inverse Problems with Practical Applications
• Computational Methods for Inverse Problems
• Numerical Methods in Matrix Computations
• Title not available (Why is that?)
• Title not available (Why is that?)
• The rate of convergence of conjugate gradients
• A bidiagonalization algorithm for solving large and sparse ill-posed systems of linear equations
• The regularizing effect of the Golub-Kahan iterative bidiagonalization and revealing the noise level in the data
• Restoration of atmospherically blurred images by symmetric indefinite conjugate gradient techniques
• Iterative Regularization and MINRES
• Discrete Inverse Problems
• An introduction to the mathematical theory of inverse problems
• Iterative regularization with minimum-residual methods
• Title not available (Why is that?)
• A Bidiagonalization-Regularization Procedure for Large Scale Discretizations of Ill-Posed Problems
• Inheritance of the discrete Picard condition in Krylov subspace methods
• A Practical Examination of Some Numerical Methods for Linear Discrete Ill-Posed Problems
• Regularization by Truncated Total Least Squares
• Core Problems in Linear Algebraic Systems
• The N‐Step Iteration Procedures
• A weighted-GCV method for Lanczos-hybrid regularization
• Solving or resolving inadequate and noisy tomographic systems
• Truncated Singular Value Decomposition Solutions to Discrete Ill-Posed Problems with Ill-Determined Numerical Rank
• An implicit shift bidiagonalization algorithm for ill-posed systems
• 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
• A joint bidiagonalization based iterative algorithm for large scale general-form Tikhonov regularization
• Approximation accuracy of the Krylov subspaces for linear discrete ill-posed problems
• Noise representation in residuals of LSQR, LSMR, and CRAIG regularization
• Regularization properties of Krylov iterative solvers CGME and LSMR for linear discrete ill-posed problems with an application to truncated randomized SVDs
• Robust methods in inverse theory
• A Framework for Regularization via Operator Approximation
• On regularizing effects of MINRES and MR-II for large scale symmetric discrete ill-posed problems
• Hybrid and Iteratively Reweighted Regularization by Unbiased Predictive Risk and Weighted GCV for Projected Systems
• The low rank approximations and Ritz values in LSQR for linear discrete ill-posed problem

Cited In (6)

• A skew-symmetric Lanczos bidiagonalization method for computing several extremal eigenpairs of a large skew-symmetric matrix
• Admissible subspaces and the subspace iteration method
• 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

Uses Software

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

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)