  Data depth is a non parametric statistical tool that measures centrality of
any element $x\in\mathbb{R}^d$ with respect to (w.r.t.) a probability
distribution or a data set. It is a natural median-oriented extension of the
cumulative distribution function (cdf) to the multivariate case. Consequently,
its upper level sets -- the depth-trimmed regions -- give rise to a definition
of multivariate quantiles. In this work, we propose two new pseudo-metrics
between continuous probability measures based on data depth and its associated
central regions. The first one is constructed as the Lp-distance between data
depth w.r.t. each distribution while the second one relies on the Hausdorff
distance between their quantile regions. It can further be seen as an original
way to extend the one-dimensional formulae of the Wasserstein distance, which
involves quantiles and cdfs, to the multivariate space. After discussing the
properties of these pseudo-metrics and providing conditions under which they
define a distance, we highlight similarities with the Wasserstein distance.
Interestingly, the derived non-asymptotic bounds show that in contrast to the
Wasserstein distance, the proposed pseudo-metrics do not suffer from the curse
of dimensionality. Moreover, based on the support function of a convex body, we
propose an efficient approximation possessing linear time complexity w.r.t. the
size of the data set and its dimension. The quality of this approximation as
well as the performance of the proposed approach are illustrated in
experiments. Furthermore, by construction the regions-based pseudo-metric
appears to be robust w.r.t. both outliers and heavy tails, a behavior witnessed
in the numerical experiments.
