Iteratively Re-weighted Least Squares

The method of iteratively reweighted least squares (IRLS) is used to solve certain optimization problems with objective functions of the form of a ''p''-norm:

:$\underset \sum_^n \big, y_i - f_i (\boldsymbol\beta) \big, ^p,$

by an iterative method in which each step involves solving a weighted least squares problem of the form:C. Sidney Burrus,
Iterative Reweighted Least Squares
'

:$\boldsymbol\beta^ = \underset \sum_^n w_i (\boldsymbol\beta^) \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 errors rather than the least square errors.

One of the advantages of IRLS over linear programming and convex programming is that it can be used with Gauss–Newton and Levenberg–Marquardt numerical algorithms.

Examples

''L''₁ minimization for sparse recovery

IRLS can be used for ''ℓ''₁ minimization and smoothed ''ℓ''_p minimization, ''p'' < 1, in compressed sensing problems. It has been proved that the algorithm has a linear rate of convergence for ''ℓ''₁ norm and superlinear for ''ℓ''_''t'' with ''t'' < 1, under the restricted isometry property, which is generally a sufficient condition for sparse solutions. However, in most practical situations, the restricted isometry property is not satisfied.

''L^p'' norm linear regression

To find the parameters ''β'' = (''β''₁, …,''β''_''k'')^T which minimize the ''L^p'' norm for the linear regression problem,

:$\underset \big\, \mathbf y - X \boldsymbol \beta \, _p = \underset \sum_^n \left, y_i - X_i \boldsymbol\beta \^p ,$

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

:$\boldsymbol\beta^ = \underset \sum_^n w_i^ \left, y_i - X_i \boldsymbol\beta \^2 = (X^ W^ X)^ X^ W^ \mathbf,$

where ''W''^(''t'') is the diagonal matrix of weights, usually with all elements set initially to:

:$w_i^ = 1$

and updated after each iteration to:

:$w_i^ = \big, y_i - X_i \boldsymbol \beta ^ \big, ^.$

In the case ''p'' = 1, this corresponds to least absolute deviation regression (in this case, the problem would be better approached by use of linear programming methods,William A. Pfeil,

Statistical Teaching Aids
', Bachelor of Science thesis, Worcester Polytechnic Institute, 2006 so the result would be exact) and the formula is:

:$w_i^ = \frac.$

To avoid dividing by zero, regularization must be done, so in practice the formula is:

:$w_i^ = \frac 1 .$

where $\delta$ is some small value, like 0.0001. Note the use of $\delta$ in the weighting function is equivalent to the Huber loss function in robust estimation. Fox, J.; Weisberg, S. (2013),
Robust Regression
', Course Notes, University of Minnesota

See also

* Feasible generalized least squares
* Weiszfeld's algorithm (for approximating the geometric median), which can be viewed as a special case of IRLS

Notes

References

Numerical Methods for Least Squares Problems by Åke Björck
(Chapter 4: Generalized Least Squares Problems.)

Practical Least-Squares for Computer Graphics. SIGGRAPH Course 11

External links

Solve under-determined linear systems iteratively

{{DEFAULTSORT:Iteratively Reweighted Least Squares
Least squares