Algorithms and complexity for least median of squares regression

J. M. Steele, W. L. Steiger

Research output: Contribution to journalArticlepeer-review

46 Scopus citations

Abstract

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
Volume14
Issue number1
DOIs
StatePublished - May 1986

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

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

Cite this