Approximation Accuracy of the Krylov Subspaces for Linear Discrete Ill-Posed Problems
arXiv:1805.10132 · doi:10.1016/j.cam.2020.112786
Abstract
For the large-scale linear discrete ill-posed problem or with contaminated by Gaussian white noise, the Lanczos bidiagonalization based Krylov solver LSQR and its mathematically equivalent CGLS, the Conjugate Gradient (CG) method implicitly applied to , are most commonly used, and CGME, the CG method applied to or with , and LSMR, which is equivalent to the minimal residual (MINRES) method applied to , have also been choices. These methods exhibit typical semi-convergence feature, and the iteration number plays the role of the regularization parameter. However, there has been no definitive answer to the long-standing fundamental question: {\em Can LSQR and CGLS find 2-norm filtering best possible regularized solutions}? The same question is for CGME and LSMR too. At iteration , LSQR, CGME and LSMR compute {\em different} iterates from the {\em same} dimensional Krylov subspace. A first and fundamental step towards to answering the above question is to {\em accurately} estimate the accuracy of the underlying dimensional Krylov subspace approximating the dimensional dominant right singular subspace of . Assuming that the singular values of are simple, we present a general theorem for the 2-norm distances between these two subspaces and derive accurate estimates on them for severely, moderately and mildly ill-posed problems. We also establish some relationships between the smallest Ritz values and these distances. Numerical experiments justify the sharpness of our results.
arXiv comment33 pages, 11 figures. arXiv admin note: text overlap with arXiv:1701.05708, arXiv:1608.05907
References in corpus (2)
Cited by in corpus (7)
- 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
- The Low Rank Approximations and Ritz Values in LSQR For Linear Discrete Ill-Posed Problems
- Regularization Properties of the Krylov Iterative Solvers CGME and LSMR For Linear Discrete Ill-Posed Problems with an Application to Truncated Randomized SVDs
- A CCBM-based generalized GKB iterative regularization algorithm for inverse Cauchy problems
- The Krylov Subspaces, Low Rank Approximations and Ritz Values of LSQR for Linear Discrete Ill-Posed Problems: the Multiple Singular Value Case
- On inner iterations of the joint bidiagonalization based algorithms for solving large scale ill-posed problems