The Wasserstein metric (also Vaserstein metric ) is a metric between probability measures on a given metric space .
One can intuitively imagine that if each distribution is viewed as a heap of “ earth ” piled up on metric space, then this metric describes the minimal “cost” of converting one heap into the other. Because of this analogy, this metric is known in computer science as the Earth Mover's Metric .
The metric got its name in 1970 from Roland Lwowitsch Dobruschin , who named it after Leonid Vaseršteĭn . Vaseršteĭn introduced the concept in 1969.
definition
Be a metric space in which every probability a Radon measure on is also Radon space called. For let the set of all probability measures be on with a finite -th moment, that is to say for on off :
-
.
Then the -th Wasserstein distance between two probability measures and out for is defined as:
-
,
where the set of all measures denotes, with and as marginal distributions with respect to the first and second factor, respectively. ( This is also called the set of all couplings between and .) For the Wasserstein distance is defined as:
where is the bearer of measure.
Examples
Dirac measure
Be and two Dirac measures with . Then the only possible pairing is . Referring now to the distance function, the absolute value function on , we obtain for any :
If now and if one takes the Euclidean distance instead of the absolute value function , one obtains:
Normal distribution
Let and be two normal distributions on the , with expected values and covariance matrices . If the Euclidean distance is now taken as the distance function, the 2-Wasserstein metric between and as the sum of the square Euclidean distance of the mean values and the square Frobenius distance between the roots of the covariances can be expressed:
-
This result also generalizes the previous example, since the Dirac measure can be viewed as normal distributions with a covariance matrix equal to zero. Then the trace terms are omitted and only the distance between the expected values remains.
application
The Wasserstein metric is a natural way to compare the probability distributions of two variables and , where one variable is derived from the other by small, non-uniform perturbations (random or deterministic).
In computer science, for example, the metric is widely used to compare discrete distributions, for example the color histograms of two digital images.
properties
Metric structure
It can be shown that all axioms of a metric are met. In addition, convergence is equivalent to the weak convergence of measures plus the convergence of the first moments.
It applies to and :
Dual representation of the
If and limited carrier who then applies
-
,
where describes the smallest Lipschitz constant of .
This can be compared to the definition of the Radon metric:
-
.
If the metric is constrained by a , then:
-
.
thus the convergence in the Radon metric implies the convergence with respect to . The reverse direction generally does not apply.
Separability and completeness
For each , the metric space is separable and complete if it is separable and complete.
literature
-
Ambrosio, L., Gigli, N. & Savaré, G .: Gradient Flows in Metric Spaces and in the Space of Probability Measures . ETH Zurich, Birkhäuser Verlag, Basel 2005, ISBN 3-7643-2428-7 .
- Richard Jordan, David Kinderlehrer , Felix Otto : The variational formulation of the Fokker-Planck equation . In: SIAM J. Math. Anal. . 29, No. 1, 1998, ISSN 0036-1410 , pp. 1-17 (electronic). doi : 10.1137 / S0036141096303359 .
Individual evidence
-
↑ a b Facundo Mémoli : Gromov-Wasserstein Distances and the Metric Approach to Object Matching . In: Foundation of Computational Mathematics . April 2011, pp. 427-430. doi : 10.1007 / s10208-011-9093-5 .
-
↑ Olkin, I. and Pukelsheim, F .: The distance between two random vectors with given dispersion matrices . In: Linear Algebra Appl. . 48, 1982, ISSN 0024-3795 , pp. 257-263. doi : 10.1016 / 0024-3795 (82) 90112-4 .
-
^ Dowson, DC and Landau, BV: The Fréchet Distance between Multivariate Normal Distributions . In: J. of Multivariate Analysis . 12, No. 3, 1982, ISSN 0047-259X , pp. 450-455. doi : 10.1016 / 0047-259X (82) 90077-X .
-
↑ Bogachev, VI, Kolesnikov, AV: The Monge-Kantorovich problem: achievements, connections, and perspectives . In: Russian Math. Surveys . 67, September, pp. 785-890. doi : 10.1070 / RM2012v067n05ABEH004808 .