Volume 58, pp. 289-315, 2023.

Nonequispaced Fast Fourier Transform Boost for the Sinkhorn Algorithm

Rajmadan Lakshmanan, Alois Pichler, and Daniel Potts

Abstract

This contribution features an accelerated computation of Sinkhorn's algorithm, which approximates the Wasserstein transportation distance, by employing nonequispaced fast Fourier transforms (NFFT). The proposed algorithm allows approximations of the Wasserstein distance by involving not more than $\mathcal{O}(n\log n)$ operations for probability measures supported by $n$ points. Furthermore, the proposed method avoids expensive allocations of the characterizing matrices. With this numerical acceleration, the transportation distance is accessible to probability measures out of reach so far. Numerical experiments using synthetic and real data affirm the computational advantage and superiority.

Full Text (PDF) [1.4 MB], BibTeX , DOI: 10.1553/etna_vol58s289

Key words

Sinkhorn's divergence, optimal transport, NFFT, entropy

AMS subject classifications

90C08, 90C15, 60G07