Least absolute deviations (LAD), also known as least absolute errors (LAE), least absolute residuals (LAR), or least absolute values (LAV), is a statistical optimality criterion and a statistical optimization technique based on minimizing the sum of absolute deviations (also sum of absolute residuals or sum of absolute errors) or the L1 norm of such values. It is analogous to the least squares technique, except that it is based on absolute values instead of squared values. It attempts to find a function which closely approximates a set of data by minimizing residuals between points generated by the function and corresponding data points. The LAD estimate also arises as the maximum likelihood estimate if the errors have a Laplace distribution. It was introduced in 1757 by Roger Joseph Boscovich.
Formulation Suppose that the data set consists of the points (xi, yi) with i = 1, 2, ..., n. We want to find a function f such that f ( x i ) ≈ y i . {\displaystyle f(x_{i})\approx y_{i}.}
To attain this goal, we suppose that the function f is of a particular form containing some parameters that need to be determined. For instance, the simplest form would be linear: f(x) = bx + c, where b and c are parameters whose values are not known but which we would like to estimate. Less simply, suppose that f(x) is quadratic, meaning that f(x) = ax2 + bx + c, where a, b and c are not yet known. (More generally, there could be not just one explanator x, but rather multiple explanators, all appearing as arguments of the function f.) We now seek estimated values of the unknown parameters that minimize the sum of the absolute values of the residuals:
S = ∑ i = 1 n | y i − f ( x i ) | . {\displaystyle S=\sum _{i=1}^{n}|y_{i}-f(x_{i})|.}
Solution 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 Recursive reduction of dimensionality 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 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 (Smallest Absolute Error over data points) 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.
Solution using linear programming The problem can be solved using any linear programming technique on the following problem specification. We wish to
Minimize ∑ i = 1 n | y i − a 0 − a 1 x i 1 − a 2 x i 2 − ⋯ − a k x i k | {\displaystyle {\text{Minimize}}\sum _{i=1}^{n}|y_{i}-a_{0}-a_{1}x_{i1}-a_{2}x_{i2}-\cdots -a_{k}x_{ik}|}
with respect to the choice of the values of the parameters a 0 , … , a k {\displaystyle a_{0},\ldots ,a_{k}} , where yi is the value of the ith observation of the dependent variable, and xij is the value of the ith observation of the jth independent variable (j = 1,...,k). We rewrite this problem in terms of artificial variables ui as
Minimize ∑ i = 1 n u i {\displaystyle {\text{Minimize}}\sum _{i=1}^{n}u_{i}}
… excerpt ends here. Continue reading the full article.
