Iteratively reweighted least squares
Part of a series on 
Regression analysis 

Models 
Estimation 
Background 

The method of iteratively reweighted least squares (IRLS) is used to solve certain optimization problems with objective functions of the form of a pnorm:
[math]\displaystyle{ \mathop{\operatorname{arg\,min}}_{\boldsymbol\beta} \sum_{i=1}^n \big y_i  f_i (\boldsymbol\beta) \big^p, }[/math]
by an iterative method in which each step involves solving a weighted least squares problem of the form:^{[1]}
[math]\displaystyle{ \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. }[/math]
IRLS is used to find the maximum likelihood estimates of a generalized linear model, and in robust regression to find an Mestimator, as a way of mitigating the influence of outliers in an otherwise normallydistributed 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_{1} minimization for sparse recovery
IRLS can be used for ℓ_{1} 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 ℓ_{1} norm and superlinear for ℓ_{t} with t < 1, under the restricted isometry property, which is generally a sufficient condition for sparse solutions.Cite error: Closing </ref>
missing for <ref>
tag
[math]\displaystyle{ \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^{\rm T} W^{(t)} X)^{1} X^{\rm T} W^{(t)} \mathbf{y}, }[/math]
where W^{(t)} is the diagonal matrix of weights, usually with all elements set initially to:
[math]\displaystyle{ w_i^{(0)} = 1 }[/math]
and updated after each iteration to:
[math]\displaystyle{ w_i^{(t)} = \bigy_i  X_i \boldsymbol \beta ^{(t)} \big^{p2}. }[/math]
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,^{[2]} so the result would be exact) and the formula is:
[math]\displaystyle{ w_i^{(t)} = \frac{1}{\bigy_i  X_i \boldsymbol \beta ^{(t)} \big}. }[/math]
To avoid dividing by zero, regularization must be done, so in practice the formula is:
[math]\displaystyle{ w_i^{(t)} = \frac 1 {\max\left\{\delta, \lefty_i  X_i \boldsymbol \beta ^{(t)} \right\right\} }. }[/math]
where [math]\displaystyle{ \delta }[/math] is some small value, like 0.0001.^{[2]} Note the use of [math]\displaystyle{ \delta }[/math] in the weighting function is equivalent to the Huber loss function in robust estimation. ^{[3]}
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
 ↑ C. Sidney Burrus, Iterative Reweighted Least Squares
 ↑ ^{2.0} ^{2.1} William A. Pfeil, Statistical Teaching Aids, Bachelor of Science thesis, Worcester Polytechnic Institute, 2006
 ↑ Fox, J.; Weisberg, S. (2013),Robust Regression, Course Notes, University of Minnesota
References
 Numerical Methods for Least Squares Problems by Åke Björck (Chapter 4: Generalized Least Squares Problems.)
 Practical LeastSquares for Computer Graphics. SIGGRAPH Course 11
External links
Original source: https://en.wikipedia.org/wiki/Iteratively reweighted least squares.
Read more 