Mixing
Effect of perturbing the atoms of a measure on the Wasserstein distance
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Let $(X,d)$ be a metric space, $x_1,ldots,x_Nin X$ and $x_1',ldots,x_N'in X$ be atoms, and $G=sum_i=1^Np_idelta_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?
pr.probability measure-theory st.statistics probability-distributions optimal-transportation
asked 2 hours ago
JohnA
23316
add a comment |Â
up vote
3
down vote
favorite
Let $(X,d)$ be a metric space, $x_1,ldots,x_Nin X$ and $x_1',ldots,x_N'in X$ be atoms, and $G=sum_i=1^Np_idelta_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?
pr.probability measure-theory st.statistics probability-distributions optimal-transportation
asked 2 hours ago
JohnA
23316
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$.
– MaoWao
1 hour ago
1
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.
– Dirk
1 hour ago
Wow, @MaoWao was typing the exact same counterexample at the same time!
– Dirk
1 hour ago
@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$.
– JohnA
51 mins ago
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Let $(X,d)$ be a metric space, $x_1,ldots,x_Nin X$ and $x_1',ldots,x_N'in X$ be atoms, and $G=sum_i=1^Np_idelta_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?
pr.probability measure-theory st.statistics probability-distributions optimal-transportation
asked 2 hours ago
JohnA
23316
Let $(X,d)$ be a metric space, $x_1,ldots,x_Nin X$ and $x_1',ldots,x_N'in X$ be atoms, and $G=sum_i=1^Np_idelta_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?
pr.probability measure-theory st.statistics probability-distributions optimal-transportation
pr.probability measure-theory st.statistics probability-distributions optimal-transportation
asked 2 hours ago
JohnA
23316
asked 2 hours ago
JohnA
23316
edited 52 mins ago
asked 2 hours ago
JohnA
23316
asked 2 hours ago
JohnA
23316
asked 2 hours ago
JohnA
23316
23316
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$.
– MaoWao
1 hour ago
1
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.
– Dirk
1 hour ago
Wow, @MaoWao was typing the exact same counterexample at the same time!
– Dirk
1 hour ago
@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$.
– JohnA
51 mins ago
add a comment |Â
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$.
– MaoWao
1 hour ago
1
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.
– Dirk
1 hour ago
Wow, @MaoWao was typing the exact same counterexample at the same time!
– Dirk
1 hour ago
@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$.
– JohnA
51 mins ago
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$.
– MaoWao
1 hour ago
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$.
– MaoWao
1 hour ago
1
1
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.
– Dirk
1 hour ago
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.
– Dirk
1 hour ago
Wow, @MaoWao was typing the exact same counterexample at the same time!
– Dirk
1 hour ago
Wow, @MaoWao was typing the exact same counterexample at the same time!
– Dirk
1 hour ago
@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$.
– JohnA
51 mins ago
@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$.
– JohnA
51 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
There is a nontrivial counterexample for $N=2$, $p=1$, and $X=mathbbR$. 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$.
answered 27 mins ago
S.Surace
666518
add a comment |Â
up vote
2
down vote
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 $yin p_2(Gamma)$ the set $~(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$.
answered 24 mins ago
Martin Kell
22112
This sounds like an interesting general construction, but I don't quite follow any of the details, e.g. what is $p_2(Gamma)$?
– JohnA
11 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
There is a nontrivial counterexample for $N=2$, $p=1$, and $X=mathbbR$. 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$.
answered 27 mins ago
S.Surace
666518
add a comment |Â
up vote
3
down vote
There is a nontrivial counterexample for $N=2$, $p=1$, and $X=mathbbR$. 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$.
answered 27 mins ago
S.Surace
666518
add a comment |Â
up vote
3
down vote
up vote
3
down vote
There is a nontrivial counterexample for $N=2$, $p=1$, and $X=mathbbR$. 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$.
answered 27 mins ago
S.Surace
666518
There is a nontrivial counterexample for $N=2$, $p=1$, and $X=mathbbR$. 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$.
answered 27 mins ago
S.Surace
666518
answered 27 mins ago
S.Surace
666518
answered 27 mins ago
S.Surace
666518
answered 27 mins ago
S.Surace
666518
666518
add a comment |Â
add a comment |Â
up vote
2
down vote
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 $yin p_2(Gamma)$ the set $~(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$.
answered 24 mins ago
Martin Kell
22112
This sounds like an interesting general construction, but I don't quite follow any of the details, e.g. what is $p_2(Gamma)$?
– JohnA
11 mins ago
add a comment |Â
up vote
2
down vote
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 $yin p_2(Gamma)$ the set $~(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$.
answered 24 mins ago
Martin Kell
22112
This sounds like an interesting general construction, but I don't quite follow any of the details, e.g. what is $p_2(Gamma)$?
– JohnA
11 mins ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
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 $yin p_2(Gamma)$ the set $~(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$.
answered 24 mins ago
Martin Kell
22112
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 $yin p_2(Gamma)$ the set $~(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$.
answered 24 mins ago
Martin Kell
22112
answered 24 mins ago
Martin Kell
22112
answered 24 mins ago
Martin Kell
22112
answered 24 mins ago
Martin Kell
22112
22112
This sounds like an interesting general construction, but I don't quite follow any of the details, e.g. what is $p_2(Gamma)$?
– JohnA
11 mins ago
add a comment |Â
This sounds like an interesting general construction, but I don't quite follow any of the details, e.g. what is $p_2(Gamma)$?
– JohnA
11 mins ago
This sounds like an interesting general construction, but I don't quite follow any of the details, e.g. what is $p_2(Gamma)$?
– JohnA
11 mins ago
This sounds like an interesting general construction, but I don't quite follow any of the details, e.g. what is $p_2(Gamma)$?
– JohnA
11 mins ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f313837%2feffect-of-perturbing-the-atoms-of-a-measure-on-the-wasserstein-distance%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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$.
– MaoWao
1 hour ago
1
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.
– Dirk
1 hour ago
Wow, @MaoWao was typing the exact same counterexample at the same time!
– Dirk
1 hour ago
@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$.
– JohnA
51 mins ago