Uniform convergence rates for the approximated halfspace and projection depth. (English) Zbl 1460.62060

For nonparametric statistical analysis of multidimensional data, a general concept that is used is data depth. Two types of depths, namely half-space depth and projection depth, are frequently used. Exact evaluation of data depth is often difficult. Hence the attention in this paper is on procedures to approximate the true depth. Statistical properties of these approximation procedures are studied in this paper. The conditions under which uniform convergence of the approximated depth to its true depth are explored and the convergence rates are evaluated. Under some regularity conditions, it is shown that uniform approximations of the depth are valid and convergence rates can be computed. Guidelines are provided to determine the number \(n\) of directions needed to achieve the desired precision. Two main theorems are established. Explicit and exact rates of convergence are established in a number of distributions including multivariate Gaussian. Explicit guidelines are given for the choice of \(n\), the random sample of directions, to achieve the desired quality of approximation. Situations, where uniform approximation cannot be achieved, are also discussed. Extensions of the concept of projection depth are also explored.


62G20 Asymptotic properties of nonparametric inference
41A25 Rate of convergence, degree of approximation
41A29 Approximation with constraints
41A63 Multidimensional problems
62H11 Directional data; spatial statistics
62H12 Estimation in multivariate analysis
Full Text: DOI arXiv Euclid


[1] Aaron, C., Cholaquidis, A., and Fraiman, R. (2017). A generalization of the maximal-spacings in several dimensions and a convexity test., Extremes, 20(3):605-634. · Zbl 1382.60023
[2] Alexander, K. S. (1984). Probability inequalities for empirical processes and a law of the iterated logarithm., Ann. Probab., 12(4):1041-1067. · Zbl 0549.60024
[3] Bingham, N. H. (1986). Variants on the law of the iterated logarithm., Bull. London Math. Soc., 18(5):433-467. · Zbl 0633.60042
[4] Bogicevic, M. and Merkle, M. (2018). Approximate calculation of Tukey’s depth and median with high-dimensional data., Yugosl. J. Oper. Res., 28(4):475-499.
[5] Burr, M. A. and Fabrizio, R. J. (2017). Uniform convergence rates for halfspace depth., Statist. Probab. Lett., 124:33-40. · Zbl 1463.62140
[6] Chen, D., Morin, P., and Wagner, U. (2013). Absolute approximation of Tukey depth: theory and experiments., Comput. Geom., 46(5):566-573. · Zbl 1261.65021
[7] Chen, Z. and Tyler, D. E. (2004). On the behavior of Tukey’s depth and median under symmetric stable distributions., J. Statist. Plann. Inference, 122(1-2):111-124. · Zbl 1040.62038
[8] Cuesta-Albertos, J. A. and Nieto-Reyes, A. (2008). The random Tukey depth., Comput. Statist. Data Anal., 52(11):4979-4988. · Zbl 1452.62344
[9] DeVore, R. A. and Lorentz, G. G. (1993)., Constructive approximation, volume 303 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin. · Zbl 0797.41016
[10] Devroye, L. (1981). Laws of the iterated logarithm for order statistics of uniform spacings., Ann. Probab., 9(5):860-867. · Zbl 0465.60038
[11] Diaconis, P. and Freedman, D. (1984). Asymptotics of graphical projection pursuit., Ann. Statist., 12(3):793-815. · Zbl 0559.62002
[12] Donoho, D. L. (1982). Breakdown properties of multivariate location estimators. Qualifying paper, Harvard, University.
[13] Donoho, D. L. and Gasko, M. (1992). Breakdown properties of location estimates based on halfspace depth and projected outlyingness., Ann. Statist., 20(4):1803-1827. · Zbl 0776.62031
[14] Dudley, R. M. (2002)., Real analysis and probability, volume 74 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge. Revised reprint of the 1989 original. · Zbl 1023.60001
[15] Dyckerhoff, R. (2004). Data depths satisfying the projection property., Allg. Stat. Arch., 88(2):163-190. · Zbl 1294.62112
[16] Dyckerhoff, R., Mozharovskyi, P., and Nagy, S. (2020). Approximate computation of projection depths., arXiv:2007.08016.
[17] Embrechts, P. and Hofert, M. (2013). A note on generalized inverses., Math. Methods Oper. Res., 77(3):423-432. · Zbl 1281.60014
[18] Fang, K. T., Kotz, S., and Ng, K. W. (1990)., Symmetric multivariate and related distributions, volume 36 of Monographs on Statistics and Applied Probability. Chapman and Hall, Ltd., London. · Zbl 0699.62048
[19] Horn, R. A. and Johnson, C. R. (1994)., Topics in matrix analysis. Cambridge University Press, Cambridge. Corrected reprint of the 1991 original. · Zbl 0801.15001
[20] Janson, S. (1986). Random coverings in several dimensions., Acta Math., 156(1-2):83-118. · Zbl 0597.60014
[21] Janson, S. (1987). Maximal spacings in several dimensions., Ann. Probab., 15(1):274-280. · Zbl 0626.60017
[22] Johnson, D. S. and Preparata, F. P. (1978). The densest hemisphere problem., Theoret. Comput. Sci., 6(1):93-107. · Zbl 0368.68053
[23] Kuelbs, J. and Dudley, R. M. (1980). Log log laws for empirical measures., Ann. Probab., 8(3):405-418. · Zbl 0442.60031
[24] Lin, P. E. (1972). Some characterizations of the multivariate \(t\) distribution., J. Multivariate Anal., 2:339-344.
[25] Liu, R. Y., Parelius, J. M., and Singh, K. (1999). Multivariate analysis by data depth: descriptive statistics, graphics and inference., Ann. Statist., 27(3):783-858. · Zbl 0984.62037
[26] Liu, R. Y. and Singh, K. (1993). A quality index based on data depth and multivariate rank tests., J. Amer. Statist. Assoc., 88(421):252-260. · Zbl 0772.62031
[27] Liu, X. and Zuo, Y. (2014). Computing projection depth and its associated estimators., Stat. Comput., 24(1):51-63. · Zbl 1325.62014
[28] Massé, J.-C. (2004). Asymptotics for the Tukey depth process, with an application to a multivariate trimmed mean., Bernoulli, 10(3):397-419. · Zbl 1053.62021
[29] Massé, J.-C. and Theodorescu, R. (1994). Halfplane trimming for bivariate distributions., J. Multivariate Anal., 48(2):188-202. · Zbl 0790.60024
[30] Mosler, K. (2002)., Multivariate dispersion, central regions and depth: The lift zonoid approach, volume 165 of Lecture Notes in Statistics. Springer-Verlag, Berlin. · Zbl 1027.62033
[31] Mozharovskyi, P., Mosler, K., and Lange, T. (2015). Classifying real-world data with the \(DD\alpha \)-procedure., Adv. Data Anal. Classif., 9(3):287-314. · Zbl 1414.62258
[32] Rousseeuw, P. J. and Ruts, I. (1999). The depth function of a population distribution., Metrika, 49(3):213-244. · Zbl 1093.62540
[33] Rudin, W. (1987)., Real and complex analysis. McGraw-Hill Book Co., New York, third edition. · Zbl 0925.00005
[34] Serfling, R. (2006). Multivariate symmetry and asymmetry., Encyclopedia of Statistical Sciences, Second Edition, 8:5338-5345.
[35] Shao, W. and Zuo, Y. (2012). Simulated annealing for higher dimensional projection depth., Comput. Statist. Data Anal., 56(12):4026-4036. · Zbl 1255.62188
[36] Shao, W. and Zuo, Y. (2020). Computing the halfspace depth with multiple try algorithm and simulated annealing algorithm., Comput. Stat., 35:203-226. · Zbl 07206119
[37] Stahel, W. A. (1981). Robuste Schätzungen: Infinitesimale Optimalität und Schätzungen von Kovarianzmatrizen. Ph.D. thesis, ETH, Zürich. · Zbl 0531.62036
[38] Talagrand, M. (1994). Sharper bounds for Gaussian and empirical processes., Ann. Probab., 22(1):28-76. · Zbl 0798.60051
[39] Tukey, J. W. (1975). Mathematics and the picturing of data. In, Proceedings of the International Congress of Mathematicians (Vancouver, BC, 1974), Vol. 2, pages 523-531. Canad. Math. Congress, Montreal, Que.
[40] Vapnik, V. N. and Chervonenkis, A. Y. (2015). On the uniform convergence of relative frequencies of events to their probabilities. In, Measures of complexity, pages 11-30. Springer, Cham. Reprint of Theor. Probability Appl. 16 (1971), 264-280. · Zbl 0247.60005
[41] Yukich, J. E. (1990). The law of the iterated logarithm for empirical processes. In, Probability in Banach spaces 6 (Sandbjerg, 1986), volume 20 of Progr. Probab., pages 265-282. Birkhäuser Boston, Boston, MA.
[42] Zolotarev, V. M. (1986)., One-dimensional stable distributions, volume 65 of Translations of Mathematical Monographs. American Mathematical Society, Providence, RI. Translated from the Russian by H. H. McFaden, Translation edited by Ben Silver. · Zbl 0589.60015
[43] Zuo, Y. (2003). Projection-based depth functions and associated medians., Ann. Statist., 31(5):1460-1490. · Zbl 1046.62056
[44] Zuo, Y. and Lai, S. (2011). Exact computation of bivariate projection depth and the Stahel-Donoho estimator., Comput. Statist. Data Anal., 55(3):1173-1179. · Zbl 1328.65050
[45] Zuo, Y. · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.