5
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

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

Preprint

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### Abstract

For the large-scale linear discrete ill-posed problem $$\min\|Ax-b\|$$ or $$Ax=b$$ with $$b$$ contaminated by 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 have intrinsic regularizing effects, where 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 can find best possible regularized solutions}? The same question is for CGME and LSMR too. At iteration $$k$$, these four methods compute iterates from the same $$k$$ dimensional Krylov subspace when starting vectors are chosen properly. A first and fundamental step towards to answering the above question is to 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 the two subspaces, derive accurate estimates on them for severely, moderately and mildly ill-posed problems, and establish some relationships between the smallest Ritz values and these distances. Numerical experiments justify our estimates and theory.

### Most cited references26

• Record: found

### Methods of conjugate gradients for solving linear systems

(1952)
Bookmark
• Record: found

### Solution of Sparse Indefinite Systems of Linear Equations

(1975)
Bookmark
• Record: found

### Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter

(1979)
Bookmark

### Author and article information

###### Journal
24 May 2018
###### Article
1805.10132