The Low Rank Approximations and Ritz Values in LSQR For Linear Discrete Ill-Posed Problems

Abstract

LSQR and its mathematically equivalent CGLS have been popularly used over the decades for large-scale linear discrete ill-posed problems, where the iteration number $k$ plays the role of the regularization parameter. It has been long known that if the Ritz values in LSQR converge to the large singular values of $A$ in natural order until its semi-convergence then LSQR must have the same the regularization ability as the truncated singular value decomposition (TSVD) method and can compute a 2-norm filtering best possible regularized solution. However, hitherto there has been no definitive rigorous result on the approximation behavior of the Ritz values in the context of ill-posed problems. In this paper, for severely, moderately and mildly ill-posed problems, we give accurate solutions of the two closely related fundamental and highly challenging problems on the regularization of LSQR: (i) How accurate are the low rank approximations generated by Lanczos bidiagonalization? (ii) Whether or not the Ritz values involved in LSQR approximate the large singular values of $A$ in natural order? We also show how to judge the accuracy of low rank approximations reliably during computation without extra cost. Numerical experiments confirm our results.

30 pages, 9 figures. arXiv admin note: text overlap with arXiv:1608.05907, arXiv:1701.05708

References in corpus (1)

• Approximation Accuracy of the Krylov Subspaces for Linear Discrete Ill-Posed Problems

Cited by in corpus (5)

• A Joint Bidiagonalization Based Algorithm for Large Scale Linear Discrete Ill-posed Problems in General-Form Regularization
• Computational methods for large-scale inverse problems: a survey on hybrid projection methods
• Regularization Properties of the Krylov Iterative Solvers CGME and LSMR For Linear Discrete Ill-Posed Problems with an Application to Truncated Randomized SVDs
• The joint bidiagonalization method for large GSVD computations in finite precision
• The Krylov Subspaces, Low Rank Approximations and Ritz Values of LSQR for Linear Discrete Ill-Posed Problems: the Multiple Singular Value Case