Abstract
This paper introduces and analyzes an original class of Krylov subspace methods that provide an efficient alternative to many well-known conjugate-gradient-like (CG-like) Krylov solvers for square nonsymmetric linear systems arising from discretizations of inverse ill-posed problems. The main idea underlying the new methods is to consider some rank-deficient approximations of the transpose of the system matrix, obtained by running the (transpose-free) Arnoldi algorithm, and then apply some Krylov solvers to a formally right-preconditioned system of equations. Theoretical insight is given, and many numerical tests show that the new solvers outperform classical Arnoldi-based or CG-like methods in a variety of situations.
Funding: This work was partially supported by GNCS-INdAM and FRA-University of Trieste. P. Novati is a member of the INdAM research group GNCS.
References
[1] S. Berisha and J. G. Nagy, Iterative image restoration. In: Academic Press Library in Signal Processing (Eds. R. Chellappa and S. Theodoridis), Vol. 4, Elsevier, 2014, pp. 193–243.10.1016/B978-0-12-396501-1.00007-8Search in Google Scholar
[2] D. Calvetti, B. Lewis, and L. Reichel, GMRES-type methods for inconsistent systems. Linear Algebra Appl. 316 (2000), 157–169.10.1016/S0024-3795(00)00064-1Search in Google Scholar
[3] D. Calvetti, B. Lewis, and L. Reichel, On the regularizing properties of the GMRES method. Numer. Math. 91 (2002), 605–625.10.1007/s002110100339Search in Google Scholar
[4] 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), 423–446.10.1016/S0377-0427(00)00414-3Search in Google Scholar
[5] M. Donatelli, D. Martin, and L. Reichel, Arnoldi methods for image deblurring with anti-reflective boundary conditions. Appl. Math. Comput. 253 (2015), 135–150.10.1016/j.amc.2014.12.058Search in Google Scholar
[6] Y. Dong, P. C. Hansen, M. E. Hochstenbach, and N. A. B. Riis, Fixing nonconvergence of algebraic iterative reconstruction with an unmatched backprojection. SIAM J. Sci. Comput. 41 (2019), No. 3, A1822–A1839.10.1137/18M1206448Search in Google Scholar
[7] S. Gazzola and P. Novati, Inheritance of the discrete Picard condition in Krylov subspace methods. BIT56 (2016), No. 3, 893–918.10.1007/s10543-015-0578-5Search in Google Scholar
[8] S. Gazzola, P. Novati, and M. R. Russo, On Krylov projection methods and Tikhonov regularization. Electron. Trans. Numer. Anal. 44 (2015), 83–123.Search in Google Scholar
[9] S. Gazzola, S. Noschese, P. Novati, and L. Reichel, Arnoldi decomposition, GMRES, and preconditioning for linear discrete ill-posed problems. Appl. Numer. Math. 142 (2019), 102–121.10.1016/j.apnum.2019.02.010Search in Google Scholar
[10] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, MD, 1996.Search in Google Scholar
[11] M. Hanke, Conjugate Gradient Type Methods for Ill-Posed Problems. Longman, Essex, UK, 1995.Search in Google Scholar
[12] M. Hanke, On Lanczos based methods for the regularization of discrete ill-posed problems. BIT41 (2001), 1008–1018.10.1023/A:1021941328858Search in Google Scholar
[13] P. C. Hansen, Regularization tools: a Matlab package for analysis and solution of discrete ill-posed problems. Numer. Algorithms6 (1994), 1–35.10.1007/BF02149761Search in Google Scholar
[14] P. C. Hansen, Rank-deficient and discrete ill-posed problems. SIAM, Philadelphia, PA, 1998.10.1137/1.9780898719697Search in Google Scholar
[15] P. C. Hansen and T. K. Jensen, Noise propagation in regularizing iterations for image deblurring. Electron. Trans. Numer. Anal. 31 (2008), 204–220.Search in Google Scholar
[16] T. K. Jensen and P. C. Hansen, Iterative regularization with minimum-residual methods. BIT47 (2007), 103–120.10.1007/s10543-006-0109-5Search in Google Scholar
[17] I. Moret, A note on the superlinear convergence of GMRES. SIAM J. Numer. Anal. 34 (1997), 513–516.10.1137/S0036142993259792Search in Google Scholar
[18] J. G. Nagy, K. M. Palmer, and L. Perrone, Iterative methods for image deblurring: a Matlab object oriented approach. Numer. Algorithms36 (2004), 73–93.10.1023/B:NUMA.0000027762.08431.64Search in Google Scholar
[19] P. Novati, Some properties of the Arnoldi based methods for linear ill-posed problems. SIAM J. Numer. Anal. 55 (2017), 1437–1455.10.1137/16M106399XSearch in Google Scholar
[20] P. Novati and M. R. Russo, A GCV based Arnoldi–Tikhonov regularization method. BIT54 (2014), No. 2, 501–521.10.1007/s10543-013-0447-zSearch in Google Scholar
[21] D. P. O’Leary and J. A. Simmons, A bidiagonalization–regularization procedure for large scale discretizations of ill-posed problems. SIAM J. Sci. Stat. Comp. 2 (1981), No. 4, 474–489.10.1137/0902037Search in Google Scholar
[22] J. R. Ringrose, Compact Non-Self-Adjoint Operators. Van Nostrand Reinhold Company, London, 1971.Search in Google Scholar
[23] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, PA, 2003.10.1137/1.9780898718003Search in Google Scholar
[24] S. Serra-Capizzano, A note on anti-reflective boundary conditions and fast deblurring models. SIAM J. Sci. Comput. 25 (2003), 1307–1325.10.1137/S1064827502410244Search in Google Scholar
© 2020 Walter de Gruyter GmbH, Berlin/Boston
