Approximation Accuracy of the Krylov Subspaces for Linear Discrete Ill-Posed Problems
For researchers in inverse problems and regularization, this work provides a theoretical foundation for understanding the approximation accuracy of Krylov subspaces, which is crucial for justifying the use of iterative regularization methods.
This paper addresses the fundamental question of whether Krylov subspace methods like LSQR, CGLS, CGME, and LSMR can find optimally filtered regularized solutions for linear discrete ill-posed problems. The authors derive accurate estimates of the 2-norm distance between the Krylov subspace and the dominant right singular subspace, providing a sinΘ theorem for severely, moderately, and mildly ill-posed problems.
For the large-scale linear discrete ill-posed problem $\min\|Ax-b\|$ 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^TAx=A^Tb$, are most commonly used, and CGME, the CG method applied to $\min\|AA^Ty-b\|$ or $AA^Ty=b$ with $x=A^Ty$, and LSMR, which is equivalent to the minimal residual (MINRES) method applied to $A^TAx=A^Tb$, 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Θ$ 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.