Optimal Transport
Table of Contents
Discrete case
![\begin{equation*}
\begin{split}
d(\mu) &= \sum_{i, j, k, l}^{} \left| d_X(x_i, x_k) - d_Y(y_j, y_j) \right| \mu_{ij}, \mu_{kl} \\
&= \sum_{ijkl}^{} \Gamma_{ijkl} \mu_{ij} \mu_{kl} \\
&= U^T \Gamma U
\end{split}
\end{equation*}](../../assets/latex/optimal_transport_9bef9f28a1be4da5047f0e8326dac35ae71413b4.png)
So the optimal transport problem becomes
![\begin{equation*}
\underset{U}{\argmin}\ \frac{1}{2} U^T \Gamma U
\end{equation*}](../../assets/latex/optimal_transport_9fc8dc70edc1fe19784a06cb25bea3c9e0ff52d0.png)
subject to linear constraints
![\begin{equation*}
\sum_{j}^{} \mu_{ij} = 1 \quad \text{and} \quad \sum_{i}^{} \mu_{ij} = 1
\end{equation*}](../../assets/latex/optimal_transport_3b778e13ed506d8cb65c0609eff612507e246be1.png)
villani09_optim_trans
7. Displacement interpolation
Notation
denotes the action functional
is a certain class of continuous curves
Cost function between an initial point
and final point
:
- Riemannian manifold
- Langrangian
is defined on
Deterministic interpolation via action-minimizing curves
Action is classically given by the time-integral of a *Lagrangian$ along the path:
A continuous curve
is absolutely continuous if there exists a function
s.t. for all intermediate times
in
,
- If
is absolutely continuous, then
is differentiable a.e. and its derivative is integrable.
- If
Examples
Let
be a curve from
to
for some strictly convex
Then, by Jensen's inequality,
![\begin{equation*}
c(y - x) = c \Bigg( \int_{0}^{1} \dot{\gamma}_t \dd{t} \Bigg) \le \int_{0}^{1} c \big( \dot{\gamma}_t \big) \dd{t} =: \mathcal{A}(\gamma)
\end{equation*}](../../assets/latex/optimal_transport_0e8f0086f5b79a622de25a3ff69c03e16cb9d243.png)
which is an equality only when , and thus the action minimizers are lines
, i.e. straight lines:
![\begin{equation*}
\gamma_t = \gamma_0 + t (\gamma_1 - \gamma_0)
\end{equation*}](../../assets/latex/optimal_transport_1bbea0bb568bfeee5cb51d9c99781f07d3a910dd.png)
Also, then we have
![\begin{equation*}
c(x, y) = c(y - x)
\end{equation*}](../../assets/latex/optimal_transport_cc2fa925cae75a001909ffec2fb3d24f12596f9d.png)
since the cost function is defined by the minimizers of .
Interpolation of random variables
is a cost function associated with the Lagrangian action
be two given laws
- Optimal coupling
of
- Random action-minimizing path
joining
to
- => random variable
is an interpolation of
and
; or equivalently
is an interpolation of
and
- This is referred to as displacement interpolation
This should be constrasted with linear interpolation
- A dynamical transference plan
is a probability measure on the space
(i.e. space of curves).
- A dynamical coupling of two probability measures
is a random curve
s.t.
and
.
A dynamical optimal transference plan is a prob. measure on
on
s.t.
- Equivalently,
is the law of a random action-minimizing curve whose endpoints constitute an optimal coupling of
.
- Such a random curve is called a dynamic optimal coupling of
.
- By abuse of language,
is sometimes referred to as the same.
- By abuse of language,
- Equivalently,