Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
67,030 characters · 19 sections · 69 citation commands
Monge-Kantorovich depth, quantiles, ranks, and signs
The concept of statistical depth was introduced in order to overcome the lack of a canonical ordering in ${\rm I}\kern-0.18em{\rm R}^d$ for $d>1$, hence the absence of the related notions of quantile and distribution functions, ranks, and signs. The earliest and most popular depth concept is halfspace depth, the definition of which goes back to Tukey Tukey:75. Since then, many other concepts have been considered: {simplicial depth} Liu:90, majority depth (Singh:91 and LS:93), {projection depth} (Liu:92, building on Stahel:81 and Donoho:82, Zuo:2003), {Mahalanobis depth} (Mahalanobis:36, Liu:92, LS:93), {Oja depth} Oja:83, {zonoid depth} (KM:97 and Koshevoy:2002), {spatial depth} (DK:92, MO:95, Chaudhuri:96, VZ:2000), $L^p$ depth ZS:2000, among many others. An axiomatic approach, aiming at unifying all those concepts, was initiated by Liu Liu:90 and Zuo and Serfling ZS:2000, who list four properties that are generally considered desirable for any statistical depth function, namely affine invariance, maximality at the center, linear monotonicity relative to the deepest points, and vanishing at infinity (see Section (ref) for details). Halfspace depth is the prototype of a depth concept satisfying the Liu-Zuo-Serfling axioms for the family $\mathcal P$ of all absolutely continuous distributions on ${\rm I}\kern-0.18em{\rm R}^d$.
An important feature of halfspace depth is the convexity of its contours, which thus satisfy the star-convexity requirement embodied in the linear monotonicity axiom. That feature is shared by most existing depth concepts and might be considered undesirable for distributions with non convex supports or level contours, and multimodal ones. Proposals have been made, under the name of { local depths}, to deal with this, while retaining the spirit of the Liu-Zuo-Serfling axioms: see CDPB:2009, HKV:2010, AR:2011, and PB:2013 who provide an in-depth discussion of those various attempts. In this paper, we take a totally different and more agnostic approach, on the model of the discussion by Serfling in Serfling:2002: if the ultimate purpose of statistical depth is to provide, for each distribution $ P$, a $ P$-related ordering of ${\rm I}\kern-0.18em{\rm R}^d$ producing adequate concepts of quantile and distribution functions, ranks and signs, the relevance of a given depth function should be evaluated in terms of the relevance of the resulting ordering, and the quantiles, ranks and signs it produces.
Now, the concepts of quantiles, ranks and signs are well understood in two particular cases, essentially, that should serve as benchmarks. The first case is that of the family $\mathcal{P}^1$ of all distributions with nonvanishing Lebesgue densities over convex support sets. Here, the concepts of quantile and distribution functions, ranks, and signs are related to the “classical" univariate ones. The second case is that of the family $\mathcal{P}^d_{\mbox{\scriptsize ell}}$ of all full-rank elliptical distributions over ${\rm I}\kern-0.18em{\rm R}^d$ ($d>1$) with radial densities over elliptical support sets. Recall that the family $\mathcal{P}^d_{\mbox{\scriptsize ell}; g}=\{P_{\mu ,\Sigma , g}\}$ of elliptical distributions with given { radial density $g$ and distribution function $G$} is a parametric family indexed by a location parameter $\mu$ and a { scatter} parameter $\Sigma$ (a symmetric positive definite real matrix) such that a random vector $X$ has distribution $P_{\mu ,\Sigma , g}$ iff the residual $Y:= \Sigma^{-1/2}(X-\mu)$, which results from transforming $X$ into isotropic position, has spherical distribution $P_{0 ,I , g}$. Further, this is equivalent to ${\rm R}_P (Y) = (Y/\|Y\|)G(\|Y\|)$ having the spherical uniform distribution $U_d$ on the unit ball $\mathbb{S}^d$ in ${\rm I}\kern-0.18em{\rm R}^d$. By {\it spherical uniform}, we mean the distribution of a random vector $r\varphi$, where $r$ is uniform on $[0,1]$, $\varphi$ is uniform on the unit sphere $\mathcal S^{d-1}$, and $r$ and $\varphi$ are mutually independent. There, spherical contours with $ P_{\mu ,I , g}$-probability contents $\tau$ coincide with the halfspace depth contours, and provide a natural definition of { $\tau$-quantile contours} for $Y$, while ${\rm R}_P (Y)$, ${\rm R}_P (Y)/\|{\rm R}_P (Y)\|$ and $\|{\rm R}_P(Y)\|$ play the roles of vector ranks, signs, and ranks, respectively (HP:2002,HP:2004,HP:2005,HP:2006,HP:2008): we call them spherical {\it vector ranks}, { \it signs}, and {\it ranks}. On the other hand, we call the inverse map $u \longmapsto {\rm Q}_P(u)$ of the vector rank map $y \longmapsto {\rm R}_P (y) = (y/\|y\|)G(\|y\|)$ the {\it vector quantile} map. In both cases, the relevance of ranks and signs, whether traditional or spherical, is related to their role as maximal invariants under groups of transformations minimally generating $\mathcal{P}^1$ or the family $\mathcal{P}^d_{\mbox{\scriptsize sph}}=\{P_{0,I,f}\}$ of { spherical} distributions, of which distribution-freeness of ${\rm R}_P$ is just a by-product, as explained in HW:2003. We argue that an adequate depth function, when restricted to those two particular cases, should lead to the same well-established concepts---classical quantiles, ranks and signs for $\mathcal{P}^1$, and spherical ones for $\mathcal P^d_{\mbox{\scriptsize sph}}$---hence should coincide with halfspace depth.
Now, a closer look at those two particular cases reveals that halfspace depth contours, in $\mathcal{P}^1$ and $\mathcal P^d_{\mbox{\scriptsize sph}}$, are the images, by the vector quantile map ${\rm Q}_P$, of the hyperspheres $\mathcal{S}(\tau)$ with radii $\tau\in[0,1)$ centered at the origin. The map ${\rm Q}_P$ is the gradient of a convex function and it transports the spherical uniform distribution $U_d$ on the unit ball $\mathbb S^d$ of ${\rm I}\kern-0.18em{\rm R}^d$ into the univariate distribution $P~\!\in~\!\mathcal{P}^1$ or into the spherical distribution $P=P_{0 ,I , f}$ of interest.
For the case of general distributions $P$, we proceed similarly, and define the map ${\rm Q}_P$ as a gradient of a convex function that transform the spherical uniform distribution $U_d$ into the target distribution, namely if $U \sim U_d$ then $Y = {\rm Q}_P(U) \sim P$. It follows by McCann's McCann1995 extension of Brenier's celebrated Polar Factorization Theorem brenier that, for any distribution $P$ on ${\rm I}\kern-0.18em{\rm R}^d$, such a gradient ${\rm Q}_P$ exists, and is essentially unique. Moreover, when $P$ has finite moments of order two, that mapping ${\rm Q} _P$ is the Monge-Kantorovich optimal transport map that transfers the spherical uniform distribution $U_d$ to $P$, where optimality is the sense of minimizing the expected quadratic cost $\min_{\rm Q} {\rm I}\kern-0.18em{\rm E}_{U} ( {\rm Q}(U) -U)^2$ subject to $U \sim U_d$ and ${\rm Q}(U) \sim P$.
This suggests a new concept of statistical depth, which we call the {\it Monge-Kantorovich (or MK) depth} ${\rm D}^{\scriptsize{\text{MK}}}$, the contours of which are obtained as the images by ${\rm Q} _P$ of the hyperspheres with radius $\tau\in[0,1]$. When restricted to $\mathcal{P}^1$ or $\mathcal P^d_{\mbox{\scriptsize sph}}$, Monge-Kantorovich and halfspace depths coincide. Under suitable regularity conditions due to Caffarelli (see villani1, Section 4.2.2), ${\rm Q} _P$ is a homeomorphism, and its inverse ${\rm R} _P:={\rm Q}_P^{-1}$ is also the gradient of a convex function; the Monge-Kantorovich depth contours are continuous and the corresponding depth regions are nested, so that Monge-Kantorovich depth indeed provides a center-outward ordering of ${\rm I}\kern-0.18em{\rm R}^d$, namely,
Thus, our approach based on the theory of measure transportation allows us to define
To the best of our knowledge, this is the first proposal of a depth concept based on the Monge-Kantorovich theory of measure transportation ---hence the first attempt to provide a measure-driven ordering of ${\rm I}\kern-0.18em{\rm R}^d$ based on measure transportation theory. Previous proposals have been made, however, of measure transportation-based vector quantile functions in Ekeland, Galichon and Henry EGH and Galichon and Henry GH:2012 (with moment conditions) and Carlier, Chernozhukov and Galichon CCG (dropping moment conditions) who also extended the notion to vector quantile regression, creating a vector analogue of Koenker and Basset's KB:78 scalar quantile regression. More recently, Decurninge Decurninge proposed a new concept of multivariate $L^p$ moments based upon a similar notion. In these contributions, however, the focus is not statistical depth and the associated ranks and quantiles, and the leading case for the reference distribution is uniform on the unit hypercube in ${\rm I}\kern-0.18em{\rm R}^d$, as opposed to the spherical uniform distribution $U_d$ we adopt here as leading case, while pointing out that other reference distributions may be entertained, such as the standard Gaussian distribution on ${\rm I}\kern-0.18em{\rm R}^d$ or the uniform on the hypercube $[0,1]^d$ as mentioned above.
We then proceed to define the empirical notions corresponding to the concepts given above. We define the empirical MK vector quantiles and ranks as the essentially unique gradients $\hat{\rm Q}_n$ and $\hat {\rm R}_n$ of a pair of convex functions solving the Kantorovich dual problem for the Monge optimal transport with quadratic costs. Using the plug-in principle, we then define the empirical rank and sign maps as $\|\hat {\rm R}_n\|$ and $\hat {\rm R}_n/\|\hat {\rm R}_n\|$ and the empirical $\tau$-quantile sets and contours as $\hat {\rm Q}_n(\mathbb{S}(\tau))$ and $\hat {\rm Q}_n(\mathcal{S}(\tau))$. We establish the uniform convergence of these quantities to their theoretical counterparts. We derive these results as a consequence of the uniform convergence of empirical transport (vector quantile and rank) maps $\hat {\rm Q}_n$ and $\hat {\rm R}_n$ to their theoretical counterparts ${\rm Q}_P$ and ${\rm R}_P$ on compact subsets of the domain's interior. This is the main theoretical result of the paper presented in Theorem 3.1. This result in turn is derived through an application of the extended continuous mapping theorem and a set of new theorems on stability of transport under deterministic perturbations of the source and target measures, given as Theorems A.1 and A.2 in the Appendix, which are new results of independent interest. Application of the extended continuous mapping theorem allows to us then to replace the deterministic perturbations by stochastic perturbations of measures and obtain the stochastic uniform convergence of the empirical transport maps.
Let $(\Omega, \mathcal{A}, {\rm I}\kern-0.18em{\rm P})$ be some probability space. Throughout, $\mathcal P$ denotes a class of probability distributions over ${\rm I}\kern-0.18em{\rm R}^d$---unless otherwise specified, the class of all Borel probability measures on ${\rm I}\kern-0.18em{\rm R}^d$. Denote by $\mathbb S^d:=\{x\in{\rm I}\kern-0.18em{\rm R}^d:\;\|x\|\leq1\}$ the unit ball, and by $\mathcal S^{d-1}:=\{x\in{\rm I}\kern-0.18em{\rm R}^d:\;\|x\|=1\}$ the unit sphere, in ${\rm I}\kern-0.18em{\rm R}^d$. For $\tau\in(0,1]$, $\mathbb{S}(\tau ):=\{x\in{\rm I}\kern-0.18em{\rm R}^d:\;\|x\|\leq\tau\}$ is the ball, and $\mathcal{S}(\tau ):=\{x\in{\rm I}\kern-0.18em{\rm R}^d:\;\|x\|=\tau\}$ the sphere, of radius $\tau$. Let $P_X$ stand for the distribution of the random vector $X$. The symbol $\partial$ will denote either the boundary of a set or the subdifferential, as will be clear from the context. Following Villani villani1, we denote by $g\#\mu$ the {\em image measure} (or {\em push-forward}) of a measure $\mu\in\mathcal P$ by a measurable map $g:{\rm I}\kern-0.18em{\rm R}^d\rightarrow{\rm I}\kern-0.18em{\rm R}^d$. Explicitly, for any Borel set $A$, $g\#\mu(A):=\mu(g^{-1}(A))$. For a Borel subset $\mathbb{D}$ of a vector space equipped with the norm $\|\cdot\|$ and $f: \mathbb{D} \mapsto {\rm I}\kern-0.18em{\rm R}$, let $$\|f\|_{\mathrm{BL}(\mathbb{D})} := \sup_{x} |f(x)| \vee \sup_{x \neq x'} | f(x) - f(x')|\|x - x'\|^{-1} .$$ For two probability distributions $P$ and $P'$ on a measurable space $\mathbb{D}$, define the bounded Lipschitz metric as $$d_{{\rm BL}} (P, P') := \| P - P'\|_{{\rm BL}} := \sup_{\|f\|_{\mathrm{BL}(\mathbb{D})} \leq 1} \int f d (P - P'),$$ which metrizes the topology of weak convergence. Throughout the paper, we let $\mathcal{U}$ and $\mathcal{Y}$ be convex subsets of ${\rm I}\kern-0.18em{\rm R}^d$ with non-empty interiors. A {\em convex} function $\psi$ on $\mathcal{U}$ refers to a function $\psi:\mathcal{U} \rightarrow{\rm I}\kern-0.18em{\rm R}\cup\{+\infty\}$ for which $\psi((1-t)x+tx')\leq (1-t)\psi(x)+t\psi(x')$ for any $(x,x')$ such that $\psi(x)$ and $\psi(x')$ are finite and for any $t\in(0,1)$. Such a function is continuous on the interior of the convex set dom $\psi:=\{x\in\mathcal{U}: \psi(x)<\infty\}$, and differentiable Lebesgue-almost everywhere in dom $\psi$, by Rademacher's theorem. Write $\nabla\psi$ for the gradient of $\psi$. For any function $\psi: \mathcal{U} \mapsto {\rm I}\kern-0.18em{\rm R} \cup \{+\infty\}$, the {\em conjugate} $\psi^*: \mathcal{Y} \mapsto {\rm I}\kern-0.18em{\rm R} \cup \{+\infty\}$ of $\psi$ is defined for each $y \in \mathcal{Y}$ by $$\psi^*(y) := \sup_{z \in \mathcal{U}} [y^\top z - \psi(z)].$$ The conjugate $\psi^\ast$ of $\psi$ is a convex lower-semi-continuous function on $\mathcal{Y}$. We shall call a {\em conjugate pair of potentials} over $(\mathcal{U}, \mathcal{Y})$ any pair of lower-semi-continuous convex functions $(\psi, \psi^*)$ that are conjugates of each other. The transpose of a matrix $A$ is denoted $A^\top$. Finally, we call {\em weak order} a complete reflexive and transitive binary relation. Finally, recall the definition of Hausdorff distance between two non-empty sets $A$ and $B$ in ${\rm I}\kern-0.18em{\rm R}^d$: $$ d_H(A,B) := \sup_{b \in B}\inf_{a \in A}\| a- b \| \vee \sup_{a \in A}\inf_{b \in B}\| a- b \|. $$
Section (ref) introduces and motivates the concepts of statistical depth, vector quantiles and vector ranks based on optimal transport maps. Section (ref) describes estimators of depth contours, quantiles and ranks, and proves consistency of these estimators. Section (ref) describes computational characterizations. The appendix presents additional theoretical results and proofs.
The notion of statistical depth serves to define a center-outward ordering of points in the support of a distribution on ${\rm I}\kern-0.18em{\rm R}^d$, for $d>1$. As such, it emulates the notion of quantile for distributions on the real line. We define it as a real-valued index on ${\rm I}\kern-0.18em{\rm R}^d$ as follows.
The depth function thus defined allows graphical representations of the distribution $P$ through depth contours, which are collections of points of equal depth relative to $P$.
By construction, the depth regions are nested: \[\forall (d,d')\in{\rm I}\kern-0.18em{\rm R}_+^2,\; d'\geq d \;\Longrightarrow\;\mathbb C_P(d')\subseteq\mathbb C_P(d).\] Hence, the depth ordering qualifies as a {\em center-outward ordering} of points in ${\rm I}\kern-0.18em{\rm R}^d$ relative to the center given by the set of the deepest points, $\arg\sup_{ x \in {\rm I}\kern-0.18em{\rm R}^d} {\rm D}_P(x).$
It is often convenient to work with depth regions indexed by their probability content.
The four axioms proposed by Liu Liu:90 and Zuo and Serfling ZS:2000 to unify the diverse depth functions proposed in the literature are the following.
The earliest and most popular depth function is {\em halfspace depth} proposed by Tukey Tukey:75:
Halfspace depth relative to any distribution with nonvanishing density on ${\rm I}\kern-0.18em{\rm R}^d$ satisfies (A1)-(A4). The appealing properties of halfspace depth are well known and well documented: see Donoho and Gasko DG:92, Mosler Mosler:2002, Koshevoy Koshevoy:2002, Ghosh and Chaudhuri GC:2005, Cuestas-Albertos and Nieto-Reyes CN:2008, Hassairi and Regaieg HR:2008, to cite only a few. Halfspace depth takes values in $[0, 1/2]$, and its contours are continuous and convex; the corresponding regions are closed, convex, and nested as $d$ decreases. Under very mild conditions, halfspace depth moreover fully characterizes the distribution $P$. For somewhat less satisfactory features, however, see Dutta et al. DGC:2011. An important feature of halfspace depth is the convexity of its contours, which implies that halfspace depth contours cannot pick non convex features in the geometry of the underlying distribution, as illustrated in Figure 1.
We shall propose below a new depth concept, the Monge-Kantorovich (MK) depth, that relinquishes the affine equivariance and star convexity of contours imposed by Axioms (A1) and (A3) and recovers non convex features of the underlying distribution. As a preview of the concept, without going through any definition, we illustrate in Figure 2 (using the same banana-shaped distribution as in Figure 1) the ability of the MK depth to capture non-convexities. In what follows, we characterize these abilities more formally. We shall emphasize that this notion comes in a package with new, interesting notions of vector ranks and quantiles, based on optimal transport, which reduce to classical notions in the univariate and multivariate spherical cases.
The principle behind the notion of depth we define here is to map the depth regions and contours relative to a well-chosen reference distribution $F$, into depth contours and regions relative to a distribution of interest $P$ on ${\rm I}\kern-0.18em{\rm R}^d$, using a well-chosen mapping. The mapping proposed here is the gradient of a convex function $\nabla \psi$ such that if $U$ has distribution $F$, then $Y = \nabla \psi (U)$ has distribution $P$, or, in terms of measures, $\nabla \psi \# F = P$. The gradient $\nabla \psi$ is said to to push $F$ forward to $P$, which is conventionally denoted by the push-forward notation, $\nabla \psi \# F = P$, which is defined in the notation section.
The gradient of a convex function property is a generalization of monotonicity in the one-dimensional case. When $F$ and $P$ have finite second-order moments, these maps are the optimal Monge-Kantorovich transport maps from $F$ to $P$ for the quadratic cost, as explained below. In the unidimensional case, when $F$ is the standard uniform, the gradient/optimal transport map $\nabla \psi$ coincides with the classical quantile function.
The following theorem, due to Brenier brenier and McCann McCann1995, establishes existence of gradients of convex functions with the required properties.
We now state a fundamental duality result due to Kantorovich and Brenier, which we explicitly rely on in Section (ref).
Next we use Theorem (ref) to define a natural notion of vector quantiles and vector ranks.
When requiring regularity of vector quantiles and ranks, we shall impose the following condition on the conjugate pair of optimal potentials $(\psi,\psi^\ast)$ over $(\mathcal{U}, \mathcal{Y})$.
Under Condition (C), we have:
that is, vector ranks and quantiles are defined as gradients of conjugate potentials for each (as opposed to almost every) value in the indicated sets, and inverse functions of each other.
Sufficient conditions for Condition (C) in the context of Definition (ref) are provided by Caffarelli's regularity theory (Villani villani1, Theorem 4.14). One set of sufficient conditions is as follows.
We now can give our {\em main} definition -- that of multivariate notions of quantiles and ranks, through which a depth function will be inherited from the reference distribution $F=U_d$.
The notion of depth proposed in Definition (ref) is based on an optimal transport map from the reference spherical uniform distribution $F=U_d$ to the distribution of interest $P$. Under Condition (C), ${\rm Q}_P$ and ${\rm R}_P$ are continuous and are mutual inverse maps, so that the MK $\tau$-quantile contours are continuously deformable into spheres and the MK depth regions with probability content $\tau$ are nested.
By choosing other reference distributions $F$, such as the uniform distribution on a unit hypercube, or the standard Gaussian distribution, we can give a more general definition of MK ranks, quantiles, and signs, which may be of interest.
Of course, all the quantities thus defined depend on the choice of the reference distribution $F$ and the depth function ${\rm D}_F$.
Here we consider in more detail the Monge-Kantorovich depth defined from a baseline spherical uniform distribution $U_d$ supported on the unit ball $\mathbb S^d$ of ${\rm I}\kern-0.18em{\rm R}^d$. Recall that this distribution is that of a random vector $r\varphi$, where $r$ is uniform on $[0,1]$, $\varphi$ is uniform on the unit sphere $\mathcal S^{d-1}$, and $r$ and $\varphi$ are mutually independent.
The spherical symmetry of distribution $U_d$ produces halfspace depth contours that are concentric spheres, the deepest point being the origin. The radius $\tau $ of the ball $\mathbb{S}(\tau )=\{x\in{\rm I}\kern-0.18em{\rm R}^d:\;\|x\|\leq\tau\}$ is also its $U_d$-probability contents, that is, $\tau =U_d({{\mathbb{S}}}(\tau ))$. Letting $\theta :=\arccos \tau $, the halfspace depth with respect to $U_d$ of a point $\tau u\in\mathcal{S}(\tau ):=\{x\in{\rm I}\kern-0.18em{\rm R}^d:\;\|x\|=\tau\}$, where $\tau \in (0,1]$ and $u\in\mathbb S^d$, is
Note that for $d=1$, $u$ takes values $\pm 1$ and, in agreement with rotational symmetry of $U_d$, that depth does not depend on $u$.
The principle behind the notion of depth we investigate further here is to map the depth regions and contours relative to the spherical uniform distribution $U_d$, namely, the concentric spheres, into depth contours and regions relative to a distribution of interest $P$ on ${\rm I}\kern-0.18em{\rm R}^d$ using the optimal transport plan from $U_d$ to $P$. Under the sufficient conditions for Condition (C) provided in Lemma (ref) (note that the conditions on $F$ are automatically satisfied in case $F=U_d$), ${\rm Q}_P$ and ${\rm R}_P$ are continuous and are inverse maps of each other, so that the MK depth contours are continuously deformable into spheres, the MK depth regions are nested, and regions and contours, when indexed by probability content, take the respective forms \[ {\rm Q}_P\left( \mathbb S(\tau)\right) \mbox{ and } {\rm Q}_P\left( \mathcal S(\tau)\right),\mbox{ for }\tau\in(0,1]. \]
The halfspace depth of a point $x\in{\rm I}\kern-0.18em{\rm R}$ relative to a distribution $P$ over ${\rm I}\kern-0.18em{\rm R}$ takes the very simple form \[ D^{\scriptsize{\text{Tukey}}}_P(x)=\min(P(x), 1-P(x)), \] where, by abuse of notation, $P$ stands for both distribution and distribution function. The nondecreasing map defined for each $x\in{\rm I}\kern-0.18em{\rm R}$ by $x\mapsto {\rm R}_P(x)=2P(x) -1$ is the derivative of a convex function and it transports distribution $P$ to $U_1$, which is uniform on $[-1,1]$, i.e., ${\rm R}_P\#P=U_1$. Hence ${\rm R}_P$ coincides with the MK vector rank of Definition (ref). Therefore, for each $x\in{\rm I}\kern-0.18em{\rm R}$, \[ D_P(x)=D^{\scriptsize{\text{Tukey}}}_{U_d}({\rm R}_P(x))=\min(P(x), 1-P(x)) \] and MK depth coincides with Tukey depth in case of all distributions with nonvanishing densities on the real line.
More generally (still in the univariate case), denoting by $F_1$ and $F_2$ the distribution functions associated with two absolutely continuous distributions $P_1$ and $P_2$, the mapping $F_2^{-1}\circ F_1$, being monotone increasing, is also the optimal transport from $P_1$ to $P_2$. The same transformation has been studied, in a different context, by Doksum Doksum:74 and Doksum and Sievers DS:76; see also the concept of convex ordering proposed by van Zwet VZ:1964.
As explained in the introduction, a $d$-dimensional random vector $X$ has elliptical distribution $P_{\mu,\Sigma,g}$ with location $\mu\in~\!{\rm I}\kern-0.18em{\rm R}^d$, positive definite symmetric $d\times d$ scatter matrix $\Sigma$ and radial density function $g$ (radial distribution function $G$) if and only if, denoting by $\Sigma^{1/2}$ the symmetric root of $\Sigma$, $Y:=\Sigma^{-1/2}(X-\mu)$ has spherical distribution $P= P_{0,I,g}$ (hence $\Vert Y\Vert $ has density $f$), which holds if and only if
Let $\Psi(t) = \int_{-\infty}^t G(r) d r$, and note that the map $z\mapsto {\rm R}_P(z)$ is the gradient of $\psi^\ast(z):= \Psi(\Vert z \Vert)$ so that, from ((ref)), $\nabla\psi^\ast\#P=U_d$ as Definition (ref) requires. That $\psi^\ast$ is convex follows from Theorem 5.1 of RockafellarConvex by noting that $\psi^\ast$ is a composition of $\Psi: {\rm I}\kern-0.18em{\rm R} \to {\rm I}\kern-0.18em{\rm R}$, a convex, non-decreasing map, and $\|\cdot \|: {\rm I}\kern-0.18em{\rm R}^d \to R$, a convex function by definition of the norm. As a consequence, the mapping ${\rm R}_P$ in ((ref)) is the MK vector rank function associated with $P=P_{0,I,f}$; and, the MK depth contours (with probability content $\tau$) of $P$ are spheres with radii $G^{-1}(\tau)$ centered at the origin: $$ D_P(x) = \{ y \in {\rm I}\kern-0.18em{\rm R}^d: \| y \| \leq G^{-1} (\tau) \}. $$ These spheres are halfspace depth contours for $P$. This is the precise sense in which MK depth reduces to halfspace for elliptical families.
It should be noted above, that we treat location and scatter parameters as known, and transform $X$ to a vector $Y$ in isotropic position. This transformation ensures basic invariance properties of the resulting depth, ranks, and quantiles with respect to affine transformations. When those parameters are unknown, they will have to be replaced with by affine-equivariant estimators, as in the usual definition of elliptical ranks and signs (see,e.g., HP:2002) in order to insure similar invariance properties for the empirical analogs. Without the aforementioned transformation, however, the invariance properties are not guaranteed, owing to the fact that composition of two gradients of convex functions is not necessarily the gradient of a convex function, unless the composition has a specific structure, as is the case above.
Having defined Monge-Kantorovich vector quantiles, ranks and depth relative to a distribution $P$ based on reference distribution $F$ on ${\rm I}\kern-0.18em{\rm R}^d$, we now turn to the estimation of these quantities. Hereafter, we shall assume that Condition (C) holds. Then, the MK vector quantiles and ranks of Definition (ref) are
for each $u \in \mathcal{U}_0$ and $y \in \mathcal{Y}_0$, respectively. We define $\Phi_0(\mathcal{U}, \mathcal{Y})$ as a collection of conjugate potentials $(\varphi, \varphi^*)$ on $(\mathcal{U}, \mathcal{Y})$ such that $\varphi(u_0)= 0$ for some fixed point $u_0 \in \mathcal{U}_0$. Under the conditions of Theorem (ref), the potentials $(\psi, \psi^*)$ solve the dual problem
Constraining the conjugate pair to lie in $\Phi_0(\mathcal{U}, \mathcal{Y})$ is a normalization that (without any loss of generality) pins down the constant, so that $(\psi,\psi^\ast)$ are uniquely determined, as argued in the proof.
We propose empirical versions of MK quantiles and ranks based on estimators $\hat P$ of $P$. The typical case is when the reference measure $F$ is known. However, our theory allows us to handle the case where $F$ is itself unknown, and so it is estimated by some $\hat F$. This is indeed useful for at least two reasons. First, we may be interested in a classical problem of comparing one distribution $P$ to a reference distribution $F$, both of which are known only up to a random sample available from each of them. Second, we may be interested in discretizing $F$ for computational reasons, as we discuss in Section (ref), in which case the discretized $F$ is the estimator of $F$.
Suppose that $\{\hat P_n\}_{n=1}^\infty$ and $\{\hat F_n\}^\infty_{n=1}$ are sequences of random measures on $\mathcal{Y}$ and $\mathcal{U}$, with finite total mass, that are consistent for $P$ and $F$, in the sense that
where $\to_{{\rm I}\kern-0.18em{\rm P}^*}$ denotes convergence in (outer) probability under probability measure ${\rm I}\kern-0.18em{\rm P}$, see van der Vaart and Wellner VvW. A basic example is where $\hat P_n$ is the empirical distribution of a random sample $(Y_i)_{i=1}^n$ drawn from $P$ and $\hat F_n$ is the empirical distribution of a random sample $(U_i)_{i=1}^n$ drawn from $F$. Other, much more complicated examples, including smoothed empirical measures and data originating from dependent processes, satisfy sufficient conditions for ((ref)) that we now give. In order to develop some examples, we introduce an ergodicity condition:
The class of ergodic processes is extremely rich, including in particular the following cases:
For a detailed motivation and discussion of the use of deterministic sequences such as, for example, the so-called {\it low-discrepancy sequences}: see, e.g., Chapter 9 and, more particularly, page 314 of ken:judd.
Thus, if the data stream $\{(W_{t,n})_{t=1}^n\}_{n=1}^\infty$ is ergodic for $P_W$, we can estimate $P_W$ by the empirical and smoothed empirical measures $$ \hat P_W(A) = \frac{1}{n} \sum_{t=1}^n 1\{W_{t,n} \in A \}, \ \quad \ \tilde P_W(A) = \frac{1}{n} \sum_{t=1}^n \int_{{\rm I}\kern-0.18em{\rm R}^d} 1\{W_{t,n} + h_n \varepsilon \in A \cap \mathcal{W} \} d \Phi (\varepsilon), $$ where $\Phi $ is the probability law of the standard $d$-dimensional Gaussian vector, $N(0,I_d)$, and $h_n \geq 0$ a semi-positive-definite matrix of bandwidths such that $\|h_n\| \to 0$ as $n \to \infty$. Note that $\tilde P_W$ may not integrate to 1, since we are forcing it to have support in $\mathcal{W}$.
Absolute continuity of $P_W$ in Lemma (ref) is invoked to show that the smoothed estimator $\tilde P_W$ is asymptotically non-defective.
We base empirical versions of MK quantiles, ranks and depth on estimators $\hat P_n$ for $P$ and $\hat F_n$ for $F$ satisfying ((ref)). This includes cases where the reference measure $F$ is known, i.e. $\hat F_n=F$. Recall Assumption (C) is maintained throughout this section.
We now state the main result of Section (ref).
The first result establishes the uniform consistency of empirical vector quantile and rank maps, hence also of empirical ranks and signs. The set ${\rm Q}_P(K)$ with $K = \mathbb{K}(\tau)$ is the statistical depth contour with probability content $\tau$. The second result, therefore, establishes consistency of the approximation $\hat{\rm Q}_n(K)$ to the theoretical depth region ${\rm Q}_P(K)$.
We work with the conditions of the previous theorem, but here, for the sake of simplicity, we first consider the lead case where $F$ is known, i.e. $\hat F_n = F$.
Uniform convergence of empirical MK rank, signs and depth to their theoretical counterparts follows by an application of the Extended Continuous Mapping Theorem.
Uniform convergence of MK empirical $\tau$-quantile contours and MK empirical depth regions with probability content $\tau$ follows also through an application of the Extended Continuous Mapping Theorem.
The main results are derived assuming we know the reference distribution $F$ and the associated depth function ${\rm D}_F$ as well as depth regions $\mathbb{K}(\tau)$ and quantile contours $\mathcal{K}(\tau)$. There are cases where these will be approximated numerically or using data. The same definitions and results extend naturally where these quantities are replaced by uniformly consistent estimators $\hat {\rm D}_{F,n}$, $\hat {\mathbb{K}}_n(\tau)$, and $\hat {\mathcal{K}}_n(\tau)$:
where $K$ is any closed subset of $\mathcal{U}_0$. These high-level conditions hold trivially for the numerical approximations we use in Section (ref). They also hold, for example, for Tukey's halfspace depth under regularity conditions. We will not discuss these conditions here.
Here we provide computational characterizations of the empirical quantiles, ranks, and depth regions for various cases of interest.
Suppose $\hat P_n$ and $\hat F_n$ satisfy Caffarelli regularity conditions, so that $\hat{\rm Q}_n=\nabla\hat\psi_n$ and $\hat{\rm R}_n=\nabla\hat\psi^\ast_n$, with $(\hat\psi_n,\hat\psi^\ast_n)$ satisfying (C). The MK empirical vector quantile maps $\hat{\rm Q}_n$ and $\hat{\rm R}_n$ can then be computed with the algorithm of Benamou and Brenier BB:2000.
Suppose now $\hat P_n$ is a discrete estimator of $P$ and $\hat F_n$ an absolutely continuous distribution with convex compact support $\mathcal{U} \subset{\rm I}\kern-0.18em{\rm R}^d\!$. Let $\hat P_n$ be of the form $\hat P_n\!=\!\sum_{k=1}^{K_n}p_{k,n}\delta_{y_{k,n}}$ for some integer $K_n$, some nonnegative weights $p_{1,n},\ldots,p_{K_n,n}$ such that $\sum_{k=1}^{K_n}p_{k,n}=1$, and $y_{1,n},\ldots,y_{K_n,n}\in{\rm I}\kern-0.18em{\rm R}^d$ . The leading example is when $\hat P_n$ is the empirical distribution of a random sample $(Y_i)_{i=1}^n$ drawn from $P$.
The MK empirical vector quantile map $\hat{\rm Q}_n$ is then equal (almost everywhere) to the gradient of a convex map $\hat\psi_n$ such that $\nabla\hat\psi_n\#\hat F_n=\hat P_n$, i.e., the $\hat F_n$-almost surely unique map $\hat{\rm Q}_n=\nabla\hat\psi_n$ satisfying the following:
The following characterization of $\hat\psi_n$ specializes Kantorovich duality to this discrete-continuous case (see, e.g.,EGH).
This lemma allows efficient computation of $\hat{\rm Q}_n$ using a gradient algorithm proposed in AHA:98. The map $\hat\psi_n$ is piecewise affine and the empirical vector quantile $\hat{\rm Q}_n$ is piecewise constant. The correspondence $\hat{\rm Q}_n^{-1}$ defined for each $k\leq K_n$ by \[ y_{k,n}\mapsto\hat{\rm Q}^{-1}_n(y_{k,n}):=\{u\in\mathcal{U}:\;\nabla\hat\psi_n(u)=y_{k,n} \} \] maps $\{y_{1,n},\ldots,y_{K_n,n}\}$ into $K_n$ regions of a partition of $\mathcal{U}$, called a {\em power diagram}. The estimator $\hat{\rm R}_n$ of the MK vector rank can be computed according to formula ((ref)) after computing the conjugate $\hat \psi^*_n$ of $\hat \psi_n$ via: $\hat \psi^*_n(y) = \sup_{u \in \mathcal{U}} \{ u^\top y - \hat \psi_n(u) \}.$ The empirical depth, depth regions, and quantiles can be computed using the depth function, according to their theoretical definitions.
Particularly amenable to computation is the case when both distribution estimators $\hat P_n$ and $\hat F_n$ are discrete with uniformly distributed mass on sets of points of the same cardinality. Let $\hat P_n=\sum_{j=1}^n\delta_{y_j}/n$ for a set $\mathcal Y_n=\{y_1,\ldots,y_n\}$ of points in ${\rm I}\kern-0.18em{\rm R}^d$ and $\hat F_n=\sum_{j=1}^n\delta_{u_j}/n$, for a set $\mathcal U_n=\{u_1,\ldots,u_n\}$ of points in ${\rm I}\kern-0.18em{\rm R}^d$. The restriction of the quantile map $\hat{\rm Q}_n$ to $\mathcal U_n$ is the bijection $u \longmapsto y=\hat{\rm Q}_n|_{\mathcal U_n}(u)$ from $\mathcal U_n$ onto $\mathcal Y_n$ and $\hat{\rm R}_n|_{\mathcal Y_n}$ is its inverse. The solutions $\hat{\rm Q}_n$ and $\hat{\rm R}_n$ can be computed with any optimal assignment algorithm. More generally, in the case of any two discrete estimators $\hat P_n$ and $\hat F_n$, the problem of finding $\hat{\rm Q}_n$ or $\hat{\rm R}_n$ is a linear programming problem.
Whenever $\hat P_n$ is finitely discrete, then the MK empirical depth regions and quantile contours are finite sets of points. For visualization purposes it may be helpful to transform them into nicer looking objects which are close to the original objects in terms of Hausdorff distance. In the example below we used $\alpha$-hulls to create approximations to the depth regions and took the boundaries of the set as a numerical approximation to the quantile contours. It may also be possible to use polygonization methods such as those in DS:88 for $d=2$ and Gruenbaum:94 for $d=3$.