1-Wasserstein distance between samples from two multivariate distributions

[dionman]

How can I compute the 1-Wasserstein distance between samples from two multivariate distributions please? I went through the examples, but didn't find an answer to this

[rflamary]

It is in the documentation there is a section for computing the W1 Wasserstein here:
https://pythonot.github.io/quickstart.html#computing-wasserstein-distance

1. Compute distance between discrete samples with M=ot.dist(xs,xt, metric='euclidean')
2. Compute the W1 with W1=ot.emd2(a,b,M) where a et b are the weights of the samples (usually uniform for empirical distribution)

[dionman]

is the computational bottleneck in step 1? can this be accelerated within the library? I think Sinkhorn distances can accelerate step 2, however this doesn't seem to be an issue in my application

[rflamary]

Step 1 in O(n^2)
Step 2 in O(n^3log(n))

with n number of samples

I strongly recommend this book for any questions on OT complexity:
https://arxiv.org/pdf/1803.00567.pdf

Please ask this kind of questions on the mailing list, on our slack or on the gitter :
https://gitter.im/PythonOT/community

[cyan-at]

I thought about using something like this: scipy rv_discrete to convert my pdf to samples to use here, but unfortunately it does not seem compatible with a multivariate discrete pdf yet