A0526
Title: Exact computation of angular half-space depth
Authors: Rainer Dyckerhoff - University of Cologne (Germany) [presenting]
Stanislav Nagy - Charles University (Czech Republic)
Abstract: Much recent research has focused on directional data, i.e., data on the unit sphere. The angular halfspace depth is a tool for nonparametric analysis of directional data. This depth was proposed as early as 1987, but its widespread use has been hampered by significant computational problems. An efficient algorithm is presented for the exact computation of the angular halfspace depth in arbitrary dimensions, which does not require the data to be in a general position. The algorithm is based on a two-step projection scheme. In the first step, the data are repeatedly projected onto a lower-dimensional sphere. Then, the data are projected from this low-dimensional sphere onto a linear space in which the usual half-space depth is computed with respect to a signed measure. Compared to known algorithms, this new algorithm is significantly faster. However, the main advantage of the proposed algorithm is that it is able to compute the depth of all data points in a sample (with respect to that sample) with the same time complexity as the depth of a single point. Another important advantage of the algorithm is its good parallelizability.
