> ## Documentation Index
> Fetch the complete documentation index at: https://aegean.ai/llms.txt
> Use this file to discover all available pages before exploring further.

# Transport maps and couplings

> Moving one density into another, and what each way of moving it costs.

[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/pantelis/eng-ai-agents/blob/main/notebooks/optimal-transport/maps-and-couplings/index.ipynb)

```python theme={null}
import numpy as np
import matplotlib.pyplot as plt
from scipy import sparse, stats
from scipy.optimize import linprog
from scipy.special import logsumexp
from scipy.stats import norm
```

```python theme={null}
# Source p_0 is the standard normal N(0, 1). Target p_1 is this Gaussian mixture.
PI = np.array([0.3, 0.5, 0.2])
MU = np.array([-2.0, 1.0, 3.5])
SIGMA = np.array([0.4, 0.6, 0.3])
U_CLIP = 1e-12  # quantile levels are clipped to [U_CLIP, 1 - U_CLIP]


def mixture_pdf(x, pi=PI, mu=MU, sigma=SIGMA):
    x = np.asarray(x, dtype=float)[..., None]
    return np.sum(pi * norm.pdf(x, mu, sigma), axis=-1)


def mixture_cdf(x, pi=PI, mu=MU, sigma=SIGMA):
    x = np.asarray(x, dtype=float)[..., None]
    return np.sum(pi * norm.cdf(x, mu, sigma), axis=-1)


def mixture_ppf(u, pi=PI, mu=MU, sigma=SIGMA, iters=64):
    """Quantile function F_1^{-1}(u) by vectorized bisection on the mixture CDF.

    The root lies between the smallest and the largest component quantile at level u.
    """
    u = np.clip(np.asarray(u, dtype=float), U_CLIP, 1 - U_CLIP)
    q = mu + sigma * norm.ppf(u)[..., None]
    lo, hi = q.min(axis=-1), q.max(axis=-1)
    for _ in range(iters):
        mid = 0.5 * (lo + hi)
        below = mixture_cdf(mid, pi, mu, sigma) < u
        lo = np.where(below, mid, lo)
        hi = np.where(below, hi, mid)
    return 0.5 * (lo + hi)


def monge_map(x0, pi=PI, mu=MU, sigma=SIGMA):
    """Increasing map T = F_1^{-1} o F_0 from N(0, 1) to the mixture."""
    return mixture_ppf(norm.cdf(x0), pi, mu, sigma)


def w2_squared(n_quad=20000, pi=PI, mu=MU, sigma=SIGMA):
    """W_2^2(p_0, p_1) as the integral of (F_0^{-1} - F_1^{-1})^2 over (0, 1), midpoint rule."""
    u = (np.arange(n_quad) + 0.5) / n_quad
    return np.mean((norm.ppf(u) - mixture_ppf(u, pi, mu, sigma)) ** 2)


def fm_path_density(t, x, pi=PI, mu=MU, sigma=SIGMA):
    """Density of x_t = (1 - t) x_0 + t x_1 with x_0 ~ N(0, 1) and x_1 ~ p_1 independent."""
    s = np.sqrt((1 - t) ** 2 + t**2 * sigma**2)
    return mixture_pdf(x, pi, t * mu, s)


def plot_transport(ax, t_grid, x_grid, density, trajectories=None, title="",
                   action=None, edge=0.22):
    """Standard figure: heatmap of p_t(x) with time on the horizontal axis.

    density has shape (len(x_grid), len(t_grid)). The source and target columns are
    drawn as profiles outside the left and right edges. trajectories, if given, has
    shape (len(t_grid), n_particles). action, if given, is reported in the title.
    """
    vmax = np.quantile(density, 0.995)
    ax.pcolormesh(t_grid, x_grid, density, shading="auto", cmap="magma", vmin=0, vmax=vmax)
    for col, side, color in ((0, -1, "tab:blue"), (-1, 1, "tab:orange")):
        profile = density[:, col] / density[:, col].max()
        t_edge = t_grid[col]
        ax.fill_betweenx(x_grid, t_edge, t_edge + side * edge * profile,
                         color=color, alpha=0.7, lw=0)
    if trajectories is not None:
        ax.plot(t_grid, trajectories, color="white", lw=0.6, alpha=0.7)
    ax.set_xlim(t_grid[0] - 1.05 * edge, t_grid[-1] + 1.05 * edge)
    ax.set_ylim(x_grid[0], x_grid[-1])
    ax.set_xticks(np.linspace(t_grid[0], t_grid[-1], 5))
    ax.set_xlabel("t")
    ax.set_ylabel("x")
    if action is not None:
        title = f"{title} (kinetic action {action:.3f})" if title else f"kinetic action {action:.3f}"
    ax.set_title(title)
```

## The transport problem

A generative model starts from a density that is easy to sample and ends at the density of the data. In this chapter the source is the standard normal $p_0 = \mathcal{N}(0, 1)$ on the real line. The target plays the role of the data. It is a mixture of three Gaussians,

$$
p_1(x) = \sum_{k=1}^{3} \pi_k \, \mathcal{N}(x;\, \mu_k, \sigma_k^2),
$$

with weights $\pi_k = (0.3, 0.5, 0.2)$, means $\mu_k = (-2, 1, 3.5)$ and standard deviations $\sigma_k = (0.4, 0.6, 0.3)$. Time runs from $t = 0$, where the mass is distributed as $p_0$, to $t = 1$, where it is distributed as $p_1$. The diffusion sections later in the book run time in the opposite direction.

Three objects describe how the mass gets from $p_0$ to $p_1$. The probability path $p_t(x)$ says where the mass is at time $t$. The velocity field $v_t(x)$ says which way, and how fast, the mass at position $x$ moves at time $t$. A particle trajectory $x_t$ follows one sample as the field carries it. This section is about the two endpoints and the ways of pairing them. Fields and trajectories return in the section on dynamic transport.

The figure below shows one probability path. Draw $x_0 \sim p_0$ and $x_1 \sim p_1$ independently and move along the straight line $x_t = (1 - t)\,x_0 + t\,x_1$. The density of $x_t$ at each time is a column of the heatmap. Time runs from left to right, and brighter color means more mass. The source density is drawn outside the left edge and the target density outside the right edge. Every transport method in this chapter is drawn in this format, so you can compare them side by side.

```python theme={null}
t_grid = np.linspace(0, 1, 101)
x_grid = np.linspace(-4.5, 5.5, 401)
p_path = np.stack([fm_path_density(t, x_grid) for t in t_grid], axis=1)
```

![Heatmap of the probability path with time from 0 to 1 on the horizontal axis and x on the vertical axis. The standard normal source is drawn as a profile on the left edge and the three-component mixture target as a profile on the right edge. The bright band starts as one wide bump, narrows slightly before t = 0.25, and splits into three bands that end at the three target components.](https://mintcdn.com/aegeanaiinc/TxnGZcYFzPhEZiXx/aiml-common/lectures/optimal-transport/maps-and-couplings/images/cell_4_output_1.png?fit=max\&auto=format\&n=TxnGZcYFzPhEZiXx\&q=85\&s=64ea4939c04bc12f8a67161e3b0bc1ab)

*The probability path of independent pairs joined by straight lines. The source $p_0$ is on the left, the target $p_1$ on the right.*

The figure below shows the same path at five times.

![Five density plots of the same path at times 0, 0.25, 0.5, 0.75 and 1. At time 0 the density is a single standard normal bump. At 0.25 it is slightly narrower and taller. At 0.5 it has a main peak with two shoulders, and at 0.75 and 1 it has three separate bumps, the mixture components.](https://mintcdn.com/aegeanaiinc/TxnGZcYFzPhEZiXx/aiml-common/lectures/optimal-transport/maps-and-couplings/images/cell_5_output_1.png?fit=max\&auto=format\&n=TxnGZcYFzPhEZiXx\&q=85\&s=70f526d7a5fe53400127f4c0491496c9)

*Snapshots of $p_t$ at five times. Each snapshot is a vertical slice of the heatmap.*

The single bump narrows a little before it splits. This narrowing comes from the choice of path. Another path between the same endpoints need not narrow. Four questions follow, and the sections of this chapter answer them: What shapes the intermediate density? Which other paths join the same two endpoints? Which velocity field produces each path? Which path costs the least to follow? This section starts with the last question, asked about the endpoints only: which way of pairing source points with target points is the cheapest?

## Transport maps

The first answer, due to Monge, is a function that sends each source point to a target point. A map $T$ transports $p_0$ to $p_1$ when $x_0 \sim p_0$ gives $T(x_0) \sim p_1$. This is written

$$
T_\sharp \, p_0 = p_1,
$$

and read as "$T$ pushes $p_0$ forward to $p_1$".

In 1D such maps are easy to build from cumulative distribution functions. Write $F_0$ for the CDF of $p_0$ and $F_1$ for the CDF of $p_1$. If $x_0 \sim p_0$, then $F_0(x_0)$ is uniform on $(0, 1)$. Applying the quantile function $F_1^{-1}$ to a uniform variable produces a sample of $p_1$. So the increasing map

$$
T(x) = F_1^{-1}\bigl(F_0(x)\bigr)
$$

transports $p_0$ to $p_1$. If $U$ is uniform, so is $1 - U$. The decreasing map $F_1^{-1}\bigl(1 - F_0(x)\bigr)$ therefore also transports $p_0$ to $p_1$.

The mixture CDF has no elementary inverse, so $F_1^{-1}(u)$ is computed by searching for the root of $F_1(x) = u$. The largest error of this inversion over a grid of quantile levels is printed below. Both maps used in this section rely on it.

```python theme={null}
u = np.linspace(U_CLIP, 1 - U_CLIP, 2001)
print(f"largest |F_1(F_1^-1(u)) - u| on the grid: {np.max(np.abs(mixture_cdf(mixture_ppf(u)) - u)):.1e}")
```

```output theme={null}
largest |F_1(F_1^-1(u)) - u| on the grid: 2.2e-16
```

```python theme={null}
u = np.linspace(1e-12, 1 - 1e-12, 2001)
assert np.all(np.isfinite(mixture_ppf(u)))
assert np.max(np.abs(mixture_cdf(mixture_ppf(u)) - u)) < 1e-9
```

```python theme={null}
def decreasing_map(x0, pi=PI, mu=MU, sigma=SIGMA):
    """Decreasing map x -> F_1^{-1}(1 - F_0(x)), which also pushes N(0, 1) to the mixture."""
    return mixture_ppf(1 - norm.cdf(x0), pi, mu, sigma)
```

```python theme={null}
rng = np.random.default_rng(0); x0 = rng.standard_normal(200_000)
for T in (monge_map, decreasing_map):
    assert stats.kstest(T(x0), mixture_cdf).statistic < 0.005
```

```python theme={null}
images = {"increasing": monge_map(x0), "decreasing": decreasing_map(x0)}
for name, y in images.items():
    ks = stats.kstest(y, mixture_cdf).statistic
    print(f"{name} map: largest gap between the CDF of T(x_0) and F_1 = {ks:.4f}")
```

```output theme={null}
increasing map: largest gap between the CDF of T(x_0) and F_1 = 0.0014
decreasing map: largest gap between the CDF of T(x_0) and F_1 = 0.0014
```

![Two histograms of 200,000 transported samples, one for the increasing map and one for the decreasing map. Both histograms follow the black curve of the three-component target density closely.](https://mintcdn.com/aegeanaiinc/TxnGZcYFzPhEZiXx/aiml-common/lectures/optimal-transport/maps-and-couplings/images/cell_11_output_1.png?fit=max\&auto=format\&n=TxnGZcYFzPhEZiXx\&q=85\&s=6244f7ea77e526c851219d9558ff1aac)

*Histograms of $T(x_0)$ for 200,000 samples $x_0 \sim p_0$. Both maps reproduce $p_1$.*

The two maps produce the same distribution, but they pair points very differently. The schematic below draws a line from $x_0$ on the source axis to $T(x_0)$ on the target axis, for source points at evenly spaced quantile levels. The increasing map keeps the order of the points, so its lines never cross. The decreasing map reverses the order, so every pair of its lines crosses.

![Two line schematics. In each, 25 source points on a lower axis are joined by straight lines to their images on an upper axis. For the increasing map the lines fan out without crossing. For the decreasing map the leftmost source point goes to the rightmost target and every pair of lines crosses.](https://mintcdn.com/aegeanaiinc/TxnGZcYFzPhEZiXx/aiml-common/lectures/optimal-transport/maps-and-couplings/images/cell_12_output_1.png?fit=max\&auto=format\&n=TxnGZcYFzPhEZiXx\&q=85\&s=b52945bd4bea365af4d84deaf1310d83)

*Source points at 25 quantile levels and their images. Matching the target density does not decide which source point goes where.*

## Monge's problem

Monge asked for the map with the smallest transport cost. With the squared distance as the cost of moving one unit of mass, the problem is

$$
\min_{T \,:\, T_\sharp p_0 = p_1} \; \int (x - T(x))^2 \, p_0(x) \, dx .
$$

The integral is the average of $(x_0 - T(x_0))^2$ over $x_0 \sim p_0$.

Two pairs of points show why the increasing map is cheaper. Take two source points $a < b$ of equal mass and two targets $c < d$. The ordered pairing sends $a \to c$ and $b \to d$. The crossed pairing sends $a \to d$ and $b \to c$. The squares $a^2, b^2, c^2, d^2$ cancel in the difference of the two costs, which leaves

$$
\begin{aligned}
&(a - d)^2 + (b - c)^2 - (a - c)^2 - (b - d)^2 \\
&\quad = 2(ac + bd - ad - bc) \\
&\quad = 2(b - a)(d - c) > 0 .
\end{aligned}
$$

The crossed pairing always costs more. A map that is not increasing sends some pair $a < b$ to $T(a) > T(b)$, and swapping the targets of small intervals of mass around $a$ and $b$ lowers the cost. So in 1D the cheapest map is the increasing one, $T = F_1^{-1} \circ F_0$ (Santambrogio, 2015). For $n$ source points and $n$ target points of equal mass, the same argument says that you solve the discrete problem by sorting both lists and pairing them in order.

The code below computes the cost of both maps on the mixture and checks the two-point identity on random points.

```python theme={null}
def cost(T, n=200_000):
    """Monte Carlo estimate of E[(x_0 - T(x_0))^2] for x_0 ~ N(0, 1), seed 0."""
    x0 = np.random.default_rng(0).standard_normal(n)
    return np.mean((x0 - T(x0)) ** 2)


cost_increasing, cost_decreasing = cost(monge_map), cost(decreasing_map)
print(f"cost of the increasing map: {cost_increasing:.4f}")
print(f"cost of the decreasing map: {cost_decreasing:.4f}")
```

```output theme={null}
cost of the increasing map: 1.5146
cost of the decreasing map: 9.2949
```

```python theme={null}
a, b, c, d = np.sort(rng.normal(size=2)).tolist() + np.sort(rng.normal(size=2)).tolist()
assert np.isclose((a-d)**2 + (b-c)**2 - (a-c)**2 - (b-d)**2, 2*(b-a)*(d-c))
assert cost(monge_map) < cost(decreasing_map)
```

None of these checks use the particular weights, means or widths of the mixture. The code below repeats them for a second target, an equal mixture of $\mathcal{N}(-1.5, 0.5^2)$ and $\mathcal{N}(2, 0.5^2)$. If you change `PI`, `MU` and `SIGMA` at the top of this section, the checks above still apply.

```python theme={null}
PI2, MU2, SIGMA2 = np.array([0.5, 0.5]), np.array([-1.5, 2.0]), np.array([0.5, 0.5])
mix2 = dict(pi=PI2, mu=MU2, sigma=SIGMA2)

u = np.linspace(1e-12, 1 - 1e-12, 2001)
assert np.all(np.isfinite(mixture_ppf(u, **mix2)))
assert np.max(np.abs(mixture_cdf(mixture_ppf(u, **mix2), **mix2) - u)) < 1e-9

monge_map2 = lambda x: monge_map(x, **mix2)
decreasing_map2 = lambda x: decreasing_map(x, **mix2)
for T in (monge_map2, decreasing_map2):
    assert stats.kstest(T(x0), lambda x: mixture_cdf(x, **mix2)).statistic < 0.005
assert cost(monge_map2) < cost(decreasing_map2)
```

## Couplings

A map sends each source point to exactly one place. Sometimes mass has to split. Take one source point $x = 0$ with mass 1 and two target points $y = 1$ and $y = 2$ with mass $1/2$ each. Any map sends the whole source point to a single target, so no map transports this source to this target.

Kantorovich replaced maps with couplings. A coupling $\pi$ is a joint distribution of a pair $(x, y)$ whose first marginal is $p_0$ and whose second marginal is $p_1$. It says how much mass at $x$ goes to $y$, and the mass at one $x$ may spread over several $y$. The cost of a coupling is $\mathbb{E}_{\pi}\bigl[(x - y)^2\bigr]$, and Kantorovich's problem is to minimize this cost over all couplings (Santambrogio, 2015; Peyré & Cuturi, 2018). A coupling need not have a density. The coupling of a map $T$ puts all its mass on the graph $y = T(x)$, so maps are a special case.

On finitely many points a coupling is a matrix $P$ with $P_{ij} \ge 0$, row sums equal to the source masses $a_i$ and column sums equal to the target masses $b_j$. Its cost is $\sum_{ij} C_{ij} P_{ij}$ with $C_{ij} = (x_i - y_j)^2$. Both the cost and the constraints are linear in $P$, so the problem is a linear program. For the split example the only coupling sends half of the mass to each target, and the solver finds it.

```python theme={null}
def discrete_ot(a, b, C):
    """Optimal coupling of masses a (rows) and b (columns) for the cost matrix C."""
    n, m = C.shape
    row_sums = sparse.kron(sparse.eye(n), np.ones((1, m)))
    col_sums = sparse.kron(np.ones((1, n)), sparse.eye(m))
    # Presolve is off because grid masses span many orders of magnitude, and the
    # presolver can then wrongly declare the problem infeasible.
    res = linprog(C.ravel(), A_eq=sparse.vstack([row_sums, col_sums]).tocsr(),
                  b_eq=np.concatenate([a, b]), bounds=(0, None), method="highs",
                  options={"presolve": False})
    if res.status != 0:
        raise RuntimeError(res.message)
    return res.x.reshape(n, m)


print(discrete_ot(np.array([1.0]), np.array([0.5, 0.5]), C=np.array([[1.0, 4.0]])))
```

```output theme={null}
[[0.5 0.5]]
```

```python theme={null}
plan = discrete_ot(np.array([1.0]), np.array([0.5, 0.5]), C=np.array([[1.0, 4.0]]))
assert np.allclose(plan, [[0.5, 0.5]])
```

Between two densities on the line a map always exists. Couplings still give more ways to pair points than maps do. The simplest is the independent coupling $p_0 \otimes p_1$, which draws $x$ and $y$ separately. It is the coupling behind the path at the top of this section. Expanding the square and using $\mathbb{E}[x] = 0$ and $\mathbb{E}[x^2] = 1$ for the standard normal gives its cost,

$$
\begin{aligned}
\mathbb{E}\bigl[(x - y)^2\bigr] &= 1 + \mathbb{E}_{p_1}\bigl[y^2\bigr] \\
&= 1 + \sum_k \pi_k \bigl(\mu_k^2 + \sigma_k^2\bigr).
\end{aligned}
$$

The code below compares this formula with a sampled estimate.

```python theme={null}
def sample_mixture(n, rng, pi=PI, mu=MU, sigma=SIGMA):
    k = rng.choice(len(pi), size=n, p=pi)
    return rng.normal(mu[k], sigma[k])


def cost_independent_mc(n, seed=0):
    """Monte Carlo cost of the independent coupling p_0 x p_1."""
    rng = np.random.default_rng(seed)
    return np.mean((rng.standard_normal(n) - sample_mixture(n, rng)) ** 2)


exact_indep = 1 + np.sum(PI * (MU**2 + SIGMA**2))
print(f"independent coupling, formula: {exact_indep:.4f}")
print(f"independent coupling, sampled: {cost_independent_mc(200_000):.4f}")
```

```output theme={null}
independent coupling, formula: 5.3960
independent coupling, sampled: 5.4136
```

```python theme={null}
exact_indep = 1 + np.sum(PI * (MU**2 + SIGMA**2))
assert abs(cost_independent_mc(200_000) / exact_indep - 1) < 0.01
```

To find the optimal coupling of the two densities, put both on a grid of $n$ points over $[-5, 6]$, give each grid point the mass of its density value (normalized to sum to 1), and solve the linear program. The figure shows the result for $n = 100$ next to the independent coupling. Each panel is the matrix $P$, with source position on the horizontal axis and target position on the vertical axis.

```python theme={null}
def grid_problem(n, lo=-5.0, hi=6.0, pi=PI, mu=MU, sigma=SIGMA):
    """Grid points, source masses, target masses and squared-distance costs."""
    x = np.linspace(lo, hi, n)
    a = norm.pdf(x)
    b = mixture_pdf(x, pi, mu, sigma)
    return x, a / a.sum(), b / b.sum(), (x[:, None] - x[None, :]) ** 2


def lp_w2_squared(n):
    x, a, b, C = grid_problem(n)
    return np.sum(discrete_ot(a, b, C) * C)


x_g, a_g, b_g, C_g = grid_problem(100)
plan_opt = discrete_ot(a_g, b_g, C_g)
plan_ind = np.outer(a_g, b_g)
print(f"grid cost, independent coupling: {np.sum(plan_ind * C_g):.4f}")
print(f"grid cost, optimal coupling:     {np.sum(plan_opt * C_g):.4f}")
print(f"cost of the increasing map:      {cost_increasing:.4f}")
```

```output theme={null}
grid cost, independent coupling: 5.3960
grid cost, optimal coupling:     1.5177
cost of the increasing map:      1.5146
```

![Two coupling matrices on a 100-point grid, source position on the horizontal axis and target position on the vertical axis. The independent coupling is three horizontal blobs, one per target component, each spread over source positions from about -2 to 2. The optimal coupling is a thin increasing staircase curve lying on the dashed red graph of the increasing map.](https://mintcdn.com/aegeanaiinc/TxnGZcYFzPhEZiXx/aiml-common/lectures/optimal-transport/maps-and-couplings/images/cell_21_output_1.png?fit=max\&auto=format\&n=TxnGZcYFzPhEZiXx\&q=85\&s=6e05ef588e45a1fc4a9b23cc77fa9886)

*Left, the independent coupling spreads each source point over the whole target. Right, the optimal coupling from the linear program concentrates on the graph of the increasing map $T$ (dashed).*

The optimal coupling of the grid problem is the coupling of the increasing map, up to the resolution of the grid. On the line, then, Kantorovich's problem and Monge's problem have the same answer. Couplings matter in this chapter for another reason: the flow matching section trains on pairs $(x_0, x_1)$ drawn from a coupling, and the choice of coupling shapes the path it learns.

## The Wasserstein distance

The cost of the optimal coupling is the squared Wasserstein distance,

$$
W_2^2(p_0, p_1) = \min_{\pi} \; \mathbb{E}_{\pi}\bigl[(x - y)^2\bigr],
$$

where the minimum runs over all couplings of $p_0$ and $p_1$. In 1D the optimal coupling pairs equal quantile levels: the point at level $u$ of $p_0$ goes to the point at level $u$ of $p_1$. Substituting $u = F_0(x)$ in the cost of the increasing map gives

$$
W_2^2(p_0, p_1) = \int_0^1 \bigl(F_0^{-1}(u) - F_1^{-1}(u)\bigr)^2 \, du ,
$$

the squared $L^2$ distance between the two quantile functions (Peyré & Cuturi, 2018). The code below evaluates this integral and compares it with the linear program as the grid is refined.

```python theme={null}
w2_ref = w2_squared()
print(f"W_2^2 from the quantile functions: {w2_ref:.4f}")
for n in (50, 100, 200):
    w2_lp = lp_w2_squared(n)
    print(f"linear program, n = {n:3d}: {w2_lp:.4f}  (relative error {abs(w2_lp / w2_ref - 1):.4f})")
```

```output theme={null}
W_2^2 from the quantile functions: 1.5149
linear program, n =  50: 1.5282  (relative error 0.0088)
linear program, n = 100: 1.5177  (relative error 0.0019)
```

```output theme={null}
linear program, n = 200: 1.5156  (relative error 0.0005)
```

```python theme={null}
errs = [abs(lp_w2_squared(n) / w2_squared() - 1) for n in (50, 100, 200)]
assert errs[-1] < 0.02 and errs[-1] < errs[0]
assert abs(cost_increasing / w2_squared() - 1) < 0.005
```

The relative error of the grid answer falls from about 0.9% at $n = 50$ to about 0.05% at $n = 200$. The quantile formula also agrees with the sampled cost of the increasing map from Monge's problem, to the third decimal place.

$W_2$ is a distance between densities. It is zero only when the two densities are equal, it is symmetric, and it satisfies the triangle inequality. Its value is the cost of moving one density into the other, so it compares densities by how far their mass must travel. Two narrow bumps that do not overlap are far apart in $W_2$ when their centers are far apart and close when their centers are close. A measure that compares density values point by point, such as the total variation distance, gives the same value in both cases, because the bumps never overlap. Later sections compare the kinetic action of every path with $W_2^2$.

## Optional: entropic transport and Sinkhorn iterations

This subsection is outside the main line of the chapter. You can skip to Brenier's theorem below.

The linear program grows quickly with the number of points: a grid of $n$ points has $n^2$ unknowns. Cuturi's remedy was to add an entropy term to the cost (Cuturi, 2013). For $\varepsilon > 0$, solve

$$
\begin{aligned}
&\min_{P} \; \sum_{ij} C_{ij} P_{ij} - \varepsilon H(P), \\
&H(P) = -\sum_{ij} P_{ij} \bigl(\log P_{ij} - 1\bigr),
\end{aligned}
$$

over the same matrices $P$ with row sums $a$ and column sums $b$. The solution has the form $P_{ij} = u_i K_{ij} v_j$ with $K_{ij} = e^{-C_{ij}/\varepsilon}$. Sinkhorn's algorithm finds the scalings by alternating between the two marginal constraints:

$$
u \leftarrow a \oslash (K v), \qquad v \leftarrow b \oslash (K^\top u),
$$

where $\oslash$ divides entry by entry. For small $\varepsilon$ the entries of $K$ underflow, so the iteration below runs on the logarithms of the scalings.

```python theme={null}
def sinkhorn(a, b, C, eps, iters=5000):
    """Entropic optimal coupling by Sinkhorn iterations on log scalings f = eps log u, g = eps log v."""
    log_a, log_b = np.log(a), np.log(b)
    f, g = np.zeros_like(a), np.zeros_like(b)
    for _ in range(iters):
        f = eps * (log_a - logsumexp((g[None, :] - C) / eps, axis=1))
        g = eps * (log_b - logsumexp((f[:, None] - C) / eps, axis=0))
    return np.exp((f[:, None] + g[None, :] - C) / eps)


EPSILONS = (1.0, 0.1, 0.01)
x_w, a_w, b_w, C = grid_problem(100)
plans_eps = {eps: sinkhorn(a_w, b_w, C, eps) for eps in EPSILONS}
print(f"independent coupling cost: {np.sum(np.outer(a_w, b_w) * C):.4f}")
for eps, P in plans_eps.items():
    print(f"epsilon = {eps:<5}: cost {np.sum(P * C):.4f}")
print(f"linear program cost:       {np.sum(discrete_ot(a_w, b_w, C) * C):.4f}")
```

```output theme={null}
independent coupling cost: 5.3960
epsilon = 1.0  : cost 1.9230
epsilon = 0.1  : cost 1.5625
epsilon = 0.01 : cost 1.5201
linear program cost:       1.5177
```

```python theme={null}
for eps in EPSILONS:
    P = sinkhorn(a_w, b_w, C, eps)
    assert np.allclose(P.sum(1), a_w, atol=1e-6) and np.allclose(P.sum(0), b_w, atol=1e-6)
costs = [np.sum(sinkhorn(a_w, b_w, C, e) * C) for e in sorted(EPSILONS)]
assert np.all(np.diff(costs) >= -1e-9)          # cost grows with eps
lp_cost = np.sum(discrete_ot(a_w, b_w, C) * C)
indep_cost = np.sum(np.outer(a_w, b_w) * C)
assert lp_cost <= costs[0] + 1e-9 and costs[-1] <= indep_cost
```

![Three entropic coupling matrices for epsilon 1, 0.1 and 0.01 on the same axes as the linear program figure. At epsilon 1 the mass is three blurred blobs around the dashed increasing map. At 0.1 the band is narrower, and at 0.01 it is a thin curve on the dashed line.](https://mintcdn.com/aegeanaiinc/TxnGZcYFzPhEZiXx/aiml-common/lectures/optimal-transport/maps-and-couplings/images/cell_26_output_1.png?fit=max\&auto=format\&n=TxnGZcYFzPhEZiXx\&q=85\&s=f55a98fc3c213dceab75b7f4d9d0f4a9)

*Entropic couplings for three values of $\varepsilon$. The dashed line is the increasing map.*

A large $\varepsilon$ rewards spread, so the coupling blurs toward the independent coupling and its cost rises. As $\varepsilon$ shrinks, the coupling and its cost approach the linear program. Each Sinkhorn iteration is two matrix-vector products, which run in parallel on modern hardware, and the result is a differentiable function of the masses and the costs. Because of these two properties, entropic transport can be computed at scale and used inside a training loss.

## Brenier's theorem

In more than one dimension there is no ordering to sort by, but the answer has the same structure. For the squared distance cost and a source $p_0$ with a density, Brenier's theorem states that the optimal coupling is given by a map, that this map is unique, and that it is the gradient of a convex function (Santambrogio, 2015; Peyré & Cuturi, 2018). In 1D an increasing function is the derivative of a convex function, so the quantile map $F_1^{-1} \circ F_0$ is the Brenier map of this section. In higher dimensions the theorem guarantees the map but gives no formula for it, and it has to be computed numerically.

Key references: (Peyré & Cuturi, 2018; Santambrogio, 2015; Cuturi, 2013)

## References

* Cuturi, M. (2013). *Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances*. arXiv \[stat.ML]. [DOI](https://doi.org/10.48550/arXiv.1306.0895)
* Peyré, G., Cuturi, M. (2018). *Computational Optimal Transport*. arXiv \[stat.ML]. [DOI](https://doi.org/10.48550/arXiv.1803.00567)
* Santambrogio, F. (2015). *Optimal transport for applied mathematicians – calculus of variations, PDEs and modeling*.

***

Found an error on this page? [Report an issue](https://github.com/aegean-ai/eaia-feedback/issues/new?template=page-issue.yml\&page=/aiml-common/lectures/optimal-transport/maps-and-couplings).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.