Wasserstein metric

src: i.ytimg.com

In mathematics, the Wasserstein or Kantorovich-Rubinstein metric or distance is a distance function defined between probability distributions on a given metric space ${\displaystyle M}$.

Intuitively, if each distribution is viewed as a unit amount of "dirt" piled on ${\displaystyle 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 "Vaserstein" being of German origin).

Video Wasserstein metric

Definition

Let ${\displaystyle (M,d)}$ be a metric space for which every probability measure on ${\displaystyle M}$ is a Radon measure (a so-called Radon space). For ${\displaystyle p\geq 1}$, let ${\displaystyle P_{p}(M)}$ denote the collection of all probability measures ${\displaystyle \mu }$ on ${\displaystyle M}$ with finite ${\displaystyle p^{\text{th}}}$ moment for some ${\displaystyle x_{0}}$ in ${\displaystyle M}$,

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

Then the ${\displaystyle p^{\text{th}}}$ Wasserstein distance between two probability measures ${\displaystyle \mu }$ and ${\displaystyle \nu }$ in ${\displaystyle P_{p}(M)}$ is defined as

${\displaystyle 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 ${\displaystyle \Gamma (\mu ,\nu )}$ denotes the collection of all measures on ${\displaystyle M\times M}$ with marginals ${\displaystyle \mu }$ and ${\displaystyle \nu }$ on the first and second factors respectively. (The set ${\displaystyle \Gamma (\mu ,\nu )}$ is also called the set of all couplings of ${\displaystyle \mu }$ and ${\displaystyle \nu }$.)

The above distance is usually denoted ${\displaystyle W_{p}(\mu ,\nu )}$ (typically among authors who prefer the "Wasserstein" spelling) or ${\displaystyle \ell _{p}(\mu ,\nu )}$ (typically among authors who prefer the "Vaserstein" spelling). The remainder of this article will use the ${\displaystyle W_{p}}$ notation.

The Wasserstein metric may be equivalently defined by

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

where ${\displaystyle \mathbf {E} [Z]}$ denotes the expected value of a random variable ${\displaystyle Z}$ and the infimum is taken over all joint distributions of the random variables ${\displaystyle X}$ and ${\displaystyle Y}$ with marginals ${\displaystyle \mu }$ and ${\displaystyle \nu }$ respectively.

Maps Wasserstein metric

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 ${\displaystyle \mu (x)}$ on a space ${\displaystyle X}$, we wish to transport the mass in such a way that it is transformed into the distribution ${\displaystyle \nu (x)}$ on the same space; transforming the 'pile of earth' ${\displaystyle \mu }$ to the pile ${\displaystyle \nu }$. 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 ${\displaystyle \mu }$ and ${\displaystyle \nu }$ are probability distributions containing a total mass of 1. Assume also that there is given some cost function

${\displaystyle c(x,y)\mapsto [0,\infty )}$

that gives the cost of transporting a unit mass from the ${\displaystyle x}$ to the point ${\displaystyle y}$. A transport plan to move ${\displaystyle \mu }$ into ${\displaystyle \nu }$ can be described by a function ${\displaystyle \gamma (x,y)}$ which gives the amount of mass to move from ${\displaystyle x}$ to ${\displaystyle y}$. In order for this plan to be meaningful, it must satisfy the following properties

${\displaystyle {\begin{aligned}\int \gamma (x,x')\mathrm {d} x'&=\mu (x)\\\int \gamma (x',x)\mathrm {d} x'&=\nu (x)\end{aligned}}}$

That is, that the total mass moved out of an infinitesimal region around ${\displaystyle x}$ must be equal to ${\displaystyle \mu (x)\mathrm {d} x}$ and the total mass moved into a region around ${\displaystyle x}$ must be ${\displaystyle \nu (x)\mathrm {d} x}$. This is equivalent to the requirement that ${\displaystyle \gamma }$ be a joint probability distribution with marginals ${\displaystyle \mu }$ and ${\displaystyle \nu }$. Thus, the infinitesimal mass transported from ${\displaystyle x}$ to ${\displaystyle y}$ is ${\displaystyle \gamma (x,y)\mathrm {d} x\mathrm {d} y}$, and the cost of moving is ${\displaystyle c(x,y)\gamma (x,y)\mathrm {d} x\mathrm {d} y}$, following the definition of the cost function. Therefore, the total cost of a transport plan ${\displaystyle \gamma }$ is

${\displaystyle {\begin{aligned}\int \int c(x,y)\gamma (x,y)\mathrm {d} x\mathrm {d} y=\int c(x,y)\mathrm {d} \gamma (x,y)\end{aligned}}}$

The plan ${\displaystyle \gamma }$ 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 ${\displaystyle \mu }$ and ${\displaystyle \nu }$; letting ${\displaystyle \Gamma }$ denote the set of all such measures as in the first section, the cost of the optimal plan is

${\displaystyle {\begin{aligned}C=\inf _{\gamma \in \Gamma (\mu ,\nu )}\int c(x,y)\mathrm {d} \gamma (x,y)\end{aligned}}}$

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 ${\displaystyle W_{1}}$ distance.

src: media.springernature.com

Examples

Point masses (degenerate distributions)

Let ${\displaystyle \mu _{1}=\delta _{a_{1}}}$ and ${\displaystyle \mu _{2}=\delta _{a_{2}}}$ be two degenerate distributions (i.e. Dirac delta distributions) located at points ${\displaystyle a_{1}}$ and ${\displaystyle a_{2}}$ in ${\displaystyle \mathbb {R} }$. There is only one possible coupling of these two measures, namely the point mass ${\displaystyle \delta _{(a_{1},a_{2})}}$ located at ${\displaystyle (a_{1},a_{2})\in \mathbb {R} ^{2}}$. Thus, using the usual absolute value function as the distance function on ${\displaystyle \mathbb {R} }$, for any ${\displaystyle p\geq 1}$, the ${\displaystyle p}$-Wasserstein distance between ${\displaystyle \mu _{1}}$ and ${\displaystyle \mu _{2}}$ is

${\displaystyle W_{p}(\mu _{1},\mu _{2})=|a_{1}-a_{2}|.}$

By similar reasoning, if ${\displaystyle \mu _{1}=\delta _{a_{1}}}$ and ${\displaystyle \mu _{2}=\delta _{a_{2}}}$ are point masses located at points ${\displaystyle a_{1}}$ and ${\displaystyle a_{2}}$ in ${\displaystyle \mathbb {R} ^{n}}$, and we use the usual Euclidean norm on ${\displaystyle \mathbb {R} ^{n}}$ as the distance function, then

${\displaystyle W_{p}(\mu _{1},\mu _{2})=\|a_{1}-a_{2}\|_{2}.}$

Normal distributions

Let ${\displaystyle \mu _{1}={\mathcal {N}}(m_{1},C_{1})}$ and ${\displaystyle \mu _{2}={\mathcal {N}}(m_{2},C_{2})}$ be two non-degenerate Gaussian measures (i.e. normal distributions) on ${\displaystyle \mathbb {R} ^{n}}$, with respective expected values ${\displaystyle m_{1}}$ and ${\displaystyle m_{2}\in \mathbb {R} ^{n}}$ and symmetric positive semi-definite covariance matrices ${\displaystyle C_{1}}$ and ${\displaystyle C_{2}\in \mathbb {R} ^{n\times n}}$. Then, with respect to the usual Euclidean norm on ${\displaystyle \mathbb {R} ^{n}}$, the 2-Wasserstein distance between ${\displaystyle \mu _{1}}$ and ${\displaystyle \mu _{2}}$ is

${\displaystyle W_{2}(\mu _{1},\mu _{2})^{2}=\|m_{1}-m_{2}\|_{2}^{2}+\mathop {\mathrm {trace} } {\bigl (}C_{1}+C_{2}-2{\bigl (}C_{2}^{1/2}C_{1}C_{2}^{1/2}{\bigr )}^{1/2}{\bigr )}.}$

This result generalises the earlier example of the Wasserstein distance between two point masses (at least in the case ${\displaystyle p=2}$), 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.

src: i.ytimg.com

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.

src: i.ytimg.com

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,

${\displaystyle 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:

${\displaystyle \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

${\displaystyle 2W_{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.

src: shakirm.com

See also

• Lévy metric
• Lévy-Prokhorov metric
• Total variation distance of probability measures
• Transportation theory
• Earth mover's distance

src: i.ytimg.com

References

• 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). doi:10.1137/S0036141096303359. ISSN 0036-1410. MR 1617171. 
• Rüschendorf, L. (2001) [1994], "Wasserstein metric", in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 

Source of article : Wikipedia