In mathematics, the Wasserstein (or Vasershtein) metric is a distance function defined between probability distributions on a given metric space M.
Intuitively, if each distribution is viewed as a unit amount of "dirt" piled on M, the metric is the minimum "cost" of turning one pile into the other, which is assumed to be the amount of dirt that needs to be moved times the 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/Vasershtein distance" was coined by R.L. Dobrushin in 1970, after the Russian mathematician Leonid Nasonovich Vasershtein who introduced the concept in 1969. Most English-language publications use the German spelling "Wasserstein" (attributed to the name "Vasershtein" being of Germanic origin).
Contents |
Definition
Let (M, d) be a metric space for which every probability measure on M is a Radon measure (a so-called Radon space). For p ≥ 1, let Pp(M) denote the collection of all probability measures μ on M with finite pth moment: for some x0 in M,
Then the pth Wasserstein distance between two probability measures μ and ν in Pp(M) is defined as
where Γ(μ, ν) denotes the collection of all measures on M × M with marginals μ and ν on the first and second factors respectively.
The above distance is usually denoted Wp(μ, ν) (typically among authors who prefer the "Wasserstein" spelling) or ℓp(μ, ν) (typically among authors who prefer the "Vasershtein" spelling). The remainder of this article will use the Wp notation.
The Wasserstein metric may be equivalently defined by
![W_{p} (\mu, \nu)^{p} = \inf \mathbf{E} \big[ | X - Y |^{p} \big],](http://wpcontent.answers.com/math/c/0/b/c0b1143976f52a21cee1c9d6699adac0.png)
where E[Z] denotes the expected value of a random variable Z and the infimum is taken over all simultaneous distributions of the random variables X and Y with marginals μ and ν respectively.
Earth mover's distance
Intuitively, if each distribution is viewed as a unit amount of "dirt" piled on M, the metric W1 is the minimum "cost" of turning one pile into the other, which is assumed to be the amount of dirt that needs to be moved times the distance it has to be moved. Because of this analogy, the Wasserstein metric W1 is known in computer science as the earth mover's distance.
Applications
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 computer science, for example, the metric W1 is widely used to compare discrete distributions, e.g. the color histograms of two digital images.
Properties
Metric structure
It can be shown that Wp satisfies all the axioms of a metric on Pp(M). Convergence with respect to W2, for example, is equivalent to the usual weak convergence of measures plus convergence of second moments.
Dual representation of W1
The following dual representation of W1 is a special case of the duality theorem of Kantorovich and Rubinstein (1958): when μ and ν have bounded support,
where Lip(f) denotes the minimal Lipschitz constant for f.
Compare this with the definition of the Radon metric:
![\rho (\mu, \nu) := \sup \left\{ \left. \int_{M} f(x) \, \mathrm{d} (\mu - \nu) (x) \right| \mbox{continuous } f : M \to [-1, 1] \right\}.](http://wpcontent.answers.com/math/4/b/f/4bf07dd9388d5cb02a7f816bfd8d29dd.png)
If the metric d is bounded by some constant C, then
and so convergence in the Radon metric (also known as strong convergence) implies convergence in the Wasserstein metric, but not vice versa.
Separability and completeness
For any p ≥ 1, the metric space (Pp(M), Wp) is separable, and is complete if (M, d) is separable and complete.
See also
References
- 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.
- Jordan, Richard; Kinderlehrer, David and Otto, Felix (1998). "The variational formulation of the Fokker-Planck equation". SIAM J. Math. Anal. 29 (1): 1–17 (electronic). doi:. MR1617171. ISSN 0036-1410.
- Rüschendorf, L. (2001), "Wasserstein metric", in Hazewinkel, Michiel, Encyclopaedia of Mathematics, Kluwer Academic Publishers, ISBN 978-1556080104, http://eom.springer.de/w/w120020.htm
 |
It has been suggested that Earth mover's distance be merged into this article or section. (Discuss) |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
