3
$\begingroup$

Let $\rho_0$ and $\rho_1$ be two probability density functions on $\mathbb{R}^d$. The Wasserstein metric is defined as
$$W_p(\rho_0,\rho_1)^p = \inf E(|X-Y|^p)$$ where the infimum is taken over all joint distributions of random variables $X$ and $Y$ whose marginals are $\rho_0$ and $\rho_1$ respectively.

I read a paper in which $W_p(\rho_1,\rho_2)$ was defined differently-

We say that a map $M: \mathbb{R}^d \to \mathbb{R}^d$ realizes a transfer of $\rho_0$ to $\rho_1$ if, for all bounded subsets $A$ of $\mathbb{R}^d$, $$\int_{x \in A} \rho_1(x)dx = \int_{M(x) \in A}\rho_0(x)dx$$ In particular, if $M$ is a smooth one-to-one map, the above just means $$\det(\nabla M(x))\rho_1(x) = \rho_0(x)$$ Using this, they defined the Wasserstein distance as $$W_p(\rho_0,\rho_1)^p = \inf_M \int|M(x)-x|^p\rho_0(x)dx$$ for all maps $M$ which transport $\rho_0$ to $\rho_1$.

My question is, why are the above definitions equivalent?

$\endgroup$

1 Answer 1

4
$\begingroup$

The second paper used Monge's formulation of the optimal transport problem, which seeks to minimize cost among all transfer maps: those maps that push $\rho_0$ to $\rho_1$. What makes this problem hard is that the set of transfer maps has no linear structure. Kantorovich proposed a relaxed version of the transport problems, in which the cost is minimized among all transfer plans $\mu$, i.e., the probability measures with marginals $\rho_0, \rho_1$. Any transfer map $M$ induces a transport plan $\mu$, namely the pushforward of $\rho_0$ via $x\mapsto (x,M(x))$ (which is supported on the graph of $M$). The converse is not true: Kantorovich allows measures that are not supported on any graph. Such measures can be through of as splitting the amount available at source at $x$ and sending parts of it to different destinations, rather than a single point $M(x)$. The obvious advantage of Kantorovich's formulation is that the set of transfer plans is convex.

So, the distance defined via the Kantorovich problem never exceeds the distance defined via the Monge problem. It is a nontrivial result that for strictly convex costs such as $c(x,y)=|c-y|^p$, $p>1$, the optimal measure in the Kantorovich problem is actually supported on a graph and therefore solves the Monge problem as well. As a consequence, both definitions of the distance turn out to be equivalent. The best source for this material is the book Topics in Optimal transportation by Villani. (Not to be confused with his later book "Optimal transport" which puts the subject in a different, more geometric framework).

Frankly, I don't know why anyone would use the Monge formulation to define a metric, since a metric is supposed to be symmetric. There's no symmetry between source and target in the Monge problem. The Kantorovich problem is obviously symmetric.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks Pavel! I actually read up a bit about this question after posting it here (I posted it last year!). I found these notes extremely useful: math.leidenuniv.nl/~vangaans/TA2011-gradient-mei11.pdf $\endgroup$
    – VSJ
    Commented Dec 30, 2012 at 8:32
  • $\begingroup$ @VSJ Yes, I figured you'd find an answer by now, but it was too good a question to leave hanging. Someone may find it from search. Thanks for adding the link; it's a very accessible introduction to the topic. $\endgroup$
    – user53153
    Commented Dec 30, 2012 at 8:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .