Least Absolute Deviations - Solving Methods

Solving Methods

Though the idea of least absolute deviations regression is just as straightforward as that of least squares regression, the least absolute deviations line is not as simple to compute efficiently. Unlike least squares regression, least absolute deviations regression does not have an analytical solving method. Therefore, an iterative approach is required. The following is an enumeration of some least absolute deviations solving methods.

• Simplex-based methods (such as the Barrodale-Roberts algorithm)
  • Because the problem is a linear program, any of the many linear programming techniques (including the simplex method as well as others) can be applied.
• Iteratively re-weighted least squares
• Wesolowsky’s direct descent method
• Li-Arce’s maximum likelihood approach
• Check all combinations of point-to-point lines for minimum sum of errors

Simplex-based methods are the “preferred” way to solve the least absolute deviations problem. A Simplex method is a method for solving a problem in linear programming. The most popular algorithm is the Barrodale-Roberts modified Simplex algorithm. The algorithms for IRLS, Wesolowsky's Method, and Li's Method can be found in Appendix A of this document, among other methods. Checking all combinations of lines traversing any two (x,y) data points is another method of finding the least absolute deviations line. Since it is known that at least one least absolute deviations line traverses at least two data points, this method will find a line by comparing the SAE of each line, and choosing the line with the smallest SAE. In addition, if multiple lines have the same, smallest SAE, then the lines outline the region of multiple solutions. Though simple, this final method is inefficient for large sets of data.