Applied and computational mathematics

Optimal transport

Finding the cheapest way to reshape one distribution of mass into another — from moving piles of sand to comparing images, probability distributions, and populations of cells.

IntuitionMoving a pile of sand into a hole at the least possible cost

Imagine a big pile of sand of some shape, and a hole in the ground of the exact same total volume but a different shape. You want to move every grain of sand into the hole using as little total effort as possible, where moving one grain a distance $d$ costs $d$ units of work — grains that travel farther cost more to move. This is the optimal transport problem: given a source distribution of mass and a target distribution with the same total mass, find the cheapest way to rearrange one into the other.

It sounds like a purely physical puzzle about sand, but the same question — matching one distribution of stuff to another at the least cost — shows up whenever you compare two probability distributions, two images, two economic supply-and-demand profiles, or two shapes. Optimal transport measures exactly how different two distributions are, and tells you exactly how to morph one into the other.

Example: A minimal example: two piles, two holes

Suppose you have one unit of sand at position $x=0$ and another unit at $x=10$ , and two unit-sized holes at $y=1$ and $y=9$ . Moving a unit of sand a distance $d$ costs $d$ . There are only two ways to match piles to holes: send $0\to1$ and $10\to9$ , or send $0\to9$ and $10\to1$ . Which matching is cheaper, and what is the minimum total cost?

Solution

The direct (non-crossing) matching costs $|0-1|+|10-9|=1+1=2$ . The crossing matching costs $|0-9|+|10-1|=9+9=18$ . So the cheapest choice sends each pile to the nearer hole without the paths crossing, for a minimum total cost of $2$ . This is already a seed of a general fact used later: for cost $|x-y|$ on the real line, an optimal transport plan is always order-preserving — it never routes two units of mass along crossing paths.

This bell-shaped standard normal curve

\mathcal N(0,1)

is only a stand-in for "a typical smooth density" — it is not itself a transport plan. Imagine it as either the source or the target density in an optimal transport problem: the theory below finds the cheapest way to reshape a curve like this one into a different target density.

UndergraduateMonge's map and Kantorovich's relaxation

In 1781, the French mathematician and military engineer Gaspard Monge posed the problem precisely: given a source measure $\mu$ on a space $X$ and a target measure $\nu$ on a space $Y$ with the same total mass, and a cost function $c(x,y)$ giving the price of moving one unit of mass from $x$ to $y$ , find a map $T:X\to Y$ that **pushes $\mu$ forward to $\nu$ ** — written $T_{\#}\mu=\nu$ , meaning $T_{\#}\mu(A) = \mu(T^{-1}(A))$ for every measurable set $A$ — while minimizing the total transport cost:

\inf_{T:\ T_{\#}\mu = \nu} \int_X c(x, T(x))\, d\mu(x)

Monge's original formulation frequently has no solution at all. The starkest example: let $\mu=\delta_0$ be a single point mass at the origin, and let $\nu=\frac12\delta_{-1}+\frac12\delta_{1}$ split its mass between two points. Any map $T$ must send $0$ to a single point $T(0)$ , so $T_{\#}\mu$ is again a point mass — it can never equal $\nu$ , no matter how $T$ is chosen. Monge's problem is infeasible here even though a perfectly sensible way to move the mass obviously exists: split it, half going left and half going right. A deterministic map simply cannot split mass.

Definition: Transport plans and couplings

Given $\mu\in\mathcal P(X)$ and $\nu\in\mathcal P(Y)$ , a transport plan (or coupling) is a probability measure $\gamma$ on $X\times Y$ whose two marginals recover $\mu$ and $\nu$ : $\Pi(\mu,\nu) = \{\gamma \in \mathcal{P}(X\times Y) : (\pi_X)_{\#}\gamma = \mu,\ (\pi_Y)_{\#}\gamma = \nu\}.$ Interpret $\gamma$ as "how much mass moves from near $x$ to near $y$ ": a deterministic map $T$ corresponds to the special coupling $\gamma=(\mathrm{id},T)_{\#}\mu$ , but a general $\gamma$ is also allowed to send a single point of mass to several destinations at once. The independent product $\mu\otimes\nu$ always lies in $\Pi(\mu,\nu)$ , so — unlike the set of Monge maps — this set is never empty.

\inf_{\gamma \in \Pi(\mu,\nu)} \int_{X \times Y} c(x,y)\, d\gamma(x,y)

Theorem: Kantorovich duality theorem

For probability measures $\mu$ on $X$ , $\nu$ on $Y$ (Polish spaces) and a continuous, bounded-below cost $c$ , the Kantorovich problem is equal to a dual maximization over pairs of Kantorovich potentials $\varphi:X\to\mathbb R$ , $\psi:Y\to\mathbb R$ satisfying $\varphi(x) + \psi(y) \le c(x,y)$ pointwise: $\min_{\gamma\in\Pi(\mu,\nu)}\int_{X\times Y} c\,d\gamma \;=\; \sup_{\varphi(x)+\psi(y)\le c(x,y)}\left(\int_X\varphi\,d\mu+\int_Y\psi\,d\nu\right),$ and both the minimum and the supremum are attained.

Why is it true?

Think of $\varphi(x)$ as a price charged for picking up mass at $x$ and $\psi(y)$ as a price paid for dropping it off at $y$ , in a decentralized market of independent shippers. No shipper can profitably undercut the direct route: buying at $\varphi(x)$ and selling at $\psi(y)$ can never beat physically moving the mass and paying $c(x,y)$ — exactly the constraint $\varphi(x)+\psi(y)\le c(x,y)$ . In a market that clears optimally, equality $\varphi(x)+\psi(y)=c(x,y)$ holds exactly along the routes actually used by an optimal plan.

Proof

For finite discrete measures $\mu=\sum_i p_i\delta_{x_i}$ , $\nu=\sum_j q_j\delta_{y_j}$ , the Kantorovich problem is the finite linear program $\min \sum_{i,j} c_{ij}\gamma_{ij}$ subject to $\gamma_{ij}\ge0$ , $\sum_j\gamma_{ij}=p_i$ , $\sum_i\gamma_{ij}=q_j$ . Its LP dual is exactly $\max \sum_i p_i\varphi_i+\sum_j q_j\psi_j$ subject to $\varphi_i+\psi_j\le c_{ij}$ for all $i,j$ — one dual variable per primal (marginal) constraint. The primal is feasible (the product coupling $p_iq_j$ always works) and bounded below by $0$ , and the feasible polytope $\{\gamma_{ij}\ge0\}\cap\Pi(\mu,\nu)$ is compact, so strong linear-programming duality gives equality of the two optimal values, with both attained. This proves the theorem exactly in the discrete case; the general statement on Polish spaces follows from the same primal-dual pattern applied via Fenchel–Rockafellar duality to convex functionals on $C_b(X\times Y)$ (Kantorovich 1942; see Villani 2009, Theorem 5.10, for the full argument).

The proof above for finite measures is a direct application of linear-programming duality — exactly the primal-dual machinery from convex optimization: the transport plan $\gamma$ is the primal variable, the potentials $\varphi,\psi$ are the dual (Lagrange) variables attached to the marginal constraints, and strong duality holds because $\Pi(\mu,\nu)$ is compact and convex. This is the first of two genuine bridges from optimal transport to its neighboring fields: measure theory supplies the language ( $\mu,\nu,\gamma$ as measures, pushforwards, marginals), and convex duality supplies the proof technique.

AdvancedBrenier's theorem and the geometry of Wasserstein space

Theorem: Brenier's theorem

Let $\mu,\nu$ be probability measures on $\mathbb R^n$ with finite second moments, and suppose $\mu$ is absolutely continuous with respect to Lebesgue measure. For the quadratic cost $c(x,y) = |x-y|^2$ there exists a convex function $\varphi:\mathbb R^n\to\mathbb R$ , unique up to an additive constant, such that $T = \nabla \varphi$ is well-defined $\mu$ -almost everywhere, satisfies $T_{\#}\mu=\nu$ , and is the (essentially) unique minimizer of both the Kantorovich problem and Monge's original problem.

Why is it true?

Any optimal plan for a strictly convex cost like $|x-y|^2$ is supported on a ** $c$ -cyclically monotone** set: no finite re-matching of pairs can lower the total cost. For the quadratic cost, cyclical monotonicity of a set of pairs $(x_i,y_i)$ turns out to be exactly the condition that some convex function $\varphi$ has $y_i$ in its subdifferential at $x_i$ for every $i$ — this is Rockafellar's theorem characterizing cyclically monotone sets as subdifferentials of convex functions. Since $\mu$ is absolutely continuous, a convex function is differentiable $\mu$ -almost everywhere (Alexandrov's theorem), turning the set-valued subdifferential into a genuine gradient map $T=\nabla\varphi$ .

Proof

(Sketch, following Brenier 1991.) Step 1: Kantorovich duality for $c=|x-y|^2$ lets one rewrite the optimal potentials via $\varphi(x)=\tfrac12|x|^2-\tilde\varphi(x)$ so that $\varphi$ is convex and its Legendre transform $\varphi^*(y)=\sup_x(x\cdot y-\varphi(x))$ plays the role of the second potential; the dual constraint becomes exactly $y\in\partial\varphi(x)$ on the support of an optimal $\gamma$ . Step 2: Rockafellar's theorem states that every cyclically monotone subset of $\mathbb R^n\times\mathbb R^n$ is contained in the graph of $\partial\varphi$ for some convex lower semicontinuous $\varphi$ ; the support of an optimal plan is cyclically monotone because $\gamma$ minimizes $\int|x-y|^2\,d\gamma$ , so no finite re-matching among finitely many pairs on the support can strictly decrease $\sum_i|x_i-y_i|^2$ . Step 3: because $\mu\ll$ Lebesgue, $\varphi$ is differentiable $\mu$ -almost everywhere by Alexandrov's theorem, so $\gamma$ is concentrated on the graph $\{(x,\nabla\varphi(x))\}$ , i.e. $\gamma=(\mathrm{id},\nabla\varphi)_{\#}\mu$ . This exhibits a deterministic optimal map $T=\nabla\varphi$ , so it also solves Monge's problem, and any other optimal map must agree with it $\mu$ -almost everywhere by strict convexity of the cost.

Once the cost is fixed to $|x-y|^2$ , the minimal transport cost itself becomes a genuine distance between probability measures — the 2-Wasserstein distance $W_2$ . The space $\mathcal P_2(\mathbb R^n)$ of probability measures with finite second moment, equipped with $W_2$ , behaves remarkably like a genuine infinite-dimensional Riemannian manifold: Felix Otto's heuristic — now called Otto calculus — treats a tangent vector at $\mu$ as a velocity field $v$ solving the continuity equation $\partial_t\mu+\nabla\!\cdot(\mu v)=0$ , with Riemannian metric $\langle v,w\rangle_\mu=\int v\cdot w\,d\mu$ . Geodesics in this formal Riemannian structure are exactly the constant-speed paths $\mu_t=((1-t)\,\mathrm{id}+t\,T)_{\#}\mu$ built from the very Brenier map $T=\nabla\varphi$ above. This formal Riemannian structure on the space of measures is the second, genuine bridge — this time from optimal transport to Riemannian geometry.

W_2(\mu,\nu)^2 = \min_{\gamma \in \Pi(\mu,\nu)} \int |x-y|^2\, d\gamma(x,y)

Example: Explicit optimal transport between two centered Gaussians

Let $\mu=\mathcal N(0,1)$ and $\nu=\mathcal N(0,2.25)$ be centered one-dimensional Gaussians with standard deviations $\sigma_1=1$ and $\sigma_2=1.5$ . Use Brenier's theorem to write down the optimal transport map $T$ pushing $\mu$ forward to $\nu$ for the quadratic cost, and compute $W_2(\mu,\nu)$ .

Solution

Both measures are centered, so the general 1D Gaussian optimal-transport map $T(x) = m_2 + \frac{\sigma_2}{\sigma_1}(x - m_1)$ reduces to the pure scalar rescaling $T(x)=\frac{\sigma_2}{\sigma_1}x=1.5x$ . This is indeed the gradient of the convex quadratic $\varphi(x)=0.75x^2$ , since $\varphi'(x)=1.5x=T(x)$ , confirming Brenier's theorem. One can check directly that $T$ pushes $\mu$ forward to $\nu$ : if $X\sim\mathcal N(0,1)$ then $1.5X\sim\mathcal N(0,1.5^2)=\mathcal N(0,2.25)=\nu$ . The transport cost is $\int(T(x)-x)^2\,d\mu(x)=\int(0.5x)^2\,d\mu(x)=0.25\cdot\mathrm{Var}(X)=0.25$ , so $W_2(\mu,\nu)=\sqrt{0.25}=0.5=\sigma_2-\sigma_1$ , matching the general Gaussian formula with equal means.

This widget natively draws a general 2D linear map

(x,y)\mapsto(ax+by,cx+dy)

. Here it is set to the purely diagonal, equal-scale case

a=d=1.5

b=c=0

, used as a visual analogy (applying the same scalar factor to both axes) for the explicit 1D Brenier map

T(x)=1.5x

from the worked example above: by Brenier's theorem, moving the centered Gaussian

\mathcal N(0,1)

to the wider centered Gaussian

\mathcal N(0,2.25)

is achieved, for the quadratic cost, by the pure scalar dilation

T(x)=1.5x

— the gradient of the convex function

\varphi(x)=0.75x^2

. Try setting

a\ne d

b,c\ne0

to see maps that are no longer valid transport maps between isotropic Gaussians.

Historical note

Gaspard Monge (1746–1818), a French mathematician and military engineer under Napoleon (and a founder of the École Polytechnique), first posed the transport problem in his 1781 memoir Mémoire sur la théorie des déblais et des remblais ("On the theory of cuttings and fillings") — literally about moving excavated earth to a construction site at minimal cost. The problem then lay largely dormant for over a century. Leonid Kantorovich (1912–1986), a Soviet mathematician, rediscovered and radically generalized it in 1942 while developing linear programming for Soviet economic planning; his relaxation to transport plans made the problem convex and tractable, and he shared the 1975 Nobel Memorial Prize in Economic Sciences (with Tjalling Koopmans) for this and related work on the optimal allocation of resources. Yann Brenier proved his gradient/polar-factorization theorem in 1991, revealing the deep link between optimal transport, convex analysis, and the Monge–Ampère equation. Cédric Villani received the 2010 Fields Medal, with the official citation highlighting his proofs of nonlinear Landau damping and convergence to equilibrium for the Boltzmann equation — results built on techniques from optimal transport theory that Villani himself had developed and systematized in two influential textbooks, cementing the subject as a central tool of modern analysis and geometry.

ResearchDisplacement convexity, curvature, and transport at scale

A geodesic $\mu_t$ in the Wasserstein space $(\mathcal P_2(\mathbb R^n),W_2)$ is called a displacement interpolation; a functional $F$ on measures (such as the entropy $\int\rho\log\rho$ for $\mu=\rho\,dx$ ) is displacement convex if $t\mapsto F(\mu_t)$ is convex along every such geodesic. Around 2006–2009, John Lott and Cédric Villani, and independently Karl-Theodor Sturm, used the displacement convexity of entropy along $W_2$ -geodesics to define a synthetic (curvature-dimension) lower bound on Ricci curvature — the $\mathrm{CD}(K,N)$ condition — for completely general metric-measure spaces, with no smooth manifold structure required. Remarkably, these curvature-dimension bounds are stable under Gromov–Hausdorff limits, letting geometers make sense of "curved" spaces that arise as limits of Riemannian manifolds, or spaces (graphs, fractals, singular spaces) that were never smooth to begin with.

A very different, thoroughly contemporary application: in 2017 Martin Arjovsky, Soumith Chintala, and Léon Bottou proposed the Wasserstein GAN, replacing the Jensen–Shannon divergence used to train classical generative adversarial networks with the (dual, Kantorovich–Rubinstein form of the) Wasserstein-1 distance between the real and generated data distributions. Because $W_1$ stays well-behaved and gives useful gradients even when two distributions have disjoint support — unlike the Jensen–Shannon divergence, which saturates — WGAN training is markedly more stable and far less prone to mode collapse, and the technique remains a standard building block of modern generative modeling.

Research frontier as of 2026

Where the subject stands (as of 2026).

1. Entropic regularization and the Sinkhorn algorithm. Solving the Kantorovich linear program exactly does not scale: for $n$ points on each side it costs roughly $O(n^3\log n)$ . In 2013 Marco Cuturi added an entropy penalty to the Kantorovich objective, $\min_{\gamma\in\Pi(\mu,\nu)}\int c\,d\gamma-\varepsilon H(\gamma)$ , whose unique minimizer takes the simple form $\gamma=\mathrm{diag}(u)K\mathrm{diag}(v)$ with $K=e^{-c/\varepsilon}$ , computable by the classical Sinkhorn–Knopp matrix-scaling algorithm in $O(n^2)$ time per iteration, trivially parallelizable on GPUs. This turned optimal transport from a theoretical tool into a practical, differentiable building block now used routinely throughout machine learning. 2. Unbalanced optimal transport. Real data rarely carries exactly equal total mass on both sides (a population of cells that is growing or dying, for instance). Unbalanced optimal transport relaxes the hard marginal constraints $\gamma\in\Pi(\mu,\nu)$ to soft divergence penalties (Wasserstein–Fisher–Rao / Hellinger–Kantorovich distances), letting mass be created or destroyed at a cost. 3. Single-cell biology and generative AI. This unbalanced, entropy-regularized machinery is now central to computational biology: frameworks such as Moscot, reported in Nature in 2025, use unbalanced, entropic optimal transport to match millions of single cells across time points, spatial locations, and molecular modalities while correctly accounting for cell birth and death — reconstructing developmental trajectories that naive equal-mass matching would get wrong. On the generative-modeling side, 2024–2026 work combines unbalanced transport with flow matching to train simulation-free neural models of complex, growing or shrinking populations, extending the line opened by the 2017 Wasserstein GAN.

Why does Monge's original formulation of optimal transport sometimes have no solution at all, while Kantorovich's relaxation always has a minimizer (under mild conditions)?

By Brenier's theorem, for the quadratic cost $c(x,y)=|x-y|^2$ and an absolutely continuous source measure $\mu$ on $\mathbb R^n$ , what form does the optimal transport map $T$ take (almost everywhere)?

In the Kantorovich duality theorem, what constraint links the two Kantorovich potentials $\varphi$ and $\psi$ in the dual problem?

Why did Cuturi's 2013 entropic regularization (leading to the Sinkhorn algorithm) transform computational optimal transport in machine learning?

References

Cédric Villani (2009). Optimal Transport: Old and New
Marco Cuturi (2013). Sinkhorn Distances: Lightspeed Computation of Optimal Transport · arXiv:1306.0895
Yann Brenier (1991). Polar Factorization and Monotone Rearrangement of Vector-Valued Functions · DOI:10.1002/cpa.3160440402
John Lott, Cédric Villani (2009). Ricci Curvature for Metric-Measure Spaces via Optimal Transport