×

zbMATH — the first resource for mathematics

Approximation accuracy of the Krylov subspaces for linear discrete ill-posed problems. (English) Zbl 1434.65043
The author makes a deep analysis on the regularizing effects of LSQR, thus establishing a general \(\sin(\Theta)\) theorem for the \(2\)-norm distances between these two subspaces and deriving accurate estimates on them for severely, moderately and mildly ill-posed problems.

MSC:
65F22 Ill-posedness and regularization problems in numerical linear algebra
15A18 Eigenvalues, singular values, and eigenvectors
65F10 Iterative numerical methods for linear systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65R32 Numerical methods for inverse problems for integral equations
65J20 Numerical solutions of ill-posed problems in abstract spaces; regularization
65J22 Numerical solution to inverse problems in abstract spaces
65R30 Numerical methods for ill-posed problems for integral equations
47A52 Linear operators and ill-posed problems, regularization
15A29 Inverse problems in linear algebra
45Q05 Inverse problems for integral equations
86A22 Inverse problems in geophysics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Engl, H. W.; Hanke, M.; Neubauer, A., Regularization of Inverse Problems (2000), Kluwer Academic Publishers
[2] Hanke, M.; Hansen, P. C., (Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion. Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion, SIAM Monographs on Mathematical Modeling and Computation (1998), SIAM: SIAM Philadelphia, PA)
[3] Hanke, M.; Hansen, P. C., (Discrete Inverse Problems: Insight and Algorithms. Discrete Inverse Problems: Insight and Algorithms, Fundamentals of Algorithms, vol. 7 (2010), SIAM: SIAM Philadelphia, PA) · Zbl 1197.65054
[4] Kirsch, A., (An Introduction To the Mathematical Theory of Inverse Problems. An Introduction To the Mathematical Theory of Inverse Problems, Applied Mathematical Sciences, vol. 120 (2011), Springer: Springer New York) · Zbl 1213.35004
[5] Mueller, J. L.; Siltanen, S., (Linear and Nonlinear Inverse Problems with Practical Applications. Linear and Nonlinear Inverse Problems with Practical Applications, Computational Science & Engineering, vol. 10 (2012), SIAM: SIAM Philadelphia, PA) · Zbl 1262.65124
[6] Aster, R. C.; Borchers, B.; Thurber, C. H., Parameter Estimation and Inverse Problems (2013), Elsevier: Elsevier New York · Zbl 1273.35306
[7] Engl, H. W., Regularization methods for the stable solution of inverse problems, Surv. Math. Ind., 3, 71-143 (1993) · Zbl 0776.65043
[8] Ito, K.; Jin, B., (Inverse Problems: Tikhonov Theory and Algorithms. Inverse Problems: Tikhonov Theory and Algorithms, Series on Applied Mathematics, vol. 22 (2015), World Scientific Publishing Co. Pte. Ltd.: World Scientific Publishing Co. Pte. Ltd. Hackensack, NJ) · Zbl 1306.65210
[9] Kaipio, J.; Somersalo, E., (Statistical and Computational Inverse Problems. Statistical and Computational Inverse Problems, Applied Mathematical Sciences, vol. 160 (2005), Springer-Verlag: Springer-Verlag New York) · Zbl 1068.65022
[10] Vogel, C. R., (Computational Methods for Inverse Problems. Computational Methods for Inverse Problems, Frontiers in Applied Mathematics, vol. 23 (2002), SIAM: SIAM Philadelphia, PA) · Zbl 1008.65103
[11] Kythe, P. K.; Puri, P., Computational Methods for Linear Integral Equations (2002), Birkhäuser Boston, Inc.: Birkhäuser Boston, Inc. Boston, MA · Zbl 1023.65134
[12] Gazzola, S.; Novati, P., Inheritance of the discrete Picard condition in Krylov subspace methods, BIT, 56, 893-918 (2016) · Zbl 1353.65023
[13] Kern, M., Numerical Methods for Inverse Problems (2016), John Wiley & Sons, Inc. · Zbl 1342.65138
[14] Tikhonov, A. N.; Arsenin, V. Y., Solutions of Ill-Posed Problems (1977), V. H. Winston & Sons: V. H. Winston & Sons Washington, D.C · Zbl 0354.65028
[15] Björck, Å., Numerical Methods for Least Squares Problems (1996), SIAM: SIAM Philadelphia, PA
[16] van der Vorst, H. A., A practical examination of some numerical methods for linear discrete ill-posed problems, SIAM Rev., 21, 100-111 (1979)
[17] Natterer, F., (The Mathematics of Computerized Tomography. The Mathematics of Computerized Tomography, Classics in Applied Mathematics, vol. 32 (2001), SIAM: SIAM Philadelphia, PA), Reprint of the 1986 original edition · Zbl 0973.92020
[18] Hanke, M.; Hansen, P. C., Analysis of discrete ill-posed problems by means of the \(L\)-curve, SIAM Rev., 34, 561-580 (1992) · Zbl 0770.65026
[19] Hansen, P. C.; O’Leary, D. P., The use of the L-curve in the regularization of discrete ill-posed problems, SIAM J. Sci. Comput., 14, 1487-1503 (1993) · Zbl 0789.65030
[20] Hanke, M., Limitations of the \(L\)-curve method in ill-posed problems, BIT, 36, 287-301 (1996) · Zbl 0849.65039
[21] Vogel, C. R., Non-convergence of the \(L\)-curve regularization parameter selection method, Inverse Problems, 12, 535-547 (1996) · Zbl 0867.65025
[22] Hanke, M., (Conjugate Gradient Type Methods for Ill-Posed Problems. Conjugate Gradient Type Methods for Ill-Posed Problems, Pitman Research Notes in Mathematics Series, vol. 327 (1995), Longman: Longman Essex) · Zbl 0830.65043
[23] Golub, G. H.; O’Leary, D. P., Some history of the conjugate gradient and Lanczos algorithms: 1948-1976, SIAM Rev., 31, 50-102 (1989) · Zbl 0673.65017
[24] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 409-436 (1952) · Zbl 0048.09901
[25] Paige, C. C.; Saunders, M. A., LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Softw., 8, 43-71 (1982) · Zbl 0478.65016
[26] Björck, Å., (Numerical Methods in Matrix Computations. Numerical Methods in Matrix Computations, Texts in Applied Mathematics, vol. 59 (2015), Springer: Springer Cham) · Zbl 1322.65047
[27] Craig, E. J., The N-step iteration procedures, J. Math. Phys., 34, 64-73 (1955) · Zbl 0065.10901
[28] Hanke, M., On Lanczos based methods for the regularization of discrete ill-posed problems, BIT, 41, Suppl., 1008-1018 (2001)
[29] Fong, D. C.L.; Saunders, M., LSMR: an iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput., 33, 2950-2971 (2011) · Zbl 1232.65052
[30] Paige, C. C.; Saunders, M. A., Solutions of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629 (1975) · Zbl 0319.65025
[31] Hnětynková, M. R.; Kubínová, Marie; Plešinger, M., Noise representation in residuals of LSQR, LSMR, and Craig regularization, Linear Algebra Appl., 533, 357-379 (2017) · Zbl 1391.15062
[32] Hnětynková, M. R.; Plešinger, M.; Strakoš, Z., The regularizing effect of the Golub-Kahan iterative bidiagonalization and revealing the noise level in the data, BIT, 49, 669-696 (2009) · Zbl 1184.65044
[33] Hofmann, B., Regularization for Applied Inverse and Ill-Posed Problems (1986), Teubner: Teubner Stuttgart, Germany · Zbl 0606.65038
[34] Hanke, M.; Hansen, P. C., Regularization methods for large-scale problems, Surv. Math. Ind., 3, 253-315 (1993) · Zbl 0805.65058
[35] Johnsson, C., On Finite Element Methods for Optimal Control ProblemsTech. Report 79-04 R (1979), Dept. of Computer Science, University of Gothenburg
[36] Björck, Å.; Eldén, L., Methods in Numerical Algebra for Ill-Posed ProblemsReport LiTH-R-33-1979 (1979), Dept. of Mathematics, Linköping Univeristy: Dept. of Mathematics, Linköping Univeristy Sweden
[37] Hanke, M.; Hansen, P. C., Regularization Tools version 4.0 for Matlab 7.3, Numer. Algorithms, 46, 189-194 (2007) · Zbl 1128.65029
[38] Fierro, R. D.; Golub, G. H.; Hansen, P. C.; O’Leary, D. P., Regularization by truncated total least squares, SIAM J. Sci. Comput., 18, 1223-1241 (1997) · Zbl 0891.65040
[39] Huang, Y.; Jia, Z., Some results on the regularization of LSQR for large-scale ill-posed problems, Sci. China Math., 60, 701-718 (2017) · Zbl 1453.65080
[40] Nemirovskii, A. S., The regularizing properties of the adjoint gradient method in ill-posed problems, USSR Comput. Math. Math. Phys., 26, 7-16 (1986) · Zbl 0615.65056
[41] Paige, C. C.; Strakoš, Z. Z., Core problems in linear algebraic systems, SIAM J. Matrix Anal. Appl., 27, 861-875 (2005) · Zbl 1097.15003
[42] van der Sluis, A.; van der Vorst, H. A., SIRT- and CG-type methods for the iterative solution of sparse linear least-squares problems, Linear Algebra Appl., 130, 257-303 (1990) · Zbl 0702.65042
[43] Berisha, S.; Nagy, J. G., Restore tools: Iterative methods for image restoration (2012), available from http://www.mathcs.emory.edu/ñagy/RestoreTools
[44] S. Gazzola, P.C. Hansen, J.G. Nagy, IR tools: A MATLAB package of iterative regularization methods and large-scale test problems, Numer. Algorithms http://dx.doi.org/10.1007/s11075-018-0570-7. · Zbl 1415.65003
[45] Frommer, A.; Maass, P., Fast CG-based methods for Tikhonov-Phillips regularization, SIAM J. Sci. Comput., 20, 1831-1850 (1999) · Zbl 0943.65068
[46] O’Leary, D. P.; Simmons, J. A., A bidiagonalization-regularization procedure for large scale discretizations of ill-posed problems, SIAM J. Sci. Stat. Comput., 2, 474-489 (1981) · Zbl 0469.65089
[47] Björck, Å., A bidiagonalization algorithm for solving large and sparse ill-posed systems of linear equations, BIT, 28, 659-670 (1988) · Zbl 0658.65041
[48] Björck, Å.; Grimme, E.; van Dooren, P., An implicit shift bidiagonalization algorithm for ill-posed systems, BIT, 34, 510-534 (1994) · Zbl 0821.65023
[49] Renaut, R. A.; Vatankhah, S.; Ardestani, V. E., Hybrid and iteratively reweighted regularization by unbiased predictive risk and weighted GCV, SIAM J. Sci. Comput., 39, B221-B243 (2017) · Zbl 1360.65115
[50] Bazán, F. S.V.; Borges, L. S., GKB-FP: an algorithm for large-scale discrete ill-posed problems, BIT, 50, 481-507 (2010) · Zbl 1207.65039
[51] Bazán, F. S.V.; Cunha, M. C.C.; Borges, L. S., Extension of GKB-FP algorithm to large-scale general-form Tikhonov regularization, Numer. Linear Algebra Appl., 21, 316-339 (2014) · Zbl 1340.65071
[52] Chung, J.; Nagy, J. G.; O’Leary, D. P., A weighted-GCV method for Lanczos-hybrid regularization, Electron. Trans. Numer. Anal., 28, 149-167 (2007) · Zbl 1171.65029
[53] Chung, J.; Palmer, K., A hybrid LSMR algorithm for large-scale Tikhonov regularization, SIAM J. Sci. Comput., 37, S562-S580 (2015) · Zbl 1325.65057
[54] van der Sluis, A.; van der Vorst, H. A., The rate of convergence of conjugate gradients, Numer. Math., 48, 543-560 (1986) · Zbl 0596.65015
[55] Stewart, G. W.; Sun, J.-G., Matrix Perturbation Theory, (Computer Science and Scientific Computing (1990), Academic Press, Inc.: Academic Press, Inc. Boston, MA)
[56] Bai, Z.; Demmel, J.; Dongarra, J.; Ruhe, A.; van der Vorst, H. A., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Vol. 11 (2000), SIAM: SIAM Philadelphia, PA
[57] Parlett, B. N., (The Symmetric Eigenvalue Problem. The Symmetric Eigenvalue Problem, Classics in Applied Mathematics, vol. 20 (1998), SIAM: SIAM Philadelphia, PA), Corrected reprint of the 1980 original · Zbl 0885.65039
[58] van der Vorst, H. A., Computational methods for large eigenvalue problems, (Handbook of Numerical Analysis, Vol. VIII (2002), North-Holland: North-Holland Amsterdam), 3-179 · Zbl 1028.65028
[59] Jia, Z.; Niu, D., An implicitly restarted refined bidiagonalization Lanczos method for computing a partial singular value decomposition, SIAM J. Matrix Anal. Appl., 25, 246-265 (2003) · Zbl 1063.65030
[60] Jia, Z.; Niu, D., A refined harmonic Lanczos bidiagonalization method and an implicitly restarted algorithm for computing the smallest singular triplets of large matrices, SIAM J. Sci. Comput., 32, 714-744 (2010) · Zbl 1215.65072
[61] Stewart, G. W., Matrix Algorithms II: Eigensystems (2001), SIAM: SIAM Philadelphia, PA · Zbl 0984.65031
[62] Jia, Z., The convergence of harmonic Ritz values, harmonic Ritz vectors, and refined harmonic Ritz vectors, Math. Comp., 74, 1441-1456 (2005) · Zbl 1072.65051
[63] Hanke, M.; Hansen, P. C., Regularization tools: A matlab package for analysis and solution of discrete ill-posed problems version 4.1 for matlab 7.3 (2008), available from www.netlib.org/numeralgo
[64] Stewart, G. W., Matrix Algorithms I: Basic Decompositions (1998), SIAM: SIAM Philadelphia, PA · Zbl 0910.65012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.