Iteratively reweighted least squares

Regression analysis

Models
Linear regression Simple regression Ordinary least squares Polynomial regression General linear model
Generalized linear model Discrete choice Logistic regression Multinomial logit Mixed logit Probit Multinomial probit Ordered logit Ordered probit Poisson
Multilevel model Fixed effects Random effects Mixed model
Nonlinear regression Nonparametric Semiparametric Robust Quantile Isotonic Principal components Least angle Local Segmented
Errors-in-variables
Estimation
Least squares Ordinary least squares Linear (math) Partial Total Generalized Weighted Non-linear Non-negative Iteratively reweighted Ridge regression LASSO
Least absolute deviations Bayesian Bayesian multivariate
Background
Regression model validation Mean and predicted response Errors and residuals Goodness of fit Studentized residual Gauss–Markov theorem
Statistics portal

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

\underset{\boldsymbol\beta} {\operatorname{arg\,min}} \sum_{i=1}^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:

\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.

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 $\ell$ minimization and smoothed $\ell$ minimization, p < 1, in the compressed sensing problems. It has been proved that the algorithm has a linear rate of convergence for $\ell$ ₁ norm and superlinear for $\ell$ _t with t < 1, under the restricted isometry property, which is generally a sufficient condition for sparse solutions.^[1]^[2] 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{\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:^[3]

\boldsymbol\beta^{(t+1)} = \underset{\boldsymbol\beta}{ \operatorname{arg\,min} } \sum_{i=1}^n w_i^{(t)} \left| y_i - X_i \boldsymbol\beta^{(t)} \right|^2 = (X^{\rm T} W^{(t)} X)^{-1} X^{\rm T} W^{(t)} \mathbf{y},

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

w_i^{(0)} = 1

and updated after each iteration to:

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 (in this case, the problem would be better approached by use of linear programming methods,^[4] so the result would be exact) and the formula is:

w_i^{(t)} = \frac{1}{\big|y_i - X_i \boldsymbol \beta ^{(t)} \big|}.

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

w_i^{(t)} = \frac{1}{\text{max}(\delta, \big|y_i - X_i \boldsymbol \beta ^{(t)} \big|)}.

where $\delta$ is some small value, like 0.0001.^[4]

Notes

↑ Chartrand, R.; Yin, W. (March 31 – April 4, 2008). "Iteratively reweighted algorithms for compressive sensing". IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2008. pp. 3869–3872.
↑ Daubechies, I.; Devore, R.; Fornasier, M.; Güntürk, C. S. N. (2010). "Iteratively reweighted least squares minimization for sparse recovery". Communications on Pure and Applied Mathematics 63: 1. doi:10.1002/cpa.20303.
↑ Gentle, James (2007). "6.8.1 Solutions that Minimize Other Norms of the Residuals". Matrix algebra. New York: Springer. doi:10.1007/978-0-387-70873-7. ISBN 978-0-387-70872-0.
↑ 4.0 4.1 William A. Pfeil, Statistical Teaching Aids, Bachelor of Science thesis, Worcester Polytechnic Institute, 2006

References

University of Colorado Applied Regression lecture slides
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.)
Practical Least-Squares for Computer Graphics. SIGGRAPH Course 11

External links

Solve under-determined linear systems iteratively