Exact computation of the halfspace depth. (English) Zbl 1468.62048
Summary: For computing the exact value of the halfspace depth of a point w.r.t. a data cloud of \(n\) points in arbitrary dimension, a theoretical framework is suggested. Based on this framework a whole class of algorithms can be derived. In all of these algorithms the depth is calculated as the minimum over a finite number of depth values w.r.t. proper projections of the data cloud. Three variants of this class are studied in more detail. All of these algorithms are capable of dealing with data that are not in general position and even with data that contain ties. As is shown by simulations, all proposed algorithms prove to be very efficient.
MSC:
| 62-08 | Computational methods for problems pertaining to statistics |
| 62H05 | Characterization and structure theory for multivariate probability distributions; copulas |
| 62F35 | Robustness and adaptive procedures (parametric inference) |
| 62H99 | Multivariate analysis |
References:
| [1] | Afshani, P.; Chan, T., On approximate range counting and depth, Discrete Comput. Geom., 42, 3-21, (2009) · Zbl 1180.68124 |
| [2] | Bremner, D.; Chen, D.; Iacono, J.; Langerman, S.; Morin, P., Output-sensitive algorithms for tukey depth and related problems, Stat. Comput., 18, 259-266, (2008) |
| [3] | Bremner, D.; Fukuda, K.; Rosta, V., Primal-dual algorithms for data depth, (Liu, R.; Serfling, R.; Souvaine, D., Data Depth: Robust Multivariate Analysis, Computational Geometry and Applications, (2006), American Mathematical Society Providence, RI), 171-194 |
| [4] | Burr, M.A., Rafalin, E., Souvaine, D.L., 2011. Dynamic maintenance of half-space depth for points and contours. arXiv:1109.1517 [cs.CG]. |
| [5] | Cascos, I.; Molchanov, I., Multivariate risks and depth-trimmed regions, Finance Stoch., 11, 373-397, (2007) · Zbl 1164.91027 |
| [6] | Chen, D.; Morin, P.; Wagner, U., Absolute approximation of tukey depth: theory and experiments, Comput. Geom., 46, 566-573, (2013) · Zbl 1261.65021 |
| [7] | Cuesta-Albertos, J. A.; Nieto-Reyes, A., The random tukey depth, Comput. Statist. Data Anal., 52, 4979-4988, (2008) · Zbl 1452.62344 |
| [8] | Donoho, D. L., Breakdown properties of multivariate location estimators, (1982), Harvard University, (Ph.D. Qualifying Paper) |
| [9] | Donoho, D. L.; Gasko, M., Breakdown properties of location estimates based on halfspace depth and projected outlyingness, Ann. Statist., 20, 1803-1827, (1992) · Zbl 0776.62031 |
| [10] | Dyckerhoff, R., Inference based on data depth, (Mosler, K., Multivariate Dispersion, Central Regions and Depth: The Lift Zonoid Approach, (2002), Springer New York), (Chapter 5) · Zbl 1027.62033 |
| [11] | Dyckerhoff, R., Data depths satisfying the projection property, AStA Adv. Stat. Anal., 88, 163-190, (2004) · Zbl 1294.62112 |
| [12] | Edelsbrunner, H., Algorithms in combinatorial geometry, (1987), Springer Berlin, Heidelberg · Zbl 0634.52001 |
| [13] | Hallin, M.; Paindaveine, D.; Šiman, M., Multivariate quantiles and multiple-output regression quantiles: from \(L_1\)-optimization to halfspace depth, Ann. Statist., 38, 635-669, (2010) · Zbl 1183.62088 |
| [14] | Hodges, J. L., A bivariate sign test, Ann. Math. Statist., 26, 523-527, (1955) · Zbl 0065.12401 |
| [15] | Johnson, T.; Kwok, I.; Ng, R., Fast computation of 2-dimensional depth contours, (Agrawal, R.; Stolorz, P., Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, (1998), AAAI Press New York), 224-228 |
| [16] | Johnson, D. S.; Preparata, F. P., The densest hemisphere problem, Theoret. Comput. Sci., 6, 93-107, (1978) · Zbl 0368.68053 |
| [17] | Kong, L.; Mizera, I., Quantile tomography: using quantiles with multivariate data, Statist. Sinica, 22, 1589-1610, (2012) · Zbl 1359.62175 |
| [18] | Koshevoy, G., The tukey depth characterizes the atomic measure, J. Multivariate Anal., 83, 360-364, (2002) · Zbl 1028.62040 |
| [19] | Koshevoy, G.; Mosler, K., Zonoid trimming for multivariate distributions, Ann. Statist., 25, 1998-2017, (1997) · Zbl 0881.62059 |
| [20] | Lange, T.; Mosler, K.; Mozharovskyi, P., Fast nonparametric classification based on data depth, Statist. Papers, 55, 49-69, (2014) · Zbl 1283.62128 |
| [21] | Liu, R. Y., On a notion of simplicial depth, Proc. Natl. Acad. Sci. USA, 85, 1732-1734, (1988) · Zbl 0635.62039 |
| [22] | Liu, R. Y., On a notion of data depth based on random simplices, Ann. Statist., 18, 405-414, (1990) · Zbl 0701.62063 |
| [23] | Liu, R. Y., Data depth and multivariate rank tests, (Dodge, Y., \(L_1\)-Statistical Analysis and Related Methods, (1992), North-Holland Amsterdam), 279-294 · Zbl 1058.62501 |
| [24] | Liu, R. Y.; Parelius, J. M.; Singh, K., Multivariate analysis by data depth: descriptive statistics, graphics and inference, (with discussion), Ann. Statist., 27, 783-858, (1999) · Zbl 0984.62037 |
| [25] | Liu, R. Y.; Singh, K., A quality index based on data depth and multivariate rank tests, J. Amer. Statist. Assoc., 88, 252-260, (1993) · Zbl 0772.62031 |
| [26] | Liu, X., 2014. Fast implementation of the Tukey depth. arXiv:1409.3901 [stat.CO]. |
| [27] | Liu, X.; Zuo, Y., Computing halfspace depth and regression depth, Commun. Stat. - Simul. Comput., 43, 969-985, (2014) · Zbl 1291.62059 |
| [28] | Miller, K.; Ramaswami, S.; Rousseeuw, P.; Sellarès, J. A.; Souvaine, D.; Streinu, I.; Struyf, A., Efficient computation of location depth contours by methods of computational geometry, Stat. Comput., 13, 153-162, (2003) |
| [29] | Mosler, K., Multivariate dispersion, central regions and depth: the lift zonoid approach, (2002), Springer New York · Zbl 1027.62033 |
| [30] | Mosler, K., Depth statistics, (Becker, C.; Fried, R.; Kuhnt, S., Robustness and Complex Data Structures, Festschrift in Honour of Ursula Gather, (2013), Springer Berlin, Heidelberg), 17-34 · Zbl 1290.62004 |
| [31] | Mosler, K.; Bazovkin, P., Stochastic linear programming with a distortion risk constraint, OR Spectrum, 36, 949-969, (2014) · Zbl 1305.90321 |
| [32] | Mosler, K.; Hoberg, R., Data analysis and classification with the zonoid depth, (Liu, R.; Serfling, R.; Souvaine, D., Data Depth: Robust Multivariate Analysis, Computational Geometry and Applications, (2006), American Mathematical Society Providence, RI), 49-59 |
| [33] | Mosler, K.; Lange, T.; Bazovkin, P., Computing zonoid trimmed regions of dimension \(d > 2\), Comput. Statist. Data Anal., 53, 2500-2510, (2009) · Zbl 1453.62159 |
| [34] | Paindaveine, D.; Šiman, M., Computing multiple-output regression quantile regions, Comput. Statist. Data Anal., 56, 840-853, (2012) · Zbl 1244.62060 |
| [35] | Paindaveine, D.; Šiman, M., Computing multiple-output regression quantile regions from projection quantiles, Comput. Statist., 27, 29-49, (2012) · Zbl 1304.65060 |
| [36] | Rousseeuw, P. J.; Hubert, M., Regression depth, (with discussion), J. Amer. Statist. Assoc., 94, 388-433, (1999) · Zbl 1007.62060 |
| [37] | Rousseeuw, P. J.; Ruts, I., Algorithm AS 307: bivariate location depth, J. Roy. Statist. Soc. Ser. C, 45, 516-526, (1996) · Zbl 0905.62002 |
| [38] | Rousseeuw, P. J.; Struyf, A., Computing location depth and regression depth in higher dimensions, Stat. Comput., 8, 193-203, (1998) |
| [39] | Ruts, I.; Rousseeuw, P. J., Computing depth contours of bivariate point clouds, Comput. Statist. Data Anal., 23, 153-168, (1996) · Zbl 0900.62337 |
| [40] | Ruts, I., Rousseeuw, P.J., 1996b. Isodepth: A program for depth contours. In: Prat, A. (ed.), Proceedings in Computational Statistics, COMPSTAT 1996. Physica, Heidelberg, pp. 441-446. |
| [41] | Stahel, W. A., Robuste schätzungen: infinitesimale optimalität und schätzungen von kovarianzmatrizen, (1981), ETH Zürich, (Ph.D. Thesis) · Zbl 0531.62036 |
| [42] | Tukey, J. W., Mathematics and the picturing of data, (James, R. D., Proceeding of the International Congress of Mathematicians, Vancouver 1974, Vol. 2, (1975), Canadian Mathematical Congress Montreal), 523-531 · Zbl 0347.62002 |
| [43] | Zuo, Y., Projection-based depth functions and associated medians, Ann. Statist., 31, 1460-1490, (2003) · Zbl 1046.62056 |
| [44] | Zuo, Y.; Serfling, R., General notions of statistical depth function, Ann. Statist., 28, 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.
