B1774
Title: ABCDepth: Efficient algorithm for Tukey depth
Authors: Milica Bogicevic - Faculty of Electrical Engineering (Serbia and Montenegro) [presenting]
Milan Merkle - University of Belgrade (Uruguay)
Abstract: A new fast approximate algorithm is presented for Tukey (halfspace) depth level sets and its implementation. Given a $d$-dimensional data set for any $d\geq 2$, the algorithm is based on a representation of level sets as intersections of balls in $\mathbb{R}^d$. Our approach does not need calculations of projections of sample points to directions. This novel idea enables calculations of level sets in very high dimensions with complexity which is linear in $d$, which provides a great advantage over all other approximate algorithms. Using different versions of this algorithm we demonstrate approximate calculations of the deepest set of points (Tukey median), Tukey's depth of a sample point and of out-of-sample point as well as approximate level sets that can be used for constructing depth contours, all with a linear in $d$ complexity. An additional theoretical advantage of this approach is that the data points are not assumed to be in any ``general position''. Examples with real and synthetic data show that the executing time of the algorithm in all mentioned versions in high dimensions is much smaller than other implemented algorithms and that it can accept thousands of multidimensional observations.
Journal