TheoremProved

Brenier's theorem

Statement

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

(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.

Topics that use this theorem

Optimal transport

Step-by-step proofs

No step-by-step proof yet for this theorem.

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