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 '18 at 20:59
  • $\begingroup$ @AlexR. Thanks, but isn't EMD just $W_1$? $\endgroup$ – Amir Sagiv Dec 11 '18 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 '18 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.