# Algorithms and complexity for least median of squares regression

- Authors
- Journal
- Discrete Applied Mathematics 0166-218X
- Publisher
- Elsevier
- Publication Date
- Volume
- 14
- Issue
- 1
- Identifiers
- DOI: 10.1016/0166-218x(86)90009-0
- Disciplines

## Abstract

Abstract 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 ƒ(α, β) = median(|y i−(α+βx i)|) ; it is piecewise linear and can have a quadratic number of local minima. Several algorithms that locate a minimizer of ƒ 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).

## There are no comments yet on this publication. Be the first to share your thoughts.