Wasserstein metric

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 distance" was coined by R. L. Dobrushin in 1970, after the Russian mathematician Leonid Vaseršteĭn who introduced the concept in 1969. Most English-language publications use the German spelling "Wasserstein" (attributed to the name "Vasershtein" being of German origin).

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 P_p(M) denote the collection of all probability measures μ on M with finite p^th moment: for some x₀ in M,

$\int_{M} d(x, x_{0})^{p} \, \mathrm{d} \mu (x) < +\infty.$

Then the p^th Wasserstein distance between two probability measures μ and ν in P_p(M) is defined as

$W_{p} (\mu, \nu):=\left( \inf_{\gamma \in \Gamma (\mu, \nu)} \int_{M \times M} d(x, y)^{p} \, \mathrm{d} \gamma (x, y) \right)^{1/p},$

where Γ(μ, ν) denotes the collection of all measures on M × M with marginals μ and ν on the first and second factors respectively. (The set Γ(μ, ν) is also called the set of all couplings of μ and ν.)

The above distance is usually denoted W_p(μ, ν) (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 W_p notation.

The Wasserstein metric may be equivalently defined by

$W_{p} (\mu, \nu)^{p} = \inf \mathbf{E} \big[ d( X , Y )^{p} \big],$

where E[Z] denotes the expected value of a random variable Z and the infimum is taken over all joint distributions of the random variables X and Y with marginals μ and ν respectively.

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 W₁ is widely used to compare discrete distributions, e.g. the color histograms of two digital images; see earth mover's distance for more details.

Properties

Metric structure

It can be shown that W_p satisfies all the axioms of a metric on P_p(M). Furthermore, convergence with respect to W_p is equivalent to the usual weak convergence of measures plus convergence of the first pth moments.

Dual representation of W₁

The following dual representation of W₁ is a special case of the duality theorem of Kantorovich and Rubinstein (1958): when μ and ν have bounded support,

$W_{1} (\mu, \nu) = \sup \left\{ \left. \int_{M} f(x) \, \mathrm{d} (\mu - \nu) (x) \right| \mbox{continuous } f : M \to \mathbb{R}, \mathrm{Lip} (f) \leq 1 \right\},$

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\}.$

If the metric d is bounded by some constant C, then

$2 W_{1} (\mu, \nu) \leq C \rho (\mu, \nu),$

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.

Separability and completeness

For any p ≥ 1, the metric space (P_p(M), W_p) is separable, and is complete if (M, d) is separable and complete.

See also

• Lévy metric
• Lévy–Prokhorov metric
• Total variation distance of probability measures
• Transportation theory