Optimal outlier removal in high-dimensional
John Dunagan, Santosh Vempala · 2001
We study the problem of finding an outlier-free subset of a set of points (or a probability distribution) in n-dimensional Euclidean space. A point x is defined to be a β-outlier if there exists some direction w in which its squared distance from the mean along w is greater than β times the average squared distance from the mean along w [1]. Our main theorem is that for any ε>0, there exists a (1-ε) fraction of the original distribution that has no O(\frac{n}{ε}(b+log \frac{n}{ε))-outliers, improving on the previous bound of O(n^7b/ε). This bound is shown to be nearly the best possible. The theorem is constructive, and results in a \frac{1}{1-ε} approximation to the following optimization problem: given a distribution μ (i.e. the ability to sample from it), and a parameter ε>0, find the minimum β for which there exists a subset of probability at least (1-ε) with no β-outliers.