Iteratively reweighted least squares

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.

The Method

Starting with a diagonal weighting matrix equal to the identity matrix W = I and a linear problem A x = b, the (weighted) linear equation is formed.

$WAx=Wb$

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

$r=b-Ax$

Using some function f(r) of the residuals, the weighting matrix is re-calculated, e.g. with f(r) = 1/|r|

$W=diag(1/|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 f(r). With f(r) = 1/|r| the objective is the least absolute deviation $SUM{|r_{i}|}$.

Sources

• Stanford Lecture Notes on the IRLS algorithm by Antoine Guitton
• Robust Estimation in Numerical Recipes in C by Press et al (requires the FileOpen plugin to view)