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:
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
edit
To find the parameters β = (β1, …,βk)T which minimize the Lp norm for the linear regression problem,
where W(t) is the diagonal matrix of weights, usually with all elements set initially to:
and updated after each iteration to:
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:
To avoid dividing by zero, regularization must be done, so in practice the formula is:
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]
^C. Sidney Burrus, Iterative Reweighted Least Squares
^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. doi:10.1109/ICASSP.2008.4518498.
^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. arXiv:0807.0575. doi:10.1002/cpa.20303.
^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.