Tree-Sliced Approximation of Wasserstein Distances
share
Optimal transport () theory provides a useful set of tools to compare probability distributions. As a consequence, the field of is gaining traction and interest within the machine learning community. A few deficiencies usually associated with include its high computational complexity when comparing discrete measures, which is quadratic when approximating it through entropic regularization; or supercubic when solving it exactly. For some applications, the fact that distances are not usually negative definite also means that they cannot be used with usual Hilbertian tools. In this work, we consider a particular family of ground metrics, namely tree metrics, which yield negative definite metrics that can be computed in linear time. By averaging over randomly sampled tree metrics, we obtain a tree-sliced-Wasserstein distance. We illustrate that the proposed tree-sliced-Wasserstein distances compare favorably with other baselines on various benchmark datasets.
READ FULL TEXT