Exact algorithms for implementation of the least absolute deviations method based on the descent through the nodal straight lines

Algorithms for the exact solution of the problem of 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. The proposed algorithms include common descent, descent with the use of sparse matrices and descend with the use of sparse matrices and taking into consideration its directions. 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. We have carried out a comparative analysis of the proposed algorithm based on descent through the nodal straight lines and Waisfeld approximate algorithm by Monte Carlo method of statistical testing. The examples of practical implementation of the proposed algorithms are described.