Nonequispaced fast Fourier transform boost for the Sinkhorn algorithm

DOI10.1553/ETNA_VOL58S289MaRDI QIDQ6105414zbMATH OpenFDO

Authors R. Lakshmanan, Alois Pichler, Daniel Potts

Publication date 9 June 2023

Published in ETNA - Electronic Transactions on Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.07524, http://etna.mcs.kent.edu/volumes/2021-2030/vol58/abstract.php?vol=58&pages=289-315

zbMATH Keywords

entropyoptimal transportNFFTSinkhorn's divergence

Mathematics Subject Classification ID

Stochastic programming (90C15) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) General theory of stochastic processes (60G07)

Abstract: This contribution features an accelerated computation of the Sinkhorn's algorithm, which approximates the Wasserstein transportation distance, by employing nonequispaced fast Fourier transforms (NFFT). The algorithm proposed allows approximations of the Wasserstein distance by involving not more than $mathcalO(nlogn)$ 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.

Recommendations

• Fast Sinkhorn. I: An \(O(N)\) algorithm for the Wasserstein-1 metric
• Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
• Algorithms for optimal transport and Wasserstein distances
• A hierarchically low-rank optimal transport dissimilarity measure for structured data
• Optimal transport: fast probabilistic approximation with exact solvers

Cites work

• scientific article; zbMATH DE number 1909499 (Why is no real title available?)
• Concerning nonnegative matrices and doubly stochastic matrices
• Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
• Efficient numerical methods for entropy-linear programming problems
• Facial recognition using tensor-tensor decompositions
• Foundations of quantization for probability distributions
• Hierarchical clustering with optimal transport
• Impossibility of fast stable approximation of analytic functions from equispaced samples
• Matrix scaling by network flow
• Numerical Fourier analysis
• On the complexity of general matrix scaling and entropy minimization via the RAS algorithm
• Optimal Transport
• Optimal transport with proximal splitting
• Separability and completeness for the Wasserstein distance
• Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems

Cited in

(6)

• Fast Sinkhorn. I: An \(O(N)\) algorithm for the Wasserstein-1 metric
• Unbalanced optimal transport and maximum mean discrepancies: interconnections and rapid evaluation
• Fast sinkhorn. II: Collinear triangular matrix and linear time accurate computation of optimal transport
• Accurate pairwise convolutions of non-negative vectors via FFT
• Approximation and interpolation of singular measures by trigonometric polynomials
• Tree approximation of scenario processes for multistage stochastic optimization: algorithms and fast implementations

This page was built for publication: Nonequispaced fast Fourier transform boost for the Sinkhorn algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6105414)