Computing the spherical depth of points in the plane

January 17, 2017
Halligan 102
Speaker: Raoul Shahsavarifar, University of New Brunswick
Host: Diane Souvaine


*Refreshments at 9.50am; talk starts at 10.00am*

The rank statistic tests play an important role in univariate nonparametric statistics. If one attempts to generalize the rank tests to a multivariate case, the problem of defining a multivariate order will occur. One approach to overcome this problem is to use the notion of data depth which measures the centrality of a point in a given data set. Over the last few decades, various notions of data depth have emerged as powerful tools for nonparametric multivariate data analysis. One of these data depths is spherical depth (Elmore, Hettmansperger, and Xuan, 2006).

For a distribution function F on R^d and a point t in R^d, the spherical depth SphD(t; F) is defined to be the probability that the point t is contained inside a random closed hyper-ball obtained from a pair of points from F. Also, the spherical depth SphD(t; S) is introduced for an arbitrary data set S and a point t in R^d. This definition is based on counting all of the closed hyper-balls, obtained from pairs of points in S, that contain t. The significant advantage of using the spherical depth in multivariate data analysis is related to its complexity of computation. Unlike most other data depths, the time complexity of the spherical depth grows linearly rather than exponentially in the dimension d. The straightforward algorithm for computing the spherical depth in dimension d takes O(dn^2).

The main result of this paper is an O(n log n) algorithm that we present for computing the bivariate spherical depth. Some geometric properties of the spherical depth are also investigated. These properties indicate that the simplicial depth (Liu, 1990 ) is bounded by the spherical depth (in particular, SphD >= 2/3 SD). To illustrate this relationship between the spherical depth and the simplicial depth, some experimental results are provided. The obtained experimental bound (SphD >= 2SD) indicates that, perhaps, a stronger theoretical bound can be achieved.

Bio: Rasoul is a PhD student in computer science at the University of New Brunswick (UNB), Canada. His research interest is computational geometry and algorithms. He is currently working on "algorithmic and geometric aspects of data depth" as his PhD project under the supervision of Dr. David Bremner. His most recent results include developing an algorithm for the spherical depth.