We consider the exact and approximate computational complexity of the
multivariate LMS linear regression estimator. The LMS estimator is
among the most widely used robust linear statistical estimators. Given
a set of n points in R^{d} and a parameter
k, the problem is equivalent to computing the slab bounded by
two parallel hyperplanes of minimum separation 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 on the computational complexity of these
problems. The lower bounds hold if deciding whether d+1 points
are coplanar requires Omega(n^{d}) time.

@inproceedings{ehm-lmsp-04,
title = {On the Least Median Square Problem},
author = {J. Erickson and S. {Har-Peled} and D. Mount},
year = 2004,
booktitle = SOCG_2004,
pages = {273--279}
}