Multilevel Arnoldi-Tikhonov Regularization Methods for Large-Scale Linear Ill-Posed Systems

This paper is devoted to the numerical solution of
large-scale linear ill-posed systems. A multilevel regularization
method is proposed. This method is based on a synthesis of
the Arnoldi-Tikhonov regularization technique and the multilevel
technique. We show that if the Arnoldi-Tikhonov method is
a regularization method, then the multilevel method is also a
regularization one. Numerical experiments presented in this paper
illustrate the effectiveness of the proposed method.

Authors:

• Yiqin Lin
• Liang Bao

Keywords:

• Discrete ill-posed problem
• Tikhonov regularization
• discrepancy principle
• Arnoldi process
• multilevel method.

References:

[1] A. S. Al-Fhaid, S. Serra-Capizzano, D. Sesana, and M. Z. Ullah,
Singular-value (and eigenvalue) distribution and krylov preconditioning
of sequences of sampling matrices approximating integral operators,
Numer. Linear Algebra Appl., 21 (2014), pp. 722–743.
[2] M. L. Baart, The use of auto-correlation for pseudo-rank determination
in noisy ill-conditioned least-squares problems, IMA J. Numer. Anal.,
2 (1982), pp. 241–247.
[3] J. Baglama and L. Reichel, Augmented GMRES-type methods, Numer.
Linear Algebra Appl., 14 (2007), pp. 337–350.
[4] A˚ . Bjo¨rck, A bidiagonalization algorithm for solving large and sparse
ill-posed systems of linear equations, BIT, 28 (1988), pp. 659–670.
[5] , Numerical Methods for Least Squares Problems, SIAM,
Philadelphia, 1996.
[6] D. Calvetti, B. Lewis, and L. Reichel, On the choice of subspace for
iterative methods for linear discrete ill-posed problems, Int. J. Appl.
Math. Comput. Sci., 11 (2001), pp. 1069–1092.
[7] , On the regularizing properties of the GMRES method, Numer.
Math., 123 (2002), pp. 605–625.
[8] D. Calvetti, S. Morigi, L. Reichel, and F. Sgallari, Tikhonov
regularization and the L-curve for large, discrete ill-posed problems,
J. Comput. Appl. Math., 123 (2000), pp. 423–446.
[9] D. Calvetti and L. Reichel, Tikhonov regularization of large linear
problems, BIT, 43 (2003), pp. 263–283.
[10] H. R. Chan and K. Chen, A multilevel algorithm for simultaneously
denoising and deblurring images, SIAM J. Sci. Comput., 32 (2010),
pp. 1043–1063.
[11] T. F. Chan and K. R. Jackson, Nonlinearly preconditioned Krylov
subspace methods for discrete Newton algorithms, SIAM J. Sci. Statist.
Comput., 5 (1984), pp. 533–542.
[12] Z. Chen, Y. Xu, and H. Yang, A multilevel augmentation method fo
solving ill-posed operator equations, SIAM J. Sci. Statist. Comput., 22
(2006), pp. 155–174.
[13] M. Donatelli and S. Serra-Capizzano, On the regularizing power
of multigrid-type algorithms, SIAM J. Sci. Comput., 27 (2006),
pp. 2053–2076.
[14] H. W. Engl, M. Hanke, and A. Neubauer, Regularization of inverse
problems, Kluwer, Dordrecht, 1996.
[15] M. I. Espanol and M. E. Kilmer, Multilevel approach for signal
restoration problems with toeplitz matrices, SIAM J. Sci. Comput., 32
(2010), pp. 299–319.
[16] J. A. Ezquerro and M. A. Hernandez, On a convex acceleration of
Newton’s method, J. Optim. Theory Appl., 100 (1999), pp. 311–326.
[17] W. Gander, On Halley’s iteration method, Amer. Math. Monthly, 92
(1985), pp. 131–134.
[18] G. H. Golub and C. F. V. Loan, Matrix Computations, John Hopkins
University Press, Baltimore, MD, 3rd ed., 1996.
[19] M. Hanke and C. R. Vogel, Two-level preconditioners for regularized
inverse problems I: theory, Numer. Math., 83 (1999), pp. 385–402.
[20] P. C. Hansen, Rank Deficient and Discrete Ill-posed Problems, SIAM,
Philadelphia, PA, 1998.
[21] M. Jacobsen, P. C. Hansen, and M. A. Saunders, Subspace
preconditioned LSQR for discrete ill-posed problems, BIT, 43 (2003),
pp. 975–989.
[22] C. T. Kelley, Solving Nonlinear Equations with Newton’s Method, SIAM,
Philadelphia, PA, 2003.
[23] J. T. King, Multilevel algoritms for ill-posed problems, Numer. Math.,
61 (1992), pp. 311–334.
[24] E. Klann, R. Ramlau, and L. Reichel, Wavelet-based multilevel methods
for linear ill-posed problems, BIT, 51 (2011), pp. 669–694.
[25] D. P. O. Leary and J. A. Simmons, A bidiagonalization-regularization
procedure for large-scale discretizations of ill-posed problems, SIAM J.
Sci. Statist. Comput., 2 (1981), pp. 474–489.
[26] B. Lewis and L. Reichel, Arnoldi-Tikhonov regularization methods, J.
Comput. Appl. Math., 226 (2009), pp. 92–102. [27] Y. Lin, L. Bao, and Y. Cao, Augmented Arnoldi-Tikhonov regularization
rethods for solving large-scale linear ill-posed systems, Mathematical
Problems in Engineering, 2013 (2013), pp. 1–8.
[28] S. Morigi, L. Reichel, and F. Sgallari, Cascadic multilevel methods for
fast nonsymmetric blur- and noise-removal, Appl. Numer. Math., 60
(2010), pp. 378–396.
[29] B. N. Parlett, The Symmetric Eigenvalue Problem, SIAM, Philadelphia,
PA, 1998.
[30] D. L. Phillips, A technique for the numerical solution of certain integral
equations of the first kind, J. ACM, 9 (1962), pp. 84–97.
[31] L. Reichel and A. Shyshkov, A new zero-finder for tikhonov
regularization, BIT Numer. Math., 48 (2008), pp. 627–643.
[32] , Cascadic multilevel methods for ill-posed problems, J. Comput.
Appl. Math., 233 (2010), pp. 1314–1325.
[33] L. Reichel and Q. Ye, Breakdown-free GMRES for singular systems,
SIAM J. Matrix Anal. Appl., 26 (2005), pp. 1001–1021.
[34] A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-Posed Problems,
Wiley, New York, 1977.
[35] A. N. Tikhonov, A. V. Goncharsky, V. V. Stepanov, and A. G. Yagola,
Numerical Methods for the Solution of Ill-Posed Problems, Kluwe,
Dordrecht, 1995.