Implicit iterative algorithm for solving regularized total~least squares problems

D. V. Ivanov ; A. I. Zhdanov

Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences, Tome 26 (2022) no. 2, pp. 311-321.

Résumé

The article considers a new iterative algorithm for solving total least squares problems. A new version of the implicit method of simple iterations based on singular value decomposition is proposed for solving a biased normal system of algebraic equations. The use of the implicit method of simple iterations based on singular value decomposition makes it possible to replace an ill-conditioned problem with a sequence of problems with a smaller condition number. This makes it possible to significantly increase the computational stability of the algorithm and, at the same time, ensures its high rate of convergence. Test examples shown that the proposed algorithm has a higher accuracy compared to the solutions obtained by non-regularized total least squares algorithms, as well as the total least squares solution with Tikhonov regularization.

Détail

Keywords: implicit regularization, total least squares, ill-conditioning, iterative regularization methods.
Mots-clés : singular value decomposition

Bibliographie

[1] Markovsky I., “Bibliography on total least squares and related methods”, Stat. Interface, 3:3 (2010), 329–334 | DOI | Zbl

[2] Pintelon R., Schoukens J., System Identification: A Frequency Domain Approach, IEEE Press, Piscataway, NJ, 2012, xliv+743 pp. | DOI

[3] Pillonetto G., Chen T., Chiuso A., De Nicolao G., Ljung L., Regularized System Identification. Learning Dynamic Models from Data, Communications and Control Engineering, Springer, Cham, 2022, xxiv+377 pp. | DOI | Zbl

[4] Markovsky I., Willems J. C., Van Huffel S., Bart De Moor, Pintelon R., “Application of structured total least squares for system identification and model reduction”, IEEE Trans. Autom. Control, 50:10 (2005), 1490–1500 | DOI | Zbl

[5] Ivanov D. V., “Identification of linear dynamic systems of fractional order with errors in variables based on an augmented system of equations”, Vestn. Samar. Gos. Tekhn. Univ., Ser. Fiz.-Mat. Nauki [J. Samara State Tech. Univ., Ser. Phys. Math. Sci.], 25:3 (2021), 508–518 | DOI | Zbl

[6] Fu H., Barlow J., “A regularized structured total least squares algorithm for high-resolution image reconstruction”, Linear Algebra Appl., 391 (2004), 75–98 | DOI | Zbl

[7] Mesarovic V. Z., Galatsanos N. P., Katsaggelos A. K., “Regularized constrained total least squares image restoration”, IEEE Trans. Image Process., 4:8 (1995), 1096–1108 | DOI

[8] Zhu W., Wang Y., Yao Y., Chang J., Graber H. L., Barbour R. L., “Iterative total least-squares image reconstruction algorithm for optical tomography by the conjugate gradient method”, J. Opt. Soc. Am. A, 14:4 (1997), 799–807 | DOI

[9] Zhu W., Wang Y., Zhang J., “Total least-squares reconstruction with wavelets for optical tomography”, J. Opt. Soc. Am. A, 15:10, 2639–2650 | DOI

[10] Lemmerling P., Mastronardi N., Van Huffel S., “Efficient implementation of a structured total least squares based speech compression method”, Linear Algebra Appl., 366 (2003), 295–315 | DOI | Zbl

[11] Khassina E. M., Lomov A. A., “Audio files compression with the STLS-ESM method”, St. Petersburg State Polytechnical University Journal. Computer Science. Telecommunications and Control Systems, 229:5 (2015), 88–96 | DOI

[12] Golub G. H., Van Loan C., “An analysis of the total least squares problem”, SIAM J. Matrix Anal. Appl., 17:6 (1980), 883–893 | DOI | Zbl

[13] Zhdanov A. I., Shamarov P. A., “The direct projection method in the problem of complete least squares”, Autom. Remote Control, 61:4 (2000), 610–620 | MR | Zbl

[14] Ivanov D., Zhdanov A., “Symmetrical augmented system of equations for the parameter identification of discrete fractional systems by generalized total least squares”, Mathematics, 9:24 (2021), 3250 | DOI

[15] Björk Å., “Newton and Rayleigh quotient methods for total least squares problem”, Recent Advances in Total Least Squares Techniques and Errors in Variables Modeling, Proceedings of the Second Workshop on Total Least Squares and Errors-in-Variables Modeling (Leuven, Belgium, August 21–24, 1996), SIAM, Philadelphia, PA, USA, 1997, 149–160 | Zbl

[16] Björck Å., Heggernes P., Matstoms P., “Methods for large scale total least squares problems”, SIAM J. Matrix Anal. Appl., 22:2 (2000), 413–429 | DOI

[17] Fasino D., Fazzi A., “A Gauss–Newton iteration for total least squares problems”, BIT Numer. Math., 58:2 (2018), 281–299 | DOI | Zbl

[18] Mohammedi A., “Rational–Lanczos technique for solving total least squares problems”, Kuwait J. Sci. Eng., 28:1 (2001), 1–12 | Zbl

[19] Fierro R. D., Golub G. H., Hansen P. C., O'Leary D. P., “Regularization by truncated total least squares”, SIAM J. Sci. Comp., 18:4 (1997), 1223–1241 | DOI | Zbl

[20] Golub G. H., Hansen P. C., O'Leary D. P., “Tikhonov regularization and total least squares”, SIAM J. Matrix Anal. Appl., 21:1 (1999), 185–194 | DOI | Zbl

[21] Lampe J., Voss H., “Solving regularized total least squares problems based on eigenproblems”, Taiwanese J. Math., 14:3A (2010), 885–909 | DOI | Zbl

[22] Sima D. M., Van Huffel S., Golub G. H., “Regularized total least squares based on quadratic eigenvalue problem solvers”, BIT Numer. Math., 44:4 (2004), 793–812 | DOI | Zbl

[23] Lampe J., Voss H., “Efficient determination of the hyperparameter in regularized total least squares problems”, Appl. Numer. Math., 62:9 (2012), 1229–1241 | DOI | Zbl

[24] Zhdanov A. I., “Direct recurrence algorithms for solving the linear equations of the method of least squares”, Comput. Math. Math. Phys., 34:6 (1994), 693–701 | MR | Zbl

[25] Vainiko G. M., Veretennikov A. Yu., Iteratsionnye protsedury v nekorrektno postavlennykh zadachakh [Iteration Procedures in Ill-Posed Problems], Nauka, Moscow, 1986, 177 pp.

[26] Zhdanov A. I., “Implicit iterative schemes based on singular decomposition and regularizing algorithms”, Vestn. Samar. Gos. Tekhn. Univ., Ser. Fiz.-Mat. Nauki [J. Samara State Tech. Univ., Ser. Phys. Math. Sci.], 22:3 (2018), 549–556 | DOI | Zbl

[27] Zhdanov A. I., “The solution of ill-posed stochastic linear algebraic equations by the maximum likelihood regularization method”, USSR Comput. Math. Math. Phys., 28:5 (1988), 93–96 | DOI | MR | Zbl

[28] Gfrerer H., “An a posteriori parameter choice for ordinary and iterated Tikhonov regularization of ill-posed problems leading to optimal convergence rates”, Math. Comp., 49:180 (1987), 507–522 | DOI | Zbl

[29] Hämarik U., Tautenhahn U., “On the monotone error rule for parameter choice in iterative and continuous regularization methods”, BIT Numer. Math., 41:5 (2001), 1029–1038 | DOI

[30] Tautenhahn U., Hämarik U., “The use of monotonicity for choosing the regularization parameter in ill-posed problems”, Inverse Probl., 15:6 (1999), 1487–1505 | DOI | Zbl

[31] Hansen P. C., “Regularization tools version 4.0 for Matlab 7.3”, Numer. Algorithms, 46:2 (2007), 189–194 | DOI | Zbl