Geodesic
Exact evaluation of linear regression models by the least absolute deviations method based on the descent through the nodal straight lines
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika, Tome 10 (2018) no. 2, pp. 47-56 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

When building linear models, in many cases one has to deal with stochastic nonhomogeneity of experimental data. This manifests itself in violation of the assumptions of the Gauss–Markov theorem, in particular, observations can contain outliers. Under these circumstances the estimation of the parameters of models is required to be performed using resistant methods. Among those is the least absolute deviations method. However, the known algorithms for its implementation are sufficiently effective only for small dimensions of models and a limited volume of samples. The purpose of this study is the development of effective computational algorithms for implementation of the least absolute deviations method, which have no limitations as to the order of models, and the amount of experimental data. Algorithms for the exact solution of the problem on estimating the parameters of linear regression models by the least absolute deviations method are described. They are based on the descent through the nodal straight lines. To reduce computational costs, the particular feature of nodal straight lines is used — all nodes located on each such straight line are intersections of a set of hyperplanes, of which only one hyperplane is different. These algorithms significantly outperform the best-known brute-force search and can be effectively used in practice. The computational complexity of the descent algorithm for nodal straight lines is assessed. The scheme of the algorithm is provided.
Keywords: the least absolute deviations method, linear regression model, algorithm, nodal straight line, hyperplane, computational complexity.
Mots-clés : nodal point 
@article{VYURM_2018_10_2_a4,
     author = {A. N. Tyrsin and A. A. Azaryan},
     title = {Exact evaluation of linear regression models by the least absolute deviations method based on the descent through the nodal straight lines},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matematika, mehanika, fizika},
     pages = {47--56},
     year = {2018},
     volume = {10},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURM_2018_10_2_a4/}
}
TY  - JOUR
AU  - A. N. Tyrsin
AU  - A. A. Azaryan
TI  - Exact evaluation of linear regression models by the least absolute deviations method based on the descent through the nodal straight lines
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika
PY  - 2018
SP  - 47
EP  - 56
VL  - 10
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VYURM_2018_10_2_a4/
LA  - ru
ID  - VYURM_2018_10_2_a4
ER  - 
%0 Journal Article
%A A. N. Tyrsin
%A A. A. Azaryan
%T Exact evaluation of linear regression models by the least absolute deviations method based on the descent through the nodal straight lines
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika
%D 2018
%P 47-56
%V 10
%N 2
%U http://geodesic.mathdoc.fr/item/VYURM_2018_10_2_a4/
%G ru
%F VYURM_2018_10_2_a4
A. N. Tyrsin; A. A. Azaryan. Exact evaluation of linear regression models by the least absolute deviations method based on the descent through the nodal straight lines. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika, Tome 10 (2018) no. 2, pp. 47-56. http://geodesic.mathdoc.fr/item/VYURM_2018_10_2_a4/

[1] Kendel M. D., St'yuart A., Statistical Inferences and Relationships, Nauka Publ., M., 1973, 899 pp. (in Russ.)

[2] Korolyuk V. S., Portenko N. I., Skorokhod A. V., Turbin A. F., A Handbook on Probability Theory and Mathematical Statistics, Nauka Publ., M., 1985, 640 pp. (in Russ.)

[3] Demidenko E. Z., Linear and nonlinear regression, Finansy i statistika Publ., M., 1981, 302 pp. (in Russ.)

[4] Ayvazyan S. A., Enyukov I. S., Meshalkin L. D., Applied statistics: Dependency Studies, Finansy i statistika Publ., M., 1985, 487 pp. (in Russ.)

[5] P. Bloomfield, W.L. Steiger, Least absolute seviations: theory, applications, and algorithms, Birkhauser, Boston–Basel–Stuttgart, 1983, 349 pp. | MR

[6] Mudrov V. I., Kushko V. L., Measurement processing methods: quasi-truth estimates, Radio i svyaz' Publ., M., 1983, 304 pp. (in Russ.)

[7] E. Weiszfeld, “On the point for which the sum of the distances to n given points is minimum”, Annals of Operations Research, 167:1 (2009), 7–41 | DOI | MR | Zbl

[8] Akimov P. A., Matasov A. I., “Levels of nonoptimality of the Weiszfeld Algorithm in the leastmodules method”, Automation and Remote Control, 71:2 (2010), 172–184 | DOI | MR | Zbl

[9] Tyrsin A. N., Maksimov K. E., “Estimation of the Linear Regression Equations Using the Least Modules Method”, Zavodskaya laboratoriya. Diagnostika materialov, 78:7 (2012), 65–71 (in Russ.)

[10] S. Boyd, L. Vandenberghe, Convex optimization, Cambridge University Press, Cambridge, 2004, 730 pp. | DOI | MR | Zbl

[11] Zukhovitskiy S. I., Avdeeva L. I., Linear and convex programming, Nauka Publ., M., 1967, 460 pp. (in Russ.)

[12] Panyukov A. V., Gorbik V. V., “Using massively parallel computations for absolutely precise solution of the linear programming problems”, Automation and Remote Control, 73:2 (2012), 276–290 | DOI | MR | Zbl

[13] Rokafellar R., Convex analysis, Mir Publ., M., 1973, 469 pp. (in Russ.)

[14] Mikhaylov G. A., Voytishek A. V., Numerical statistical modeling. Monte Carlo methods, Akademiya Publ., M., 2006, 368 pp. (in Russ.)

[15] Kormen T. Kh., Leyzerson Ch., Rivest R., Shtayn K., Algorithms: construction and analysis, Vil'yams Publ., M., 2013, 1323 pp. (in Russ.)