# Computing Wassertein Distance

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.

• en.wikipedia.org/wiki/… Dec 11, 2018 at 20:59
• @AlexR. Thanks, but isn't EMD just $W_1$? Dec 11, 2018 at 22:18
• 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. Dec 11, 2018 at 23:50
• @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 Oct 15, 2020 at 11:29