Iteratively reweighted least squares

For International lunar research station, see International Lunar Research Station.

Short description: Method for solving certain optimization problems

Part of a series on

Regression analysis
Models

* Linear regression
* Simple regression
* Polynomial regression
* General linear model

* Generalized linear model
* Discrete choice
* Binomial regression
* Binary regression
* Logistic regression
* Multinomial logit
* Mixed logit
* Probit
* Multinomial probit
* Ordered logit
* Ordered probit
* Poisson

* Multilevel model
* Fixed effects
* Random effects
* Linear mixed-effects model
* Nonlinear mixed-effects model

* Nonlinear regression
* Nonparametric
* Semiparametric
* Robust
* Quantile
* Isotonic
* Principal components
* Least angle
* Local
* Segmented

* Errors-in-variables

Estimation

* Least squares
* Linear
* Non-linear

* Ordinary
* Weighted
* Generalized

* Partial
* Total
* Non-negative
* Ridge regression
* Regularized

* Least absolute deviations
* Iteratively reweighted
* Bayesian
* Bayesian multivariate

Background

* Regression validation
* Mean and predicted response
* Errors and residuals
* Goodness of fit
* Studentized residual
* Gauss–Markov theorem

* v
* t
* e

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:

argminβ∑i=1n|yi−fi(β)|p,

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

β(t+1)=argminβ∑i=1nwi(β(t))|yi−fi(β)|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.

## Contents

* 1 Examples
* 1.1 L1 minimization for sparse recovery
* 1.2 Lp norm linear regression
* 2 See also
* 3 Notes
* 4 References
* 5 External links

## Examples

### L1 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.[2][3]

### Lp norm linear regression

To find the parameters β = (β1, …,βk)T which minimize the Lp norm for the linear regression problem,

argminβ‖𝐲−Xβ‖p=argminβ∑i=1n|yi−Xiβ|p,

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

β(t+1)=argminβ∑i=1nwi(t)|yi−Xiβ|2=(XTW(t)X)−1XTW(t)𝐲,

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

wi(0)=1

and updated after each iteration to:

wi(t)=|yi−Xiβ(t)|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,[5] so the result would be exact) and the formula is:

wi(t)=1|yi−Xiβ(t)|.

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

wi(t)=1max⁡{δ,|yi−Xiβ(t)|}.

where δ is some small value, like 0.0001.[5] Note the use of δ 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

## Notes

1. ↑ C. Sidney Burrus, Iterative Reweighted Least Squares
2. ↑ Chartrand, R.; Yin, W. (March 31 – April 4, 2008). "Iteratively reweighted algorithms for compressive sensing". pp. 3869–3872. doi:10.1109/ICASSP.2008.4518498.
3. ↑ 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–38. doi:10.1002/cpa.20303.
4. ↑ Gentle, James (2007). "6.8.1 Solutions that Minimize Other Norms of the Residuals". Matrix algebra. Springer Texts in Statistics. New York: Springer. doi:10.1007/978-0-387-70873-7. ISBN 978-0-387-70872-0.
5. ↑ 5.0 5.1 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

## 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

* v
* t
* e

Least squares and regression analysis

Computational statistics|

* Least squares
* Linear least squares
* Non-linear least squares
* Iteratively reweighted least squares

Correlation and dependence|

* Pearson product-moment correlation
* Rank correlation (Spearman's rho
* Kendall's tau)
* Partial correlation
* Confounding variable

Regression analysis|

* Ordinary least squares
* Partial least squares
* Total least squares
* Ridge regression

Regression as a
statistical model|

| Linear regression|

* Simple linear regression
* Ordinary least squares
* Generalized least squares
* Weighted least squares
* General linear model

|

Predictor structure|

* Polynomial regression
* Growth curve (statistics)
* Segmented regression
* Local regression

Non-standard|

* Nonlinear regression
* Nonparametric
* Semiparametric
* Robust
* Quantile
* Isotonic

Non-normal errors|

* Generalized linear model
* Binomial
* Poisson
* Logistic

Decomposition of variance|

* Analysis of variance
* Analysis of covariance
* Multivariate AOV

Model exploration|

* Stepwise regression
* Model selection
* Mallows's Cp
* AIC
* BIC
* Model specification
* Regression validation

Background|

* Mean and predicted response
* Gauss–Markov theorem
* Errors and residuals
* Goodness of fit
* Studentized residual
* Minimum mean-square error

Design of experiments|

* Response surface methodology
* Optimal design
* Bayesian design

Numerical approximation|

* Numerical analysis
* Approximation theory
* Numerical integration
* Gaussian quadrature
* Orthogonal polynomials
* Chebyshev polynomials
* Chebyshev nodes

Applications|

* Curve fitting
* Calibration curve
* Numerical smoothing and differentiation
* System identification
* Moving least squares

* Regression analysis category
* Statistics category
*   * Statistics outline
* Statistics topics

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Iteratively reweighted least squares. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Iteratively_reweighted_least_squares&oldid=3988556"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template