The low rank approximations and Ritz values in LSQR for linear discrete ill-posed problem*The work was supported by the National Science Foundation of China (No. 11771249). (24th March 2020)

• Record Type: Journal Article
• Authors: Jia, Zhongxiao
• Is Part Of: Inverse problems. Volume 36:Number 4(2020)
• Publication Date: 2020-03-24
• Subjects: discrete ill-posed -- LSQR iterate -- TSVD solution -- semi-convergence -- Golub–Kahan bidiagonalization -- Ritz values -- near best rank k approximation; Inverse problems (Differential equations) -- Periodicals; 515.357
• DOI: 10.1088/1361-6420/ab6f42
• Languages: English
• ISSNs: 0266-5611

Abstract

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, that is, they interlace the first k + 1 large singular values of A, until the semi-convergence of LSQR occurs 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 Golub–Kahan 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 reliably judge the accuracy of low rank approximations cheaply. Numerical experiments confirm our results.