We consider iterative methods for solving a linear ill-posed problem of the form

\begin{align*} Ax\approx y = y^\delta - \delta \cdot n \end{align*} wherein \(A:\mathcal {X}\rightarrow \mathcal {Y}\) is a compact linear operator, and \(y^\delta \) is a version of the right-hand side obtained by noisy measurements, with \(\left \|n\right \| =1\) and \(0 < \delta \ll 1\). We assume that we only have access to \(y^\delta \). It is well known that naïve solution using the pseudoinverse operator \(A^\dagger y^\delta \) may lead to amplification of the measurement noise, unbounded in the infinite-dimensional case and bounded but large in the finite-dimensional case.

Conjugate gradients applied to the normal equations (CG) \(A^\ast A x^\delta = A^\ast y^\delta \) with an appropriate stopping rule and CG applied to the system solving for a Tikhonov-regularized solution (CGT) \((A^\ast A + c I_{\mathcal {X}}) x^{(\delta ,c)} = A^\ast y^\delta \) (\(c>0\) is the Tikhonov parameter) are closely related methods. It has been long observed that they build iterates from the same family of Krylov subspaces, due to the scalar shift invariance property of Krylov subspaces [4]; i.e., \(\mathcal {K}_m(A^\ast A, A^\ast y^\delta ) = \mathcal {K}_m(A^\ast A + c I_{\mathcal {X}}, A^\ast y^\delta )\). With this in mind, one can express both CG-based iterates with respect to the same Lanczos basis. In particular, one can use this to understand how the representation of the CGT iterates change as a function of \(c\) with \(c\rightarrow 0\) yielding a CG iterate. Let \(x^\delta _m = \sum _{i=1}^{m}z_i^{(m)}v_i\) be the CG iterate where \(\left \lbrace v_i\right \rbrace _{i=1}^m\) is the Lanczos basis for \(\mathcal {K}_m(A^\ast A, A^\ast y^\delta )\). Via linear algebraic manipulations, one can show that the CGT iterate can be expressed as

\begin{align*} x^{(\delta ,c)}_m = \sum _{i=1}^{m} \gamma ^{(m)}_i(c) z_i^{(m)}v_i, \end{align*} where \(\left \lbrace \gamma _i^{(m)}(c)\right \rbrace _{i=1}^m\) are functions of the Tikhonov parameter. These coefficient multiplier functions can be shown to have decay properties as \(c\rightarrow \infty \) with the speed of decay increasing with \(i\), asymptotically. This has the effect of filtering out the contribution of the later terms of the CG iterate. Thus, we call these functions Lanczos filters, as they express the effect of CGT regularization in terms of the CG expressed in the Lanczos basis rather than in terms of the singular vector basis, as is the case of classical definition of filter function in regularization theory [3].

Much of this work is explored in the context of infinite dimensional ill-posed problems to present the analysis as generally as possible. For this, we build upon the work in [1] (which works with the equivalent Golub-Kahan/LSQR formulation of these methods) to prove some additional convergence results, to help us understand the beahvior of the CG and CGT iterates.

If we restrict our focus on the behavior of these methods when applied to finite-dimensional discrete ill-posed problems, we can understand these filters as dampening the influence of Lanczos vectors that are more highly polluted with noise. The mechanics by which noise comes to pollute the Lanczos vectors has been illuminated by means of Gauss-Radau quadrature in [5, 6], and the review [2] and references therein discuss how this has been previously used for Tikhonov parameter selection.

We demonstrate with numerical experiments that good parameter choices correspond to appropriate damping of the Lanczos vectors corresponding to larger amplifications of the measurement noise. Building on this idea, one can consider approaches other than Tikhonov for damping amplified noise. We conclude by noting that analysis of other hybrid regularization schemes via damping of (Krylov) subspace basis vectors from the iteration itself may be a useful avenue for understanding the behavior of these methods for different choice of parameter, etc.

References

• [1]  A. Alqahtani, R. Ramlau, and L. Reichel, Error estimates for Golub–Kahan bidiagonalization with tikhonov regularization for ill–posed operator equations, 39, p. 025002.

• [2]  J. Chung and S. Gazzola, Computational methods for large-scale inverse problems: A survey on hybrid projection methods, 66, pp. 205–284.

• [3]  H. W. Engl, M. Hanke, and A. Neubauer, Regularization of inverse problems, vol. 375 of Mathematics and its Applications, Kluwer Academic Publishers Group, Dordrecht, 1996.

• [4]  A. Frommer and P. Maass, Fast CG-based methods for Tikhonov–Phillips regularization, 20, pp. 1831–1850.

• [5]  I. Hnětynková, M. Kubínová, and M. Plešinger, Noise representation in residuals of LSQR, LSMR, and CRAIG regularization, 533, pp. 357–379.

• [6]  I. Hnětynková, M. Plešinger, and Z. Strakoš, The regularizing effect of the Golub-Kahan iterative bidiagonalization and revealing the noise level in the data, 49, pp. 669–696.