B1811
Title: On polynomial-time algorithms for data depths
Authors: Jeremy Guerin - LTCI, Telecom Paris, Institut Polytechnique de Paris (France) [presenting]
Pavlo Mozharovskyi - Telecom Paris, Institut Polytechnique de Paris (France)
Abstract: Data depth is a set of methods in non-parametric statistics that generalize to higher dimensions, such concepts as cumulative distribution function, median, and quantiles. Having undergone substantial theoretical developments and being known for its attractive properties that include affine invariance and robustness, statistical depth function became a universal methodology with numerous applications. Nevertheless, employing it in practice can be impeded by the high computational complexity of algorithms, in particular for larger data sets. In order to solve this computation problem, we define a new class of depths that can be (re)formulated as a polynomial optimization problem. We study the properties of this class and show that it includes several popular depth notions. To compute these depth functions, we suggest using a hierarchy of semi-definite programming relaxations based on the sum of squares certificates of positivity. The goal is to provide polynomial-time algorithms for depth functions, depending on their properties.
