# On the quality of randomized approximations of Tukey's depth

arXiv: https://arxiv.org/abs/2309.05657 · HTML: https://mlsanity.com/paper/2309.05657/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 54 references that are in the map.
- First posted on arXiv 11 Sep 2023.

## Builds on (most cited first, 5 of 5)

- [Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model](https://mlsanity.com/paper/1506.00691/) (2015)
- [Recent progress in log-concave density estimation](https://mlsanity.com/paper/1709.03154/) (2017)
- [Choosing among notions of multivariate depth statistics](https://mlsanity.com/paper/2004.01927/) (2020)
- [Exact computation of the halfspace depth](https://mlsanity.com/paper/1411.6927/) (2014)
- [Data depth and floating body](https://mlsanity.com/paper/1809.10925/) (2018)

## Built on by (most cited first, 2 of 2)

- [Tukey Depth Mechanisms for Practical Private Mean Estimation](https://mlsanity.com/paper/2502.18698/) (2025)
- [seMCD: Sequentially implemented Monte Carlo depth computation with statistical guarantees](https://mlsanity.com/paper/2507.06227/) (2025)

## Abstract (arXiv)

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.