Title: Efficient computation of the angular halfspace depth
Authors: Rainer Dyckerhoff - University of Cologne (Germany) [presenting]
Stanislav Nagy - Charles University (Czech Republic)
Petra Laketa - 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 (also known as angular Tukey's depth) is a tool for non-parametric analysis of directional data. This depth was proposed already in 1987, but its widespread use in practice has been hampered by significant computational issues. An efficient algorithm is presented that is capable of exactly computing the angular halfspace depth in arbitrary dimension and that does not require the data to be in a general position. This algorithm is based on two projection schemes. In a first step, the data are repeatedly projected on a lower dimensional sphere. In a second step, the data are projected from the sphere to a linear space in which a variant of the usual halfspace depth is evaluated. Compared to the algorithm implemented in the R package `depth', this new algorithm is considerably faster. A major advantage of the new algorithm is that the calculation of the depths of additional points with respect to the same dataset is extremely fast. In many cases, the calculation of 1000 depths requires less than ten times the time for calculating the depth of a single point.