Iteratively reweighted least squares

The method of iteratively reweighted least squares (IRLS) is used to solve certain optimization problems. It solves objective functions of the form:

${\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}({\boldsymbol {\beta }}){\big |}y_{i}-f_{i}({\boldsymbol {\beta }}){\big |}^{2},$

by an iterative method in which each step involves solving a weighted least squares problem of the form:

${\boldsymbol {\beta }}^{(t+1)}={\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}({\boldsymbol {\beta }}^{(t)}){\big |}y_{i}-f_{i}({\boldsymbol {\beta }}){\big |}^{2}.$

IRLS is used to find the maximum likelihood estimates of a generalized linear model, and in robust regression to find 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 reweighted least squares, in which the objective function is the sum of distances of the estimator from the samples.

Examples

L^p norm linear regression

To find the parameters β = (β₁, …,β_k)^T which minimise the L^p norm for the linear regression problem:

${\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}{\big \|}\mathbf {y} -X{\boldsymbol {\beta }}\|_{p}={\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}\left|y_{i}-X_{i}{\boldsymbol {\beta }}\right|^{p}$

The IRLS algorithm at step t+1 involves solving the weighted linear least squares problem:

${\boldsymbol {\beta }}^{(t+1)}={\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}^{(t)}\left|y_{i}-X_{i}{\boldsymbol {\beta }}\right|^{2}=(X^{\top }WX)^{-1}X^{\top }W\mathbf {y} ,$

where W is the diagonal matrix of weights with elements:

$w_{i}^{(t)}={\big |}y_{i}-X_{i}{\boldsymbol {\beta }}^{(t)}{\big |}^{p-2}.$

In the case p = 1, this corresponds to least absolute deviation regression.

Convergence

Convergence of the method is not guaranteed.

References

• Stanford Lecture Notes on the IRLS algorithm by Antoine Guitton
• Numerical Methods for Least Squares Problems by Åke Björck (Chapter 4: Generalized Least Squares Problems.)
• Robust Estimation in Numerical Recipes in C by Press et al (requires the FileOpen plugin to view)