PaperlayerView exact revision on arXiv

Source-linked AI summary

Computational Optimal Transport

Gabriel Peyré, Marco Cuturi

arXiv:1803.00567v4stat.ML

TL;DR

Optimal transport compares distributions by finding low-cost ways to move mass, but naive assignment formulations become computationally intractable as problem size grows. This book reviews numerical OT methods, especially entropic regularization, and explains theoretical results and applications that support scalable computation in data sciences.

  • Problem

    Naively optimizing transport over all permutations is infeasible because their number grows factorially, motivating efficient optimization algorithms.

  • Method

    The book synthesizes OT theory, numerical methods, and applications, emphasizing entropic regularization and its matrix-vector-based optimization schemes.

  • Results

    With a density in one input measure and quadratic Euclidean cost, the optimal transport plan is unique and supported on a Monge map.

  • Takeaways & Limitations

    Entropic regularization provides simple iterative computations that are particularly suited to GPU execution and large-scale data-science applications.

  • Takeaways & Limitations

    Sinkhorn iterations can become numerically unstable when kernel entries underflow to zero, causing division-by-zero updates.

Abstract

from arXiv · show

Optimal transport (OT) theory can be informally described using the words of the French mathematician Gaspard Monge (1746-1818): A worker with a shovel in hand has to move a large pile of sand lying on a construction site. The goal of the worker is to erect with all that sand a target pile with a prescribed shape (for example, that of a giant sand castle). Naturally, the worker wishes to minimize her total effort, quantified for instance as the total distance or time spent carrying shovelfuls of sand. Mathematicians interested in OT cast that problem as that of comparing two probability distributions, two different piles of sand of the same volume. They consider all of the many possible ways to morph, transport or reshape the first pile into the second, and associate a "global" cost to every such transport, using the "local" consideration of how much it costs to move a grain of sand from one place to another. Recent years have witnessed the spread of OT in several fields, thanks to the emergence of approximate solvers that can scale to sizes and dimensions that are relevant to data sciences. Thanks to this newfound scalability, OT is being increasingly used to unlock various problems in imaging sciences (such as color or texture processing), computer vision and graphics (for shape manipulation) or machine learning (for regression, classification and density fitting). This short book reviews OT with a bias toward numerical methods and their applications in data sciences, and sheds lights on the theoretical properties of OT that make it particularly useful for some of these applications.

Introduction

Optimal transport extends the shortest-path principle of minimizing effort when sending an item from one point to another. In simple spaces, least-effort movement follows straight lines, while more involved metric spaces use geodesic curves.

  • The shortest-path principle favors the least possible effort when sending a commodity, person, or bit of information to a target point.
  • In the plane, least-effort movement typically follows a straight line.
  • In more involved metric spaces, least-effort movement follows geodesic curves.
  • Optimal transport generalizes this shortest-path intuition beyond moving only one item.

4 Introduction

Optimal transport provides an abstract framework for comparing distributions represented as bags of features or descriptors, and has become an applied tool with an active computational research field. The survey therefore leaves several topics uncovered while building on an extensive reference literature.

  • Optimal transport offers tools for comparing distributions represented as bags of features or descriptors.
  • The theory’s formal and abstract concepts have motivated several reference books, including monographs by Villani, Rachev and Rüschendorf, and Santambrogio.
  • Computational optimal transport remains highly active, so the survey does not cover a wide variety of topics, including distributionally robust optimization and some low-dimensional Monge–Ampère methods.

Theoretical Foundations

The section develops optimal transport from discrete matchings and histogram couplings to transport between arbitrary measures, emphasizing efficient optimization, relaxation tightness, and structural properties of optimal maps. It also characterizes Wasserstein geometry while noting limitations in image registration and regularity analysis.

  • Optimal transport is introduced progressively from probability-vector matchings and couplings to discrete measures and arbitrary measures.Computations between histograms provide the basic entry point for implementation.
  • The permutation formulation is computationally prohibitive because Perm(n) contains n! possibilities, exceeding 10^100 when n=70.Efficient algorithms are therefore required to optimize transport costs over permutations.
  • Optimal transport requires caution for image registration because push-forward densities include a Jacobian and therefore do not directly describe image warping.The associated Monge–Ampère analysis is also difficult because solutions need not be smooth in full generality.
  • For equal uniform marginals, Kantorovich’s relaxation is tight: an optimal transport plan can be chosen as a permutation matrix.This establishes equivalence between the assignment formulation and its Kantorovich relaxation in the discrete case.
  • The Wp Wasserstein distance is symmetric, separates measures, and satisfies the triangle inequality; in one dimension, its geometry is equivalent to an Lp space.Locally, one-dimensional transport reduces to the ℓp norm between ordered value vectors.
  • Under quadratic cost on R^d, if one input measure has a density, the optimal Kantorovich plan is unique and induced by a Monge map.The map is uniquely represented as T(x) = ∇ϕ(x), where ϕ is convex and pushes α forward to β.

Algorithmic Foundations

Optimal transport is formulated as a linear program whose primal and dual forms support complementary-slackness optimality conditions and specialized combinatorial algorithms. The chapter develops network simplex, dual ascent, and auction methods, including iteration, complexity, and approximation guarantees for the latter.

  • Linear-program formulation: OT fits linear programming because its objective and constraints are linear, while its discrete structure motivates specialized combinatorial optimization methods.The chapter presents tools for solving the discrete OT formulation through primal or dual linear programs.
  • Linear-program formulation: The primal OT problem becomes a standard-form linear program by vectorizing the transport matrix and encoding row- and column-sum constraints with a matrix.The formulation uses an (n + m) × nm constraint matrix and a cost vector formed by stacking columns of the cost matrix.
  • Primal-dual optimality: Complementary feasible primal and dual solutions are both optimal: positive transport occurs only where the corresponding reduced cost is zero.If Ci,j > fi + gj, complementary slackness forces Pi,j = 0.
  • Network simplex: The network simplex algorithm starts from an extremal transport solution, computes complementary dual variables, and pivots along violating edges until no dual constraint is violated.When a cycle is created, the transport plan is updated without increasing cost.
  • Auction and dual ascent methods: The auction algorithm maintains ε-complementary slackness, takes at most N = n∥C∥∞/ε steps, and returns an assignment whose cost is nε suboptimal.Its naive termination cost is N3∥C∥∞/ε operations, reducible to N3 log ∥C∥∞ with ε-scaling.

Entropic Regularization of Optimal Transport … 4.1. Entropic Regularization

Entropic regularization approximates Kantorovich optimal transport by adding an entropy-based penalty, yielding a unique solution and simple numerical schemes. As ε varies, the regularized coupling interpolates between maximum-entropy optimal transport and independence, while extending naturally through relative entropy and Schrödinger formulations.

  • Entropic Regularization of Optimal Transport: Entropic regularization adds −H to the Kantorovich objective, producing approximate transport solutions whose minimization admits a simple alternating scheme.The chapter presents this family of numerical schemes as useful for optimal transport and its generalizations.
  • 4.1. Entropic Regularization: The ε-regularized objective is ε-strongly convex, so its transport problem has a unique optimal coupling.The entropy term also pushes solutions away from sparse boundary points toward an entropic center.
  • 4.1. Entropic Regularization: As ε → 0, the unique regularized coupling converges to the maximum-entropy solution among all optimal Kantorovich transport couplings.Entropy selects one optimal coupling when the unregularized problem has multiple solutions.
  • 4.1. Entropic Regularization: As ε → +∞, the regularized coupling converges to a ⊗ b, the maximal-entropy coupling whose marginals are independent.Thus large regularization favors the product coupling rather than the sparse routes typical of unregularized transport.
  • 4.1. Entropic Regularization: The relative-entropy formulation is a projection onto a Gibbs distribution and is known as the static Schrödinger problem.As ε → 0, its unique solution converges to the maximum-entropy optimal transport solution.
  • 4.1. Entropic Regularization: For arbitrary measures, discrete entropy is replaced by relative entropy KL(π|α ⊗ β), whose resulting solution depends on the reference measures only through their support.Replacing α, β by measures with the same zero-measure sets gives the same solution.
  • 4.1. Entropic Regularization: Equivalently, the regularization penalizes mutual information, which is nonnegative and vanishes exactly when the transported variables are independent.For generic measures, the coupling tends to α ⊗ β as ε → +∞ and to an optimal transport coupling as ε → 0.
  • 4.1. Entropic Regularization: Entropic regularization generates copulas interpolating between independence, ξπ+∞(s, t) = st, and full dependence, ξπ0(s, t) = min(s, t).These correspond respectively to the product coupling and a fully dependent optimal coupling.

4.2 Sinkhorn’s Algorithm and Its Convergence

Sinkhorn’s algorithm solves entropically regularized optimal transport by alternately scaling a Gibbs kernel to satisfy the marginal constraints. Its iterations converge linearly, provide scalable approximate solutions, and face slower convergence and numerical instability as ε decreases.

  • Matrix scaling: Sinkhorn alternately updates scaling vectors u and v so that P = diag(u)K diag(v) satisfies the prescribed marginal constraints.The updates are initialized with an arbitrary positive vector, commonly v^(0) = 1_m, and scaling vectors are defined up to a multiplicative constant.
  • Applications: The method is efficient and scalable through parallelization, defines a differentiable loss, and supports extensions for machine learning, vision, graphics, and imaging.When the unregularized solution is supported on a Monge map, positive ε provides a smooth approximation useful for imaging and principal geodesics.
  • Numerical stability: Sinkhorn can fail to terminate when entries of the Gibbs kernel K become too negligible for positive numerical storage, causing matrix products to degenerate.This numerical issue can obscure the slowdown theoretically associated with ε approaching zero.
  • Convergence: Linear convergence holds for the matrix iterates in the Hilbert metric, while the constraint-violation rate degrades as ε → 0.The convergence factor is λ(K)^ℓ in the stated Hilbert-metric bound.

4.3. Speeding Up Sinkhorn’s Iterations

The local convergence of Sinkhorn’s iterations is governed by the second eigenvalue of a positive Jacobian, since the dominant eigenvalue 1 reflects the additive-constant ambiguity in f. In simple cases, the convergence parameter scales as κ ∼ ε.

  • Local convergence rate: The Jacobian is positive and has dominant eigenvector 1_m with eigenvalue 1 by the Perron–Frobenius theorem.Its row-sum property is ∂Φ(f)1_n = 1_n.
  • Local convergence rate: Because f is defined up to a constant, the second eigenvalue 1 − κ < 1 governs the local linear rate for sufficiently large ℓ.The dominant eigenvalue corresponds to the additive-constant freedom in f.
  • Scaling in simple cases: In numerically examined simple cases, including a smooth Monge map when ε = 0, the rate parameter scales like κ ∼ ε.The bistochastic assignment case is cited for further details.

4.3 Speeding Up Sinkhorn’s Iterations

Sinkhorn iterations are bottlenecked by kernel matrix-vector products, but parallel execution and separable kernels can substantially accelerate computation. In the separable case, exact kernel applications reduce quadratic complexity to O(n^(1+1/d)) when n = m.

  • Naive Sinkhorn iterations are bottlenecked by vector-matrix products with K and K⊤, each requiring O(nm) computation.
  • Sinkhorn iterations are GPU friendly, while matrix-matrix operations enable greater parallelism for computing many OT distances at large scale.The basic method uses matrix-vector products; batching histogram pairs yields matrix-matrix operations with stronger parallelism.
  • When costs are additive across d sub-indices, the Sinkhorn kernel becomes multiplicatively separable and supports exact fast evaluation of Ku.The separable structure avoids explicitly instantiating the full n × n kernel matrix.
  • O(n1+1/d) replaces O(n2) per iteration for separable kernels when n = m.The speed-up applies when n = Q k nk, which is typically exponential in dimension d.
  • On a regular grid over [0, 1]d with q-norm-based ground cost, multiplication by K can use separate one-dimensional nk × nk convolution matrices.

4.3. Speeding Up Sinkhorn’s Iterations

Sinkhorn iterations can be accelerated by exploiting separable or structured kernels, reducing multiplications to efficient convolutions and enabling large-grid computations. On manifolds, heat-kernel approximations and extrapolation schemes further reduce iteration cost or improve local convergence rates.

  • Separable convolutions: Separable kernels reduce Sinkhorn’s kernel multiplications to repeated 1-D convolutions that are extremely efficient on GPUs.For larger dimensions, the same 1-D convolutions are applied to tensor slices of the reshaped multiplier.
  • Structured and manifold kernels: Translation-invariant kernels on uniform Euclidean grids turn multiplication by K into convolution, while manifold kernels can be approximated using Laplacian or heat kernels.The manifold approximations rely on discretizing the Laplace–Beltrami operator, for example with a cotangent Laplacian.
  • Structured and manifold kernels: For 2-D manifolds, sparse Cholesky factorization and matrix reordering make each Sinkhorn iteration linear-complexity under the Laplacian-based approximation.The approach requires repeated resolutions of positive symmetric linear systems, which can be accelerated by precomputation.
  • Extrapolation acceleration: Extrapolation accelerates the local linear convergence rate from O((1 − κ)^ℓ) to O((1 − √κ)^ℓ).The method applies linear or nonlinear extrapolation to the Sinkhorn fixed-point mapping near the solution.

4.4. Stability and Log-Domain Computations · 4.4 Stability and Log-Domain Computations · 4.4. Stability and Log-Domain Computations

The section explains how log-domain formulations stabilize Sinkhorn computations when ε is small, while revealing Sinkhorn as block coordinate ascent on the entropic dual. These formulations are mathematically equivalent to standard updates but trade numerical stability for higher computational cost and limited parallelization.

  • 4.4 Stability and Log-Domain Computations: Small ε can cause numerical overflow in Sinkhorn computations, motivating log-domain calculations that arise naturally from the associated dual problem.The dual formulation provides the basis for analyzing stabilized iterations.
  • 4.4 Stability and Log-Domain Computations: Sinkhorn iterations are mathematically equivalent to exact block coordinate ascent on the unconstrained entropic dual problem.Alternating updates of the dual variables cancel the respective objective gradients and recover the primal scaling iterations.
  • 4.4 Stability and Log-Domain Computations: The dual updates admit a soft-min interpretation, with minε providing a differentiable approximation that converges to min as ε →0.The same notation rewrites Sinkhorn updates and connects them to entropic c-transforms.
  • 4.4 Stability and Log-Domain Computations: Although minε converges to min as ε →0, the alternating iterations themselves fail to converge at ε = 0 for the unregularized constrained dual.The limiting soft-min operation therefore does not imply convergence of the corresponding iterations.
  • 4.4 Stability and Log-Domain Computations: Log-sum-exp stabilization avoids underflow for small ε, and subtracting previously computed scalings yields an alternative stabilized iteration.Both approaches preserve mathematical equivalence with the original Sinkhorn updates.
  • 4.4 Stability and Log-Domain Computations: The stabilized log-domain iterations are stable for arbitrary ε > 0 because S(f, g) remains bounded, but each step requires nm exponential computations.The stability improvement therefore carries a substantial per-iteration computational cost.
  • 4.4 Stability and Log-Domain Computations: Soft-min computations are typically slower than matrix multiplications, require line-by-line processing, and prevent efficient parallel application of Sinkhorn maps across several marginals.In low-dimensional Euclidean domains, multiscale solvers with decaying ε and sparse grids can significantly accelerate computation.
  • 4.4 Stability and Log-Domain Computations: An unconstrained dual formulation is better conditioned because its functional Hessian is uniformly bounded by ε, though the alternative formulation has disadvantages.Semidual problems provide another route to improved conditioning.

4.5 Regularized Approximations of the Optimal Transport Cost · 4.5. Regularized Approximations of the Optimal Transport Cost

The section develops entropic and finite-step Sinkhorn approximations to optimal transport, emphasizing convexity, differentiability, bounds, and practical limitations caused by incomplete convergence and primal infeasibility.

  • 4.5 Regularized Approximations of the Optimal Transport Cost: The entropic dual is a smooth, unconstrained concave maximization problem approximating the original Kantorovich dual.Its optimal solutions are feasible Kantorovich potentials.
  • 4.5. Regularized Approximations of the Optimal Transport Cost: The regularized cost C(a, b) is jointly convex in a and b for ε ≥0 and smooth, making it suitable as a loss function in variational problems.For ε > 0, its gradient is expressed using optimal dual solutions normalized so their coordinates sum to 0.
  • 4.5. Regularized Approximations of the Optimal Transport Cost: Sinkhorn divergences approximate the Wasserstein distance by evaluating primal and dual objectives at solutions produced by the Sinkhorn algorithm.The associated relationships rely on equality of primal and dual optimal values and normalization of the optimal transport plan.
  • 4.5. Regularized Approximations of the Optimal Transport Cost: The theoretical bounds are useful only at Sinkhorn convergence, whereas finite iteration counts require an algorithmic Sinkhorn functional.This finite-step functional lower bounds the regularized cost as soon as L ≥1.
  • 4.5. Regularized Approximations of the Optimal Transport Cost: Sinkhorn primal iterates are not primal feasible before convergence, so their transport cost cannot directly approximate the regularized cost.A rounding scheme can instead provide an upper bound, computable with parallel matrix operations for multiple histogram pairs.
  • 4.5. Regularized Approximations of the Optimal Transport Cost: Unlike the regularized cost, the finite dual Sinkhorn divergence is generally nonconvex in its arguments.The text notes that this nonconvexity can be checked numerically.
  • 4.5. Regularized Approximations of the Optimal Transport Cost: Despite its nonconvexity, the finite Sinkhorn divergence is differentiable with respect to the cost matrix and histogram arguments.Automatic differentiation techniques can compute these derivatives.

4.6 Generalized Sinkhorn · 4.6. Generalized Sinkhorn · G (KTu) KTu , (4.51)

Generalized Sinkhorn extends the regularized OT framework to broader structured convex problems while preserving the solution’s scaling form. Its proximal-KL iterations support convergence guarantees, efficient computation, stabilization, and applications including unbalanced OT, gradient flows, multimarginal problems, and barycenters.

  • 4.6 Generalized Sinkhorn: Generalized Sinkhorn applies to structured convex optimization problems that include regularized OT with hard marginal constraints.Setting F and G as indicator functions of closed convex sets retrieves the constraints defining U(a, b).
  • 4.6 Generalized Sinkhorn: The unique solution of the generalized problem retains the scaling form established for regularized OT.The proof of Proposition 4.3 carries over to the generalized formulation.
  • G (KTu) KTu , (4.51): Sinkhorn iterations extend to the generalized problem through proximal operators for the KL divergence.These iterations are given by equation (4.51).
  • G (KTu) KTu , (4.51): For some choices of F and G, generalized Sinkhorn iterations have a linear convergence rate and extend to arbitrary measures.The convergence result is stated for specific functions F and G.
  • G (KTu) KTu , (4.51): The iterations are especially useful when ProxKL G is available in closed form or can be computed very efficiently.Separable functions reduce the relevant computations to simple scalar optimization problems, and log-domain calculations can stabilize them.
  • G (KTu) KTu , (4.51): Generalized Sinkhorn approximates solutions for unbalanced OT and gradient flow problems.The cited applications correspond to problems of the forms (10.7) and (9.26).
  • G (KTu) KTu , (4.51): The generalized Sinkhorn iterates are a special case of Dykstra’s algorithm and alternate maximization on the dual problem.Their dual formulation uses Fenchel–Legendre conjugates and associated scaling variables.
  • G (KTu) KTu , (4.51): The generalized formulation also covers multimarginal Sinkhorn algorithms and regularized barycenter iterations.It extends to more than two functions and more than one coupling, with multimarginal and barycenter schemes as particular cases.

Semidiscrete Optimal Transport

Semidiscrete optimal transport studies the case where one measure is discrete and the other is arbitrary, converting the problem into finite-dimensional optimization with a geometric Laguerre-cell structure. The resulting optimal map is piecewise constant, while specialized solvers and convergence analyses support practical computation.

  • Problem setting: The semidiscrete setting pairs a discrete measure of Dirac masses with an arbitrary measure, including measures having a density.In low-dimensional spaces, transporting a continuous density to a discrete measure has a strong geometric interpretation.
  • Finite-dimensional formulation: Restricting the c-transform to the discrete support converts the semidiscrete problem into a finite-dimensional optimization over dual weights.The discrete transform maps a vector of weights to a continuous function.
  • Geometric structure: The dual weights define Laguerre cells, which partition the source space and reduce to a Voronoi diagram when all weights are equal.For squared Euclidean cost, these cells form a power diagram and can be computed using computational-geometry algorithms.
  • Optimal map: After optimizing the dual weights, the transport map sends every point in a Laguerre cell to its associated discrete support point, making the map piecewise constant.Gradient descent is presented as one method for minimizing the semidiscrete energy.
  • Numerical methods: Damped Newton methods achieve linear convergence under conditions including a continuous source density and Laguerre-cell volumes bounded below.Backtracking is used to prevent cells from vanishing between iterations.
  • Limitations: When neither measure is discrete, finite-dimensional semidiscrete strategies are unavailable and stochastic optimization of the dual problem is required.This limitation distinguishes continuous-continuous problems from the semidiscrete formulation.

W1 Optimal Transport

W1 optimal transport uses a metric ground cost, yielding a Lipschitz dual formulation with useful robustness and efficient flow-based numerical methods. Its theory and computation extend from metric spaces to Euclidean domains and graphs.

  • W1 Optimal Transport: Metric-cost OT is harder to analyze than squared-distance OT because optimal Kantorovich couplings are generally nonunique.The squared-metric case can ensure uniqueness under absolute continuity, unlike the ground-distance setting.
  • W1 Optimal Transport: Linear ground distances are more robust to outliers and noise than quadratic costs and enable dual formulations based on local flow, divergence, and Lipschitz constraints.These structures suggest cheaper numerical algorithms aligned with minimum-cost flow methods.
  • W1 Optimal Transport: For c(x, y) = d(x, y), a function is a c-transform exactly when its Lipschitz constant satisfies Lip(f) ≤1, and then fc = −f.This reduces the dual representation to pairs of the form (f, −f) with Lip(f) ≤1.
  • W1 Optimal Transport: In Euclidean spaces, the global Lipschitz constraint becomes the local gradient bound ∥∇f∥∞≤1, while the dual Beckmann formulation uses a flow field under a fixed divergence constraint.The flow represents local mass movement, with div(s) = 0 outside the input supports to express mass conservation.
  • W1 Optimal Transport: On graphs, W1 can be computed using local gradient and divergence operators rather than a full n × n coupling, producing a linear program that is an instance of min-cost flow.Dedicated simplex solvers can efficiently solve the resulting graph problem.

Dynamic Formulations

The dynamic formulation views optimal transport as a minimum-length curve of measures satisfying mass conservation, linking OT to fluid dynamics and enabling numerical computation. Its discretizations and solvers extend this viewpoint to grids, graphs, unbalanced transport, and path-space formulations.

  • Dynamic Formulations: Dynamic optimal transport represents the transformation between measures as a minimum-length curve, offering an intuitive interpretation linked to fluid dynamics and numerical computation.The construction starts at α0 at t = 0 and reaches α1 at t = 1.
  • 7.1. Continuous Formulation: For X = Y = R^d with squared Euclidean cost, W2 is computed by minimizing path length over measure curves advected by vector fields satisfying mass conservation.The continuity equation is ∂tαt + div(αtvt) = 0, with αt=0 = α0 and αt=1 = α1, understood distributionally.
  • 7.1. Continuous Formulation: Introducing momentum Jt converts the nonconvex formulation in (αt, vt) into a convex formulation in (αt, Jt).The momentum must vanish wherever αt(x) = 0, and the formulation extends consistently to measures without Lebesgue densities.
  • 7.1. Continuous Formulation: Displacement interpolation is obtained by pushing an optimal coupling π through Pt(x, y) = (1 − t)x + ty, and in the discrete case is typically supported on n + m − 1 points.When an optimal Monge map exists, the path equals McCann’s interpolation; these interpolations support color, shape, and illumination processing.
  • 7.2. Discretization on Uniform Staggered Grids: The numerical scheme discretizes time and space on a staggered uniform grid, representing densities and momentum at complementary half-grid locations and enforcing discrete divergence constraints.The method is described in dimension d = 2 and extends straightforwardly to higher dimensions; graph variants replace uniform-grid divergence with graph structure.
  • 7.3. Proximal Solvers: Quadratic-cone interior-point solvers provide fast convergence and high precision, but each costly iteration requires solving a linear system whose dimension scales with problem size.Proximal splitting methods include Douglas–Rachford and are closely related to the alternating direction method of multipliers.
  • 7.4. Dynamical Unbalanced OT: As τ → 0 with equal total masses, WFR(α0, α1) converges to classical OT, while dynamic path-space formulations recover displacement interpolation and connect entropic OT to Brownian bridges.For ε → 0, the path-space solution converges to the dynamic formulation; at positive ε, it corresponds to Gaussian blurring of traveling Diracs.

Statistical Divergences

This section introduces statistical divergences as pointwise comparisons of probability measures and contrasts them with Wasserstein distance and other integral probability metrics. It develops their structural properties, discusses representative geometries, and reviews statistical and scaling behavior relevant to data science applications.

  • Divergences: Divergences compare two measures through their pointwise mass ratio, without introducing mass transportation, and can serve as loss functions for probability estimation.The chapter compares Wasserstein distance with major distances and divergences and studies approximation from samples.
  • ϕ-Divergences: Every entropy function induces a ϕ-divergence, which is jointly 1-homogeneous, convex, and weakly* lower semicontinuous in its two measure arguments.For superlinear entropy growth, the divergence is infinite when the first measure lacks a density with respect to the second.
  • Kullback–Leibler divergence: The Kullback–Leibler divergence is both a ϕ-divergence and a Bregman divergence, whose optimization-related properties support mirror descent and Sinkhorn-iteration analysis.Bregman divergences are convex in their first argument and vanish exactly when their arguments coincide.
  • Energy Distance: The energy distance is scale-free and avoids the bandwidth parameter required by usual kernels such as the Gaussian.Its scaling behavior is described for dilations on X = R^d.
  • Regularized Divergences: Regularized Wasserstein divergence interpolates between Wasserstein distance and energy distance, with limits 2Wp as ε→0 and ∥α −β∥2 as ε→+∞.Its sample-complexity rates likewise interpolate between those of optimal transport and maximum mean discrepancy.

Variational Wasserstein Problems

Variational Wasserstein problems exploit mass displacement and data geometry to define fitting objectives, with barycenters, clustering, and gradient flows providing important applications and computational formulations. Their analysis includes convexity, uniqueness, fixed-point algorithms, discretization choices, and numerical limitations.

  • Motivation: Wasserstein geometry compares measures using mass displacement and a ground cost, offering a fitting perspective distinct from Euclidean, total variation, Hellinger, and Kullback–Leibler divergences.Its effectiveness depends on choosing a cost that captures the geometry of the data.
  • Variational structure: Convex-combination parameterizations preserve convexity in Wasserstein fitting problems, whereas general parameterizations θ 7→ αθ are generally nonconvex.The convex cases include barycenter computation and one iteration of dictionary learning with a Wasserstein loss.
  • Numerical limitations: Computing local minimizers generally requires Eulerian or Lagrangian discretization, and overly small gradient-flow steps can cause locking, preventing distributions from evolving.Gradient formulas may also require solving a continuous semi-discrete potential problem, which is difficult to apply in high dimension.
  • Barycenters: When X = R^d and c(x, y) = ∥x − y∥2, a barycenter is unique if at least one input measure has a density.Barycenter support lies in the convex hull of the input supports, and discrete barycenter approximations have consistency results.
  • Algorithms: Barycenter fixed-point iterations decrease the objective under mild conditions and converge to the barycenter, while covariance fixed-point iterations converge in practice to the positive definite solution.For discrete measures supported on fewer than n points, a sorting procedure computes barycenters in O(n log(n)) operations.

Extensions of Optimal Transport

The section extends Kantorovich optimal transport to multimarginal, unnormalized, and more general measure settings, while also addressing local regularity and important geometric invariances. These formulations support applications including quantum chemistry, noisy imaging and machine learning, and shape matching.

  • Multimarginal optimal transport: Multimarginal OT couples S histograms or measures and extends entropic regularization and Sinkhorn computation to this higher-order setting.The multimarginal formulation uses couplings with prescribed marginals and can be generalized from discrete histograms to measures.
  • Multimarginal optimal transport: A typical application of multimarginal OT is approximating solutions to quantum chemistry problems, particularly in density functional theory.
  • Barycenters: Barycenter solutions can be computed from a multimarginal coupling through a barycentric map, and discrete input measures yield a discrete barycenter.For discrete inputs, the barycenter is obtained from an optimal multimarginal coupling and has finite support.
  • Unbalanced optimal transport: Unbalanced OT relaxes hard marginal constraints by penalizing marginal deviations, allowing arbitrary positive histograms and recovering balanced OT as mass-variation penalties diverge.The method is useful when data are noisy, total mass carries signal strength, or normalization is not meaningful.
  • Geometric invariances: OT extensions also target applications where standard distances lack invariance to rescaling, translation, or rotations, including shape matching.Nonconvex variants have been proposed to handle such global transformations.
Loading 1803.00567v4…