About A. N. Tikhonov's regularized least squares method

V. I. Erokhin ; V. V. Volkov

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 13 (2017) no. 1, pp. 4-16

Résumé

The Tikhonov's regularized least squares method (RLS) and its applications to problems of noisy data processing are considered. The starting point of this research is method for solving approximate systems of linear algebraic equations (SLAE), proposed by A. N. Tikhonov in 1980 that he later named 'RLS'. The traditional method of finding sustainable solutions of the problems with approximate data is Tikhonov's regularization: unconditional minimization of the smoothing functional. RLS differs from this approach. This method makes use of the solution approach to the mathematical programming problem of a special kind. Nowadays RLS has not become a common tool for solving approximate linear systems, and the theory of RLS is not well researched. The purpose of the article is to remedy this deficiency. A number of important theoretical and practical aspects of RLS are considered. New results are presented. One of the results is the method of constructing a model SLAE with the exact right-hand side and approximate matrix for which a priori lower bounds for the maximum relative error of RLS are achieved. It is shown that, under certain conditions, RLS reduces to the problem of minimizing the smoothing functional or to the least squares method or — and this is an unexpected result — to the problem of finding a stationary point of smoothing functional with a negative regularization parameter. The algebraic transformation which reduces the conditionality of the RLS problem to a numerical solution is constructed and substantiated. We propose illustrative example of RLS through an applied image restoration problem for an image, registered by a device with an inexact point-spread function. The results of computational experiments are given. Refs 18. Figs 3.

Détail

Keywords: the approximate system of linear algebraic equations, regularized least squares method.

Bibliographie

[1] Tikhonov A. N., “About approximate systems of linear algebraic equations”, USSR Computational Mathematics and Mathematical Physics, 20:6 (1980), 1373–1383 (In Russian) | Zbl

[2] Tikhonov A. N., “About normal solutions of approximate systems of linear algebraic equations”, Papers of Academy of sciences of USSR, 254:3 (1980), 549–554 (In Russian) | Zbl

[3] Tikhonov A. N., “About methods of automation of processing observations”, Vestnik of Academy of sciences of USSR, 1983, no. 1, 14–25 (In Russian)

[4] Tikhonov A. N., Arsenin V. Ya., Methods of solving incorrect problems, Nauka Publ., M., 1986, 288 pp. (In Russian)

[5] Ivanov V. K., Vasin V. V., Tanana V. P., Theory of linear incorrect problems and it's applications, Nauka Publ., M., 1978, 206 pp. (In Russian)

[6] Tikhonov A. N., Goncharsky A. V., Stepanov V. V., Yagola A. G., Numerical methods of solving incorrect problems, Nauka Publ., M., 1990, 229 pp. (In Russian)

[7] Voevodin V. V., Kuznetcov Yu. A., Matrices and calculations, Nauka Publ., M., 1984, 320 pp. (In Russian)

[8] Volkov V. V., Erokhin V. I., “Tikhonov solutions of approximately given systems of linear algebraic equations under finite pertuberations of their matrices”, Computational Mathematics and Mathematical Physics, 50:4 (2010), 589–605 | DOI | MR | Zbl

[9] Lawson Ch., Hanson R. J., Solving least squares problems, Englewood Cliffs, New Jork, 1985, 374 pp. | MR

[10] Volkov V. V., Recovering linear dependencies on inaccurate information, PhD dissertation, Moscow State University of Education, M., 2011, 135 pp. (In Russian)

[11] Horn R. A., Johnson Ch. R., Matrix analysis, Cambridge University Press, Cambridge, 1985, 561 pp. | MR | Zbl

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

[13] Zhdanov A. I., “The method of augmented regularized normal equations”, Computational Mathematics and Mathematical Physics, 52:2 (2012), 194–197 | DOI | MR | Zbl

[14] Gorelik V. A., Erokhin V. I., Optimal matrix correction of inconsistent systems of linear algebraic equations by minimum of euclidean norm, VC RAN, M., 2004, 194 pp. (In Russian)

[15] Erokhin V. I., Volkov V. V., Budaev A. A., “Using negative regularization parameter in Tikhonov's regularized least squares method”, Proceedings of Saint Petersburg State Technological Institute (Technical University), 2014, no. 24(50), 86–92 (In Russian)

[16] Sizikov V. S., Inverse applied problems and Matlab, Lan' Publ., Saint Petersburg, 2011, 256 pp. (In Russian)

[17] Voskoboinikov Yu. E., Litasov V. A., “A stable image reconstruction algorithm for inexact point-spread function”, Optoelectronics, Instrumentation and Data Processing, 42:6 (2006), 3–15 (In Russian)

[18] Erokhin V. I., Volkov V. V., “Recovering images, registered by device with inexact point-spread function, using tikhonov's regularized least squares method”, Intern. Journal of Artificial Intelligence, 13:1 (2015), 12 pp. (data obrascheniya: 01.06.2016) http://www.ceser.in/ceserp/index.php/ijai/article/view/3531