Regression analysis of data based on the method of least absolute deviations in dynamic estimation problems

The use of regression analysis in dynamic problems of system estimation requires a high-speed algorithm of model parameter determination. Moreover, the original data may have stochastic heterogeneity which entails the necessity of the estimates of model parameters be resistant to various data anomalies. However, stable estimation methods, including the least absolute deviations method, are significantly inferior to the parametric ones. The goal of the study is to describe a computationally efficient algorithm for implementing the method of least absolute deviations for dynamic estimation of regression models and to study its capabilities for solving practical problems. This algorithm is based on descending along nodal lines. In this case, instead of the values of the objective function, its derivative in the direction of descent is considered. The computational complexity of the algorithm is also reduced due to the use of the solution of the problem at the previous step as a starting point and efficient updating of observations in the current data sample. The external performance of the proposed dynamic version of the algorithm of gradient descent along nodal lines has been compared with the static version and with the least squares method. It is shown that the dynamic version of the algorithm of gradient descent along the nodal lines make it possible to bring the speed close to that of the least squares method for common practical situations and to use the proposed version in dynamic estimation problems for a wide class of systems.

1. Probability and mathematical statistics: Encyclopedia. — Moscow: Bol’shaya Rossiiskaya Éntsiklopediya, 1999. — 910 p. [in Russian].

2. Arkes J. Regression Analysis: A Practical Introduction. — New York: Taylor & Francis Group, 2019. — 363 p.

3. Hoffmann J. P. Linear Regression Models: Applications in R. — Boca Raton: CRC Press, 2022. — 437 p.

4. Demidenko E. Z. Linear and non-linear regression. — Moscow: Finansy i Statistika, 1981. — 302 p. [in Russian].

5. Mudrov V. I., Kushko V. L. Measurement processing methods. Quasi-plausible estimates. — Moscow: Radio i svyaz’, 1983. — 304 p. [in Russian].

6. Bloomfield P., Steiger W. L. Least Absolute Seviations: Theory, Applications, and Algorithms. — Boston – Basel – Stuttgart: Birkhauser, 1983. — 349 p.

7. Birkes D., Dodge Y. Alternative Methods of Regression. — John Wiley & Sons, 1993. — 239 p.

8. Armstrong R. D., Kung D. S. Algorithm AS 132: Least absolute value estimates for a simple linear regression problem / Applied Statistics 1978. Vol. 7. P. 363 – 366. DOI: 10.2307/2347181

9. Wesolowsky G. O. A new descent algorithm for the least absolute value regression problem / Communications in Statistics, Simulation and Computation. 1981. Vol. 10. N 5. P. 479 – 491. DOI: 10.1080/03610918108812224

10. Akimov P. A., Matasov A. I. Nonoptimality levels of the Weisfeld algorithm in the method of the least modules / Avtom. Teplomekh. 2010. N 2. P. 4 – 16 [in Russian].

11. Krzic A. S., Sersic D. L1 Minimization Using Recursive Reduction of Dimensionality / Signal Processing. 2018. Vol. 151. P. 119 – 129. DOI: 10.1016/j.sigpro.2018.05.002

12. Wei Xue, Wensheng Zhang, Gaohang Yu. Least absolute deviations learning of multiple tasks / Journal of Industrial & Management Optimization. 2018. N 14(2). P. 719 – 729. DOI: 10.3934/jimo.2017071

13. Tyrsin A. N. Algorithms for descending along nodal lines in the problem of estimating regression equations by the method of least modules / Zavod. Lab. Diagn. Mater. 2021. Vol. 87. N 5. P. 68 – 75 [in Russian]. DOI: 10.26896/1028-6861-2021-87-5-68-75

14. Akimov P. A., Matasov A. I. Iterative algorithm for L1-approximation in dynamic estimation problems / Avtom. Teplomekh. 2015. N 5. P. 7 – 26 [in Russian]. DOI: 10.1134/S000511791505001X

15. Tyrsin A. N., Golovanov O. A. Dynamic regression modeling based on gradient descent along nodal lines / Sovr. Naukoem. Tekhnol. 2021. N 10. P. 88 – 93 [in Russian]. DOI: 10.17513/snt.38859

16. Tyrsin A. N., Azaryan A. A. Accurate least moduli estimation of linear regression models based on nodal descent / Vestn. YuUrGU. Ser. Mat. Mekh. Fiz. 2018. Vol. 10. N 2. P. 47 – 56 [in Russian]. DOI: 10.14529/mmph180205

17. Mestnikov S. V., Everstova G. V. Jordan – Gauss transform and linear optimization. — Yakutsk: Izd. dom SVFU, 2019. — 160 p. [in Russian].

18. Mikhailov G. A., Voitishek A. V. Numerical statistical modeling. Monte-Carlo methods. — Moscow: Akademiya, 2006. — 368 p. [in Russian].

19. Tukey J. W. A Survey of Sampling from Contaminated Distribution / Contributions to Probability and Statistics. — Stanford: Stanford Univ. Press, 1960. P. 443 – 485.

20. Huber P. Robustness in statistics. — Moscow: Mir, 1984. — 304 p. [Russian translation].

21. Orlov A. I. Diversity of the models for regression analysis (generalizing article) / Zavod. Lab. Diagn. Mater. 2018. Vol. 84. N 5. P. 63 – 73 [in Russian]. DOI: 10.26896/1028-6861-2018-84-5-63-73