Let $\mu$ and $\nu$ be two measures on some (at least measurable) space $X$. In optimal transport theory, Monge's problem to $$ \text{minimize} \quad \int c(x,T(x))\mu(dx) \quad \text{over measurable mappings }T: X \rightarrow Y \text{ and } T_\#\mu = \nu$$ has a relatively straightforward interpretation: We try to find a measurable map $T$ that minimizes the cost to move mass from $x$ to $T(x)$. Now, the Kantorovich problem to $$ \text{minimize} \quad \int c(x,y)\pi(dx,dy) \quad \text{over couplings } \pi \text{ with first and second marginals } \mu \text{ and } \nu \text{, respectively,}$$ I find to be much harder to interpret as a real `mass transfer' problem; If $\pi^\star$ is an optimal coupling to the Kantorovich problem, what does $\pi^\star$ tell me where how much mass really goes? How do I interpret the Kantorovich problem?
-
$\begingroup$ A coupling $\pi$ only tells you that the probability mass to be transported from $A$ to $B$ is $\pi(A\times B)$, for any sets $A$ and $B$ in the corresponding $\sigma$-algebras. A solution to Monge's problem gives you a more detailed information -- where each point $x\in X$ is transported to. $\endgroup$– Iosif PinelisCommented Jan 13, 2021 at 15:51
-
1$\begingroup$ I see a coupling as like a spreadsheet. Think about the case where the measures you're trying to couple are discrete: maybe one measure is on $\{A,\ldots,J\}$ and the other is on $\{1,2,\ldots,12\}$. The marginal measures prescribe the row and column totals, and then a coupling is any assignment of (non-negative) numbers to the array compatible with those totals. In this discrete case (which is easier), you can read off the amount transported from E to 7 for example as the E7 entry in the spreadsheet. $\endgroup$– Anthony QuasCommented Jan 13, 2021 at 17:12
-
$\begingroup$ Same idea as a markov chain $\endgroup$– Piyush GroverCommented Jan 13, 2021 at 17:29
-
1$\begingroup$ If source $X$ and target $Y$ are finite spaces of cardinality $m,n$, respectively, then couplings between the uniform measures $\frac{1}{m}1_X$ and $\frac{1}{n}1_Y$ are represented by doubly stochastic $m\times n$ matrices $(a_{ij})$, where every column sums to $1/m$ and every row sums to $1/n$. When $m=n$, it is very important exercise to prove that the set of doubly stochastic matrices is compact convex and has $m!$ extreme points corresponding precisely to permutation matrices. The proof motivates the idea of cyclical monotonicity, which is key definition in OT. $\endgroup$– JHMCommented Jan 13, 2021 at 18:15
-
$\begingroup$ @JHM Do you have a reference to this? I'd like to read up on it. $\endgroup$– ABIMCommented Jun 19 at 14:47
4 Answers
Of the mass $\mu(A)$ in $A$ a fraction $\pi(A \times B)$ is transported to $B$, so you can think of this as a randomized transport map. A basic example to think of is $\mu=\delta_0$ and $\nu=(\delta_1+\delta_{-1})/2$. Half the mass at 0 is sent to 1 and half is sent to -1. You can get a better intuition from reading more about construction of couplings:
[1] Lindvall, Torgny. Lectures on the coupling method. Courier Corporation, 2002.
[2] Thorisson, Hermann. "Coupling methods in probability theory." Scandinavian journal of statistics (1995): 159-182.
-
$\begingroup$ I have a concern about the first line. $\pi(A \times B)$ is not the fraction of the mass $\mu(A)$ that is transported to $B$. Instead, it is simply the mass transported from $A$ to $B$. For example, when $\mu(A) = 1/3$ and $\pi(A, B) = 1/3$, we do not mean that one-third of $1/3 = 1/9$ is transported; we instead mean that the whole $1/3$ is transported from $A$ to $B$. So under this coupling, $\pi(A, S) = 0$ for all $S \neq B$, since there is no mass left at $A$ to be transported elsewhere. Correct me if I am wrong. $\endgroup$– rimsCommented Sep 29 at 21:43
The interpretation of couplings as randomized transport maps is not without problems. In general, extreme points of the space of couplings need not be supported on the graph of a function; see, for example, here.
However, it is possible to interpret them as deterministic transport maps on extended spaces:
Theorem: There exist a probability space $(\Omega,\Sigma,\tau)$ such that for any two Polish spaces $X$ and $Y$ and corresponding Borel probability measures $\mu$ and $\nu$, there exist measurable functions $g_1:\Omega\to X$ and $g_2:\Omega\to Y$ satisfying $\mu=\tau\circ g_1^{-1}$ and $\nu=\tau\circ g_2^{-1}$ and such that for every coupling $\pi$ of $\mu$ and $\nu$, there is a measure preserving bijection with measurable inverse $T_\pi:\Omega\to\Omega$ such that $\pi$ is the distribution of the function $$\omega\mapsto \Big(g_1(\omega),g_2\big(T(\omega)\big)\Big)$$ under $\tau$.
The proof leverages the existence of monstrous probability spaces (such as uncountable products of the uniform distribution) with somewhat unconventional properties; see Section 7 here for the details.
The answers above already say it all. Still, if you are a visual person, have a look at the following optimal coupling/transport plan (or to be precise, a sample thereof. Note that the colour's strength is a function of the empirical density.) between a univariate $T$ distribution with 3 degrees of freedom and a standard Gaussian. You can really interpret this as "to reshape optimally a $T_3$ distribution to get a Gaussian, I need to push the mass contained in the tails towards the middle". To see this, observe that an infinitesimal volume element around -4 for the student will approximately be transported to -2. This is a particularity of the 1D case, but the intuition "holds" for higher dimensions.
Given any coupling $\pi$ between two measures $\mu$ and $\nu$, you can construct a associated transport plan. To do so, for each point $x \in X$, you distribute the mass according the "marginal distribution" of $\pi$ at $x$. At first, this does not seemed well defined, since for non-atomic measures singletons will be sets of measure zero. However, there is a well defined disintegration of $\pi$, which gives a well-defined marginal $\mu$-almost everywhere, which is how to define the transport rigorously. In the picture below, I've tried to draw the "marginal of $\pi$ at $x$" in purple.
Kantorovich's theorem says that the optimal coupling is often concentrated on a much smaller subset of $X \times Y$, and a solution to the Monge problem transports each point $x \in X$ to a unique point $y \in Y$. However, the transport is defined for an arbitrary coupling.
