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. Because of this analogy, the metric is known in computer science as the earth mover's distance.
The name "Wasserstein distance" was coined by R. L. Dobrushin in 1970, after learning of it in the work of Russian mathematician Leonid Vaseršteĭn 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 German origin).
Let be a metric space for which every probability measure on is a Radon measure (a so-called Radon space). For , let denote the collection of all probability measures on with finite moment. Then, there exists some in such that:
The Wasserstein distance between two probability measures and in is defined as
The above distance is usually denoted (typically among authors who prefer the "Wasserstein" spelling) or (typically among authors who prefer the "Vaserstein" spelling). The remainder of this article will use the notation.
The Wasserstein metric may be equivalently defined by
Intuition and connection to optimal transport
One way to understand the motivation of 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
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.
Point masses (degenerate distributions)
Let and be two degenerate distributions (i.e. Dirac delta distributions) located at points and in . There is only one possible coupling of these two measures, namely the point mass located at . Thus, using the usual absolute value function as the distance function on , for any , the -Wasserstein distance between and is
By similar reasoning, if and are point masses located at points and in , and we use the usual Euclidean norm on as the distance function, then
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
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.
The Wasserstein metric is a natural way to compare the probability distributions of two variables X and Y, where one variable is derived from the other by small, non-uniform perturbations (random or deterministic).
In their paper 'Wasserstein GAN', Arjovsky et al. use the Wasserstein-1 metric as a way to improve the original framework of Generative Adversarial Networks (GAN), to alleviate the vanishing gradient and the mode collapse issues. The special case of normal distributions is used in a Frechet Inception Distance.
It can be shown that Wp satisfies all the axioms of a metric on Pp(M). Furthermore, convergence with respect to Wp is equivalent to the usual weak convergence of measures plus convergence of the first pth moments.
Dual representation of W1
where Lip(f) denotes the minimal Lipschitz constant for f.
Compare this with the definition of the Radon metric:
If the metric d is bounded by some constant C, then
and 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.
Equivalence of W2 and a negative-order Sobolev norm
Under suitable assumptions, the Wasserstein distance of order two is Lipschitz equivalent to a negative-order homogeneous Sobolev norm. More precisely, if we take to be a connected Riemannian manifold equipped with a positive measure , then we may define for the seminorm
and for a signed measure on the dual norm
Then any two probability measures and on satisfy the upper bound
Separability and completeness
- Lévy metric
- Lévy–Prokhorov metric
- Total variation distance of probability measures
- Transportation theory
- Earth mover's distance
- Olkin, I. and Pukelsheim, F. (1982). "The distance between two random vectors with given dispersion matrices". Linear Algebra Appl. 48: 257–263. doi:10.1016/0024-3795(82)90112-4. ISSN 0024-3795.CS1 maint: multiple names: authors list (link)
- Arjovski (2017). "Wasserstein Generative Adversarial Networks". ICML.
- Petitjean, M. (2002). "Chiral mixtures" (PDF). Journal of Mathematical Physics. 43 (8): 4147–4157. doi:10.1063/1.1484559.
- Petitjean, M. (2004). "From shape similarity to shape complementarity: toward a docking theory". Journal of Mathematical Chemistry. 35 (3): 147–158. doi:10.1023/B:JOMC.0000033252.59423.6b. S2CID 121320315.
- Clement, Philippe; Desch, Wolfgang (2008). "An elementary proof of the triangle inequality for the Wasserstein metric". Proceedings of the American Mathematical Society. 136 (1): 333–339. doi:10.1090/S0002-9939-07-09020-X.
- Peyre, Rémi (2018). "Comparison between W2 distance and Ḣ−1 norm, and localization of Wasserstein distance". ESAIM Control Optim. Calc. Var. 24 (4): 1489–1501. doi:10.1051/cocv/2017050. ISSN 1292-8119. (See Theorems 2.1 and 2.5.)
- Bogachev, V.I.; Kolesnikov, A.V. (2012). "The Monge–Kantorovich problem: achievements, connections, and perspectives". Russian Math. Surveys. 67 (5): 785–890. doi:10.1070/RM2012v067n05ABEH004808.
- Villani, Cédric (2008). Optimal Transport, Old and New. Springer. ISBN 978-3-540-71050-9.
- Ambrosio, L., Gigli, N. & Savaré, G. (2005). Gradient Flows in Metric Spaces and in the Space of Probability Measures. Basel: ETH Zürich, Birkhäuser Verlag. ISBN 3-7643-2428-7.CS1 maint: multiple names: authors list (link)
- Jordan, Richard; Kinderlehrer, David; Otto, Felix (1998). "The variational formulation of the Fokker–Planck equation". SIAM J. Math. Anal. 29 (1): 1–17 (electronic). CiteSeerX 10.1.1.6.8815. doi:10.1137/S0036141096303359. ISSN 0036-1410. MR 1617171.
- Rüschendorf, L. (2001) , "Wasserstein metric", Encyclopedia of Mathematics, EMS Press