Optimal Transport — Mathematics Knowledge System

Overview

Optimal transport (OT) studies the problem of moving one probability distribution to another at minimum cost. The Monge problem (1781) asks for a map T that pushes mu forward to nu minimizing integral c(x, T(x)) dmu(x). The Kantorovich relaxation (1942) formulates this as a linear program over transport plans (joint distributions). Kantorovich duality gives a dual linear program. Wasserstein distances (arising as the optimal transport cost) define a metric on the space of probability measures that is geometrically natural. OT has applications in economics, image processing, machine learning (Wasserstein GANs), and statistics.

Intuition

Imagine two sandpiles: one shaped like distribution mu, the other like nu. How do you rearrange the sand at minimum total effort (mass times distance moved)? The Monge problem seeks the optimal transport map T; the Kantorovich problem relaxes this to 'splitting' mass (a transport plan). The Wasserstein-2 distance W_2(mu, nu) is the square root of the minimum cost with cost = squared Euclidean distance. W_2 metrizes weak convergence and has beautiful geometric properties: geodesics (shortest paths) in the space of measures are displacement interpolations, used in image morphing and fluid dynamics.

Formal Definition

Definition

Kantorovich formulation: for probability measures mu on X and nu on Y with cost function c: X x Y -> R, the optimal transport cost is OT(mu,nu) = inf_{pi in Gamma(mu,nu)} integral c(x,y) dpi(x,y), where Gamma(mu,nu) = {pi in P(X x Y) : (pi_X)_* pi = mu, (pi_Y)_* pi = nu} is the set of transport plans (couplings). Kantorovich duality: OT(mu,nu) = sup_{phi in L^1(mu), psi in L^1(nu), phi(x)+psi(y)<=c(x,y)} [integral phi dmu + integral psi dnu]. For c(x,y) = |x-y|^p, the p-th Wasserstein distance is W_p(mu,nu) = OT(mu,nu)^{1/p}.

\mathrm{OT}(\mu,\nu) = \inf_{\pi \in \Gamma(\mu,\nu)} \int c(x,y)\,d\pi(x,y)

Kantorovich primal problem

\mathrm{OT}(\mu,\nu) = \sup_{\phi \oplus \psi \le c} \left[\int \phi\, d\mu + \int \psi\, d\nu\right]

Kantorovich dual problem

W_p(\mu,\nu) = \left(\inf_{\pi \in \Gamma(\mu,\nu)} \int |x-y|^p\, d\pi\right)^{1/p}

Wasserstein-p distance

T = \nabla\varphi \text{ (Brenier): optimal map for quadratic cost = gradient of convex function}

Brenier's theorem

Notation

Notation	Meaning
$\Gamma(\mu,\nu)$	Set of transport plans (couplings of mu and nu)
$W_p$	Wasserstein-p distance
$\pi$	Transport plan (joint distribution on X x Y)
$\varphi, \psi$	Kantorovich potentials (dual variables)

Theorems

Theorem 1: Kantorovich Duality

For lower semicontinuous cost c: X x Y -> [0,inf], OT(mu,nu) = sup {integral phi dmu + integral psi dnu : phi in C_b(X), psi in C_b(Y), phi(x)+psi(y) <= c(x,y) for all x,y}. The supremum is attained; the optimal phi, psi are c-conjugates of each other: psi(y) = inf_x {c(x,y) - phi(x)}. For c = |x-y|, the dual is: OT(mu,nu) = sup_{Lip-1 phi} integral phi d(mu-nu) (Kantorovich-Rubinstein formula).

Theorem 2: Brenier's Theorem

For mu, nu probability measures on R^d with mu absolutely continuous w.r.t. Lebesgue measure and cost c(x,y) = |x-y|^2/2, the optimal transport plan is unique and is induced by a map T: T = nabla varphi for some convex function varphi (a gradient of convex function). Moreover T = nabla varphi is the unique measure-preserving map with T-pushforward-mu = nu that minimizes integral |T(x)-x|^2 dmu(x).

Theorem 3: Wasserstein Geodesics (Displacement Interpolation)

For mu, nu in P_2(R^d) (measures with finite second moment) and the quadratic cost, the Wasserstein-2 geodesic (constant-speed shortest path in (P_2, W_2)) is mu_t = (T_t)*mu (pushforward) where T_t(x) = (1-t)x + t*T(x) and T = nabla varphi is the Brenier map. This is the displacement interpolation: each particle at x moves linearly from x towards T(x) at time t.

Worked Examples

1
W_1(mu,nu) = inf_{pi coupling} integral |x-y| dpi. By Kantorovich-Rubinstein: W_1 = sup_{Lip-1 phi} integral phi d(mu-nu).
$W_1(\mu,\nu) = \sup_{\|\phi\|_{\mathrm{Lip}} \le 1}\int \phi\,d(\mu-\nu)$
2
Take phi(x) = x (1-Lipschitz): integral phi dmu = 0.5*0 + 0.5*2 = 1. Integral phi dnu = 1. So phi contributes 1-1=0.
3
Take phi(x) = |x-1| (1-Lip): integral phi dmu = 0.5*1 + 0.5*1 = 1. Integral phi dnu = 0. Difference = 1.
4
So W_1(mu,nu) >= 1. The transport plan: move 0.5 mass from x=0 to y=1 (cost 0.5) and 0.5 mass from x=2 to y=1 (cost 0.5). Total = 1. So W_1 = 1.
$W_1(\mu,\nu) = 1$

✓ Answer

W_1(0.5*delta_0 + 0.5*delta_2, delta_1) = 1.

Practice Problems

Hardproof writing

Prove the Kantorovich-Rubinstein formula W_1(mu, nu) = sup_{phi 1-Lip} integral phi d(mu - nu) for measures on R.

Common Mistakes

Common Mistake

Confusing the Wasserstein distance W_p with the total variation distance.

Total variation (TV) distance: d_TV(mu,nu) = (1/2)||mu-nu||_1 (half the L^1 distance of densities). It depends only on where the measures differ, not on how far apart those regions are. Wasserstein W_1: W_1(mu,nu) is the minimum cost to move mu to nu with cost = distance. Two distant Dirac masses delta_0 and delta_1 have d_TV = 1 (maximum) and W_1 = 1 (= their distance). Nearby measures can have large TV but small W_p: W_p metrizes weak convergence, TV does not.

Quiz

Brenier's theorem states that for absolutely continuous mu and quadratic cost, the optimal transport map T:

Is always a linear mapIs the gradient of a convex functionIs the identity map if mu = nuMinimizes the total variation ||mu - nu||

Historical Background

Gaspard Monge posed the original earth-moving problem in 1781. Leonid Kantorovich reformulated it as a linear programming problem in 1942, earning him the Nobel Prize in Economics (1975). The Wasserstein distance was studied in the Russian literature (Vasershtein, 1969) and by Dobrushin. The field was revolutionized by Brenier's theorem (1987) characterizing OT maps as gradients of convex functions. Villani's 2003 and 2008 monographs, and his Fields Medal (2010), brought OT to the mathematical mainstream. Cuturi's Sinkhorn algorithm (2013) made OT computationally tractable for machine learning.

1781
Monge poses the earth-moving problem
Gaspard Monge
1942
Kantorovich reformulates as linear programming, introduces duality
Leonid Kantorovich
1987
Brenier's theorem: OT map = gradient of convex function (for quadratic cost)
Yann Brenier
2013
Cuturi introduces entropic regularization and Sinkhorn algorithm for fast OT
Marco Cuturi

Summary

OT: move distribution mu to nu at minimum cost. Kantorovich: linear program over transport plans Gamma(mu,nu).
Kantorovich duality: OT = sup of dual linear program with potentials phi, psi.
Wasserstein-p distance: W_p = OT^{1/p} with cost |x-y|^p. Metrizes weak convergence.
Brenier: for quadratic cost and absolutely continuous mu, optimal map = gradient of convex function.

References

BookVillani, C. Optimal Transport: Old and New. Springer, 2009.
BookSantambrogio, F. Optimal Transport for Applied Mathematicians. Birkhauser, 2015.
WebsiteWikipedia -- Transportation theory (mathematics)