Optimal Outlier Removal

John Dunagan


May 9,
refreshments at 3:45pm


Given a set of points in $n$-dimensional Euclidean space, we define a point $x$ to be a $\gamma$-outlier if there exists some direction $w$ in which it is more than $\gamma$ standard deviations from the mean along $w$. Outlier removal is the problem of removing an $\epsilon$ fraction of points so that the remaining subset has no $\gamma$-outliers. We characterize the optimal trade-off between $\epsilon$ and $\gamma$ using a simple algorithm for outlier removal. The algorithm suggests a natural linear ordering of the point set with interesting properties.

It is our hope that this work will be of interest to experimental scientists as well as the mathematics community. For a demonstration, please visit http://theory.lcs.mit.edu/~jdunagan

This is joint work with Santosh Vempala.

Speaker's Contact Info: jdunagan(at-sign)math.mit.edu

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on April 26, 2001 at 03:42 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.