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.
