About the Wasserstein “metric”

I've just encountered the Wasserstein metric, and it doesn't seem obvious to me why this is in fact a metric on the space of measures of a given metric space $X$. Except for non-negativity and symmetry (which are obvious), I don't know how to proceed.

Do you guys have any advices or links to useful references ?

Thanks in advance !
Cyril

-
A useful material as mentioned in my answer is the book of Cedric Villani "Topics in optimal transportation". Also one good source is Luigi Ambrosio's and Nicola Gigli's "User's guide to optimal transportation". It deals alot of nice results and detailed treatment of this topic. For instance, it considers the cases when $X$ is one of the following: Polish, geodesic metric space, Riemannian manifold, geodesic space with Alexandrov curvature (positive or nonpositive), and it defines a Metric Ricci curvature for a compact geodesic space $X$ through the study of its associated Wasserstein space. – T. Eskin Jun 15 '12 at 12:38

1 Answer

So I assume that what puzzles you are the triangle-inequality and $W_{p}(\mu,\mu)=0$, where $W_{p}$ denotes the $p$-Wasserstein metric.

Here's some preliminary information. I will denote $\Pi(\mu,\nu)$ the collection of all transference plans from $\mu$ and $\nu$, i.e. $\pi\in\Pi(\mu,\nu)$ iff $\mu$ is the first marginal of $\pi$ and $\nu$ is the second. This can also be expressed in form $\mu=(\mathrm{pr}_{1})_{\#}\pi$ and $\nu=(\mathrm{pr}_{2})_{\#}\pi$, where $\#$ denotes the push-forward. If $(X,d)$ is Polish then for every pair of probability measures $\mu,\nu$ there exists an optimal transference plan $\pi\in\Pi(\mu,\nu)$ so that $W_{p}(\mu,\nu)=\left(\int_{X\times X}d(x,y)^{p}\,d\pi(x,y)\right)^{\frac{1}{p}}$. The proof of this can be found in the book 'Topics in optimal transportation', Cedric Villani, 2003, and the key point consists of noting that $\Pi(\mu,\nu)$ is compact in the weak-convergence of measures (which is shown by using Prokhorov's theorem).

Now to the metric itself.

The triangle-inequality uses a so called "Gluing lemma" (also found in Villani's book). It states that if $\mu_{1},\mu_{2},\mu_{3}$ are Borel probability measures on $X$, and $\pi_{1,2}\in\Pi(\mu_{1},\mu_{2})$ and $\pi_{2,3}\in\Pi(\mu_{2},\mu_{3})$ are optimal transference plans, then there exists a Borel probability measure $\mu$ on $X^{3}$ with marginals $\pi_{1,2}$ to the left $X\times X$ and $\pi_{2,3}$ to the right $X\times X$. This measure in a sense glues together $\pi_{1,2}$ and $\pi_{2,3}$. It follows by a simple argument using the marginal properties of each measure that the marginal of $\mu$ to $X\times X$ (the first and third $X$) denoted by $\pi_{1,3}$ is a transference plan in $\Pi(\mu_{1},\mu_{3})$ (not necessarily optimal!) $(*)$. Using minkovski inequality of $L^{p}(X^{3},\mu)$ $(**)$, marginal properties of the measures $(***)$, optimality of $\pi_{1,2}$ and $\pi_{2,3}$ $(****)$, we obtain \begin{align*} W_{p}(\mu_{1},\mu_{3}) &\overset{(*)}{\leq} \bigg(\int_{X\times X}d(x,z)^{p}\,d\pi_{1,3}(x,z)\bigg)^{\frac{1}{p}}\overset{(***)}{=}\bigg(\int_{X\times X\times X}d(x,z)^{p}\,d\mu(x,y,z)\bigg)^{\frac{1}{p}} \\ &\leq \bigg(\int_{X\times X\times X}(d(x,y)+d(y,z))^{p}\,d\mu(x,y,z)\bigg)^{\frac{1}{p}} \\ &\overset{(**)}{\leq}\bigg(\int_{X\times X\times X}d(x,y)^{p}\,d\mu(x,y,z)\bigg)^{\frac{1}{p}}+\bigg(\int_{X\times X\times X}d(y,z)^{p}\,d\mu(x,y,z)\bigg)^{\frac{1}{p}} \\ &\overset{(***)}{=}\bigg(\int_{X\times X}d(x,y)^{p}\,d\pi_{1,2}(x,y)\bigg)^{\frac{1}{p}}+\bigg(\int_{X X\times X}d(y,z)^{p}\,d\pi_{2,3}(y,z)\bigg)^{\frac{1}{p}} \\ &\overset{(****)}{=}W_{p}(\mu_{1},\mu_{2})+W_{p}(\mu_{2},\mu_{3}). \end{align*} So we have the triangle-inequality.

About the $W_{p}(\mu,\mu)=0$, take the homeomorphism $f:X\to\Delta$ given by $x\mapsto(x,x)$, i.e. $\Delta$ is the "diagonal" of $X\times X$. Then take $\nu:=f_{\#}\mu$ (which is a Borel probability measure on the diagonal $\Delta$) and furthermore define a Borel probability measure $\pi$ on the product space $X\times X$ by setting $\pi(A)=\nu(A\cap\Delta)$ for all Borel sets $A$. Now $\pi$ is a transference plan between $\mu$ to itself (not necessarily optimal!), which is a straight-forward proof, and it vanishes outside the diagonal (i.e. $\pi(\Delta^{c})=0$). Since the diagonal is the zero set of the metric $d$, we conclude that \begin{equation*} W_{p}(\mu,\mu)^{p}\leq \int_{X\times X}d(x,y)^{p}\,\pi(x,y)=\int_{\Delta}d(x,y)^{p}\,\pi(x,y)+\int_{\Delta^{c}}d(x,y)^{p}\,\pi(x,y)=0+0=0, \end{equation*} whence $W_{p}(\mu,\mu)=0$.

-
By the way, here's some terminology explained: a $\it{transference\,\,plan}$ from $\mu$ to $\nu$ is a member of $\Pi(\mu,\nu)$. Intuitively, $d\pi(x,y)$ measures the amount of mass that $\pi$ transfers from $x$ to $y$ and $d(x,y)^{p}$ is the cost function. An optimal plan is such $\pi$ for which the infimum is reached in the definition of $W_{p}$, and for every other transference plan we have an inequality $\leq$. As mentioned above, given that $X$ is Polish guarantees the existence of optimal transference plans between any pair of Borel prob. measures. – T. Eskin Jun 15 '12 at 13:53
Thanks, that's much clearer ! I will get Villani's book to see what he says about that – Cyril Benezet Jun 15 '12 at 17:34