Approximate calculation of Tukey's depth and median with high-dimensional data

DOI10.2298/YJOR180520022BMaRDI QIDQ4987798zbMATH OpenWikidataFDO

Authors Milica Bogićević, Milan Merkle

Publication date 4 May 2021

Published in Yugoslav Journal of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.03174

zbMATH Keywords

big datacomputing Tukey's depthdepth functionsmultivariate medians

Mathematics Subject Classification ID

Robustness and adaptive procedures (parametric inference) (62F35) Nonparametric tolerance and confidence regions (62G15) Characterization and structure theory for multivariate probability distributions; copulas (62H05)

Abstract: We present a new fast approximate algorithm for Tukey (halfspace) depth level sets and its implementation-ABCDepth. Given a $d$-dimensional data set for any $dgeq1$, 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 approximate 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") and Tukey's depth of a sample point or out-of-sample point, 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 "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 the time of other implemented algorithms. Also, our algorithms can be used with thousands of multidimensional observations.

Recommendations

• Approximating Tukey's Depth
• Fast implementation of the Tukey depth
• Absolute approximation of Tukey depth: theory and experiments
• An algorithm for the multivariate Tukey median
• Approximate computation of projection depths

Cites work

• Absolute approximation of Tukey depth: theory and experiments
• Algorithm AS 307: Bivariate Location Depth
• Breakdown properties of location estimates based on halfspace depth and projected outlyingness
• Computing depth contours of bivariate point clouds
• Computing halfspace depth and regression depth
• Computing the discrete Fréchet distance with imprecise input
• Exact computation of the halfspace depth
• General notions of statistical depth function.
• High-dimensional computation of the deepest location.
• scientific article; zbMATH DE number 3541764 (Why is no real title available?)
• scientific article; zbMATH DE number 1203741 (Why is no real title available?)
• scientific article; zbMATH DE number 194744 (Why is no real title available?)
• scientific article; zbMATH DE number 6469174 (Why is no real title available?)
• Jensen's inequality for medians
• Jensen's inequality for multivariate medians
• Multivariate spatial U-quantiles: A Bahadur-Kiefer representation, a Theil-Sen estimator for multiple regression, and a robust dispersion estimator
• Some intriguing properties of Tukey's half-space depth
• The depth function of a population distribution.

Cited in

(8)

• The random Tukey depth
• Fast implementation of the Tukey depth
• Absolute approximation of Tukey depth: theory and experiments
• Uniform convergence rates for the approximated halfspace and projection depth
• An algorithm for the multivariate Tukey median
• Approximating Tukey's Depth
• Tukey depths and Hamilton-Jacobi differential equations
• Tukey’s Depth for Object Data

Describes a project that uses

Uses Software

• ABCDepth
• depth
• AS 307
• Quicksort

This page was built for publication: Approximate calculation of Tukey's depth and median with high-dimensional data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4987798)