In
mathematics, the
Wasserstein distance or
Kantorovich
Leonid Vitalyevich Kantorovich ( rus, Леони́д Вита́льевич Канторо́вич, , p=lʲɪɐˈnʲit vʲɪˈtalʲjɪvʲɪtɕ kəntɐˈrovʲɪtɕ, a=Ru-Leonid_Vitaliyevich_Kantorovich.ogg; 19 January 19127 April 1986) was a Soviet ...
–
Rubinstein Rubinstein is a surname of German and Yiddish origin, mostly found among Ashkenazi Jews; it denotes "ruby-stone". Notable persons named Rubinstein include:
A–E
* Akiba Rubinstein (1880–1961), Polish chess grandmaster
* Amnon Rubinstein (bor ...
metric is a
distance function
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general sett ...
defined between
probability distributions
In probability theory and statistics, a probability distribution is the mathematical Function (mathematics), function that gives the probabilities of occurrence of different possible outcomes for an Experiment (probability theory), experiment. ...
on a given
metric space
In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general sett ...
. It is named after
Leonid Vaseršteĭn
Leonid Nisonovich Vaserstein ( rus, Леонид Нисонович Васерштейн) is a Russian- American mathematician, currently Professor of Mathematics at Penn State University. His research is focused on algebra and dynamical systems ...
.
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. This problem was first formalised by
Gaspard Monge
Gaspard Monge, Comte de Péluse (9 May 1746 – 28 July 1818) was a French mathematician, commonly presented as the inventor of descriptive geometry, (the mathematical basis of) technical drawing, and the father of differential geometry. Duri ...
in 1781. Because of this analogy, the metric is known in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
as the
earth mover's distance
In statistics, the earth mover's distance (EMD) is a measure of the distance between two probability distributions over a region ''D''. In mathematics, this is known as the Wasserstein metric. Informally, if the distributions are interpreted ...
.
The name "Wasserstein distance" was coined by
R. L. Dobrushin in 1970, after learning of it in the work of
Leonid Vaseršteĭn
Leonid Nisonovich Vaserstein ( rus, Леонид Нисонович Васерштейн) is a Russian- American mathematician, currently Professor of Mathematics at Penn State University. His research is focused on algebra and dynamical systems ...
on Markov processes describing large systems of automata (Russian, 1969). However the metric was first defined by
Leonid Kantorovich
Leonid Vitalyevich Kantorovich ( rus, Леони́д Вита́льевич Канторо́вич, , p=lʲɪɐˈnʲit vʲɪˈtalʲjɪvʲɪtɕ kəntɐˈrovʲɪtɕ, a=Ru-Leonid_Vitaliyevich_Kantorovich.ogg; 19 January 19127 April 1986) was a Sovie ...
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
English usually refers to:
* English language
* English people
English may also refer to:
Peoples, culture, and language
* ''English'', an adjective for something of, from, or related to England
** English national id ...
-language publications use the
German
German(s) may refer to:
* Germany (of or related to)
**Germania (historical use)
* Germans, citizens of Germany, people of German ancestry, or native speakers of the German language
** For citizens of Germany, see also German nationality law
**Ger ...
spelling "Wasserstein" (attributed to the name "Vaseršteĭn" being of
German
German(s) may refer to:
* Germany (of or related to)
**Germania (historical use)
* Germans, citizens of Germany, people of German ancestry, or native speakers of the German language
** For citizens of Germany, see also German nationality law
**Ger ...
origin).
Definition
Let
be a
metric space
In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general sett ...
that is a
Radon space
In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset. Polish spaces are so named bec ...
. For
, the Wasserstein
-distance between two
s and on with finite -Moment (mathematics)">moments is
:
where
is the set of all
couplings of
and
. A coupling
is a
coupling (probability)">couplings of
and
. A coupling
is a joint probability measure on
whose marginal distribution">marginals
The Marginals, also called the "''Paddy Irish''" gang, was a New York street gang during the early 1900s which, under stevedore Thomas F. "Tanner" Smith, succeeded the longtime Hudson Dusters in their territory of New York's Lower West Side.
Base ...
are
and
on the first and second factors, respectively. That is,
:
:
Intuition and connection to optimal transport

One way to understand 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
Given two random variables that are defined on the same probability space, the joint probability distribution is the corresponding probability distribution on all possible pairs of outputs. The joint distribution can just as well be considere ...
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.
Examples
Point masses (degenerate distributions)
Let
and
be two
degenerate distribution
In mathematics, a degenerate distribution is, according to some, a probability distribution in a space with support only on a manifold of lower dimension, and according to others a distribution with support only at a single point. By the latter ...
s (i.e.
Dirac delta distribution
In mathematics, the Dirac delta distribution ( distribution), also known as the unit impulse, is a generalized function or distribution over the real numbers, whose value is zero everywhere except at zero, and whose integral over the entire ...
s) 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
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
on
as the distance function, then
:
Normal distributions
Let
and
be two non-degenerate
Gaussian measure
In mathematics, Gaussian measure is a Borel measure on finite-dimensional Euclidean space R''n'', closely related to the normal distribution in statistics. There is also a generalization to infinite-dimensional spaces. Gaussian measures are named ...
s (i.e.
normal distribution
In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is
:
f(x) = \frac e^
The parameter \mu i ...
s) on
, with respective
expected value
In probability theory, the expected value (also called expectation, expectancy, mathematical expectation, mean, average, or first moment) is a generalization of the weighted average. Informally, the expected value is the arithmetic mean of a ...
s
and
and
symmetric positive semi-definite covariance matrices
In probability theory and statistics, a covariance matrix (also known as auto-covariance matrix, dispersion matrix, variance matrix, or variance–covariance matrix) is a square matrix giving the covariance between each pair of elements o ...
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
Trace may refer to:
Arts and entertainment Music
* ''Trace'' (Son Volt album), 1995
* ''Trace'' (Died Pretty album), 1993
* Trace (band), a Dutch progressive rock band
* ''The Trace'' (album)
Other uses in arts and entertainment
* ''Trace'' ...
term disappears and only the term involving the Euclidean distance between the means remains.
One-dimensional distributions
Let
be probability measures on
, and denote their
cumulative distribution functions
In probability theory and statistics, the cumulative distribution function (CDF) of a real-valued random variable X, or just distribution function of X, evaluated at x, is the probability that X will take a value less than or equal to x.
Eve ...
by
and
. Then the transport problem has an analytic solution: Optimal transport preserves the order of probability mass elements, so the mass at quantile
of
moves to quantile
of
.
Thus, the
-Wasserstein distance between
and
is
:
where
and
are the
quantile functions (inverse CDFs).
In the case of
, a change of variables leads to the formula
:
.
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''
1 is widely used to compare discrete distributions, ''e.g.'' the
color histogram
In image processing and photography, a color histogram is a representation of the distribution of colors in an image. For digital images, a color histogram represents the number of pixels that have colors in each of a fixed list of color ranges, ...
s of two
digital images
A digital image is an image composed of picture elements, also known as ''pixels'', each with ''finite'', '' discrete quantities'' of numeric representation for its intensity or gray level that is an output from its two-dimensional functions f ...
; see
earth mover's distance
In statistics, the earth mover's distance (EMD) is a measure of the distance between two probability distributions over a region ''D''. In mathematics, this is known as the Wasserstein metric. Informally, if the distributions are interpreted ...
for more details.
In their paper '
Wasserstein GAN
The Wasserstein Generative Adversarial Network (WGAN) is a variant of generative adversarial network (GAN) proposed in 2017 that aims to "improve the stability of learning, get rid of problems like mode collapse, and provide meaningful learning c ...
', Arjovsky et al. use the Wasserstein-1 metric as a way to improve the original framework of
Generative Adversarial Networks
A generative adversarial network (GAN) is a class of machine learning frameworks designed by Ian Goodfellow and his colleagues in June 2014. Two neural networks contest with each other in the form of a zero-sum game, where one agent's gain is a ...
(GAN), to alleviate the
vanishing gradient
In machine learning, the vanishing gradient problem is encountered when training artificial neural networks with gradient-based learning methods and backpropagation. In such methods, during each iteration of training each of the neural network's ...
and the mode collapse issues. The special case of normal distributions is used in a
Frechet Inception Distance.
The Wasserstein metric has a formal link with
Procrustes analysis
In statistics, Procrustes analysis is a form of statistical shape analysis used to analyse the distribution of a set of shapes. The name ''Procrustes'' ( el, Προκρούστης) refers to a bandit from Greek mythology who made his victims fit ...
, with application to chirality measures, and to shape analysis.
In computational biology, Wasserstein metric can be used to compare between
persistence diagrams of cytometry datasets.
The Wasserstein metric also has been used in inverse problems in geophysics.
The Wasserstein metric is used in
Integrated information theory
Integrated information theory (IIT) attempts to provide a framework capable of explaining why some physical systems (such as human brains) are conscious, why they feel the particular way they do in particular states (e.g. why our visual field appe ...
to compute the difference between concepts and conceptual structures.
Properties
Metric structure
It can be shown that ''W''
''p'' satisfies all the
axiom
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy o ...
s of a
metric
Metric or metrical may refer to:
* Metric system, an internationally adopted decimal system of measurement
* An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement
Mathematics
In mathem ...
on ''P''
''p''(''M''). Furthermore, convergence with respect to ''W''
''p'' is equivalent to the usual
weak convergence of measures
In mathematics, more specifically measure theory, there are various notions of the convergence of measures. For an intuitive general sense of what is meant by ''convergence of measures'', consider a sequence of measures μ''n'' on a space, sharing ...
plus convergence of the first ''p''th moments.
Dual representation of ''W''1
The following dual representation of ''W''
1 is a special case of the duality theorem of
Kantorovich
Leonid Vitalyevich Kantorovich ( rus, Леони́д Вита́льевич Канторо́вич, , p=lʲɪɐˈnʲit vʲɪˈtalʲjɪvʲɪtɕ kəntɐˈrovʲɪtɕ, a=Ru-Leonid_Vitaliyevich_Kantorovich.ogg; 19 January 19127 April 1986) was a Soviet ...
and Rubinstein (1958): when ''μ'' and ''ν'' have
bounded
Boundedness or bounded may refer to:
Economics
* Bounded rationality, the idea that human rationality in decision-making is bounded by the available information, the cognitive limitations, and the time available to make the decision
* Bounded e ...
support
Support may refer to:
Arts, entertainment, and media
* Supporting character
Business and finance
* Support (technical analysis)
* Child support
* Customer support
* Income Support
Construction
* Support (structure), or lateral support, a ...
,
:
where Lip(''f'') denotes the minimal
Lipschitz constant
In mathematical analysis, Lipschitz continuity, named after German mathematician Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: there exi ...
for ''f''.
Compare this with the definition of the
Radon metric
In mathematics (specifically in measure theory), a Radon measure, named after Johann Radon, is a measure on the σ-algebra of Borel sets of a Hausdorff topological space ''X'' that is finite on all compact sets, outer regular on all Borel set ...
:
:
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
In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset. Polish spaces are so named ...
) implies convergence in the Wasserstein metric, but not vice versa.
Proof
The following is an intuitive proof which skips over technical points. A fully rigorous proof is found in.
Discrete case: When
is discrete, solving for the 1-Wasserstein distance is a problem in linear programming:
where
:
and by the Dual linear program#Strong duality">duality theorem of linear programming, since the primal problem is feasible and bounded, so is the dual problem, and the minimum in the first problem equals the maximum in the second problem. That is, the problem pair exhibits ''strong duality''.
For the general case, the dual problem is found by converting sums to integrals:
(x)
An emoticon (, , rarely , ), short for "emotion icon", also known simply as an emote, is a pictorial representation of a facial expression using characters—usually punctuation marks, numbers, and letters—to express a person's feelings, ...
+ \mathbb E_
(y)
A thumb signal, usually described as a thumbs-up or thumbs-down, is a common hand gesture achieved by a closed fist held with the thumb extended upward or downward in approval or disapproval, respectively. These gestures have become metaphors ...
\
f(x) + g(y) \leq c(x, y)
\endand the ''strong duality'' still holds.
This is the Kantorovich duality theorem.
Cédric Villani
Cédric Patrice Thierry Villani (; born 5 October 1973) is a French politician and mathematician working primarily on partial differential equations, Riemannian geometry and mathematical physics. He was awarded the Fields Medal in 2010, and he ...
recounts the following interpretation from
Luis Caffarelli
Luis Angel Caffarelli (born December 8, 1948) is an Argentine mathematician and luminary in the field of partial differential equations and their applications.
Career
Caffarelli was born and grew up in Buenos Aires. He obtained his Masters of S ...
:
Suppose you want to ship some coal from mines, distributed as , to factories, distributed as . The cost function of transport is . Now a shipper comes and offers to do the transport for you. You would pay him per coal for loading the coal at , and pay him per coal for unloading the coal at .
For you to accept the deal, the price schedule must satisfy . The Kantorovich duality states that the shipper can make a price schedule that makes you pay almost as much as you would ship yourself.
This result can be pressed further to yield:

The two infimal convolution steps are visually clear when the probability space is
.
For notational convenience, let
denote the infimal convolution operation.
For the first step, where we used
, plot out the curve of
, then at each point, draw a cone of slope 1, and take the lower envelope of the cones as
, as shown in the diagram, then
cannot increase with slope larger than 1. Thus all its secants have slope
.
For the second step, picture the infimal convolution
, then if all secants of
have slope at most 1, then the lower envelope of
are just the cone-apices themselves, thus
.
1D Example. When both
are distributions on
, then integration by parts give
(x)
An emoticon (, , rarely , ), short for "emotion icon", also known simply as an emote, is a pictorial representation of a facial expression using characters—usually punctuation marks, numbers, and letters—to express a person's feelings, ...
- \mathbb E_
(y)
A thumb signal, usually described as a thumbs-up or thumbs-down, is a common hand gesture achieved by a closed fist held with the thumb extended upward or downward in approval or disapproval, respectively. These gestures have become metaphors ...
= \int f'(x) (F_\nu(x) - F_\mu(x)) dxthus
Fluid mechanics interpretation of ''W''2
Benamou & Brenier found a dual representation of
by
fluid mechanics
Fluid mechanics is the branch of physics concerned with the mechanics of fluids (liquids, gases, and plasmas) and the forces on them.
It has applications in a wide range of disciplines, including mechanical, aerospace, civil, chemical and ...
, which allows efficient solution by
convex optimization
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization prob ...
.
Given two probability distributions on
with density
, then
where
is a velocity field, and
is the fluid density field, such that
That is, the mass should be conserved, and the velocity field should transport the probability distribution
to
during the time interval
, T
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
/math>.
Equivalence of ''W''2 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
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
Riemannian manifold
In differential geometry, a Riemannian manifold or Riemannian space , so called after the German mathematician Bernhard Riemann, is a real, smooth manifold ''M'' equipped with a positive-definite inner product ''g'p'' on the tangent spac ...
equipped with a positive measure
, then we may define for
the seminorm
:
and for a
signed measure
In mathematics, signed measure is a generalization of the concept of (positive) measure by allowing the set function to take negative values.
Definition
There are two slightly different concepts of a signed measure, depending on whether or not ...
on
the dual norm
:
Then any two probability measures
and
on
satisfy the upper bound
:
In the other direction, if
and
each have densities with respect to the
standard volume measure on
that are both bounded above some
, and
has non-negative
Ricci curvature
In differential geometry, the Ricci curvature tensor, named after Gregorio Ricci-Curbastro, is a geometric object which is determined by a choice of Riemannian or pseudo-Riemannian metric on a manifold. It can be considered, broadly, as a measur ...
, then
:
Separability and completeness
For any ''p'' ≥ 1, the metric space (''P''
''p''(''M''), ''W''
''p'') is
separable, and is
complete
Complete may refer to:
Logic
* Completeness (logic)
* Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable
Mathematics
* The completeness of the real numbers, which implies ...
if (''M'', ''d'') is separable and complete.
[
]
See also
*
Hutchinson metric
In mathematics, the Hutchinson metric otherwise known as Kantorovich metric is a function which measures "the discrepancy between two images for use in fractal image processing" and "can also be applied to describe the similarity between DNA s ...
*
Lévy metric In mathematics, the Lévy metric is a metric on the space of cumulative distribution functions of one-dimensional random variables. It is a special case of the Lévy–Prokhorov metric, and is named after the French mathematician Paul Lévy.
Defin ...
*
Lévy–Prokhorov metric In mathematics, the Lévy–Prokhorov metric (sometimes known just as the Prokhorov metric) is a metric (i.e., a definition of distance) on the collection of probability measures on a given metric space. It is named after the French mathematician ...
*
Fréchet distance
In mathematics, the Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves. It is named after Maurice Fréchet.
Intuitive definition
Imagine a person traversin ...
*
Total variation distance of probability measures In probability theory, the total variation distance is a distance measure for probability distributions. It is an example of a statistical distance metric, and is sometimes called the statistical distance, statistical difference or variational dist ...
*
Transportation theory
*
Earth mover's distance
In statistics, the earth mover's distance (EMD) is a measure of the distance between two probability distributions over a region ''D''. In mathematics, this is known as the Wasserstein metric. Informally, if the distributions are interpreted ...
*
Wasserstein GAN
The Wasserstein Generative Adversarial Network (WGAN) is a variant of generative adversarial network (GAN) proposed in 2017 that aims to "improve the stability of learning, get rid of problems like mode collapse, and provide meaningful learning c ...
References
Further reading
*
*
*
*
External links
* {{cite web , url=https://stats.stackexchange.com/q/295617 , title=What is the advantages of Wasserstein metric compared to Kullback–Leibler divergence? , date=August 1, 2017 , work=
Stack Exchange
Stack Exchange is a network of question-and-answer (Q&A) websites on topics in diverse fields, each site covering a specific topic, where questions, answers, and users are subject to a reputation award process. The reputation system allows t ...
Measure theory
Metric geometry
Theory of probability distributions
Statistical distance