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

Authors: Yiqin Lin, Liang Bao

Abstract:

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.

Keywords: Discrete ill-posed problem, Tikhonov regularization, discrepancy principle, Arnoldi process, multilevel method.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.2021701

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.