×

Lower bounds for computing statistical depth. (English) Zbl 1098.62502

Summary: Given a finite set of points \(S,\) two measures of the depth of a query point \(\theta\) with respect to \(S\) are the Simplicial depth of Liu and the halfspace depth of Tukey (also known as Location depth). We show that computing these depths requires \(\Omega(n \log n)\) time, which matches the upper bound complexities of the algorithms of Rousseeuw and Ruts. Our lower bound proofs may also be applied to two bivariate sign tests: that of Hodges, and that of Oja and Nyblom.

MSC:

62-07 Data analysis (statistics) (MSC2010)
62H99 Multivariate analysis
65C60 Computational problems in statistics (MSC2010)

Software:

AS 307
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ben-Or, M., 1983. Lower bounds for algebraic computation trees. Proceedings of the 15th Annual ACM Symposium on Theory and Computation, pp. 80–86.
[2] Hodges, J.: A bivariate sign test. Ann. math. Statist. 26, 523-527 (1955) · Zbl 0065.12401
[3] Langerman, S., Steiger, W., 2000. The complexity of hyperplane depth in the plane. Japan Conference on Discrete and Computational Geometry. · Zbl 0953.65040
[4] Liu, R.: On a notion of data depth based upon random simplices. Ann. statist. 18, 405-414 (1990) · Zbl 0701.62063
[5] Liu, R.; Singh, K.: Ordering directional data: concepts of data depth on circles and spheres. Ann. statist. 20, No. 3, 1468-1484 (1992) · Zbl 0766.62027
[6] Liu, R.; Singh, K.: A quality index based on data depth and multivariate rank tests. J. amer. Statist. assoc. 88, No. 421, 252-260 (1993) · Zbl 0772.62031
[7] Liu, R.; Parelius, J.; Singh, K.: Multivariate analysis of data depth: descriptive statistics and inference. Ann. statist. 27, No. 3, 783-858 (1999) · Zbl 0984.62037
[8] Miller, K., Ramaswami, S., Rousseeuw, P., Sellarès, T., Souvaine, D., Streinu, I., Struyf, A., 2001. Fast implementation of depth contours using topological sweep. Proceedings of 12th Symposium on Discrete Algorithms (SODA), Washington DC. · Zbl 0988.65005
[9] Oja, H.; Nyblom, J.: Bivariate sign tests. J. amer. Statist. assoc. 84, No. 405, 249-259 (1989) · Zbl 0677.62043
[10] Paul, W., Simon, J., 1980. Decision trees and random access machines. Logic and Algorithmics, Monograph 30, L’Enseignement Mathematique.
[11] Rousseeuw, P.; Hubert, M.: Regression depth. J. amer. Statist. assoc. 94, 388-402 (1999) · Zbl 1007.62060
[12] Rousseeuw, P.; Ruts, I.: Bivariate location depth. Appl. statist. 45, 516-526 (1996) · Zbl 0905.62002
[13] Rousseeuw, P.; Ruts, I.: The depth function of a population distribution. Metrika 49, No. 3, 213-244 (1999) · Zbl 1093.62540
[14] Small, C.: A survey of multidimensional medians. Internat. statist. Rev. 58, 263-277 (1990)
[15] Tukey, J., 1975. Mathematics and the picturing of data. Proceedings of the International Congress of Mathematicians, Vancouver, pp. 523–531. · Zbl 0347.62002
[16] Zuo, Y.; Serfling, R.: General notations of statistical depth function. Ann. statist. 28, No. 2, 461-482 (2000) · Zbl 1106.62334
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.