Optimal outlier removal in high-dimensional

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