In mathematics, the Wasserstein distance or Kantorovich–Rubinstein metric is a distance function defined between probability distributions on a given metric space . It is named after Leonid Vaseršteĭn.
Intuitively, if each distribution is viewed as a unit amount of earth (soil) piled on , the metric is the minimum "cost" of turning one pile into the other, which is assumed to be the amount of earth that needs to be moved times the mean distance it has to be moved. This problem was first formalised by Gaspard Monge in 1781. Because of this analogy, the metric is known in computer science as the earth mover's distance.
Definition
Let be a metric space that is a Polish space. For , the Wasserstein -distance between two probability measures and on with finite -moments is
where is the set of all couplings of and ; is defined to be
and corresponds to a supremum norm. Here, a coupling is a joint probability measure on whose marginals are and on the first and second factors, respectively. This means that for all measurable , it fulfills and .
The case of is special:where denotes the essential supremum of with respect to measure . The metric space (P∞(M), W∞) is complete if (M, d) is separable and complete. Here, P∞ is the space of all probability measures with bounded support.
Naming The name "Wasserstein distance" was coined by R. L. Dobrushin in 1970, after learning of it in the work of Leonid Vaseršteĭn on Markov processes describing large systems of automata (Russian, 1969). However the metric was first defined by Leonid Kantorovich in The Mathematical Method of Production Planning and Organization (Russian original 1939) in the context of optimal transport planning of goods and materials. Some scholars thus encourage use of the terms "Kantorovich metric" and "Kantorovich distance". Most English-language publications use the German spelling "Wasserstein" (attributed to the name "Vaseršteĭn" () being of Yiddish origin).
Intuition and connection to optimal transport
One way to understand the above definition is to consider the optimal transport problem. That is, for a distribution of mass on a space , we wish to transport the mass in such a way that it is transformed into the distribution on the same space; transforming the 'pile of earth' to the pile . This problem only makes sense if the pile to be created has the same mass as the pile to be moved; therefore without loss of generality assume that and are probability distributions containing a total mass of 1. Assume also that there is given some cost function
that gives the cost of transporting a unit mass from the point to the point . A transport plan to move into can be described by a function which gives the amount of mass to move from to . You can imagine the task as the need to move a pile of earth of shape to the hole in the ground of shape such that at the end, both the pile of earth and the hole in the ground completely vanish. In order for this plan to be meaningful, it must satisfy the following properties:
the amount of earth moved out of point must equal the amount that was there to begin with; that is,
and the amount of earth moved into point must equal the depth of the hole that was there at the beginning; that is,
That is, that the total mass moved out of an infinitesimal region around must be equal to and the total mass moved into a region around must be . This is equivalent to the requirement that be a joint probability distribution with marginals and . Thus, the infinitesimal mass transported from to is , and the cost of moving is , following the definition of the cost function. Therefore, the total cost of a transport plan is
The plan is not unique; the optimal transport plan is the plan with the minimal cost out of all possible transport plans. As mentioned, the requirement for a plan to be valid is that it is a joint distribution with marginals and ; letting denote the set of all such measures as in the first section, the cost of the optimal plan is
If the cost of a move is simply the distance between the two points, then the optimal cost is identical to the definition of the distance.
Fortification Gaspard Monge, who first considered the problem, considered it as an abstraction of a practical problem. Monge studied descriptive geometry in the context of military fortification. At the time, the outer walls were built with a large amount of earth which would be costly to transport. Furthermore, the ground near the outer walls would also be shaped with structures like ditches to remove favorable attacking positions. The military engineer, during design, should design it according to the terrain, so that for each sector of the fortress, the volume of the déblai (the earth excavated) would approximately equal the remblai (the material which built up the body of the rampart).
Monge abstracted the problem of minimizing transport cost between the déblai and remblai into a problem in pure geometry, and published it as Mémoire sur la Théorie des Déblais et des Remblais.
Examples
Point masses
Point masses naturally arise in statistics. If and are empirical distributions, each based on observations, thenwhere the infimum is over all permutations of elements. This is a linear assignment problem, and can be solved by the Hungarian algorithm in cubic time.
Normal distributions
Let and be two non-degenerate Gaussian measures (i.e. normal distributions) on , with respective expected values and and symmetric positive semi-definite covariance matrices and . Then, with respect to the usual Euclidean norm on , the 2-Wasserstein distance between and is
where denotes the principal square root of . Note that the second term (involving the trace) is precisely the (unnormalised) Bures metric between and . This result generalises the earlier example of the Wasserstein distance between two point masses (at least in the case ), since a point mass can be regarded as a normal distribution with covariance matrix equal to zero, in which case the trace term disappears and only the term involving the Euclidean distance between the means remains.
One-dimensional distributions
Let be probability measures on , and denote their cumulative distribution functions by and . Then the transport problem has an analytic solution: Optimal transport preserves the order of probability mass elements, so the mass at quantile of moves to quantile of . Thus, the -Wasserstein distance between and is
where and are the quantile functions (inverse CDFs). In the case of , a change of variables leads to the formulaS. S. Vallander, Theory of Probability and its Applications, 1974, Volume 18, Issue 4, Pages 784–786 DOI: https://doi.org/10.1137/1118101
Properties
Metric structure
Wp satisfies all the axioms of a metric on the Wasserstein space Pp(M) consisting of all Borel probability measures on M having finite pth moment.
Convergence with respect to Wp is equivalent to the usual weak convergence of measures plus convergence of the first pth moments.
For any p ≥ 1, the metric space (Pp(M), Wp) is separable, and is complete if (M, d) is separable and complete.
Existence By a theorem of Gangbo and McCann, if are subsets of , and the cost function for some strictly convex function , then the optimal transport problem has a unique optimal transport map. In particular, for all , optimal transport map exists and is unique.
Duality Kantorovich and Rubinstein proved a duality representation theorem for general cost functions , of which the Wasserstein metric is a special case.
Given a cost function , it produces a duality transformation defined byThis generalizes Legendre transformation, which is the case where with a sign flip.
We say that a function is c-convex iff for some . Like in the case of convex transformation, a function is c-convex iff its double dual is itself. In this language, the Kantorovich duality states theorem:If are Polish probability spaces, is lower semicontinuous, and there exists some upper semicontinuous functions such that , thenIf furthermore, only takes real values, there exists a transport plan with finite cost, and there exists some functions such that , then
Proof The following is an intuitive proof which skips over technical points. A fully rigorous proof is found in.
Discrete case: When is discrete, solving for the 1-Wasserstein distance is a problem in linear programming:
where is a general "cost function".
By carefully writing the above equations as matrix equations, we obtain its dual problem:
and by the duality theorem of linear programming, since the primal problem is feasible and bounded, so is the dual problem, and the minimum in the first problem equals the maximum in the second problem. That is, the problem pair exhibits strong duality.
For the general case, the dual problem is found by converting sums to integrals:
and the strong duality still holds. This is the Kantorovich duality theorem. Cédric Villani recounts the following interpretation from Luis Caffarelli: Suppose you want to ship some coal from mines, distributed as , to factories, distributed as . The cost function of transport is . Now a shipper comes and offers to do the transport for you. You would pay him per coal for loading the coal at , and pay him per coal for unloading the coal at .
For you to accept the deal, the price schedule must satisfy . The Kantorovich duality states that the shipper can make a price schedule that makes you pay almost as much as you would ship yourself.This result can be pressed further to yield:
The two infimal convolution steps are visually clear when the probability space is .
For notational convenience, let denote the infimal convolution operation.
For the first step, where we used , plot out the curve of , then at each point, draw a cone of slope 1, and take the lower envelope of the cones as , as shown in the diagram, then cannot increase with slope larger than 1. Thus all its secants have slope .
For the second step, picture the infimal convolution , then if all secants of have slope at most 1, then the lower envelope of are just the cone-apices themselves, thus .
1D Example. When both are distributions on , then integration by parts give
thus
W1 In the case of W1, we have , and there is a particularly simple way to state that a function is c-convex in this case: a function is c-convex iff it is Lipschitz, with Lipschitz constant . In this case, , so the Kantorovich duality states thatThis form shows that W1 is an integral probability metric. If there exists a that reaches the supremum exactly, then such a function is called a Kantorovich potential for this optimal transport problem.
For example, for any , the optimal transport plan of moving an upside-down unit hemisphere centered at to a rightside-up unit hemisphere centered at is simply moving it along the z-direction. This is proven by using the Kantorovich potential .
Connection to Radon measure Compare this with the definition of the Radon metric:If the metric d of the metric space (M,d) is bounded by some constant C, thenand so convergence in the Radon metric (identical to total variation convergence when M is a Polish space) implies convergence in the Wasserstein metric, but not vice versa.
Geometric interpretation Monge's original insight was that, in the case where is a Riemannian manifold with the geodesic distance metric, the duality of optimal transport is geometrically meaningful.
Let be an optimal transport plan from to . To avoid complications and make the imagery clear, suppose that is a deterministic plan. That is, it is equivalent to a transport map , so that any infinitesimal lump of coal at is transported to . The entire transport map can then be drawn as a family of geodesic curve segments in connecting each to its corresponding . These are transport rays.