On the quality of randomized approximations of Tukey's depth
This addresses the computational bottleneck for approximating Tukey's depth in high-dimensional statistics, but it is incremental as it builds on existing randomized methods and focuses on specific distributional assumptions.
The paper investigates the conditions under which randomized algorithms provide good approximations of Tukey's depth for multivariate data, proving that polynomial-time algorithms can approximate extreme depths (near 0 and 1/2) for log-concave isotropic distributions, but exponential complexity is required for intermediate depths.
Tukey's depth (or halfspace depth) is a widely used measure of centrality for multivariate data. However, exact computation of Tukey's depth is known to be a hard problem in high dimensions. As a remedy, randomized approximations of Tukey's depth have been proposed. In this paper we explore when such randomized algorithms return a good approximation of Tukey's depth. We study the case when the data are sampled from a log-concave isotropic distribution. We prove that, if one requires that the algorithm runs in polynomial time in the dimension, the randomized algorithm correctly approximates the maximal depth $1/2$ and depths close to zero. On the other hand, for any point of intermediate depth, any good approximation requires exponential complexity.