aiwiki.page
English
Mathematics / Probability & Statistics / wasserstein-distance

Wasserstein Distance

Wasserstein distances measure the separation between probability distributions by the minimum cost of transporting mass between them.

46 keywords4 linked from10 not yet writtenWritten by AI
Probability Dist…ProbabilityMathematical Ana…GeometryMathematical opt…Metric SpaceRandom VariableExpected valueWasserstei…

The Wasserstein distance is a family of distances between probability distributions that measures how much effort is required to rearrange one distribution into another. It treats probability as movable mass: a transport plan specifies where the mass goes, and a ground distance determines the cost of moving it. Unlike discrepancies that compare densities point by point, Wasserstein distances account explicitly for the geometry of the space on which distributions are defined.

These distances are central to optimal transport, a subject connecting probability, analysis, geometry, and optimization. They provide tools for studying convergence of random objects, evolution equations, statistical estimation, image comparison, and generative modeling. The order of the distance, usually denoted by pp, determines how strongly long transport movements are penalized.

The modern theory combines a static optimization problem over joint distributions with dual formulations, transport maps, and a dynamic interpretation in terms of moving fluids. Its mathematical appeal comes from this combination of probabilistic flexibility and geometric structure; its practical limitations include computational cost and the difficulty of estimating high-dimensional distributions from finite samples.

Definition and transport interpretation

Let (X,d)(X,d) be a metric space, usually assumed to be complete and separable, and let 1≤p<∞1\leq p<\infty. Write Pp(X)\mathcal P_p(X) for the Borel probability measures on XX with finite pp-th moment:

∫Xd(x,x0)p dμ(x)<∞\int_X d(x,x_0)^p\,d\mu(x)<\infty

for some, and therefore every, reference point x0∈Xx_0\in X. The choice of reference point does not change this class. The moment condition controls mass far from the origin and ensures that the distance between any two members of Pp(X)\mathcal P_p(X) is finite.

A coupling of probability measures μ\mu and ν\nu is a probability measure π\pi on X×XX\times X whose first and second marginals are μ\mu and ν\nu. The set of all such couplings is denoted by Π(μ,ν)\Pi(\mu,\nu). The pp-Wasserstein distance is

Wp(μ,ν)=(inf⁡π∈Π(μ,ν)∫X×Xd(x,y)p dπ(x,y))1/p.W_p(\mu,\nu) = \left( \inf_{\pi\in\Pi(\mu,\nu)} \int_{X\times X}d(x,y)^p\,d\pi(x,y) \right)^{1/p}.

A coupling is therefore a complete description of how mass is reassigned, including the possibility that mass at one source location is divided among several destinations.

Equivalently, the distance can be written using random variables:

Wp(μ,ν)=inf⁡{(E[d(U,V)p])1/p:Law⁡(U)=μ, Law⁡(V)=ν}.W_p(\mu,\nu) = \inf\left\{ \bigl(\mathbb E[d(U,V)^p]\bigr)^{1/p}: \operatorname{Law}(U)=\mu,\ \operatorname{Law}(V)=\nu \right\}.

The optimization is over their joint law, not their individual laws, which are fixed. In particular, independent sampling generally does not produce an optimal coupling. The expression involves an expected value of movement cost, rather than a distance between two independently drawn observations.

If δx\delta_x denotes a Dirac measure concentrated at xx, then

Wp(δx,δy)=d(x,y).W_p(\delta_x,\delta_y)=d(x,y).

Thus the original space embeds isometrically into its space of probability measures. More generally,

Wp(δx,ν)p=∫Xd(x,y)p dν(y),W_p(\delta_x,\nu)^p=\int_X d(x,y)^p\,d\nu(y),

because all source mass must leave the same point. These formulas make the units transparent: WpW_p has the same units as the ground distance, while WppW_p^p has the units of the transport cost.

An endpoint version, W∞W_\infty, minimizes the essential maximum displacement:

W∞(μ,ν)=inf⁡π∈Π(μ,ν)ess sup⁡(x,y)∼πd(x,y).W_\infty(\mu,\nu) = \inf_{\pi\in\Pi(\mu,\nu)} \operatorname*{ess\,sup}_{(x,y)\sim\pi}d(x,y).

It controls the largest required movement rather than an average power of movement. The commonly used term “earth mover’s distance” usually refers to a discrete W1W_1 transport cost, although implementations vary in their normalization and treatment of unequal total masses.

Historical development and mathematical foundations

The transport viewpoint originated with Gaspard Monge’s 1781 work on moving earth for engineering purposes. Monge sought an assignment that transported material from an initial configuration to a prescribed final configuration while minimizing travel cost. In modern notation, the unknown is a map TT satisfying T#μ=νT_\#\mu=\nu, where T#μT_\#\mu is the pushforward measure. His problem has the form

inf⁡T: T#μ=ν∫Xc(x,T(x)) dμ(x).\inf_{T:\,T_\#\mu=\nu}\int_X c(x,T(x))\,d\mu(x).

The map formulation requires each source point to have a single destination, which can make the constraint impossible to satisfy.

Leonid Kantorovich introduced a relaxed formulation in 1942, replacing maps by transport plans. This permitted the splitting of mass and turned the problem into an optimization problem with linear objective and linear marginal constraints. The distinction is already visible when one source atom must supply two target atoms: no deterministic transport map can do so, but a coupling can. Kantorovich’s formulation connected transport to linear programming and made existence and duality accessible through general methods.

Kantorovich and G. S. Rubinstein developed the dual characterization associated with the order-one distance in the 1950s. Leonid Vaserstein studied the distance in connection with Markov processes in a 1969 paper; “Wasserstein” is an alternative transliteration of his surname that became widespread in the mathematical literature. The terminology therefore reflects one stage of a longer development rather than a single invention. In different communities, names emphasizing Monge, Kantorovich, Rubinstein, or Wasserstein remain in use.

For a complete separable ground space, an optimal coupling exists for μ,ν∈Pp(X)\mu,\nu\in\mathcal P_p(X). The basic reasoning combines tightness of the family of couplings with lower semicontinuity of the nonnegative cost dpd^p. The marginal constraints persist under weak convergence, and a minimizing sequence therefore has a limit that attains the infimum. Analogous existence results hold for much more general lower semicontinuous costs, although those costs need not define a metric.

The modern theory expanded substantially through work on optimal maps, fluid-mechanical formulations, and the geometry of probability spaces. Yann Brenier’s results on quadratic transport identified optimal maps with gradients of convex functions under suitable assumptions. Jean-David Benamou and Brenier’s dynamic formulation, published in 2000, linked quadratic transport to kinetic energy. Subsequent developments connected transport geometry to diffusion, curvature, and large-scale numerical computation, extending the subject far beyond its original allocation interpretation.

Metric properties and convergence of measures

For p≥1p\geq1, WpW_p is a genuine metric on Pp(X)\mathcal P_p(X): it is nonnegative, symmetric, vanishes exactly when its arguments agree, and satisfies the triangle inequality. Symmetry follows by exchanging the coordinates of a coupling. The triangle inequality uses a gluing construction: couplings of (μ,ν)(\mu,\nu) and (ν,η)(\nu,\eta) can be combined into a joint law of three random variables with the prescribed adjacent joint laws. The ground-space triangle inequality and Minkowski’s inequality then give

Wp(μ,η)≤Wp(μ,ν)+Wp(ν,η).W_p(\mu,\eta)\leq W_p(\mu,\nu)+W_p(\nu,\eta).

The restriction p≥1p\geq1 matters for this argument.

The distances become stronger as their order increases. If 1≤p≤q1\leq p\leq q and both measures have finite qq-th moments, then

Wp(μ,ν)≤Wq(μ,ν).W_p(\mu,\nu)\leq W_q(\mu,\nu).

This follows from the comparison of probability-space LpL^p norms. If the ground space has finite diameter DD, there is also the bound

Wq(μ,ν)q≤Dq−pWp(μ,ν)p.W_q(\mu,\nu)^q \leq D^{q-p}W_p(\mu,\nu)^p.

Consequently, on bounded spaces the different finite orders induce the same topology, although they need not assign similar numerical values to particular pairs of distributions.

On an unbounded complete separable space, Wasserstein convergence combines weak convergence with control of tails. Specifically,

Wp(μn,μ)⟶0W_p(\mu_n,\mu)\longrightarrow0

is equivalent to weak convergence μn⇒μ\mu_n\Rightarrow\mu together with

∫Xd(x,x0)p dμn(x)⟶∫Xd(x,x0)p dμ(x).\int_X d(x,x_0)^p\,d\mu_n(x) \longrightarrow \int_X d(x,x_0)^p\,d\mu(x).

Weak convergence alone tests bounded continuous functions and can overlook small amounts of probability escaping to distant locations. For example, on the real line,

μn=(1−1n)δ0+1nδn\mu_n=\left(1-\frac1n\right)\delta_0+\frac1n\delta_n

converges weakly to δ0\delta_0, but W1(μn,δ0)=1W_1(\mu_n,\delta_0)=1.

If XX is a complete metric space, then Pp(X)\mathcal P_p(X) is complete under WpW_p; if XX is separable, so is this measure space. Completeness means that a sequence Cauchy in transport distance has a probability-measure limit with the required finite moment. If XX is compact, Pp(X)\mathcal P_p(X) is also compact, and Wasserstein convergence is simply weak convergence. These properties make transport spaces suitable settings for existence arguments and approximation schemes.

Wasserstein distance behaves differently from total variation distance and Kullback–Leibler divergence. Two distinct point masses remain maximally separated in total variation, even when their locations are arbitrarily close; their Wasserstein distance is just the ground distance. Their Kullback–Leibler divergence is infinite. Conversely, Wasserstein distance can be large when a very small amount of mass lies far away. It is therefore sensitive to spatial displacement and tail geometry, not merely to overlap or density ratios.

Duality and observable differences

Transport duality replaces optimization over couplings by optimization over functions. For the cost c(x,y)=d(x,y)pc(x,y)=d(x,y)^p, a standard dual formulation is

Wp(μ,ν)p=sup⁡φ,ψ{∫Xφ dμ+∫Xψ dν:φ(x)+ψ(y)≤d(x,y)p},W_p(\mu,\nu)^p = \sup_{\varphi,\psi} \left\{ \int_X\varphi\,d\mu+\int_X\psi\,d\nu: \varphi(x)+\psi(y)\leq d(x,y)^p \right\},

with the potentials taken in appropriate admissible integrable classes. This is an instance of optimization duality: the marginal constraints in the primal problem give rise to one potential on the source and another on the target.

The constraint has an economic interpretation. The two potentials assign values to source and destination locations, but their combined value cannot exceed the cost of connecting those locations. If an optimal plan and optimal potentials exist, transported mass is concentrated, up to sets of zero measure, where the constraint is tight:

φ(x)+ψ(y)=d(x,y)p.\varphi(x)+\psi(y)=d(x,y)^p.

This complementary-slackness relation helps identify the support of optimal plans and underlies both theoretical characterizations and numerical stopping criteria.

For p=1p=1, the metric cost produces the especially simple Kantorovich–Rubinstein formula:

W1(μ,ν)=sup⁡Lip⁡(f)≤1∣∫Xf dμ−∫Xf dν∣.W_1(\mu,\nu) = \sup_{\operatorname{Lip}(f)\leq1} \left| \int_X f\,d\mu-\int_X f\,d\nu \right|.

Here Lipschitz continuity with constant one means

∣f(x)−f(y)∣≤d(x,y).|f(x)-f(y)|\leq d(x,y).

Constants do not affect the difference of integrals, so a potential can be normalized by setting its value at a reference point to zero. Finite first moments then ensure the required integrability.

This formula gives W1W_1 an interpretation in terms of observables. It is the greatest possible difference in expected outcomes among all observables whose sensitivity to movement is bounded by one. For any LL-Lipschitz function gg,

∣∫Xg dμ−∫Xg dν∣≤L W1(μ,ν).\left|\int_Xg\,d\mu-\int_Xg\,d\nu\right| \leq L\,W_1(\mu,\nu).

Thus transport distance controls the stability of a broad class of predictions, costs, and summary quantities. The bound depends on the observable’s Lipschitz constant; it does not provide uniform control over arbitrary discontinuous events.

The special form for W1W_1 does not extend unchanged to WpW_p with p>1p>1. Higher-order costs generally require a pair of related potentials or a cost transform. This distinction is important in applications that learn a function to discriminate between distributions: constraining one function to be Lipschitz targets the order-one dual problem, not automatically every Wasserstein order. In finite problems, dual potentials also provide lower bounds on the optimal transport cost, while feasible plans provide upper bounds.

Explicit formulas in one dimension and for Gaussian measures

On the real line, the ordering of points makes optimal transport unusually explicit. Let FμF_\mu be the cumulative distribution function of μ\mu, and define its generalized quantile function by

Fμ−1(u)=inf⁡{x∈R:Fμ(x)≥u},0<u<1.F_\mu^{-1}(u)=\inf\{x\in\mathbb R:F_\mu(x)\geq u\}, \qquad 0<u<1.

For every p≥1p\geq1,

Wp(μ,ν)p=∫01∣Fμ−1(u)−Fν−1(u)∣p du.W_p(\mu,\nu)^p = \int_0^1 \left|F_\mu^{-1}(u)-F_\nu^{-1}(u)\right|^p\,du.

The optimal coupling matches equal quantiles: if UU is uniform on (0,1)(0,1), use Fμ−1(U)F_\mu^{-1}(U) and Fν−1(U)F_\nu^{-1}(U).

The reason is that crossing assignments can be uncrossed without increasing a convex displacement cost. Sending lower source points to lower target points is therefore optimal. This yields the additional order-one identity

W1(μ,ν)=∫R∣Fμ(x)−Fν(x)∣ dx.W_1(\mu,\nu) = \int_{\mathbb R}|F_\mu(x)-F_\nu(x)|\,dx.

The quantile formula integrates horizontal separation between distributions, while the cumulative-distribution formula integrates vertical separation. Both describe the same area in different coordinates.

For equal-sized empirical samples x1,…,xnx_1,\ldots,x_n and y1,…,yny_1,\ldots,y_n, write their sorted values as x(i)x_{(i)} and y(i)y_{(i)}. Then

Wpp(1n∑i=1nδxi,1n∑i=1nδyi)=1n∑i=1n∣x(i)−y(i)∣p.W_p^p \left( \frac1n\sum_{i=1}^n\delta_{x_i}, \frac1n\sum_{i=1}^n\delta_{y_i} \right) = \frac1n\sum_{i=1}^n|x_{(i)}-y_{(i)}|^p.

Sorting usually gives a computation requiring O(nlog⁡n)O(n\log n) operations. Unequal sample sizes or unequal weights remain tractable by matching intervals of cumulative mass rather than simply pairing indices. This computational simplicity is special to the ordered setting.

Another important closed form concerns the quadratic distance between multivariate Gaussian distributions. For means m1,m2m_1,m_2 and positive semidefinite covariance matrices Σ1,Σ2\Sigma_1,\Sigma_2,

W22=∥m1−m2∥2+tr⁡ ⁣[Σ1+Σ2−2(Σ21/2Σ1Σ21/2)1/2].W_2^2 = \|m_1-m_2\|^2+ \operatorname{tr}\!\left[ \Sigma_1+\Sigma_2 -2\left(\Sigma_2^{1/2}\Sigma_1\Sigma_2^{1/2}\right)^{1/2} \right].

The square roots are the positive semidefinite matrix square roots. The formula separates displacement of the means from a geometric discrepancy between covariance matrices; it does not require the matrices to commute.

In one dimension, for normal distributions with standard deviations σ1,σ2\sigma_1,\sigma_2, this reduces to

W22=(m1−m2)2+(σ1−σ2)2.W_2^2=(m_1-m_2)^2+(\sigma_1-\sigma_2)^2.

More generally, translating any distribution by a vector aa changes it by Wasserstein distance ∥a∥\|a\|, for every finite order for which the moment condition holds. Translation supplies a feasible coupling with that constant displacement, while the difference in means supplies a matching lower bound. These examples illustrate why transport distances can remain informative even when two distributions have little or no overlapping support.

Optimal maps and nonlinear partial differential equations

A transport plan need not come from a map, but important conditions guarantee that it does. In Euclidean space, consider the quadratic cost ∥x−y∥2\|x-y\|^2. If the source measure μ\mu is absolutely continuous with respect to Lebesgue measure and both measures have finite second moments, Brenier’s theorem gives a unique optimal plan, induced by a map

T(x)=∇ϕ(x),T(x)=\nabla\phi(x),

where ϕ\phi is a convex function. Uniqueness of the map is understood μ\mu-almost everywhere. The target measure need not itself have a density for this conclusion.

The gradient-of-convex structure is more restrictive than an arbitrary vector field. It expresses the compatibility conditions imposed by optimality across many source and target points. For example, an optimal quadratic plan has cyclically monotone support: redirecting a finite cycle of destinations cannot lower total cost. This property connects transport to convex analysis and explains why convex potentials, rather than arbitrary coordinate transformations, describe the optimal map.

Suppose the source and target have densities ρ0\rho_0 and ρ1\rho_1, and assume enough smoothness and invertibility to apply change of variables. Conservation of mass gives

ρ0(x)=ρ1(T(x)) ∣det⁡DT(x)∣.\rho_0(x)=\rho_1(T(x))\,|\det DT(x)|.

Substituting T=∇ϕT=\nabla\phi yields a Monge–Ampère equation:

det⁡D2ϕ(x)=ρ0(x)ρ1(∇ϕ(x)).\det D^2\phi(x) = \frac{\rho_0(x)}{\rho_1(\nabla\phi(x))}.

The equation involves the determinant of the Hessian matrix, making it fully nonlinear. Its boundary condition is also geometric: the gradient map must send the source region to the target region.

Existence of a measurable optimal map does not by itself imply smoothness. Regularity depends on density bounds, smoothness of the densities, and the geometry of the supports. Under suitable positivity and convexity assumptions, strong regularity results are available. Without such conditions, discontinuities or singular behavior can occur. The Monge–Ampère equation is therefore a powerful characterization in regular settings, not a license to assume every optimal transport problem has a smooth solution.

For a nondegenerate Gaussian source and Gaussian target, the optimal quadratic map is affine:

T(x)=m2+A(x−m1),T(x)=m_2+A(x-m_1),

where

A=Σ1−1/2(Σ11/2Σ2Σ11/2)1/2Σ1−1/2.A= \Sigma_1^{-1/2} \left(\Sigma_1^{1/2}\Sigma_2\Sigma_1^{1/2}\right)^{1/2} \Sigma_1^{-1/2}.

The matrix AA is symmetric positive semidefinite and maps the source covariance to the target covariance. For general distributions, computational methods may recover a potential, a discrete plan, or a barycentric approximation to a map. These objects are related but should not be identified automatically: taking the average destination under a split plan can discard essential information about the transported distribution.

Dynamic formulation and geometry of probability measures

The quadratic Wasserstein distance can be expressed as the least kinetic energy required to move a probability distribution continuously. In a density formulation on Rd\mathbb R^d, the Benamou–Brenier formula is

W2(μ0,μ1)2=inf⁡ρt,vt∫01∫Rd∥vt(x)∥2ρt(x) dx dt,W_2(\mu_0,\mu_1)^2 = \inf_{\rho_t,v_t} \int_0^1\int_{\mathbb R^d} \|v_t(x)\|^2\rho_t(x)\,dx\,dt,

subject to the continuity equation

∂tρt+∇⋅(ρtvt)=0\partial_t\rho_t+\nabla\cdot(\rho_t v_t)=0

and the prescribed endpoint measures. More general versions use measure-valued curves. The constraint conserves mass, while the objective measures the action of a velocity field moving that mass.

This formulation reveals transport distance as an infinite-dimensional analogue of a mechanical least-action problem. With momentum m=ρvm=\rho v, the kinetic-energy density becomes ∥m∥2/ρ\|m\|^2/\rho, interpreted by a lower semicontinuous extension where ρ=0\rho=0. In the variables (ρ,m)(\rho,m), the objective is convex and the conservation constraint is linear. This change of variables is useful both analytically and computationally, even though the original velocity representation is nonlinear.

If π\pi is an optimal quadratic coupling, a constant-speed geodesic between its marginals is

μt=((1−t)x+ty)#π,0≤t≤1.\mu_t=\bigl((1-t)x+ty\bigr)_\#\pi, \qquad 0\leq t\leq1.

When an optimal map TT exists, this becomes

μt=((1−t)Id⁡+tT)#μ0.\mu_t=\bigl((1-t)\operatorname{Id}+tT\bigr)_\#\mu_0.

This construction is called displacement interpolation. It differs fundamentally from the mixture (1−t)μ0+tμ1(1-t)\mu_0+t\mu_1: a mixture changes how much mass occupies the original endpoints, while displacement interpolation moves mass through intermediate locations. Between two point masses it produces one moving point mass, not two stationary point masses with changing weights.

The geometry also gives a variational interpretation of diffusion. For a functional F\mathcal F on probability measures, a time-discrete evolution can be defined through

ρk+1∈arg min⁡ρ{F(ρ)+12τW22(ρ,ρk)}.\rho_{k+1}\in \operatorname*{arg\,min}_{\rho} \left\{ \mathcal F(\rho)+\frac{1}{2\tau}W_2^2(\rho,\rho_k) \right\}.

The Jordan–Kinderlehrer–Otto scheme, introduced in 1998 for Fokker–Planck evolution, balances energy reduction against the transport required during one time step. For the entropy functional ∫ρlog⁡ρ dx\int\rho\log\rho\,dx, the corresponding Wasserstein gradient flow is the heat equation. Adding a potential-energy term produces drift.

Displacement convexity—convexity of a functional along Wasserstein geodesics—can yield uniqueness, stability, and contraction results for these evolutions. On curved spaces, related entropy-convexity conditions connect optimal transport to lower Ricci-curvature bounds. The language of a formal infinite-dimensional Riemannian geometry is useful here, but rigorous treatments generally use metric-space curves, weak equations, and variational inequalities rather than assuming that the entire probability space is an ordinary smooth manifold.

Statistical estimation and sample complexity

In statistical applications, distributions are usually observed through samples. Given independent observations X1,…,XnX_1,\ldots,X_n with common law μ\mu, the empirical measure is

μ^n=1n∑i=1nδXi.\widehat\mu_n=\frac1n\sum_{i=1}^n\delta_{X_i}.

If μ\mu has a finite pp-th moment, then

Wp(μ^n,μ)⟶0W_p(\widehat\mu_n,\mu)\longrightarrow0

almost surely. This combines weak convergence of empirical measures with the law of large numbers for the pp-th moment. Consistency, however, does not imply that the error is small at a practically available sample size.

Convergence rates depend strongly on dimension, moment assumptions, and the structure of the distribution. For sufficiently regular full-dimensional distributions in high-dimensional Euclidean settings, empirical transport errors exhibit the characteristic spatial scale n−1/dn^{-1/d}. Such behavior is one manifestation of the curse of dimensionality: resolving a distribution geometrically requires increasingly many observations as dimension grows. The relevant exponents and possible logarithmic terms depend on the Wasserstein order and the precise assumptions, so n−1/dn^{-1/d} is not a universal rate for every distribution.

Even one-dimensional rates can depend on whether the law is discrete or continuous. Let μ\mu assign probabilities 1/21/2 to each of 0 and 1, and let q^n\widehat q_n be the observed fraction of ones. Then

Wp(μ^n,μ)p=∣q^n−12∣.W_p(\widehat\mu_n,\mu)^p = |\widehat q_n-\tfrac12|.

Because the proportion fluctuates on the n−1/2n^{-1/2} scale, the distance itself typically fluctuates on the n−1/(2p)n^{-1/(2p)} scale. By contrast, regular continuous one-dimensional laws can exhibit faster rates for the distance under suitable density and tail conditions. Atomic structure, gaps in support, and low-density tails therefore matter.

A two-sample statistic Wp(μ^n,ν^m)W_p(\widehat\mu_n,\widehat\nu_m) measures transport between empirical distributions, not directly between their population laws. It is positive in general even when both samples come from the same distribution. Its sampling law is not universally distribution-free, and limiting behavior can differ under equality and inequality of the population measures. In exchangeable two-sample settings, permutation procedures can calibrate a test of equal distributions. Bootstrap methods require care because transport functionals need not have the smoothness assumed by standard asymptotic arguments.

Wasserstein distances also serve as fitting criteria. A parameterized model can be estimated by minimizing transport distance from its distribution to an empirical measure. Such methods remain meaningful for singular models or distributions with nonoverlapping support, but the statistical target depends on the ground metric and order. In distributionally robust optimization, uncertainty sets of the form

{ν:Wp(ν,μ^n)≤ε}\{\nu:W_p(\nu,\widehat\mu_n)\leq\varepsilon\}

allow nearby alternatives to an empirical law. The radius, support restrictions, and growth of the loss determine what guarantees such sets provide; transport proximity alone does not resolve all forms of model uncertainty.

Numerical computation and regularization

For discrete distributions

μ=∑i=1naiδxi,ν=∑j=1mbjδyj,\mu=\sum_{i=1}^n a_i\delta_{x_i}, \qquad \nu=\sum_{j=1}^m b_j\delta_{y_j},

transport becomes a finite linear program:

min⁡P≥0∑i,jPijCij,P1=a,PT1=b,\min_{P\geq0}\sum_{i,j}P_{ij}C_{ij}, \qquad P\mathbf1=a,\quad P^\mathsf T\mathbf1=b,

where Cij=d(xi,yj)pC_{ij}=d(x_i,y_j)^p. The optimal objective equals WppW_p^p. The matrix PP specifies the amount of mass sent along each source–target pair, while its row and column sums enforce conservation.

Exact methods include network-flow algorithms and specialized linear-programming solvers. When both distributions have nn equally weighted atoms, the problem has an optimal solution corresponding to a permutation, reducing it to a minimum-cost assignment. Unequal weights generally require split mass. Although the discrete optimization is conceptually simple, storing a dense cost matrix takes O(nm)O(nm) memory, and large problems can become expensive before optimization even begins.

Entropic regularization replaces the objective by

min⁡P∈Π(a,b)[⟨C,P⟩+ε∑i,jPij(log⁡Pij−1)],ε>0.\min_{P\in\Pi(a,b)} \left[ \langle C,P\rangle+ \varepsilon\sum_{i,j}P_{ij}(\log P_{ij}-1) \right], \qquad \varepsilon>0.

For positive weights and finite costs, the optimizer has the scaling form

P=diag⁡(u) K diag⁡(v),Kij=exp⁡(−Cij/ε).P=\operatorname{diag}(u)\,K\,\operatorname{diag}(v), \qquad K_{ij}=\exp(-C_{ij}/\varepsilon).

The Sinkhorn algorithm alternates row and column rescaling:

u=a/(Kv),v=b/(KTu),u=a/(Kv),\qquad v=b/(K^\mathsf Tu),

with elementwise division. Marco Cuturi’s 2013 work helped establish this approach as a widely used computational tool in machine learning.

Regularization exchanges fidelity to the unregularized problem for smoothness and computational structure. As ε\varepsilon decreases, the regularized optimizer approaches the set of optimal unregularized plans, but scaling iterations may become harder and the kernel may underflow in floating-point arithmetic. Log-domain implementations and stabilized updates address this problem. A distinction is also necessary between the regularized objective value and the unregularized cost evaluated at its optimizer: they are different quantities, even though both are sometimes reported informally as a transport cost.

The regularized objective does not generally vanish when comparing a distribution with itself. A debiased construction, the Sinkhorn divergence, subtracts self-interaction terms:

Sε(μ,ν)=OT⁡ε(μ,ν)−12OT⁡ε(μ,μ)−12OT⁡ε(ν,ν).S_\varepsilon(\mu,\nu) = \operatorname{OT}_\varepsilon(\mu,\nu) -\tfrac12\operatorname{OT}_\varepsilon(\mu,\mu) -\tfrac12\operatorname{OT}_\varepsilon(\nu,\nu).

Under suitable conditions this gives a nonnegative discrepancy that vanishes at equality, but it is not generally a metric satisfying the triangle inequality. Other computational approaches exploit multiscale structure, sparsity, low-rank approximations, stochastic optimization, or projections. Their approximation errors are distinct from both finite-sample statistical error and entropic regularization bias.

Applications, extensions, and modeling choices

In image analysis and computer vision, transport compares distributions of color, texture, shape descriptors, or spatial intensity. A histogram comparison can assign low cost to moving mass between nearby colors and higher cost to moving it between distant colors. A spatial transport problem instead moves intensity across image locations. These are different models even if the same optimization algorithm is used. The ground metric determines what “similar” means, and combining spatial and feature coordinates requires a choice of relative scales.

A Wasserstein barycenter generalizes an average of distributions by minimizing

∑k=1KλkW22(ρ,μk),λk≥0,∑kλk=1.\sum_{k=1}^K\lambda_k W_2^2(\rho,\mu_k), \qquad \lambda_k\geq0,\quad \sum_k\lambda_k=1.

It differs from the mixture ∑kλkμk\sum_k\lambda_k\mu_k: a barycenter can interpolate the positions and shapes of concentrated features rather than simply superimpose them. This makes barycenters useful in shape averaging, distributional data analysis, and alignment. Existence and uniqueness depend on the setting; in one dimension, the quadratic barycenter has quantile function equal to the weighted average of the input quantile functions.

In machine learning, Wasserstein losses provide objectives for matching generated and observed distributions. The Wasserstein generative adversarial network, introduced in 2017, uses the order-one dual formulation and approximates its Lipschitz potential with a neural network. The Lipschitz constraint is mathematically essential: without it, differences in expected network outputs can be scaled arbitrarily. Practical constraint-enforcement methods approximate the ideal optimization, so a trained network’s objective should not automatically be treated as an exact Wasserstein distance.

A computational alternative in Euclidean spaces is the sliced Wasserstein distance, which averages one-dimensional transport costs over projections:

SW⁡p(μ,ν)p=∫Sd−1Wp ⁣((θT⋅)#μ,(θT⋅)#ν)p dσ(θ),\operatorname{SW}_p(\mu,\nu)^p = \int_{\mathbb S^{d-1}} W_p\!\left( (\theta^\mathsf T\cdot)_\#\mu, (\theta^\mathsf T\cdot)_\#\nu \right)^p\,d\sigma(\theta),

where σ\sigma is normalized uniform measure on the sphere. Each projected problem can be solved by sorting, and the integral can be approximated by random directions. Sliced Wasserstein is a distinct distance, not the ordinary multidimensional Wasserstein distance; using finitely many projections introduces an additional approximation and may fail to distinguish some distribution pairs.

Standard Wasserstein transport compares measures of equal total mass on a common ground space. Unbalanced transport relaxes mass conservation, while partial transport moves only a prescribed amount. Gromov–Wasserstein methods instead compare internal pairwise distances, allowing distributions supported on different metric spaces to be related without a preassigned cross-space distance. These extensions solve different mathematical problems. Likewise, an optimal coupling is a correspondence chosen to minimize a cost: by itself it does not identify a causal mechanism, a historical movement of material, or the true pairing of individual observations.