Iteratively reweighted least squares

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

${\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}({\boldsymbol {\beta }}){\big [}y_{i}-\mathbf {x} _{i}^{\top }{\boldsymbol {\beta }}{\big ]}^{2},$

by an iterative method in which each step involves solving a standard weighted linear 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}-\mathbf {x} _{i}^{\top }{\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.

The method

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

$WAx=Wb\,$

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

$r=Ax-b\,$

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 {\rm {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

• 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)