Accelerating the Sinkhorn Algorithm for Sparse Multi-Marginal Optimal Transport via Fast Fourier Transforms

We consider the numerical solution of the discrete multi-marginal optimal transport (MOT) by means of the Sinkhorn algorithm. In general, the Sinkhorn algorithm suffers from the curse of dimensionality with respect to the number of marginals. If the MOT cost function decouples according to a tree or...

Full description

Saved in:
Bibliographic Details
Published in:Algorithms 2022-09, Vol.15 (9), p.311
Main Authors: Ba, Fatima Antarou, Quellmalz, Michael
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Complexity
Cost function
Entropy
fast Fourier transform
Fast Fourier transformations
image processing
Mathematical analysis
multi-marginal optimal transport
optimal transport
Optimization
Probability
Sinkhorn algorithm
Sparsity
Wasserstein barycenter
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the numerical solution of the discrete multi-marginal optimal transport (MOT) by means of the Sinkhorn algorithm. In general, the Sinkhorn algorithm suffers from the curse of dimensionality with respect to the number of marginals. If the MOT cost function decouples according to a tree or circle, its complexity is linear in the number of marginal measures. In this case, we speed up the convolution with the radial kernel required in the Sinkhorn algorithm via non-uniform fast Fourier methods. Each step of the proposed accelerated Sinkhorn algorithm with a tree-structured cost function has a complexity of O(KN) instead of the classical O(KN2) for straightforward matrix–vector operations, where K is the number of marginals and each marginal measure is supported on, at most, N points. In the case of a circle-structured cost function, the complexity improves from O(KN3) to O(KN2). This is confirmed through numerical experiments.
ISSN:1999-4893
1999-4893
DOI:10.3390/a15090311