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 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, under the assumption that deciding whether n given points in ℝd are affinely nondegenerate requires Ω(nd) time.
Original language | English (US) |
---|---|
Pages | 273-279 |
Number of pages | 7 |
DOIs | |
State | Published - 2004 |
Event | Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: Jun 9 2004 → Jun 11 2004 |
Other
Other | Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) |
---|---|
Country/Territory | United States |
City | Brooklyn, NY |
Period | 6/9/04 → 6/11/04 |
Keywords
- Approximation algorithms
- LMS regression
- Lower bounds
- Robust statistics
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics