Affordable Access

Publisher Website

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
  • Computer Science

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.