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

Abstract

For the large-scale linear discrete ill-posed problem $\min \Vert Ax-b\Vert$ or $Ax=b$ with $b$ 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 $A^{T}Ax=A^{T}b$, are most commonly used, and CGME, the CG method applied to $\min \Vert A{A}^{T}y-b\Vert$ or $A{A}^{T}y=b$ with $x=A^{T}y$, and LSMR, which is equivalent to the minimal residual (MINRES) method applied to $A^{T}Ax=A^{T}b$, have also been choices. These methods exhibit typical semi-convergence feature, and the iteration number $k$ 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 $k$, LSQR, CGME and LSMR compute {\em different} iterates from the {\em same} $k$ dimensional Krylov subspace. A first and fundamental step towards to answering the above question is to {\em accurately} estimate the accuracy of the underlying $k$ dimensional Krylov subspace approximating the $k$ dimensional dominant right singular subspace of $A$. Assuming that the singular values of $A$ are simple, we present a general $\sin \Theta$ 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.

33 pages, 11 figures. arXiv admin note: text overlap with arXiv:1701.05708, arXiv:1608.05907

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