×

Extension of Tikhonov regularization method using linear fractional programming. (English) Zbl 1441.47009

Given a real \(m\times n\) matrix \(A\) with \(m\geq n\) and a noisy vector \(b\), this paper focuses on the following least-squares problem: \(\min_{x\in \mathbb{R}^n}\|Ax-b\|^2\). Here \(\|\cdot\|\) is the Euclidean norm. This problem is commonly studied in the framework of the Tikhonov regularization which consists of solving the regularized least-squares problem: \(\min_{x\in \mathbb{R}^n}\|Ax-b\|^2+\|L_{\lambda}x\|^2\), where \(L_{\lambda}\) is the regularization matrix and \(\lambda\) is the regularization parameter. In recent years, various extensions of the Tikhonov regularization have been proposed where authors used the SVD factorization of the matrix \(A\) to provide better-suited regularization matrix and the regularization parameter. Inspired by the recent developments, in this paper the authors propose an extended Tikhonov regularization framework which involves \(2n\) unknown parameters. The parameters can be obtained by solving a linear fractional programming problem. Under the appropriate selection of these parameters, various known methods can be subsumed as a particular case of the proposed approach. The authors provide thorough numerical experimentation to show the efficacy and feasibility of the developed regularization framework. This well-written paper may serve as a valuable resource for researchers working in linear inverse and ill-posed problems and in related fields.

MSC:

47A52 Linear operators and ill-posed problems, regularization
65F22 Ill-posedness and regularization problems in numerical linear algebra
49K40 Sensitivity, stability, well-posedness
65N20 Numerical methods for ill-posed problems for boundary value problems involving PDEs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kabanikhin, S. I., Definitions and examples of inverse and ill-posed problems, J. Inverse Ill-Posed Probl., 16, 317-357 (2008) · Zbl 1170.35100
[2] Hansen, P. C., Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion (1997), SIAM: SIAM Philadelphia · Zbl 0890.65037
[3] Hanson, R. J., A numerical method for solving Fredholm integral equations of the first kind using singular values, SIAM J. Numer. Anal., 8, 616-622 (1971) · Zbl 0199.50803
[4] Varah, J. M., On the numerical solution of ill-conditioned linear systems with applications to ill-posed problems, SIAM J. Numer. Anal., 10, 257-267 (1973) · Zbl 0261.65034
[5] Tikhonov, A. N., Solution of incorrectly formulated problems and the regularization method, Sov. Math. Dokl., 4, 1035-1038 (1963), English translation of Dokl. Akad. Nauk. SSSR., 151 (1963) 501-504 · Zbl 0141.11001
[6] Bjorck, A., Numerical Methods for Least Squares Problems (1996), SIAM: SIAM Philadelphia · Zbl 0847.65023
[7] Elfving, T., Some Numerical Results Obtained with Two Gradient Methods for Solving the Linear Least Squares ProblemReport LITH-MATR-75-5 (1978), Dept. of Mathematics, Linkoping University: Dept. of Mathematics, Linkoping University Sweden
[8] 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
[9] Paige, C. C.; Saunders, M. A., LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8, 43-71 (1982) · Zbl 0478.65016
[10] Paige, C. C.; Saunders, M. A., Algorithm 583. LSQR: Sparse linear equations and least squares problems, ACM Trans. Math. Software, 8, 195-209 (1982)
[11] Fuhry, M.; Reichel, L., A new Tikhonov regularization method, J. Numer. Algorithms, 59, 433-445 (2012) · Zbl 1236.65038
[12] Noschese, S.; Reichel, L., Some matrix nearness problems suggested by Tikhonov regularization, Linear Algebra Appl., 502, 366-386 (2015) · Zbl 1338.65109
[13] Yang, X. J.; Wang, L., A modified Tikhonov regularization method, J. Comput. Appl. Math., 288, 180-192 (2015) · Zbl 1328.65096
[14] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), the Johns Hopkins University Press: the Johns Hopkins University Press Baltimore, MD · Zbl 0865.65009
[15] Engl, H. W.; Hanke, M.; Neubauer, A., Regularization of Inverse Problems (1996), Kluwer: Kluwer Dordecht · Zbl 0859.65054
[16] Rezghi, M.; Hosseini, S. M., A new variant of L-curve for Tikhonov regularization, J. Comput. Appl. Math., 231, 914-924 (2009) · Zbl 1169.65036
[17] Reichel, L.; Sadok, H., A new L-curve for ill-posed problems, J. Comput. Appl. Math., 219, 493-508 (2008) · Zbl 1145.65035
[18] Baumeister, J., Stable Solution of Inverse Problems (1987), Vieweg: Vieweg Braunschweig · Zbl 0623.35008
[19] Bajalinov, E. B., Linear Fractional Programming: Theory, Methods, Applications and Software (2003), Kluwer Academic Publishers · Zbl 1067.90154
[20] Charnes, A.; Cooper, W. W., Programming with linear fractional functionals, J. Naval Res. Logist., 9, 181-186 (1962) · Zbl 0127.36901
[21] Dinkelbach, W., Die maximierung eines quotienten zweier linearer funktionen unter linearen nebenbedingungen, Wahrscheinlichkeitstheorie, 1, 141-145 (1962) · Zbl 0124.36402
[22] Tantawy, S. F., A new procedure for solving linear fractional programming problems, J. Math. Comput. Model., 48, 969-973 (2008) · Zbl 1156.90445
[23] Chun-feng, W.; Pei-ping, S., A global optimization algorithm for linear fractional programming, J. Appl. Math. Comput., 204, 281-287 (2008) · Zbl 1159.65064
[24] Schaible, S., Duality in fractional programming: A unified approach, J. Oper. Res., 24, 452-461 (1976) · Zbl 0348.90120
[25] Singh, S., Optimal conditions in fractional programming, J. Optim. Theory Appl., 33, 287-294 (1981) · Zbl 0422.90078
[26] Hansen, P. C., Regularization tools version 4.0 for Matlab 7.3, J. Numer. Algorithms, 46, 189-194 (2007) · Zbl 1128.65029
[27] Shaw, C. B., 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
[28] Baker, C. T.H., The Numerical Treatment of Integral Equations (1977), Clarendon Press: Clarendon Press Oxford · Zbl 0373.65060
[29] Baart, M. L., The use of auto-correlation for pseudo-rank determination in noisy ill-conditioned least squres problems, IMA J. Numer. Anal., 2, 241-247 (1982) · Zbl 0484.65021
[30] Phillips, D. L., A technique for the numerical solution of certain integral equations of the first kind, J. Assoc. Comput. Mach., 9, 84-97 (1962) · Zbl 0108.29902
[31] Axelsson, O., Iterative Solution Methods (1994), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0795.65014
[32] Bjorck, A.; Elfving, T.; Strakos, Z., Stability of conjugate gradient and Lanczos methods for linear least squares problems, SIAM J. Matrix Anal. Appl., 19, 720-736 (1998) · Zbl 0924.65035
[33] Hansen, P. C., (Discrete Inverse Problems: Insight and Algorithms. Discrete Inverse Problems: Insight and Algorithms, Fundamentals of Algorithms (2010), SIAM) · Zbl 1197.65054
[34] Paige, C. C.; Saunders, M. S., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 2, 617-629 (1975) · Zbl 0319.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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.