Coast to Coast Seminar Series: Live from Fredricton, New Brunswick "Halfspace depth: motivation, computation, optimization"

Abstract

The halfspace depth of a point p with respect to a set of points S is the minimum of over all closed halfspaces h with boundary through p, of |h n P |. In this talk I will discuss a motivating example from computational statistics due to Ivan Mizera, and briefly review a method of computing halfspace depth (due to myself, Komei Fukuda, and Vera Rosta) based on discretization of the space of all hyperplanes through P . I will finish by discussing faster, but more memory intensive methods based on branch-and-cut. Several authors have worked on similar methods; the latest being myself and Dan Chen. Compared with some of the earlier formulations we take advantage of more of the geometry of the problem. Unfortunately the transition from integer program to mixed integer program introduces some numerical complications; in particular it introduces "arbitrarily large" and "arbitrarily small" constants into the formulation. Eliminating this numerical unpleasantness is an interesting open (as far as I know) problem.