Suppose $\Omega$ is a suitably regular domain in $\mathbb{R}^n$ and $\rho_0,\rho_1\in\textrm{Prob}(\Omega)$. Benamou and Brenier showed that the $L_2$ transportation distance between $\rho_0$ and $\rho_1$ can be computed as follows:


where $\rho(x,t)$ satisfies $\rho(x,0)=\rho_0(x)$, $\rho(x,1)=\rho_1(x)$, and $\frac{\partial\rho}{\partial t}+\nabla\cdot(\rho v)=0$. This formula appears in many discretizations of optimal transportation.

We know $d(\cdot,\cdot)$ satisfies the triangle inequality because it was derived from the Wasserstein distance. But, this evidence for the triangle inequality is "heavy" in that if you define Wasserstein distances using the above PDE formulation, you could only prove triangle inequality after showing a (complicated) relationship with the theory of optimal transportation.

Is it possible to prove the triangle inequality directly from the "PDE-constrained optimization" formulation written above? Even an informal proof that ignores regularity issues etc. would be useful for me.


PS -- The Benamou/Brenier paper is "A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem," which lives here: http://link.springer.com/article/10.1007%2Fs002110050002

PPS -- Also posted here, but I realized it's probably not the right place: https://math.stackexchange.com/posts/796634/edit


I first wrote a longer answer, but it got somehow lost. Here is a rewritten shorter one. The idea is to simply construct a curve going from $\rho_0$ to $\rho_1$ to $\rho_2$. The only thing is to check how to make the reparametrization, i.e. decide the time $T$ when you move from the first transport to the other. This is how it should go:

Suppose $\rho_0,\rho_1,\rho_2\in\textrm{Prob}(\Omega)$ with $d_1 = d(\rho_0,\rho_1) >0$ and $d_2 = d(\rho_1,\rho_2) >0$. Let $T \in (0,1)$ so that $\frac{1-T}{T} = \frac{d_1}{d_2}$ and let $(\rho^1,v^1)$ and $(\rho^2,v^2)$ be admissible pairs (i.e. having the correct marginals and satisfying the continuity equation) for defining the infimum in the distances $d_1$ and $d_2$. Let us assume that they even realize the infima. Now define an admissible pair $(\rho,v)$ for the distance from $\rho_0$ to $\rho_2$ as $$ \rho(x,t) = \begin{cases} \rho^1(x,t/T), & t \le T\\ \rho^2(x,(t-T)/(1-T)), & t > T\\ \end{cases} $$ and $$ v(x,t) = \begin{cases} \frac1Tv^1(x,t/T), & t \le T\\ \frac1{1-T}v^2(x,(t-T)/(1-T)), & t > T.\\ \end{cases} $$ Now $$ d(\rho_0,\rho_2)^2\le \int_{\Omega}\int_0^1\rho(x,t)|v(x,t)|^2\,dt\,dx = \frac1{T}d_1^2 + \frac1{1-T}d_2^2 = (d_1 + d_2)^2. $$

  • $\begingroup$ Tricky! Stupidly, I was fixing $T=\frac{1}{2}.$ Thanks -- this is very useful! $\endgroup$ – Justin May 16 '14 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.