Fast Sinkhorn Algorithm for Wasserstein-1 Distances

[tolgabirdal]

🚀 Feature

Could we please consider having a differentiable implementation of:
Fast Sinkhorn I: an O(n) Algorithm for the Wasserstein-1 Metric
Qichen Liao, Jing Chen, Zihao Wang, Bo Bai, Shi Jin, and Hao Wu
https://arxiv.org/pdf/2202.10042.pdf

Motivation

W-1 is used a lot in a variety applications like point cloud comparison. This paper claims to provide an accurate and fast implementation. O(N) complexity is theoretically optimal.

[youssef62]

Hello, I want to implement this. @rflamary Do you think this is an interesting contribution?
I am thinking of starting with the 1d case (for which the algorithm is explicitly explained in the paper).

[rflamary]

Yes this could be interesting as an entropic version of ot.lp.emd_1d. You might need to implement it in cython since there are may loops and i'm not sure the algorithm can be vectorized.

[youssef62]

Hello @rflamary, while working on this, I was wondering :
Why would it be an entropic version of ot.lp.emd_1d and not ot.wasserstein_1d? The former can compute the earth mover distance for many pointwise distances while the latter is for the p-norm distance. So the latter looks like a better interface for this contribution as the proposed algorithm works only for the $L_1$ distance.