Iteratively re-weighted least squares

The method of iteratively re-weighted least squares (IRLS) is a numerical algorithm for minimizing any specified objective function using a standard weighted least squares method such as Gaussian elimination. Whereas techniques are widely available and highly optimized for weighted least squares, there are few techniques for minimization of other objective functions.

The IRLS is commonly used to perform robust regression with an M-estimator, as a way of mitigating the influence of outliers in an otherwise normally distributed data set. For example, by minimizing the least absolute error rather than the least square error.

Although not a linear regression problem, Weiszfeld's algorithm for approximating the geometric median can also be viewed as a special case of iteratively re-weighted least squares, in which the objective function is the sum of distances of the estimator from the samples.

The method

Starting with a diagonal weighting matrix equal to the identity matrix $scriptstyle\; W\; =\; I$ and a linear problem $scriptstyle\; A\; x\; =\; b$, the (weighted) linear equation

:$W\; A\; x\; =\; W\; b\; ,$

is formed. The least squares solution of this equation is then found using standard linear algebra methods. The residuals

:$r\; =\; b\; -\; A\; x\; ,$

are calculated and the weighting matrix is updated to some non-negative function $scriptstyle\; f(r)$ of the residuals, "r", e.g., $scriptstyle\; f(r)\; =\; 1/|r|$

:$W\; =\; mathop\{\; m\; diag\}(\; f(r)\; ).\; ,$

With these new weights, the weighted least squares equation is re-solved and the residuals are re-calculated. The process can be iterated many times.

The solution to which this iterative process converges is the minimizer of an objective function related to the function $scriptstyle\; f(r)$. With $scriptstyle\; f(r)\; =\; 1/|r|$ the objective is the least absolute deviation $scriptstyle\; sum\; |r\_i|$.

Convergence

Convergence of the method is not guaranteed. For example, choosing "f(r) = |r|^p" with "p" < −1 or "p" ≥ 1 may cause successive solutions to keep oscillating without converging to a limit.

References

* [http://sepwww.stanford.edu/public/docs/sep103/antoine2/paper_html/index.html Stanford Lecture Notes on the IRLS algorithm by Antoine Guitton]
* [http://www.mai.liu.se/~akbjo/LSPbook.html Numerical Methods for Least Squares Problems by Åke Björck] (Chapter 4: Generalized Least Squares Problems.)
* [http://www.nrbook.com/a/bookcpdf/c15-7.pdf Robust Estimation in Numerical Recipes in C by Press et al] (requires the [http://www.nr.com/plugin/plugin_faq.html FileOpen] plugin to view)