Sinkhorn distances

[bkj]

In this followup paper the authors talk about using Sinkhorn distances to reduce complexity from O(dim ** 3 * log(dim)) to O(nnz ** 2).

Does this library use this Sinkhorn trick? Or, if not, do you have any ideas on how it might compare to the SInkhorn trick in terms of runtime?

Thanks!
~ Ben

[zdk123]

The matlab code for the linked paper is here: https://github.com/gaohuang/S-WMD (although they don't specify a license).

I would definitely be interested in a python/OR-tools-based implementation

[vmarkovtsev]

Whoa, I completely missed this! Thanks for the suggestions, I need to take a look.

[ajbouh]

I enjoyed this talk about sWMD: https://channel9.msdn.com/Events/Neural-Information-Processing-Systems-Conference/Neural-Information-Processing-Systems-Conference-NIPS-2016/Supervised-Word-Movers-Distance

I also came across this Python implementation of sWMD: https://github.com/ByronPan/sWMD

@vmarkovtsev, any updated thoughts about how much work it'd be to extend the approach taken here in wmd-relax?