4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\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, 2018 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, 2018 at 12:23
  • $\begingroup$ Wow, @MaoWao was typing the exact same counterexample at the same time! $\endgroup$
    – Dirk
    Oct 26, 2018 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, 2018 at 12:50

2 Answers 2

Reset to default
6
$\begingroup$

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$.

Improve this answer
$\endgroup$
3
$\begingroup$

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$.

Improve this answer
$\endgroup$
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, 2018 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, 2018 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.