Statistical depth meets computational geometry: a short survey <s> Halfspace location depth <s> This paper presents algorithms for approximating a set of n points by a linear function, or a line, that minimizes the L 1 norm of vertical and orthogonal distances. The algorithms find exact solutions based upon geometric properties of the problems as opposed to approximate solutions based upon existing numerical techniques. The algorithmic complexity of these problems appears not to have been investigated before our work in [9], although O(n 3 ) naive algorithms can be easily obtained based on some simple characteristics of optimal L 1 solutions. In this paper, an O(n) optimal time algorithm for the weighted vertical L 1 problem is presented. The algorithm is based upon a modified multi-dimensional search technique which extends the applicability of the basic technique to a wider class of problems. An O(n 1.5 log 2 n) algorithm is presented for the unweighted orthogonal problem, and an O(n 2 ) algorithm is presented for the weighted problem. An O( n log n) lower bound for the orthogonal L 1 problem is shown under a certain model of computation. Also, the complexity of solving the orthogonal L 1 problem is related to the construction of the k-belt of an arrangement of lines. <s> BIB001 </s> Statistical depth meets computational geometry: a short survey <s> Halfspace location depth <s> We derive the asymptotic distribution of the maximal depth regression estimator recently proposed in Rousseeuw and Hubert. The estimator is obtained by maximizing a projection-based depth and the limiting distribution is characterized through a max-min operation of a continuous process. The same techniques can be used to obtain the limiting distribution of some other depth estimators including Tukey's deepest point based on half-space depth. Results for the special case of two-dimensional problems have been available, but the earlier arguments have relied on some special geometric properties in the low-dimensional space. This paper completes the extension to higher dimensions for both regression and multivariate location models. <s> BIB002 </s> Statistical depth meets computational geometry: a short survey <s> Halfspace location depth <s> Abstract We propose the bagplot, a bivariate generalization of the univariate boxplot. The key notion is the half space location depth of a point relative to a bivariate dataset, which extends the univariate concept of rank. The “depth median” is the deepest location, and it is surrounded by a “bag” containing the n/2 observations with largest depth. Magnifying the bag by a factor 3 yields the “fence” (which is not plotted). Observations between the bag and the fence are marked by a light gray loop, whereas observations outside the fence are flagged as outliers. The bagplot visualizes the location, spread, correlation, skewness, and tails of the data. It is equivariant for linear transformations, and not limited to elliptical distributions. Software for drawing the bagplot is made available for the S-Plus and MATLAB environments. The bagplot is illustrated on several datasets—for example, in a scatterplot matrix of multivariate data. <s> BIB003 </s> Statistical depth meets computational geometry: a short survey <s> Halfspace location depth <s> Using the DD-plot (depth vs. depth plot), we introduce a new nonparametric classification algorithm and call it DD-classifier. The algorithm is completely nonparametric, and it requires no prior knowledge of the underlying distributions or the form of the separating curve. Thus, it can be applied to a wide range of classification problems. The algorithm is completely data driven and its classification outcome can be easily visualized in a two-dimensional plot regardless of the dimension of the data. Moreover, it has the advantage of bypassing the estimation of underlying parameters such as means and scales, which is often required by the existing classification procedures. We study the asymptotic properties of the DD-classifier and its misclassification rate. Specifically, we show that DD-classifier is asymptotically equivalent to the Bayes rule under suitable conditions, and it can achieve Bayes error for a family broader than elliptical distributions. The performance of the classifier is also examined u... <s> BIB004 </s> Statistical depth meets computational geometry: a short survey <s> Halfspace location depth <s> This article defines and studies a depth for multivariate functional data. By the multivariate nature and by including a weight function, it acknowledges important characteristics of functional data, namely differences in the amount of local amplitude, shape, and phase variation. We study both population and finite sample versions. The multivariate sample of curves may include warping functions, derivatives, and integrals of the original curves for a better overall representation of the functional data via the depth. We present a simulation study and data examples that confirm the good performance of this depth function. Supplementary materials for this article are available online. <s> BIB005 </s> Statistical depth meets computational geometry: a short survey <s> Halfspace location depth <s> We construct classifiers for multivariate and functional data. Our approach is based on a kind of distance between data points and classes. The distance measure needs to be robust to outliers and invariant to linear transformations of the data. For this purpose we can use the bagdistance which is based on halfspace depth. It satisfies most of the properties of a norm but is able to reflect asymmetry when the class is skewed. Alternatively we can compute a measure of outlyingness based on the skew-adjusted projection depth. In either case we propose the DistSpace transform which maps each data point to the vector of its distances to all classes, followed by k-nearest neighbor (kNN) classification of the transformed data points. This combines invariance and robustness with the simplicity and wide applicability of kNN. The proposal is compared with other methods in experiments with real and simulated data. <s> BIB006 </s> Statistical depth meets computational geometry: a short survey <s> Halfspace location depth <s> Functional data are occurring more and more often in practice, and various statistical techniques have been developed to analyze them. In this paper we consider multivariate functional data, where for each curve and each time point a \(p\)-dimensional vector of measurements is observed. For functional data the study of outlier detection has started only recently, and was mostly limited to univariate curves \((p=1)\). In this paper we set up a taxonomy of functional outliers, and construct new numerical and graphical techniques for the detection of outliers in multivariate functional data, with univariate curves included as a special case. Our tools include statistical depth functions and distance measures derived from them. The methods we study are affine invariant in \(p\)-dimensional space, and do not assume elliptical or any other symmetry. <s> BIB007
Let X n = {x 1 , . . . , x n } be a finite set of data points in R d . The Tukey depth or halfspace depth (introduced by BIB001 and further developed by  ) of any point θ in R d (not necessarily a data point) determines how central the point is inside the data cloud. The halfspace depth of θ is defined as the minimal number of data points in any closed halfspace determined by a hyperplane through θ: hdepth(θ; X n ) = min u =1 #{i; u τ x i u τ θ}. Thus, a point lying outside the convex hull of X n has depth 0, and any data point has depth at least 1. The set of all points with depth k is called the kth depth region D k . The halfspace depth regions form a sequence of nested polyhedra. Each D k is the intersection of all halfspaces containing at least n − k + 1 data points. Moreover, every data point must be a vertex of one or more depth regions. The point with maximal halfspace depth is called the Tukey median. When the innermost depth region is larger than a singleton, the Tukey median is defined as its centroid. This makes the Tukey median unique by construction. Note that the depth regions give an indication of the shape of the data cloud. Based on this idea one can construct the bagplot BIB003 , a bivariate version of the univariate boxplot. Figure 2 shows such a bagplot. The cross in the white disk is the Tukey median. The dark area is an interpolation between two subsequent depth regions, and contains 50% of the data. This area (the "bag") gives an idea of the shape of the majority of the data cloud. Inflating the bag by a factor of 3 relative to the Tukey median yields the "fence" (not shown), and data points outside the fence are called outliers and marked by stars. Finally, the light gray area is the convex hull of the non-outlying data points. More generally, in the multivariate case one can define the bagdistance [HRS15b] of a point x relative to the Tukey median and the bag. Assume that the Tukey median lies in the interior of the bag, not on its boundary (this excludes degenerate cases). Then the bagdistance is the smallest real number λ such that the bag inflated (or deflated) by λ around the Tukey median contains the point x. When the Tukey median equals 0, it is shown in BIB006 that the bagdistance satisfies all axioms of a norm except that ||ax|| = |a|||x|| only needs to hold when a 0. The bagdistance is used for outlier detection BIB007 and statistical classification BIB006 . An often used criterion to judge the robustness of an estimator is its breakdown value. The breakdown value is the smallest fraction of data points that we need to replace in order to move the estimator of the contaminated data set arbitrarily far away. The classical mean of a data set has breakdown value zero since we can move it anywhere by moving one observation. Note that for any estimator which is equivariant for translation (which is required to call it a location estimator) the breakdown value can be at most 1/2. (If we replace half of the points by a far-away translation image of the remaining half, the estimator cannot distinguish which were the original data.) The Tukey depth and the corresponding median have good statistical properties. The Tukey median T * is a location estimator with breakdown value ε n (T * ; X n ) 1/(d + 1) for any data set in general position. This means that it remains in a predetermined bounded region unless n/(d + 1) or more data points are moved. At an elliptically symmetric distribution the breakdown value becomes 1/3 for large n, irrespective of d. Moreover, the halfspace depth is invariant under all nonsingular affine transformations of the data, making the Tukey median affine equivariant. Since data transformations such as rotation and rescaling are very common in statistics, this is an important property. The statistical asymptotics of the Tukey median have been studied in BIB002 . The need for fast algorithms for the halfspace depth has only grown over the years, since it is currently being applied to a variety of settings such as nonparametric classification BIB004 . A related development is the fast growing field of functional data analysis, where the data are functions on a univariate interval (e.g. time or wavelength) or on a rectangle (e.g. surfaces, images). Often the function values are themselves multivariate. One can then define the depth of a curve (surface) by integrating the depth over all points as in BIB005 . This functional depth can again be used for outlier detection and classification BIB007 BIB006 , but it requires computing depths in many multivariate data sets instead of just one. Remark: centerpoints. There is a close relationship between the Tukey depth and centerpoints, which have been long studied in computational geometry. In fact, Tukey depth extends the notion of centerpoint. A centerpoint is any point with halfspace depth ⌈n/(d+1)⌉. A consequence of Helly's theorem is that there always exists at least one centerpoint, so the depth of the Tukey median cannot be less than ⌈n/(d + 1)⌉.