![]() |
![]() |
ETNA - Electronic Transactions on Numerical Analysis
|
![]() |
Verlag der Österreichischen Akademie der Wissenschaften Austrian Academy of Sciences Press
A-1011 Wien, Dr. Ignaz Seipel-Platz 2
Tel. +43-1-515 81/DW 3420, Fax +43-1-515 81/DW 3400 https://verlag.oeaw.ac.at, e-mail: verlag@oeaw.ac.at |
![]() |
|
DATUM, UNTERSCHRIFT / DATE, SIGNATURE
BANK AUSTRIA CREDITANSTALT, WIEN (IBAN AT04 1100 0006 2280 0100, BIC BKAUATWW), DEUTSCHE BANK MÜNCHEN (IBAN DE16 7007 0024 0238 8270 00, BIC DEUTDEDBMUC)
|
ETNA - Electronic Transactions on Numerical Analysis, pp. 289-315, 2023/03/23
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.
Keywords: Sinkhorn's divergence, optimal transport, NFFT, entropy