Understanding Optimal Transport in One Dimension.

I'm trying to understand these lecture notes. https://sites.ualberta.ca/~mathirl/IUSEP/IUSEP_2018/lecture_notes/Pass1.pdf I understand the formulation of the Monge Problem. However, I'm having trouble understanding one-dimensional optimal transport with cost function being $$c(x-y)^2$$.In particular I do not really understand this lecture slide.

In particular, I do not understand why the solution must satisfy $$c(x_o,T(x_0))+c(x_1,T(x_1)) \leq c(x_0,T(x_1))+c(x_1,T(x_0))$$.

Also, I do not fully understand why this implies that if $$x_1>x_0$$ then $$T(x_1) \geq T(x_0)$$. (I understand this by doing a few concrete examples, but I do not understand how the condition $$c(x_o,T(x_0))+c(x_1,T(x_1)) \leq c(x_0,T(x_1))+c(x_1,T(x_0))$$ means that $$T$$ is monotone increasing.)

Finally, I do not understand why we must choose T(x) so that $$\int_{-\infty}^{x} f(t) dt= \int_{-\infty}^{T(x)} g(s) ds$$. Thank you very much and sorry for the basic questions.

• Hi does anyone have any ideas? thanks – kemb Apr 21 at 21:59
• Maybe mathoverflow.net is a better place for this one. – NoChance Apr 22 at 23:05
• if there is no mass at $x_0$ or $x_1$ (or in a small interval around them for the continuous case), the monotonicity claim is false – LinAlg Apr 23 at 23:50
• @LinAlg so it is not increasing if there is no mass at $x_0$ or $x_1$? Could you explain this further? – kemb Apr 24 at 1:40
• Apparently the slides assume a strictly positive mass function. – LinAlg Apr 24 at 12:13

1) Regardless of any assumptions on $$c$$, if for some $$x_0$$ and $$x_1$$ we had $$c(x_0,T(x_0))+c(x_1,T(x_1)) > c(x_0,T(x_1))+c(x_1,T(x_0))$$ (the opposite of the inequality we are claiming) then I claim (see below) that you could swap the destinations of a little bits of mass transported from near $$x_0$$ and $$x_1$$, that is send the one from around $$x_0$$ to near $$T(x_1)$$ instead and vice versa. The inequality then would ensure that this swap results in lower overall cost. Hence for optimal transport plan we never have $$c(x_0,T(x_0))+c(x_1,T(x_1)) > c(x_0,T(x_1))+c(x_1,T(x_0))$$, i.e. we always have $$c(x_0,T(x_0))+c(x_1,T(x_1)) \leq c(x_0,T(x_1))+c(x_1,T(x_0))$$.

The claim is clearest for a discrete setup. Namely, suppose instead of sand, you need to move $$N$$ pebbles (of identical mass) located at $$x_1\leq x_2 \leq \ldots \leq x_N$$ to new locations $$y_1\leq y_2 \leq \ldots \leq y_N$$, that is map $$x_i$$ to $$T(x_i)=y_{\sigma(i)}$$ for some permutation $$\sigma$$, while minimizing cost function $$\sum_i c(x_i, T(x_i))$$. Then if your current $$T$$ (meaning your current permutation $$\sigma$$) had the property that for some $$i$$ and $$j$$ you had $$c(x_i,T(x_i))+c(x_j,T(x_j)) > c(x_i,T(x_j))+c(x_j,T(x_i))$$ then you could change $$T$$ by swapping where it sends the two pebbles $$x_i$$ and $$x_j$$ (postmultiplying $$\sigma$$ by transposition $$(i,j)$$), literally replacing the two terms $$c(x_i,T(x_i))+c(x_j,T(x_j))$$ in the cost function sum by the two terms $$c(x_i,T(x_j))+c(x_j,T(x_i))$$, so getting less costly transport plan.

For non-discrete situation, this is a bit more subtle: the conditions given in the slides are unaffected by changing $$T$$ on set of measure zero, so we can not really claim anything about individual values. On the other hand, (a more careful version of) the argument above (with estimates) does go through if we assume $$T$$ to be piecewise continuous, ignore the values at discontinuity points and, say, assume $$f$$ is continuous on open set $$X$$.

There probably is something slicker and more general, but missing that, here is an argument: Suppose $$c(x_0,T(x_0))+c(x_1,T(x_1)) > c(x_0,T(x_1))+c(x_1,T(x_0))$$ for some piecewise-continuous $$T$$ and $$x_0$$ and $$x_1$$ are points where $$T$$ is continuous.

Claim 1: Then there exist $$\delta x_0 >0$$ and $$\delta x_1>0$$ such that $$\int_{x_0}^{x_0+ \delta x_0} f(x) dx= \int_{x_1}^{x_1+ \delta x_1} f(x) dx$$ and $$c(x^+_0,T(x^+_0))+c(x^+_1,T(x^+_1)) > c(x^+_0,T(x^+_1))+c(x_1,T(x^+_0))$$ for all $$x^+_0\in [x_0, x_0+\delta x_0], x^+_1\in [x_1, x_1+\delta x_1]$$( these are the "bits of mass near $$x_0$$ and $$x_1$$" that we are going to swap; proof of the claim is below).

This claim basically says that $$\hat{X}=[x_0,x_0+\delta x_0] \cup [x_1,x_1+\delta x_1]$$ is a subdomain of $$X$$ on which the transport plan is suboptimal. This implies that the transport plan is suboptimal on all of $$X$$. Namely, define new $$\hat{T}$$ that is equal to old $$T$$ outside $$\hat{X}$$ and on $$\hat{X}$$ sends the $$[x_0,x_0+\delta x_0]$$ to where $$T$$ used to send $$[x_1,x_1+\delta x_1]$$ and vice versa: define monotone $$\phi:[x_0, x_0+\delta x_0]\to [x_1, x_1+\delta x_1]$$ by $$\int_{x_0}^{x} f(x)dx=\int_{x_1}^{\phi(x)} f(x)dx$$ and its (monotone) inverse $$\psi:[x_1, x_1+\delta x_1]\to [x_0, x_0+\delta x_0]$$ by $$\int_{x_1}^{x} f(x)dx=\int_{x_1}^{\psi(x)} f(x)dx$$ (this is the swapping of the two bits of sand), and let $$\hat{T}(x)=T(\phi(x))$$ if $$[x_0, x_0+\delta x_0]$$, and $$\hat{T}(x)=T(\psi(x))$$ if $$[x_1, x_1+\delta x_1]$$ ("send the swapped bits to where the original used to go"). The definitions of $$\phi$$ and $$\psi$$ are such that $$\hat{T}$$ is a transport map, and the inequality from claim 1 means that $$\int_{\hat{X}} c(t, \hat{T}(t)) dt < \int_{\hat{X}} c(t, T(t))$$. (The map $$\hat{T}$$ is also piecewise continuous.) Thus we have proved that if $$T$$ were optimal piecewise continuous transport map then we must actually have $$c(x_0,T(x_0))+c(x_1,T(x_1)) \leq c(x_0,T(x_1))+c(x_1,T(x_0))$$ at least for all points $$x_0, x_1$$ where $$T$$ is continuous.

Proof of Claim 1: Let $$I(t, s)=\int_{x_0}^{x_0+ t} f(x) dx -\int_{x_1}^{x_1+ s} f(x) dx$$. Then $$I$$ is continuous near $$(0,0)$$ (on a ball of size $$\varepsilon_1$$), and for $$a< \varepsilon_2$$ we have $$I(0,a)<0$$ and $$I(a, 0)>0$$. We want to show that for any $$\varepsilon>0$$ there are positive $$s$$, $$t$$ with $$|s,t|<\varepsilon$$ with $$I(s,t)=0$$. Take a path from $$(0, a)$$ to $$(0, a)$$ within positive quadrant of $$\min(\varepsilon, \varepsilon_1, \varepsilon_2)$$. Then the value of $$I$$ along the path goes from positive to negative, so by continuity it must be zero somewhere, so providing the small positive $$(s, t)$$ with $$I(s,t)=0$$ that we want.

Now to finish the proof of the claim we just observe that $$C(u,v)=c(x_0+u,T(x_0+u))+c(x_1+v,T(x_1+v))-c(x_0+u,T(x_1+v))+c(x_1+v,T(x_0+u))$$ is continuous near $$(0,0)$$ so if it is positive at $$(0,0)$$ it is positive for all $$(u,v)$$ small enough, say $$u<\varepsilon$$, $$v<\varepsilon$$ and we can pick $$t=\delta x_0<\varepsilon$$ and $$s=\delta x_1<\varepsilon$$ to ensure this.

2) Now, for a function $$c$$ with $$\frac{\partial^2 c}{\partial x \partial y}<0$$ the inequality $$c(x,y)+c(x+\delta x, y+\delta y)< c(x, y+\delta y)+c(x+\delta x, y)$$ is true precisely when $$\delta x$$ and $$\delta y$$ are of the same sign. I will explain why this is true just below, but assuming this, we conclude precisely that $$\delta x=x_1-x_0$$ and $$\delta y=T(x_1)-T(x_0)$$ should be of the same sign, i.e. that $$T$$ is monotone.

The reason for this is that $$\frac{\partial^2 c}{\partial x \partial y}<0$$ is the infinitesimal version of the inequality $$c(x,y)+c(x+\delta x, y+\delta y)< c(x, y+\delta y)+c(x+\delta x, y)$$ -- if $$\delta x$$ and $$\delta y$$ are small, just Taylor expand the two sides of this last inequality to second order. However, we need the implication the other way, from the infenitesimal version $$\frac{\partial^2 c}{\partial x \partial y}<0$$ to the "global" one. This can be visualized by breaking the rectangle with vertices $$(x,y)$$, $$(x+\delta x, y+\delta y)$$, $$(x, y+\delta y)$$ and $$(x+\delta x, y)$$ into many small rectangles and applying the infinitesimal version to each small piece. But of course one wants to be rigorous, so one applies the Green's theorem to the line integral of the vector field $$(-\frac{\partial c}{\partial x}, \frac{\partial c}{\partial y})$$ (or to $$(-\frac{\partial c}{\partial x}, 0)$$, or to $$(0, \frac{\partial c}{\partial y} )$$ -- your choice) around the boundary of the rectangle. The condition on $$\delta x$$ and $$\delta y$$ insures that the orientations in Green's theorem work out in the correct way.

3) This is just the "transport constraint" from slide 9 i.e. $$\int_{T^{−1}(A)} f(x)dx =\int_A g(y)dy$$ applied to the case of monotone $$T$$: let $$A=(-\infty, T(x)]$$, then $$T^{-1}(A)=(-\infty, x]$$, now plug in.

• Hi I don't really understand still the reason why the solution must satisfy $c(x_o,T(x_0))+c(x_1,T(x_1)) \leq c(x_0,T(x_1))+c(x_1,T(x_0))$. So are you saying that if the inequality is $>$ rather than $\leq$ then we have less overall cost? Not sure I really understand, you could make this explanation clearer, thank you – kemb Apr 23 at 0:38
• I meant could you not you could. I just need help on this one part. Thanks! – kemb Apr 23 at 9:41
• I have made some edits and added the discussion for the discrete case, which has the main idea and I hope is understandable. I have also added the proof for piecewise continuous $T$, though it is a bit technical, and I'm not at all sure there isn't some better way to do this in higher generality. – Max Apr 23 at 14:34