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*}

So the optimal transport problem becomes

\begin{equation*} \underset{U}{\argmin}\ \frac{1}{2} U^T \Gamma U \end{equation*}

subject to linear constraints

\begin{equation*} \sum_{j}^{} \mu_{ij} = 1 \quad \text{and} \quad \sum_{i}^{} \mu_{ij} = 1 \end{equation*}

villani09_optim_trans

7. Displacement interpolation

Notation

  • $\mathcal{A}$ denotes the action functional
  • $\mathcal{C}$ is a certain class of continuous curves

  • Cost function between an initial point $x$ and final point $y$:

    \begin{equation*} c(x, y) := \inf \left\{ \mathcal{A}(\gamma); \quad \gamma_0 = x, \quad \gamma_1 = y; \quad y \in \mathcal{C} \right\} \end{equation*}
  • Riemannian manifold $M$
  • Langrangian $L$ is defined on $TM \times [0, 1]$

Deterministic interpolation via action-minimizing curves

  • Action is classically given by the time-integral of a *Lagrangian$ along the path:

    \begin{equation*} \mathcal{A}(\gamma) := \int_{0}^{1} L(\gamma_t, \dot{\gamma}_t, t) \dd{t} \end{equation*}

  • A continuous curve $\gamma: [0, 1] \to \mathcal{X}$ is absolutely continuous if there exists a function $\ell \in L^1 \big( [0, 1]; \dd{t} \big)$ s.t. for all intermediate times $t_0 < t_1$ in $[0, 1]$,

    \begin{equation*} d \big( \gamma_{t_0}, \gamma_{t_1} \big) \le \int_{t_0}^{t_1} \ell(t) \dd{t} \end{equation*}
    • If $\gamma$ is absolutely continuous, then $t \mapsto d(\gamma_{t_0}, \gamma_{t_1})$ is differentiable a.e. and its derivative is integrable.
Examples

Let

  • $\mathcal{X} = \mathbb{R}^n$
  • $\gamma_t$ be a curve from $\gamma_0 = x$ to $\gamma_1 = y$
  • $L(x, v, t) = c(v)$ for some strictly convex $c$

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*}

which is an equality only when $\dot{\gamma}_t = \text{const}$, and thus the action minimizers are lines $\dot{\gamma}_t = \text{const}$, i.e. straight lines:

\begin{equation*} \gamma_t = \gamma_0 + t (\gamma_1 - \gamma_0) \end{equation*}

Also, then we have

\begin{equation*} c(x, y) = c(y - x) \end{equation*}

since the cost function is defined by the minimizers of $\mathcal{A}(\gamma)$.

Interpolation of random variables

  • $c$ is a cost function associated with the Lagrangian action $\mathcal{A}$
  • $\mu_0, \mu_1$ be two given laws
  • Optimal coupling $\big( X_0, X_1 \big)$ of $\big( \mu_0, \mu_1 \big)$
  • Random action-minimizing path $\big( X_t \big)_{0 \le t \le 1}$ joining $X_0$ to $X_1$
  • => random variable $X_t$ is an interpolation of $X_0$ and $X_1$; or equivalently $\mu_t$ is an interpolation of $\mu_0$ and $\mu_1$
    • This is referred to as displacement interpolation

    • This should be constrasted with linear interpolation

      \begin{equation*} \mu_t = (1 - t) \mu_0 + t \mu_1 \end{equation*}
  • A dynamical transference plan $\Pi$ is a probability measure on the space $C \big( [0, 1]; \mathcal{X} \big)$ (i.e. space of curves).
  • A dynamical coupling of two probability measures $\mu_0, \mu_1 \in \mathcal{P}(\mathcal{X})$ is a random curve $\gamma: [0, 1] \to \mathcal{X}$ s.t. $\Law( \gamma_0) = \mu_0$ and $\Law( \gamma_1) = \mu_1$.

  • A dynamical optimal transference plan is a prob. measure on $\Pi$ on $\Gamma$ s.t.

    \begin{equation*} \pi_{0, 1} := \ppushf{\big( e_0, e_1 \big)} \Pi \end{equation*}
    • Equivalently, $\Pi$ is the law of a random action-minimizing curve whose endpoints constitute an optimal coupling of $(\mu_0, \mu_1)$.
    • Such a random curve is called a dynamic optimal coupling of $(\mu_0, \mu_1)$.
      • By abuse of language, $\Pi$ is sometimes referred to as the same.