On the Least Median Square Problem |
| |
Authors: | Jeff Erickson Sariel Har-Peled David M Mount |
| |
Institution: | (1) Department of Computer Science, University of Illinois, Urbana, IL 61801, USA;(2) Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742, USA |
| |
Abstract: | 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
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
are affinely non-degenerate requires Ω(nd) time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|