The regularization theory of the Krylov iterative solvers LSQR and CGLS for linear discrete ill-posed problems, part I: the simple singular value case Article Swipe

MAKE IMPACT

Zhongxiao Jia · YOU? · · 2017 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1701.05708

For the large-scale linear discrete ill-posed problem $\min\|Ax-b\|$ or $Ax=b$ with $b$ contaminated by a white noise, the Lanczos bidiagonalization based LSQR method and its mathematically equivalent Conjugate Gradient (CG) method for $A^TAx=A^Tb$ are most commonly used. They have intrinsic regularizing effects, where the number $k$ of iterations plays the role of regularization parameter. However, there has been no answer to the long-standing fundamental concern by Björck and Eldén in 1979: for which kinds of problems LSQR and CGLS can find best possible regularized solutions? Here a best possible regularized solution means that it is at least as accurate as the best regularized solution obtained by the truncated singular value decomposition (TSVD) method or standard-form Tikhonov regularization. In this paper, assuming that the singular values of $A$ are simple, we analyze the regularization of LSQR for severely, moderately and mildly ill-posed problems. We establish accurate estimates for the 2-norm distance between the underlying $k$-dimensional Krylov subspace and the $k$-dimensional dominant right singular subspace of $A$. For the first two kinds of problems, we then prove that LSQR finds a best possible regularized solution at semi-convergence occurring at iteration $k_0$ and that, for $k=1,2,\ldots,k_0$, (i) the $k$-step Lanczos bidiagonalization always generates a near best rank $k$ approximation to $A$; (ii) the $k$ Ritz values always approximate the first $k$ large singular values in natural order; (iii) the $k$-step LSQR always captures the $k$ dominant SVD components of $A$. For the third kind of problem, we prove that LSQR generally cannot find a best possible regularized solution. Numerical experiments confirm our theory.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/1701.05708

PDF

https://arxiv.org/pdf/1701.05708

OA Status

green

Cited By

2

References

76

Related Works

10

OpenAlex ID

https://openalex.org/W2579891415

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W2579891415

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.1701.05708

Digital Object Identifier

Title

The regularization theory of the Krylov iterative solvers LSQR and CGLS for linear discrete ill-posed problems, part I: the simple singular value case

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2017

Year of publication

Publication date

2017-01-20

Full publication date if available

Authors

Zhongxiao Jia

List of authors in order

Landing page

https://arxiv.org/abs/1701.05708

Publisher landing page

PDF URL

https://arxiv.org/pdf/1701.05708

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/1701.05708

Direct OA link when available

Concepts

Mathematics, Lanczos resampling, Tikhonov regularization, Krylov subspace, Regularization (linguistics), Singular value, Singular value decomposition, Applied mathematics, Conjugate gradient method, Well-posed problem, Mathematical analysis, Inverse problem, Linear system, Mathematical optimization, Algorithm, Eigenvalues and eigenvectors, Computer science, Physics, Artificial intelligence, Quantum mechanics

Top concepts (fields/topics) attached by OpenAlex

Cited by

2

Total citation count in OpenAlex

Citations by year (recent)

2020: 1, 2018: 1

Per-year citation counts (last 5 years)

References (count)

76

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload