Algorithms and complexity for least median of squares regression

J. M. Steele, W. L. Steiger

Research output: Contribution to journalArticlepeer-review

47 Scopus citations


Given n points {(xi, yi)} in the plane we study the problem of calculating the least median of squares regression line. This involves the study of the function f{hook}(α, β) = median(|yi-(α+βxi)|); it is piecewise linear and can have a quadratic number of local minima. Several algorithms that locate a minimizer of f{hook} are presented. The best of these has time complexity O(n3) in the worst case. Our most practical algorithm appears to be one which has worst case behavior of O(n3 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).

Original languageEnglish (US)
Pages (from-to)93-100
Number of pages8
JournalDiscrete Applied Mathematics
Issue number1
StatePublished - May 1986

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Algorithms and complexity for least median of squares regression'. Together they form a unique fingerprint.

Cite this