On the least median square problem

Research output: Contribution to journalArticlepeer-review


We consider the exact and approximate computational complexity of the multivariate least median-of-squares (LMS) linear regression estimator. The LMS estimator is among the most widely used robust linear statistical estimators. Given a set of n points in ℝd and a parameter k, the problem is equivalent to computing the narrowest slab bounded by two parallel hyperplanes that contains k of the points. We present algorithms for the exact and approximate versions of the multivariate LMS problem. We also provide nearly matching lower bounds for these problems. These lower bounds hold under the assumptions that k is Ω(n) and that deciding whether n given points in ℝd are affinely non-degenerate requires Ω(nd) time.

Original languageEnglish (US)
Pages (from-to)593-607
Number of pages15
JournalDiscrete and Computational Geometry
Issue number4
StatePublished - Dec 2006

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'On the least median square problem'. Together they form a unique fingerprint.

Cite this