1 Problem formulation and core concepts

Optimal transport studies how to move “mass” so that one probability distribution is transformed into another at minimum total cost. It formalizes the intuition behind relocating resources, matching samples, or transforming uncertainty: each unit of mass at a source point may be sent to one or several destination points, with the total expense computed from a prescribed cost rule.

At the core of the field are two ingredients: (i) a mathematical description of the source and target distributions, and (ii) a rule assigning a cost to shipping mass between locations. Different formulations specify whether mass must move as a deterministic map or may split, and they define whether the problem is posed in a static way or as an evolving process.

1.1 Monge’s formulation

Monge’s original problem seeks a transport map \(T\) that pushes a source distribution \(\mu\) to a target distribution \(\nu\) while minimizing the average shipping cost. In the common case where \(\mu\) and \(\nu\) are probability measures on a space \(X\), “pushing forward” means \(T_\#\mu=\nu\). The total cost is typically written as \[ \int_X c(x,T(x))\, d\mu(x), \] where \(c(x,y)\) is the cost of moving mass from \(x\) to \(y\). Monge’s constraint forces each source point to send its mass along a single destination determined by \(T\), disallowing mass splitting.

This formulation is conceptually direct but can be challenging mathematically because the existence and smoothness of an optimal map depend sensitively on the cost function and the measures involved.

1.2 Kantorovich’s relaxation

Kantorovich introduced a relaxation that allows mass splitting. Instead of searching for a deterministic map, the problem searches over joint distributions of source–destination pairs that respect the marginals.

1.2.1 Transport plans and couplings

A transport plan can be represented by a probability measure \(\pi\) on \(X\times X\) (or on source space times destination space) such that its first marginal equals \(\mu\) and its second marginal equals \(\nu\). Such a \(\pi\) is called a coupling of \(\mu\) and \(\nu\). The objective becomes \[ \int_{X\times X} c(x,y)\, d\pi(x,y), \] minimized over all couplings.

This viewpoint captures both deterministic behavior (where all mass sent from \(x\) goes to a single \(y\)) and randomized or splitting behavior (where different destinations receive fractions of the mass at \(x\)).

1.2.2 Feasibility and marginal constraints

Feasibility requires that \(\mu\) and \(\nu\) be compatible with the total mass notion used. In the standard probability setting, both are probability measures, so total mass is automatically balanced. When the problem is posed for general measures with equal finite mass, couplings exist when the masses match; otherwise, one must use variants such as unbalanced transport (treated later).

Marginal constraints encode conservation: the amount leaving each source point (in aggregate) must equal \(\mu\), and the amount arriving at each destination point (in aggregate) must equal \(\nu\).

1.3 Cost functions and metrics

The cost function \(c(x,y)\) is the modeling choice that determines what “expensive” means. A common selection is based on a ground metric \(d(x,y)\), with costs such as \(c(x,y)=d(x,y)\) or \(c(x,y)=d(x,y)^p\) for \(p\ge 1\). When the cost has a metric structure and the exponent is chosen appropriately, the resulting optimal transport cost can define or relate to Wasserstein distances.

Cost functions may also be more general, including asymmetric or non-metric forms. In theory, properties like existence of minimizers and regularity of optimal plans depend on how \(c\) behaves (e.g., continuity, growth, or convexity).

1.4 Existence and uniqueness (high-level)

In the Kantorovich setting, existence of an optimal coupling is typically ensured under mild conditions: compactness of the domain, or integrability assumptions that control the growth of the cost, along with lower semicontinuity of \(c\). Uniqueness is more delicate: even when an optimal plan exists, it may not be unique, especially when multiple couplings produce the same minimal cost.

Uniqueness of the corresponding optimal map is usually stronger than uniqueness of the plan. Under additional regularity assumptions and with costs derived from convex structures, the optimal plan often concentrates on graphs, allowing the map-like behavior to emerge.

2 Mathematical properties

Many defining features of optimal transport arise from geometry, convexity, and measure-theoretic structure. The theory connects the optimal value to distances between distributions, describes the shape of optimal solutions, and characterizes circumstances under which the optimal transport behaves deterministically.

2.1 Geometric interpretation

Optimal transport can be visualized as the rearrangement of mass in space. The geometry of the ground cost shapes how mass flows: moving directly between nearby points is cheaper than sending it across long distances, and convex costs tend to prefer smoother transport.

2.1.1 Mass splitting vs. deterministic maps

When an optimal plan corresponds to a deterministic map, the coupling \(\pi\) concentrates on pairs \((x,T(x))\), so each source point is matched to a single destination. In contrast, when splitting is optimal, the plan assigns nontrivial mass to multiple destinations for the same source point, reflecting ambiguity or non-smooth constraints imposed by the measures and the cost.

Which regime occurs is governed by the measures’ regularity and the geometry of the cost. In many classical settings, optimality is deterministic almost everywhere, though exceptions exist.

2.1.2 Wasserstein distance as a metric

For certain costs of the form \(c(x,y)=d(x,y)^p\), the optimal cost raised to an appropriate power yields the Wasserstein-\(p\) distance between distributions. Under suitable assumptions on \(d\) and \(p\), this distance satisfies the axioms of a metric: nonnegativity, symmetry, and the identity of indiscernibles (zero distance occurs when the distributions coincide), along with a triangle inequality.

This metric interpretation is central in analysis and applications because it turns distributional comparisons into quantitative geometric objects.

2.2 Regularity and structure of optimal solutions

Optimal transport solutions often admit a rich structure described using potentials and convexity-like properties. These potentials encode the “pressure” or “pricing” of locations in the dual formulation.

2.2.1 c-convexity and potentials

A key concept is \(c\)-convexity, a generalization of convexity adapted to a cost function \(c\). It uses the cost to define how potentials generate optimal transport. In many settings, an optimal plan can be described in terms of potentials \(\varphi\) and \(\psi\) such that optimal pairs \((x,y)\) satisfy an equality condition involving \(\varphi(x)\), \(\psi(y)\), and \(c(x,y)\).

These potentials play a role similar to supporting hyperplanes in convex geometry: they determine where the transport “touches” optimality.

2.2.2 Dual attainment

The dual problem typically involves maximizing an expression over potential functions subject to constraints tied to the cost. Under regularity conditions, the dual maximum is achieved (“attainment”), providing a certificate of optimality for the primal solution.

Dual attainment is valuable because it yields practical ways to verify optimality and interpret the structure of transport plans.

2.3 Special cases and tractable regimes

Some configurations are especially well-behaved and lead to explicit solutions or efficient algorithms.

  • One-dimensional transport is often solvable via quantile matching, producing a transparent formula for the optimal coupling.
  • Gaussian-to-Gaussian transport admits a closed-form characterization under squared Euclidean costs, linking optimal transport to linear algebraic transformations.
  • Discrete measures reduce the problem to linear programming or allow regularization schemes that scale to larger instances.

In these regimes, the general theory becomes computationally useful and the structure of solutions can be expressed in simpler terms.

3 Duality and variational characterizations

Duality transforms the optimization problem into a variational problem over potentials. This re-expression clarifies why optimality holds, how it can be certified, and how geometry and convex analysis enter the picture.

3.1 Kantorovich dual problem

In Kantorovich duality, one maximizes over functions \(\varphi\) and \(\psi\) constrained so that \[ \varphi(x)+\psi(y)\le c(x,y) \] for all relevant pairs \((x,y)\). The objective then integrates \(\varphi\) against \(\mu\) and \(\psi\) against \(\nu\). The resulting optimal dual value equals the optimal primal cost under appropriate conditions.

This framework converts an optimization over couplings (measures on product spaces) into an optimization over functions on the original spaces.

3.2 Complementary slackness insights

When primal and dual optimizers exist, they often satisfy a complementary slackness condition. Conceptually, mass can only be transported along pairs \((x,y)\) where the dual constraint is tight: \[ \varphi(x)+\psi(y)=c(x,y) \] for the pairs receiving positive mass under the optimal coupling.

This principle provides a direct mechanism for identifying where transport occurs and supports structural statements like “optimal pairs lie on a surface determined by potentials.”

3.3 c-transform and potentials

The constraint \(\varphi(x)+\psi(y)\le c(x,y)\) leads to operators that map one potential to another. The \(c\)-transform sends a function \(\varphi\) to \[ \varphi^{c}(y)=\inf_x \big(c(x,y)-\varphi(x)\big), \] and similarly one defines transforms for \(\psi\). At optimality, potentials relate through these transforms, and \(c\)-convexity emerges as the class of functions consistent with such relations.

These operations are central to both theory (characterizing solutions) and algorithms (iteratively improving potentials).

3.4 Connections to convex analysis

Although optimal transport is not limited to Euclidean settings, its analytic backbone connects to convexity. In the squared Euclidean cost case, the dual structure relates to Legendre–Fenchel transforms and convex conjugates. More broadly, \(c\)-convexity functions as a generalized convexity notion with cost-adjusted supporting functions.

Thus, methods from convex analysis—subgradients, differentiability properties, and stability under perturbations—often inform transport regularity results and computational design.

4 Discrete optimal transport

Discrete optimal transport addresses the case where \(\mu\) and \(\nu\) are sums of point masses. This setting is the backbone of many data-driven computations because empirical measures are naturally discrete.

4.1 Earth Mover’s Distance (EMD)

Earth Mover’s Distance is a common name for the optimal transport cost when the cost is based on a ground metric and the measures are discrete. It represents the minimum “work” required to rearrange piles of mass into another configuration, where work scales with distance moved and amount shipped.

EMD is widely used because it aligns with intuitive notions of moving resources and because it produces a meaningful distance-like quantity between histograms.

4.2 Linear programming approach

In discrete settings, the Kantorovich formulation becomes a linear program. The decision variables are the masses \(\pi_{ij}\) shipped from source point \(i\) to destination point \(j\).

4.2.1 Constraint structure

Marginal constraints enforce conservation:

  • For each source \(i\), the outgoing shipment \(\sum_j \pi_{ij}\) must match the source mass at \(i\).
  • For each destination \(j\), the incoming shipment \(\sum_i \pi_{ij}\) must match the destination mass at \(j\).
  • Nonnegativity \(\pi_{ij}\ge 0\) ensures shipments are physically meaningful.

The objective is a weighted sum \(\sum_{i,j} c_{ij}\pi_{ij}\) where \(c_{ij}=c(x_i,y_j)\).

4.2.2 Computational complexity (overview)

Solving the full linear program can be expensive because the number of variables grows as the product of the numbers of support points. Complexity depends on the solver and structure of the cost matrix, but in general, large discrete problems require specialized methods, exploitation of sparsity, or approximation via regularization.

This motivates entropic regularization and other faster schemes.

4.3 Entropic regularization

Entropic regularization modifies the objective by adding a term proportional to the entropy of the coupling. This yields a strictly convex optimization problem (in many settings), leading to smoother couplings and computational tractability.

4.3.1 Sinkhorn algorithm

A standard method is the Sinkhorn algorithm, an iterative procedure that rescales rows and columns of the Gibbs kernel \(K_{ij}=\exp(-c_{ij}/\varepsilon)\). Starting from one set of scaling factors, each iteration enforces the marginal constraints by normalizing with respect to the current scaling.

The algorithm is attractive because it reduces the computational burden compared with generic linear programming and can leverage matrix operations efficiently.

4.3.2 Convergence and stability considerations

Convergence properties depend on the regularization strength \(\varepsilon\). Larger \(\varepsilon\) yields faster convergence and more diffuse transport, while smaller \(\varepsilon\) better approximates the unregularized optimum but can cause numerical instability and require more iterations.

Stability analysis often focuses on how errors in scaling factors propagate and how conditioning depends on the cost matrix and \(\varepsilon\).

4.4 Approximations and acceleration methods

Practical implementations use strategies such as:

  • Warm starts when solving related problems repeatedly.
  • Low-rank or sparsity-aware approximations of the cost kernel.
  • Multi-scale approaches that solve at coarse resolutions before refining.
  • Alternative regularization schemes that trade off bias and speed.

These methods aim to maintain accuracy while reducing runtime, especially for large-scale applications.

5 Continuous optimal transport

Continuous optimal transport treats probability measures that are not limited to finitely many points, such as densities on manifolds or subsets of Euclidean space. The theory connects measure transport to functional analysis and partial differential equations.

5.1 Wasserstein spaces

Wasserstein spaces \( \mathcal{P}_p(X) \) consist of probability measures with finite \(p\)-moment relative to a metric space \((X,d)\). The Wasserstein distance defines a geometry on these spaces, enabling convergence notions and continuity properties for distribution-valued processes.

This framework allows one to interpret evolution of probability distributions as motion in a metric space, which is central to gradient-flow and dynamics perspectives.

5.2 Benamou–Brenier dynamic formulation

The Benamou–Brenier formulation rewrites optimal transport as a problem of finding a time-dependent density and velocity field. For squared Euclidean cost, it expresses the transport cost as an infimum of kinetic energy over admissible mass-conserving flows.

5.2.1 Continuity equation viewpoint

The admissibility constraints are typically written as a continuity equation that encodes conservation of mass over time. In effect, the density changes according to the divergence of the flux (density times velocity), ensuring no creation or destruction occurs.

This transforms the problem from choosing a single coupling to designing an entire trajectory in time.

5.2.2 Interpretation via fluid flows

The velocity field offers a physical analogy: the mass distribution evolves like an incompressible or compressible fluid depending on the setting. The objective corresponds to the integral of the squared speed of the flow, so the optimal transport path is the least-energy route that carries the initial density to the final one.

Even when the analogy is not literal, it often guides intuition for regularity and approximation schemes.

Dynamic formulations enable connections to PDE theory. Under additional structures, optimal transport can be linked to gradient flows of energy functionals in Wasserstein spaces. This perspective explains why diffusion-like processes and certain nonlinear PDEs can be interpreted as steepest-descent evolutions with respect to Wasserstein geometry.

The topic is broad; the general message is that optimal transport provides a bridge between variational principles and evolution equations.

6 Statistical and machine learning applications

Optimal transport has become influential in statistics and machine learning because it provides meaningful ways to measure differences between distributions and to construct couplings between datasets or feature representations.

6.1 Distribution comparison and distances

Wasserstein distances serve as alternatives to divergence measures that may behave poorly under support mismatch. In many settings, Wasserstein-based comparisons capture the geometry of the underlying space, yielding smoother notions of “closeness” between empirical distributions.

This is used for tasks such as distribution-level similarity, hypothesis testing, and clustering based on distributional structure.

6.2 Barycenters and averaging

An optimal transport barycenter is a distribution that minimizes the weighted sum of Wasserstein distances to given distributions. Barycenters can be seen as an averaging procedure that respects geometry: instead of averaging parameters elementwise, one aligns mass optimally and then aggregates.

This concept supports interpolation between distributions and model-building where an “average” distribution is required.

6.3 Domain adaptation and matching

In domain adaptation, source and target data may have different distributions. Optimal transport provides a way to align them by transporting mass from source to target, sometimes in feature space, and then transferring learned structure. Couplings can act as soft matchings between samples or as reweighting schemes.

The result is often improved generalization when direct overlap between supports is limited.

6.4 Generative modeling viewpoints

Generative modeling can use optimal transport ideas to compare generated samples with target data. Wasserstein-based losses encourage the generator to produce samples that match the target distribution in a geometry-aware way, which is particularly useful in settings where adversarial training or moment matching is unstable.

Entropic regularization and scalable solvers further make these approaches practical.

6.5 Computational pipelines and practical considerations

Real-world pipelines often rely on discrete approximations (empirical measures) and computational accelerations such as Sinkhorn regularization. Practical issues include:

  • choosing the ground metric and cost exponent,
  • selecting regularization strength to balance bias and stability,
  • managing memory for large cost matrices,
  • and addressing sample size effects.

Despite these challenges, optimal transport remains a flexible tool for distribution alignment and comparison.

7 Numerical methods and implementation

Numerical implementation determines whether optimal transport can be used at scale. Methods differ mainly in how they approximate the optimization, enforce constraints, and manage computational cost.

7.1 Choosing solvers (overview)

Common solver categories include:

  • Linear programming approaches for small discrete problems.
  • Sinkhorn-type methods for entropically regularized formulations.
  • Network flow and specialized combinatorial methods when the cost structure fits a graph model.
  • Gradient-based optimization over potentials in the dual.

The best choice depends on problem size, required accuracy, and available hardware.

7.2 Regularization and hyperparameters

For entropic regularization, the key parameter is \(\varepsilon\). It controls the trade-off between fidelity to the unregularized optimum and numerical smoothness. A second set of choices includes stopping criteria, scaling tolerances, and whether to compute in log-space to avoid underflow.

Hyperparameter selection is often guided by validation metrics or by studying convergence behavior.

7.3 Handling constraints and noise

When empirical measures contain sampling noise, strict enforcement of exact marginal constraints may overfit. Some applications benefit from regularization, robustified costs, or relaxed/unbalanced formulations. Constraint handling also arises in cases where support is large but only partial mass should be transported efficiently.

Robust computational practice often includes monitoring marginal errors and ensuring nonnegativity in computed couplings.

7.4 Complexity vs. accuracy trade-offs

Approximations generally introduce bias but improve runtime. For instance, entropic regularization yields smoother couplings that are easier to compute but differ from the exact optimal plan. The trade-off is influenced by:

  • the regularization strength,
  • the iteration budget,
  • the structure of the cost matrix,
  • and whether multiscale or acceleration techniques are used.

Understanding this balance is essential for producing results that are both reliable and computationally feasible.

7.5 Software ecosystems (general)

A variety of libraries support optimal transport workflows, typically offering:

  • computation of Wasserstein distances (often entropic),
  • barycenter routines,
  • and sampling-based solvers.

Many packages also integrate with common machine learning frameworks, allowing automatic differentiation for learning tasks where transport losses appear in training objectives.

The specific tool choice is less important than verifying numerical correctness, reproducibility, and parameter conventions.

8 Theoretical extensions and generalizations

Optimal transport extends beyond the balanced, two-marginal, deterministic-cost setup. Generalizations address unequal total mass, multiple distributions, uncertainty, and limiting behaviors.

8.1 Unbalanced optimal transport

Unbalanced transport relaxes the requirement that the source and target have equal total mass. Instead of strict marginal constraints, deviations are penalized using divergence-like terms. This accommodates situations where probability mass is missing or extra, such as when comparing features extracted with different coverage or when measuring “approximate” distributions.

The result is more flexible but introduces additional modeling choices and changes the underlying metric properties.

8.2 Semi-discrete and multi-marginal transport

  • Semi-discrete transport combines a continuous source with a discrete target. The structure often enables algorithms based on partitioning the space using power diagrams or related geometric constructions.
  • Multi-marginal transport considers couplings among more than two distributions simultaneously. This can model complex dependencies but typically increases computational difficulty and requires specialized theory.

These variants highlight how the structure of marginals affects both existence and algorithm design.

8.3 Robust and stochastic variants (high-level)

Robust variants incorporate uncertainty in the measures or in the cost. Stochastic formulations may treat mass transport under random perturbations or through expected cost minimization. Such approaches aim to produce couplings that are not overly sensitive to noise or sampling variability.

These ideas connect optimal transport to statistical robustness and to probabilistic modeling.

8.4 Limit relations and asymptotic behaviors

As parameters vary, regularized optimal transport solutions can converge to unregularized ones. Understanding asymptotic regimes also includes analyzing how transport costs behave as sample sizes increase, as regularization weakens, or as domain geometry changes. These results justify approximations and clarify when computational surrogates remain faithful to the target problem.

9 Typical worked examples (conceptual)

Worked examples illustrate how general principles become concrete computations. The examples below emphasize conceptual mechanics rather than full derivations.

9.1 1D optimal transport (quantile coupling)

For measures on a line with cost based on distance, the optimal coupling pairs quantiles. In practice, one can sort samples from the source and target, then match them in order (for suitable costs), resulting in a monotone transport map. This reflects the fact that in one dimension, “crossing” transport is never beneficial when the cost is convex in distance.

The quantile-coupling viewpoint links optimal transport to distribution functions and empirical order statistics.

9.2 Gaussian-to-Gaussian transport (insight level)

When both source and target are multivariate Gaussians and the cost is squared Euclidean distance, the optimal coupling can be described using linear transformations that align the covariance structures. The optimal map typically involves transporting means and then transforming one covariance into the other through a matrix relation connected to a matrix square root.

This example highlights how optimal transport can reduce to algebra when distributions have strong structure.

9.3 Histogram matching with EMD and Sinkhorn

Given two histograms, one can compute the EMD by solving a transportation problem between bin centers with costs given by distances between bins. For larger histograms, entropic regularization with the Sinkhorn algorithm provides a scalable approximation. The resulting coupling can be interpreted as a soft matching matrix between bins, where nearby bins exchange more mass due to lower cost.

The conceptual workflow is: build the cost matrix, choose regularization, compute scaling factors iteratively, then read off the transport plan.

9.4 Barycenter of multiple distributions

To compute a barycenter, one selects several input distributions and solves for a distribution that minimizes a weighted sum of transport distances to them. In discrete settings, the barycenter can be obtained iteratively by combining couplings between the barycenter and each input, updating its support and weights. The conceptual outcome is an average that reflects geometry: features shift and blend according to the optimal alignments rather than via naive averaging.

This example demonstrates transport’s ability to produce structured “mean” distributions in a distributional space.