Brenier's theorem #

Let E be a finite-dimensional real inner product space, such as ℝⁿ, and consider the quadratic transport cost c (x, y) = ‖x - y‖ ^ 2 / 2. Brenier's theorem says that when the source law μ is absolutely continuous with respect to Lebesgue measure and the optimal cost is finite, the optimal transport plan is unique and is induced by the gradient of a convex function: there is a proper lower semicontinuous convex u : E → EReal, finite and differentiable μ-almost everywhere, such that x ↦ ∇ u (x) pushes μ to ν and is the unique optimal transport map.

The proof avoids Kantorovich duality. The support of an optimal plan of finite cost is c-cyclically monotone (TauCeti.IsOptimalCoupling.isCyclicallyMonotone_support), so by Rockafellar's theorem it lies in the subdifferential graph of a Legendre–Fenchel conjugate u (TauCeti.IsCyclicallyMonotone.exists_fenchelConjugate_innerₗ_subset_subdifferential). By Rademacher's theorem for convex functions (TauCeti.ae_eventually_ne_top_and_differentiableAt_toReal), u is differentiable at almost every point of its effective domain, which contains μ-almost every point because the plan has first marginal μ; there the subgradient is the gradient (TauCeti.gradient_toReal_eq_of_mem_subdifferential). So the plan is the graph plan of ∇ u. Uniqueness follows by applying this to the sum of two optimal plans, which is again optimal.

When the target ν is absolutely continuous as well, the same argument applies to the plan with exchanged coordinates, which lies in the subdifferential graph of the Legendre–Fenchel conjugate u⋆ by conjugate-subgradient reciprocity. So ∇ u⋆ is the optimal transport map from ν back to μ, and the two maps are inverse to each other almost everywhere: conjugate potentials give inverse maps.

Conversely, between finite measures with finite second moments on any real inner product space, every plan concentrated on the subdifferential graph of a function u : E → EReal is optimal, and so is every transport map selecting a subgradient of u almost everywhere, in particular the gradient of a convex function. Expanding the square, the quadratic cost of a plan is a fixed second-moment term minus its correlation ∫ ⟪x, y⟫, and on the subdifferential graph of a Legendre–Fenchel conjugate the Fenchel–Young inequality ⟪x, y⟫ ≤ u x + u⋆ y is an equality. The real representatives of u and u⋆ are integrable, being squeezed between affine functions and the correlation, so integrating Fenchel–Young against any other coupling bounds its correlation by that of the given plan. A general u is first replaced, through Rockafellar's theorem, by a conjugate whose subdifferential graph contains its own. With the forward direction this gives the Knott–Smith optimality criterion on separable spaces.

Absolute continuity is taken with respect to an arbitrary additive Haar measure ρ on E, which for E = ℝⁿ covers Lebesgue measure. The real representative x ↦ (u x).toReal is the function whose gradient is taken; where u is finite near x it agrees with u near x. The cost ‖x - y‖ ^ 2 / 2 is the normalisation of the convex-analysis bridges; its optimal plans and maps are those of ‖x - y‖ ^ 2, whose transport cost is twice as large (TauCeti.transportCost_const_mul).

Main statements #

TauCeti.IsOptimalCoupling.exists_support_subset_subdifferential — on any real inner product space, the support of an optimal quadratic plan of finite cost lies in the subdifferential graph of a proper lower semicontinuous convex function;
TauCeti.isCyclicallyMonotone_support_of_eLpNorm_eq — a coupling realizing the quadratic Wasserstein distance between laws with finite second moments has cyclically monotone support for the cost ‖x - y‖ ^ 2 / 2;
TauCeti.eq_graphPlan_gradient_of_ae_mem_subdifferential — for an absolutely continuous source, a plan concentrated on the subdifferential graph of a proper lower semicontinuous convex function is the graph plan of its gradient, differentiable almost everywhere;
TauCeti.IsOptimalCoupling.exists_eq_graphPlan_gradient — for an absolutely continuous source, an optimal quadratic plan of finite cost is the graph plan of the gradient of such a function, differentiable almost everywhere;
TauCeti.IsOptimalCoupling.exists_eq_graphPlan_of_absolutelyContinuous — the graph-plan conclusion of TauCeti.IsOptimalCoupling.exists_eq_graphPlan_gradient for the cost edist ^ 2 of the quadratic Wasserstein distance: out of an absolutely continuous source, an optimal plan to a law at finite W₂ distance is the graph plan of a measurable map;
TauCeti.map_swap_eq_graphPlan_gradient_fenchelConjugate, TauCeti.IsCoupling.gradient_fenchelConjugate_comp_gradient_ae_eq_id and TauCeti.IsCoupling.gradient_comp_gradient_fenchelConjugate_ae_eq_id — for an absolutely continuous target, the exchanged plan is the graph plan of the gradient of the conjugate potential, and the two gradients are inverse to each other almost everywhere;
TauCeti.IsOptimalCoupling.unique — for an absolutely continuous source and finite optimal cost, the optimal quadratic plan is unique;
TauCeti.gradient_ae_eq_gradient_of_hasLaw — uniqueness of the monotone rearrangement: two gradients of convex functions pushing an absolutely continuous μ to the same law agree μ-almost everywhere, when both laws have finite second moments;
TauCeti.exists_isKantorovichOptimalTransportMap_gradient — Brenier's theorem: the gradient of a convex function is the almost everywhere unique optimal transport map, and its graph plan is the unique optimal plan;
TauCeti.exists_isKantorovichOptimalTransportMap_gradient_and_gradient_fenchelConjugate — Brenier's theorem with the inverse map: when both laws are absolutely continuous, the gradients of a convex potential and of its conjugate are the optimal transport maps in the two directions, and they are inverse to each other almost everywhere;
TauCeti.exists_isKantorovichOptimalTransportMap_gradient_and_mongeAmpereMeasure_eq — when both laws are absolutely continuous, the Brenier potential u is a weak solution of its transport equation: its Monge–Ampère measure weighted by ν is μ, and ν is carried by the subgradient image of the interior of its effective domain;
TauCeti.exists_isKantorovichOptimalTransportMap_gradient_and_mongeAmpereMeasure_eq_withDensity — when the target has density g positive almost everywhere on a closed convex set K carrying it, there is a Brenier potential u with all its slopes in K, and it is an Aleksandrov solution: MA_u = (g ∘ ∇u)⁻¹ μ;
TauCeti.exists_isKantorovichOptimalTransportMap_gradient_and_rnDeriv_ae_eq — when both laws are absolutely continuous, with densities g₀ and g₁, the Brenier potential u solves the Monge–Ampère equation g₀ x = g₁ (∇ u x) det (D²u x) almost everywhere, with D²u the Alexandrov Hessian;
exists_isKantorovichOptimalTransportMap_gradient_and_rnDeriv_ae_eq_map_smul_add_smul_gradient — when only the source law is absolutely continuous, with density g₀, the interpolating maps Tₜ x = (1 - t) • x + t • ∇ u x push it, for 0 ≤ t < 1, to absolutely continuous laws with densities gₜ, and the Jacobian equation g₀ x = det ((1 - t) • 1 + t • D²u x) gₜ (Tₜ x) holds almost everywhere;
TauCeti.transportCost_norm_sub_sq_div_two_ne_top — laws with finite second moment have finite quadratic transport cost, so Brenier's theorem applies to them;
TauCeti.IsCoupling.isOptimalCoupling_of_isCyclicallyMonotone_norm_sub_sq_div_two and TauCeti.IsCoupling.isOptimalCoupling_of_ae_mem_subdifferential — for marginals with finite second moments, a plan concentrated on a cyclically monotone set, or on the subdifferential graph of any function, is optimal;
TauCeti.isKantorovichOptimalTransportMap_of_ae_mem_subdifferential and TauCeti.isKantorovichOptimalTransportMap_gradient — the converse of Brenier's theorem: a transport map selecting subgradients of a function, such as the gradient of a convex function, is an optimal transport map;
TauCeti.IsCoupling.isOptimalCoupling_iff_exists_ae_mem_subdifferential — the Knott–Smith optimality criterion: on a separable space, a plan between marginals with finite second moments is optimal exactly when it is concentrated on the subdifferential graph of a proper lower semicontinuous convex function.

References #

M. Knott and C. S. Smith, On the optimal mapping of distributions, J. Optim. Theory Appl. 43 (1984), 39--49, for the optimality criterion.
Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions, Comm. Pure Appl. Math. 44 (1991), 375--417.
C. Villani, Topics in Optimal Transportation, Graduate Studies in Mathematics 58, 2003, Theorem 2.12, whose proof of the converse direction is followed here.
R. J. McCann, Existence and uniqueness of monotone measure-preserving maps, Duke Math. J. 80 (1995), 309--323, for the route through cyclical monotonicity of the support.