Iteratively reweighted least squares explained

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:

$$\backslash mathop\_\; \backslash sum\_^n\; \backslash big|\; y\_i\; -\; f\_i\; (\backslash boldsymbol\backslash beta)\; \backslash big|^p,$$

by an iterative method in which each step involves solving a weighted least squares problem of the form:^[1]

$$\backslash boldsymbol\backslash beta^\; =\; \backslash underset\; \backslash sum\_^n\; w\_i\; (\backslash boldsymbol\backslash beta^)\; \backslash big|\; y\_i\; -\; f\_i\; (\backslash boldsymbol\backslash beta)\; \backslash 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.^{[2] [3]}

L^p norm linear regression

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

$$\backslash underset\; \backslash big\backslash |\; \backslash mathbf\; y\; -\; X\; \backslash boldsymbol\; \backslash beta\; \backslash |\_p\; =\backslash underset\; \backslash sum\_^n\; \backslash left|\; y\_i\; -\; X\_i\; \backslash boldsymbol\backslash beta\; \backslash right|^p,$$

the IRLS algorithm at step t + 1 involves solving the weighted linear least squares problem:^[4]

$$\backslash boldsymbol\backslash beta^\; =\backslash underset\; \backslash sum\_^n\; w\_i^\; \backslash left|\; y\_i\; -\; X\_i\; \backslash boldsymbol\backslash beta\; \backslash right|^2\; =(X^\; W^\; X)^\; X^\; W^\; \backslash 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^\; =\; \backslash big|y\_i\; -\; X\_i\; \backslash boldsymbol\; \backslash beta\; ^\; \backslash 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,^[5] so the result would be exact) and the formula is:

$$w\_i^\; =\; \backslash frac.$$

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

$$w\_i^\; =\; \backslash 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. ^[6]

See also

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

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

Notes and References

1. C. Sidney Burrus, Iterative Reweighted Least Squares
2. Chartrand . R. . Yin . W. . Iteratively reweighted algorithms for compressive sensing . IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2008 . 3869–3872 . March 31 – April 4, 2008 . 10.1109/ICASSP.2008.4518498 .
3. Daubechies . I. . Devore . R. . Fornasier . M. . Güntürk . C. S. N. . Iteratively reweighted least squares minimization for sparse recovery . 10.1002/cpa.20303 . Communications on Pure and Applied Mathematics . 63 . 1–38 . 2010 . 0807.0575 .
4. Book: Gentle, James . 6.8.1 Solutions that Minimize Other Norms of the Residuals . Matrix algebra . 978-0-387-70872-0 . 10.1007/978-0-387-70873-7 . Springer . New York . 2007 . Springer Texts in Statistics .
5. William A. Pfeil,Statistical Teaching Aids, Bachelor of Science thesis, Worcester Polytechnic Institute, 2006
6. Fox, J.; Weisberg, S. (2013),Robust Regression, Course Notes, University of Minnesota