×

Efficiently solving total least squares with Tikhonov identical regularization. (English) Zbl 1391.90498

Summary: The Tikhonov identical regularized total least squares (TI) is to deal with the ill-conditioned system of linear equations where the data are contaminated by noise. A standard approach for (TI) is to reformulate it as a problem of finding a zero point of some decreasing concave non-smooth univariate function such that the classical bisection search and Dinkelbach’s method can be applied. In this paper, by exploring the hidden convexity of (TI), we reformulate it as a new problem of finding a zero point of a strictly decreasing, smooth and concave univariate function. This allows us to apply the classical Newton’s method to the reformulated problem, which converges globally to the unique root with an asymptotic quadratic convergence rate. Moreover, in every iteration of Newton’s method, no optimization subproblem such as the extended trust-region subproblem is needed to evaluate the new univariate function value as it has an explicit expression. Promising numerical results based on the new algorithm are reported.

MSC:

90C26 Nonconvex programming, global optimization
90C20 Quadratic programming
90C32 Fractional programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beck, A; Ben-Tal, A, On the solution of the Tikhonov regularization of the total least squares problem, SIAM J. Optim., 17, 98-118, (2006) · Zbl 1112.65034 · doi:10.1137/050624418
[2] Beck, A; Teboulle, M, A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid, Math. Program. Ser. A., 118, 13-15, (2009) · Zbl 1176.90451 · doi:10.1007/s10107-007-0181-x
[3] Beck, A; Ben-Tal, A; Teboulle, M, Finding a global optimal solution for a quadratically constrained fractional quadratic problem with applications to the regularized total least squares, SIAM J. Matrix Anal. Appl., 28, 425-445, (2006) · Zbl 1115.65065 · doi:10.1137/040616851
[4] Charnes, A; Cooper, WW, Programming with linear fractional functionals, Nav. Res. Logist. Q., 9, 181-186, (1962) · Zbl 0127.36901 · doi:10.1002/nav.3800090303
[5] Dinkelbach, W, On nonlinear fractional programming, Manag. Sci., 13, 492-498, (1967) · Zbl 0152.18402 · doi:10.1287/mnsc.13.7.492
[6] Gol’stein, EG, Dual problems of convex and fractionally-convex programming in functional spaces, Sov. Math. Dokl., 8, 212-216, (1967)
[7] Golub, GH; Loan, CF, An analysis of the total least-squares problem, SIAM J. Numer. Anal., 17, 883-893, (1980) · Zbl 0468.65011 · doi:10.1137/0717073
[8] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[9] Hansen, PC, Regularization tools: a Matlab package for analysis and solution of discrete ill-posed problems, Numer. Algorithm, 6, 1-35, (1994) · Zbl 0789.65029 · doi:10.1007/BF02149761
[10] 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 · doi:10.1137/0914086
[11] Hebden, MD, An algorithm for minimization using exact second derivatives, Int. J. Distrib. Sens. Netw., 2014, 1-8, (1973)
[12] Jagannathan, R, On some properities of programming problems in parametric form pertaining to fractional programming, Manag. Sci., 12, 609-615, (1966) · Zbl 0143.21602 · doi:10.1287/mnsc.12.7.609
[13] Jain, A.K.: Fundamentals of Digital Image Processing. Prentice-Hall, Englewood Cliffs (1989) · Zbl 0744.68134
[14] Lampe, J; Voss, H, Large-scale Tikhonov regularization of total least squares, J. Comput. Appl. Math., 238, 95-108, (2013) · Zbl 1254.65052 · doi:10.1016/j.cam.2012.08.023
[15] Moosaei, H; Ketabchi, S; Pardalos, PM, Tikhonov regularization for infeasible absolute value equations, Optimization, 65, 1531-1537, (2016) · Zbl 1346.90688 · doi:10.1080/02331934.2016.1154963
[16] Moré, JJ, Generalization of the trust region problem, Optim. Methods Softw., 2, 189-209, (1993) · doi:10.1080/10556789308805542
[17] Renaut, RA; Guo, H, Efficient algorithms for solution of regularized total least squares, SIAM J. Matrix Anal. Appl., 26, 457-476, (2005) · Zbl 1082.65045 · doi:10.1137/S0895479802419889
[18] Schaible, S, Fractional programming II: on dinkelbach’s algorithm, Manag. Sci., 22, 868-873, (1976) · Zbl 0346.90052 · doi:10.1287/mnsc.22.8.868
[19] Sima, D; Huffel, S; Golub, GH, Regularized total least squares based on quadratic eigenvalue problem solvers, BIT, 44, 793-812, (2004) · Zbl 1079.65048 · doi:10.1007/s10543-004-6024-8
[20] Tikhonov, A.N., Arsenin, V.Y.: Solution of Ill-Posed Problems. V.H. Winston, Washington (1977) · Zbl 0354.65028
[21] Van Huffel, S., Lemmerling, P.: Total Least Squares and Errors-in-Variables Modeling. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 1002.65500 · doi:10.1007/978-94-017-3552-0
[22] Van Huffel, S., Vandewalle, J.: The Total Least Squares Problem: Computational Aspects and Analysis. Frontiers in Applied Mathematics. SIAM, Philadelphia (1991) · Zbl 0789.62054 · doi:10.1137/1.9781611971002
[23] Xia, Y; Wang, S; Sheu, RL, S-lemma with equality and its applications, Math. Program. Ser. A., 156, 513-547, (2016) · Zbl 1333.90086 · doi:10.1007/s10107-015-0907-0
[24] Zhang, A; Hayashi, S, Celis-dennis-tapia based approach to quadratic fractional programming problems with two quadratic constraints, Numer. Algebra Control Optim., 1, 83-98, (2011) · Zbl 1219.90169 · doi:10.3934/naco.2011.1.83
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.