Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 273-279, 2004.

- Download SoCG version (© 2004 ACM):
- Official SoCG version from ACM's Digital Library (subscription or $5 payment required)

Abstract:

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 ofnpoints inRand a parameter^{d}k, the problem is equivalent to computing the slab bounded by two parallel hyperplanes of minimum separation that containskof 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, under the assumption that deciding whetherngiven points inR^{d}are affinely nondegenerate requires Ω(n) time.^{d}

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 06 Jul 2004