Algorithms and complexity for least median of squares regression. (English) Zbl 0587.62078
Given n points \(\{(x_ i,y_ i)\}\) in the plane we study the problem of calculating the least median of squares regression line. This involves the study of the function \(f(\alpha,\beta)=median(| y_ i-(\alpha +\beta x_ i)|);\) it is piecewise linear and can have a quadratic number of local minima.
Several algorithms that locate a minimizer of f are presented. The best of these has time complexity \(O(n^ 3)\) in the worst case. Our most practical algorithm appears to be one which has worst case behavior of \(O(n^ 3\log (n))\), but we provide a probabilistic speed-up of this algorithm which appears to have expected time complexity of O((n log(n))\({}^ 2)\).
Several algorithms that locate a minimizer of f are presented. The best of these has time complexity \(O(n^ 3)\) in the worst case. Our most practical algorithm appears to be one which has worst case behavior of \(O(n^ 3\log (n))\), but we provide a probabilistic speed-up of this algorithm which appears to have expected time complexity of O((n log(n))\({}^ 2)\).
MSC:
| 62F35 | Robustness and adaptive procedures (parametric inference) |
| 65C99 | Probabilistic methods, stochastic differential equations |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
breakdown point; robustness; least median of squares regression line; piecewise linear; quadratic number of local minima; algorithms; time complexityReferences:
| [1] | Donoho, D. L.; Huber, P. J., The notion of breakdown point, (Bickel, P. J.; Doksum, K.; Hodges, J. L., A Festschrift for Erich L. Lehman (1983), Wadsworth: Wadsworth Belmont, CA), 157-184 · Zbl 0523.62032 |
| [2] | Hampel, F. R., A general qualitative definition of robustness, Ann. Math. Statist., 42, 1887-1896 (1971) · Zbl 0229.62041 |
| [3] | Hodges, J. L., Efficiency in normal samples and tolerance of extreme values of location, (Proc. Fifth Berkeley Symposium on Mathematical Statistics and Probability (1967)), 163-168 · Zbl 0211.50205 |
| [4] | Leroy, A.; Rousseeuw, P. J., PROGRES: A program for robust regression, (Report 201 (1984), Centrum voor Statistiek en Operationeel Onderzoek, Univ. of Brussels) · Zbl 0551.62049 |
| [5] | Rousseeuw, P. J., Least median of squares regression, J. Amer. Statist. Assoc., 79, 871-880 (1984) · Zbl 0547.62046 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
