Fast implementation of the Tukey depth

Xiaohui Liu ()
Additional contact information
Xiaohui Liu: Jiangxi University of Finance and Economics

Computational Statistics, 2017, vol. 32, issue 4, No 9, 1395-1410

Abstract: Abstract Tukey depth function is one of the most famous multivariate tools serving robust purposes. It is also very well known for its computability problems in dimensions $$p \ge 3$$ p ≥ 3 . In this paper, we address this computing issue by presenting two combinatorial algorithms. The first is naive and calculates the Tukey depth of a single point with complexity $$O\left( n^{p-1}\log (n)\right) $$ O n p - 1 log ( n ) , while the second further utilizes the quasiconcave of the Tukey depth function and hence is more efficient than the first. Both require very minimal memory and run much faster than the existing ones. All experiments indicate that they compute the exact Tukey depth.

Keywords: Tukey depth; Quasiconcave; Combinatorial property; Fast computation (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s00180-016-0697-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:compst:v:32:y:2017:i:4:d:10.1007_s00180-016-0697-8

Ordering information: This journal article can be ordered from
http://www.springer.com/statistics/journal/180/PS2

DOI: 10.1007/s00180-016-0697-8

Access Statistics for this article

Computational Statistics is currently edited by Wataru Sakamoto, Ricardo Cao and Jürgen Symanzik

More articles in Computational Statistics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().