Let $(X,d)$ be a metric space, $x_1,\ldots,x_N\in X$ and $x_1',\ldots,x_N'\in X$ be atoms, and $G=\sum_{i=1}^Np_i\delta_{x_i}$, $G'=\sum_{i=1}^Np_i'\delta_{x_i}$, and $G''=\sum_{i=1}^Np_i'\delta_{x_i'}$ be mixing measures. In words: $G$ and $G'$ have the same atoms, but different weights. $G'$ and $G''$ have different atoms, but the same weights.

Assuming $G'\ne G''$ (i.e. there is at least one distinct atom), is it true that $W_p(G,G')\le W_p(G,G'')$? Here, $W_p$ is the usual $p$th Wasserstein distance between the measures $G$ and $G'$.

In other words, if two discrete measures have the same support, does "perturbing" the atoms in one of the measures always increase the Wasserstein distance? Or is it possible to move the atoms in one measure in such a way to decrease the Wasserstein distance?

  • $\begingroup$ Are you sure this is the question you want to ask? There are simple counterexamples like $p_1=1/3$, $p_2=2/3$, $p_1'=p_2$, $p_2'=p_1$ and $x_1'=x_2$, $x_2'=x_1$. $\endgroup$ – MaoWao Oct 26 '18 at 12:22
  • 1
    $\begingroup$ There is this case where $x_1 = 0$, $x_2=0$, $p_1 = \tfrac23$, $p_2 = \tfrac13$, $p_1' = \tfrac13$, $p_2' = \tfrac23$ and $x_1' = 1$, $x_2' = 0$ where $W_p(G,G') > 0$ but $G = G''$… But this cheating since reordering the indices in $G''$ gives exactly $G$, so you probably excluded this implicitly. $\endgroup$ – Dirk Oct 26 '18 at 12:23
  • $\begingroup$ Wow, @MaoWao was typing the exact same counterexample at the same time! $\endgroup$ – Dirk Oct 26 '18 at 12:24
  • $\begingroup$ @Dirk is correct. I am interested in the nontrivial case $G'\ne G''$, i.e. there is at least one atom $x_k'$ that is different from any of the $x_i$. $\endgroup$ – JohnA Oct 26 '18 at 12:50

There is a nontrivial counterexample for $N=2$, $p=1$, and $X=\mathbb{R}$. Pick $x_1=-2$, $x_2=2$, $x'_1=-1$, $x'_2=1$ and $p_1=4/5$ and $p_1'=1/5$. Then $2.2=W_1(G,G'')<W_1(G,G')=2.4$. (I hope I did not mess up the calculation).

The intuition seems clear:

In the counterexample, you have to move $1/5$ of the total mass from $-2$ to $-1$ and $3/5$ of the total mass from $-2$ to $1$, while moving another $1/5$ of the total mass from $2$ to $1$. This is cheaper than moving $3/5$ of the mass all the way from $-2$ to $2$.


Without further constraints this is not true and easy to see if $X$ is Euclidean: Let $\Gamma$ be the support of an optimal coupling between $G$ and $G'$. If for fixed $y\in p_2(\Gamma)$ the set $\{x \in X ~|~(x,y)\in \Gamma \}$ lies in the interior of a half space whose boundary passes through $y$ then moving $y$ towards the interior of the half space decreases the optimal transport distance. For $N=2$ this works in any geodesic space, just let $x'_2$ be a point on a geodesic connecting $x_1$ and $x_2$.

  • $\begingroup$ This sounds like an interesting general construction, but I don't quite follow any of the details, e.g. what is $p_2(\Gamma)$? $\endgroup$ – JohnA Oct 26 '18 at 13:30
  • $\begingroup$ $p_2(\Gamma)$ is the projection to the second factor, i.e. $p_2:(x,y)\mapsto y$. The rough idea of the construction: Look at all initial points of a given final point $y$. If they all lie into a "common" direction then one can move $y$ towards that direction to decrease the transport a bit. Call the moved point $y'$. If everything is transported as before with $y$ replaced by $y'$ then the transport cost is smaller though possibly not optimal (in many cases it is optimal but in a few it is not). $\endgroup$ – Martin Kell Oct 26 '18 at 17:19

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.