×

zbMATH — the first resource for mathematics

Old and new parameter choice rules for discrete ill-posed problems. (English) Zbl 1267.65045
Summary: Linear discrete ill-posed problems are difficult to solve numerically because their solution is very sensitive to perturbations, which may stem from errors in the data and from round-off errors introduced during the solution process. The computation of a meaningful approximate solution requires that the given problem is replaced by a nearby problem that is less sensitive to disturbances. This replacement is known as regularization. A regularization parameter determines how much the regularized problem differs from the original one. The proper choice of this parameter is important for the quality of the computed solution.
This paper studies the performance of known and new approaches to choosing a suitable value of the regularization parameter for the truncated singular value decomposition method and for the LSQR iterative Krylov subspace method in the situation when no accurate estimate of the norm of the error in the data is available. The regularization parameter choice rules considered include several L-curve methods, T. Regińska’s method [SIAM J. Sci. Comput. 17, No. 3, 740–749 (1996; Zbl 0865.65023)] and a modification thereof, extrapolation methods, the quasi-optimality criterion, rules designed for use with LSQR as well as hybrid methods.

MSC:
65F22 Ill-posedness and regularization problems in numerical linear algebra
65F10 Iterative numerical methods for linear systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bakushinskii, AB, Remarks on choosing a regularization parameter using quasi-optimality and ratio criterion, USSR Comp. Math. Math. Phys., 24, 181-182, (1984) · Zbl 0595.65064
[2] Bauer, F; Kindermann, S, Recent results on the quasi-optimality principle, J. Inverse Ill-Posed Probl., 17, 5-18, (2009) · Zbl 1159.65051
[3] Bauer, F; Lukas, MA, Comparing parameter choice methods for regularization of ill-posed problem, Math. Comput. Simul., 81, 1795-1841, (2011) · Zbl 1220.65063
[4] Bauer, F., Reiß, M.: Regularization independent of the noise-level: an analysis of quasi-optimality. Inverse Probl. 24, 055009 (16 pp) (2008) · Zbl 1147.49024
[5] Björck, Å.: Numerical Methods for Least Squares Problems. SIAM, Philadelphia (1996) · Zbl 0847.65023
[6] Brezinski, C; Rodriguez, G; Seatzu, S, Error estimates for linear systems with applications to regularization, Numer. Algorithms, 49, 85-104, (2008) · Zbl 1162.65018
[7] Brezinski, C; Rodriguez, G; Seatzu, S, Error estimates for the regularization of least squares problems, Numer. Algorithms, 51, 61-76, (2009) · Zbl 1166.65331
[8] Calvetti, D; Golub, GH; Reichel, L, Estimation of the L-curve via Lanczos bidiagonalization, BIT, 39, 603-619, (1999) · Zbl 0945.65044
[9] Calvetti, D; Hansen, PC; Reichel, L, L-curve curvature bounds via Lanczos bidiagonalization, Electron. Trans. Numer. Anal., 14, 20-35, (2002) · Zbl 1029.65041
[10] Calvetti, D; Lewis, B; Reichel, L; GMRES, L-curves, and discrete ill-posed problems, BIT, 42, 44-65, (2002) · Zbl 1003.65040
[11] Calvetti, D; Reichel, L, Tikhonov regularization of large linear problems, BIT, 43, 263-283, (2003) · Zbl 1038.65048
[12] Castellanos, JL; Gómez, S; Guerra, V, The triangle method for finding the corner of the L-curve, Appl. Numer. Math., 43, 359-373, (2002) · Zbl 1014.65022
[13] Donatelli, M, Fast transforms for high order boundary conditions in deconvolution problems, BIT, 50, 559-576, (2010) · Zbl 1204.65151
[14] Eldén, L, A weighted pseudoinverse, generalized singular values, and constrained least squares problems, BIT, 22, 487-501, (1982) · Zbl 0509.65019
[15] Engl, H.W., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Kluwer, Dordrecht (1996) · Zbl 0859.65054
[16] Golub, GH; Meurant, G; Griffiths, DF (ed.); Watson, GA (ed.), Matrices, moments and quadrature, 105-156, (1994), Essex · Zbl 0795.65019
[17] Golub, G.H., Meurant, G.: Matrices, Moments and Quadrature with Applications. Princeton University Press, Princeton (2010) · Zbl 1217.65056
[18] Golub, GH; Matt, U; Golub, GH (ed.); Lui, SH (ed.); Luk, F (ed.); Plemmons, R (ed.), Tikhonov regularization for large scale problems, 3-26, (1997), New York · Zbl 0927.65058
[19] Golub, GH; Matt, U, Generalized cross-validation for large scale problems, J. Comput. Graph. Stat., 6, 1-34, (1997)
[20] Hanke, M.: Conjugate Gradient Type Methods for Ill-Posed Problems. Longman, Essex (1995) · Zbl 0830.65043
[21] Hanke, M, Limitations of the L-curve method in ill-posed problems, BIT, 36, 287-301, (1996) · Zbl 0849.65039
[22] Hanke, M; Hansen, PC, Regularization methods for large-scale problems, Surv. Math. Ind., 3, 253-315, (1993) · Zbl 0805.65058
[23] Hansen, PC, Regularization, GSVD and truncated GSVD, BIT, 29, 491-504, (1989) · Zbl 0682.65021
[24] Hansen, PC, Analysis of the discrete ill-posed problems by means of the L-curve, SIAM Rev., 34, 561-580, (1992) · Zbl 0770.65026
[25] Hansen, P.C.: Rank-Deficient and Discrete Ill-Posed Problems. SIAM, Philadelphia (1998) · Zbl 0890.65037
[26] Hansen, PC, Regularization tools version 4.0 for Matlab 7.3, Numer. Algorithms, 46, 189-194, (2007) · Zbl 1128.65029
[27] Hansen, PC; Jensen, TK; Rodriguez, G, An adaptive pruning algorithm for the discrete L-curve criterion, J. Comput. Appl. Math., 198, 483-492, (2006) · Zbl 1101.65044
[28] Hansen, PC; O’Leary, DP, 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
[29] Hämarik, U; Palm, R; Raus, T, A family of rules for parameter choice in Tikhonov regularization of ill-posed problems with inexact noise level, J. Comput. Appl. Math., 236, 2146-2157, (2012) · Zbl 1247.65071
[30] Hnětynková, I; 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
[31] Kindermann, S, Convergence analysis of minimization-based noise level-free parameter choice rules for linear ill-posed problems, Electron. Trans. Numer. Anal., 38, 233-257, (2011) · Zbl 1287.65043
[32] Lukas, MA, Robust generalized cross-validation for choosing the regularization parameter, Inverse Probl., 22, 1883-1902, (2006) · Zbl 1104.62032
[33] Morigi, S; Reichel, L; Sgallari, F; Zama, F, Iterative methods for ill-posed problems and semiconvergent sequences, J. Comput. Appl. Math., 193, 157-167, (2006) · Zbl 1092.65025
[34] Neuman, A; Reichel, L; Sadok, H, Implementations of range restricted iterative methods for linear discrete ill-posed problems, Linear Algebra Appl., 436, 3974-3990, (2012) · Zbl 1241.65045
[35] Neuman, A; Reichel, L; Sadok, H, Algorithms for range restricted iterative methods for linear discrete ill-posed problems, Numer. Algorithms, 59, 325-331, (2012) · Zbl 1236.65040
[36] Paige, CC; Saunders, MA, LSQR an algorithm for sparse linear equations and sparse least squares, Trans. Math. Software, 8, 43-71, (1982) · Zbl 0478.65016
[37] Phillips, DL, A technique for the numerical solution of certain integral equations of the first kind, J. ACM, 9, 84-97, (1962) · Zbl 0108.29902
[38] Reichel, L; Rodriguez, G; Seatzu, S, Error estimates for large-scale ill-posed problems, Numer. Algorithms, 51, 341-361, (2009) · Zbl 1166.65332
[39] Reichel, L; Sadok, H, A new L-curve for ill-posed problems, J. Comput. Appl. Math., 219, 493-508, (2008) · Zbl 1145.65035
[40] Reichel, L; Ye, Q, Simple square smoothing regularization operators, Electron. Trans. Numer. Anal., 33, 63-83, (2009) · Zbl 1171.65033
[41] Regińska, T, A regularization parameter in discrete ill-posed problems, SIAM J. Sci. Comput., 17, 740-749, (1996) · Zbl 0865.65023
[42] Shaw, CB, Improvements of the resolution of an instrument by numerical solution of an integral equation, J. Math. Anal. Appl., 37, 83-112, (1972) · Zbl 0237.65086
[43] Tikhonov, A., Arsenin, V.: Solutions of Ill-Posed Problems. Wiley, New York (1977) · Zbl 0354.65028
[44] Vogel, CR, Non-convergence of the L-curve regularization parameter selection method, Inverse Probl., 12, 535-547, (1996) · Zbl 0867.65025
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.