Improved performance guarantees for Tukey's median

Stanislav Minsker, Yinan Shen

Is there a natural way to order data in dimension greater than one? The approach based on the notion of data depth, often associated with John Tukey, is among the most popular. Tuk…