Discrete Monge optimal transport

58 Views Asked by At

Here is the problem

Let $\mu$ and $\nu$ be defined by

$$ \begin{aligned} \mu&=\sum_{i=1}^{N_{\mu}}\alpha_i\delta_{x_i},\\ \nu&=\sum_{j=1}^{N_{\nu}}\beta_j\delta_{y_j}, \end{aligned} $$

where $\alpha_i,\beta_j>0$ and $x_i\ne x_j$ for all $i\ne j$ and $y_i\ne y_j$ for all $i\ne j$. Show that

  • i) If $N_{\mu}<N_{\nu}$, then there are no transport maps $T$ such that $T_{\#\mu}=\nu$.

  • ii) If $N_{\mu}=N_{\nu}$, is there necessarily a transport map?

My attempt

i)

Assume that $N_{\mu}<N_{\nu}$.

Let's suppose that there exists

$$ T:\mathbb{R}^d\rightarrow \mathbb{R}^d $$

transport map such that $T$ conserves mass: for every $A\subseteq \mathbb{R}^d$,

$$ \begin{aligned} \left(T_{\#\mu}\right)(A)&=\mu\left((T)^{-1}(A)\right)=\sum_{i=1}^{N_{\mu}}\alpha_i\delta_{T(x_i)}(A)\\ &=\nu(A)=\sum_{j=1}^{N_{\nu}}\beta_j\delta_{y_j}(A). \end{aligned} $$

Now let's take $A=\mathbb{R}^d$, thus

$$ \begin{aligned} \left(T_{\#\mu}\right)(A)&=\left(T_{\#\mu}\right)\left(\mathbb{R}^d\right)\\ &=\sum_{i=1}^{N_{\mu}}\alpha_i\delta_{T(x_i)}\left(\mathbb{R}^d\right)=\sum_{i=1}^{N_{\mu}}\alpha_i, \end{aligned} $$

this is because the codomain of $T$ is $\mathbb{R}^d$.

Similarly

$$ \begin{aligned} \nu(A)&=\nu\left(\mathbb{R}^d\right)\\ &=\sum_{j=1}^{N_{\nu}}\beta_j\delta_{y_j}\left(\mathbb{R}^d\right)=\sum_{j=1}^{N_{\nu}}\beta_j. \end{aligned} $$

Therefore

$$ \sum_{i=1}^{N_{\mu}}\alpha_i=\sum_{j=1}^{N_{\nu}}\beta_j. $$

Not sure how to continue, any ideas?

1

There are 1 best solutions below

0
On BEST ANSWER

I believe ideas naturally come when you have in mind that if $X\sim\mu$ then $T(X)\sim T_\sharp\mu$.

So it is clear that the support of $T_\sharp\mu$ is in $\{T(x_1),\cdots,T(x_{N_\mu})\}$ which is of size at most $N_\mu$. Yet the support of $\nu$ is of size $N_\nu$. So if $N_\mu<N_\nu$ then $T_\sharp\mu\neq\nu$.

For ii), take for instance $\mu=\frac12\delta_0+\frac12\delta_1$. Then $T_\sharp\mu=\frac12\delta_{T(0)}+\frac12\delta_{T(1)}$. So it cannot be equal for instance to $\nu=\frac14\delta_0+\frac34\delta_1$.