Des moindres carrés aux moindres déviations

Des moindres carrés aux moindres déviations

Jean-Jacques Fuchs

IRISA/Université de Rennes I Campus de Beaulieu – 35042 Rennes Cedex

Corresponding Author Email: 
fuchs@irisa.fr
Page: 
109-119
|
DOI: 
https://doi.org/10.3166/TS.27.109-119
Received: 
1 October 2009
| |
Accepted: 
15 May 2010
| | Citation

OPEN ACCESS

Abstract: 

Linear regression is mostly dominated by least squares which corresponds to Gaussian noise. But it is known for a long time that if outliers may be present in the measurements, robust regression techniques such as the least absolute deviation method, are preferable. One can also consider an intermediate cost function where residues larger than a threshold h are weighted by the ℓ1-norm and the others by the ℓ2-norm. This leads to the Huber penalization that is optimal for a certain contaminated Gaussian distribution. No closed-form solution exist for these cost function and we propose an algorithm which, initialized by the least squares estimate that is optimal for h infinite, builds the sequence of estimates associated with decreasing h, a zero h corresponding the least absolute deviation estimate.

RÉSUMÉ

La régression linéaire est un domaine important en pratique qui est, en général, associée aux moindres carrés. Mais on sait depuis longtemps que si les erreurs ne sont pas vraiment gaussiennes et peuvent inclure des valeurs aberrantes il est préférable d’utiliser la norme ℓ1 et de passer aux moindres déviations. Une version intermédiaire consiste à minimiser la norme ℓ1 pour les résidus supérieurs à un seuil h et la norme ℓ2 pour les autres, on retrouve alors la fonction de pénalisation de Huber qui est optimale dans un certain sens. On propose un algorithme qui génère la suite de ces optimums. Le coût considéré dépend d’un paramètre h. L’algorithme démarre en h infini avec l’optimum des moindres carrés qui est simple à obtenir, on propage la solution pour h décroissant, et en h nul, on a l’optimum des moindres déviations.

Keywords: 

linear regression, least squares, least deviations, robust estimation

MOTS-CLÉS

régression linéaire, moindres carrés, moindres déviations, estimation robuste

Extended Abstract
1. Introduction
2. Généralités
3. Algorithme D’optimisation
4. Conclusions
  References

Barrodale I., Roberts F. (1973). « An improved algorithm for Discrete ℓ1 linear Approximation », SIAM J. Num. Analysis, vol. 10, n° 5, p. 839-848.

Bloomfield P., Steiger W. (1983). Least Absolute Deviations : Theory, Applications and Algorithms, Birkauser, Boston.

Efron B., Johnstone I., Hastie T., Tibshirani R. (2004). « Least angle regression », Annals of Statistics, vol. 32, p. 407-499.

Fletcher R. (1987). Practical Methods of Optimization, John Wiley & Sons, New York.

Fuchs J.-J. (1999). « A new approach to robust linear regression », 14th IFAC World Congress, Beijing, p. 427-432, july.

Geman D., Yang C. (1995). « Nonlinear image recovery with half-quadratic regularization », IEEE Transactions on Image Processing, vol. 7, n° 7, p. 932-946.

Holland P., Welsh R. (1977). « Robust regression using iteratively reweighted least squares », Comm. Statistics, vol. 6, n° 9, p. 813-828.

Huber P. (1981). Robust statistics, 2nd edn, John Wiley & Sons. Li Y., Arce G. (2004). « A Maximum Likelihood Approach to Least Absolute Deviation Regression », J. of Appl. Sign. Proc., vol. 2004, n° 12, p. 1762-1769.

Rosset S., Zhu J. (2007). « Piecewise Linear Regularized Solution Paths », The Annals of Statistics, vol. 35, n° 3, p. 1012-1030.

Rusinsky S., Olsen E. (1989). « L1 and L∞ Minimization via a Variant of Karmarkar’s algorithm », IEEE Transactions on Signal Processing, vol. 37, n° 2, p. 245-253.

Tibshirani R. (1996). « Regression shrinkage and selection via the lasso. », J. Royal. Statist. Soc. B., vol. 1, p. 267-288.