For two probability measures $\mu$ and $\nu$, the Wassertein Distance is defined as $$W_p (\mu , \nu) = \left[ \inf\limits_{\gamma \in \Gamma} |x-y|^p \, d\gamma (x,y) \right] ^{\frac{1}{p}} \, , $$ where $\Gamma$ is the set of all measures $\gamma $ for which $\mu$ and $\nu$ are marginals.

This is a highly non-constructive definition. So, given two sample sets, say $x_1 , \ldots , x_n$ iid from $\mu$ and $y_1 , \ldots , y_n$ from $\nu$, it is not at all obvious how to estimate $W_p (\mu , \nu)$, or even how to compute the distance between the empirical distribution.

Question: Given iid samples from $\mu$ and $\nu$, how does one compute the distance between the empirical distributions?

What is known? In the special case of $p=1$, $W_1 (\mu , \nu) = \int_{-\infty} ^{\infty} |F_{\mu}(y) - F_{\nu}(y)| \, dy$, where $F_{\mu}$ and $F_{\nu}$ are the CDFs of the respective measures. The proof can be easily extended to show that $W_p ^p (\mu , \nu) = \int_{-\infty} ^{\infty} |F_{\mu}(y) - F_{\nu}(y)|^p \, dy$, but not to an equality.

  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – Alex R.
    Dec 11, 2018 at 20:59
  • $\begingroup$ @AlexR. Thanks, but isn't EMD just $W_1$? $\endgroup$
    – Amir Sagiv
    Dec 11, 2018 at 22:18
  • $\begingroup$ If I'm not mistaken, it can be $W_p$, as it's a discretization of Wasserstein distance to a histogram. The distance function $d_{ij}$ is arbitrary, and can refer to any norm. $\endgroup$
    – Alex R.
    Dec 11, 2018 at 23:50
  • $\begingroup$ @AmirSagiv you forgot the 2 constraints that the transport function $\gamma$ should sum to $\mu$ and $\nu$ respectively. The unconstrained formula you currently show is the ill-posed Monge problem, but if the 2 missing constraints are included instead, you would have the more popular Kantorovich formulation $\endgroup$
    – develarist
    Oct 15, 2020 at 11:29

1 Answer 1


Many of the known aspects of computation of the Wasserstein distance, as well as computation of the optimal-transport map, have been summarized in this excellent survey by Peyre and Cuturi: https://arxiv.org/abs/1803.00567


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.