A0231
Title: An efficient algorithm for computing the angular halfspace depth of a whole sample
Authors: Rainer Dyckerhoff - University of Cologne (Germany) [presenting]
Stanislav Nagy - Charles University (Czech Republic)
Abstract: A great deal of research has recently 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 in practice has been hampered by significant computational issues. We present an efficient algorithm for exactly computing the angular halfspace depth in arbitrary dimensions. Moreover, this algorithm 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 is repeatedly projected onto a lower-dimensional sphere. Then, the data is projected from this lower dimensional sphere onto a linear space in which the usual halfspace depth is calculated with respect to a signed measure. Compared to known algorithms, this new algorithm is considerably 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. This is particularly important since calculating the depth of all points in a sample is a common task when using depth-based methods.
