When does the Tukey median work?
  We analyze the performance of the Tukey median estimator under total
variation (TV) distance corruptions. Previous results show that under Huber's
additive corruption model, the breakdown point is 1/3 for high-dimensional
halfspace-symmetric distributions. We show that under TV corruptions, the
breakdown point reduces to 1/4 for the same set of distributions. We also show
that a certain projection algorithm can attain the optimal breakdown point of
1/2. Both the Tukey median estimator and the projection algorithm achieve
sample complexity linear in dimension.
