# Accelerating the Sinkhorn algorithm for sparse multi-marginal optimal transport by fast Fourier transforms

arXiv: https://arxiv.org/abs/2208.03120 · HTML: https://mlsanity.com/paper/2208.03120/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2022.

## Built on by (most cited first, 5 of 5)

- [Path Structured Multimarginal Schr"odinger Bridge for Probabilistic Learning of Hardware Resource Usage by Control Software](https://mlsanity.com/paper/2310.00604/) (2023)
- [Stochastic Learning of Computational Resource Usage as Graph Structured Multimarginal Schr"odinger Bridge](https://mlsanity.com/paper/2405.12463/) (2024)
- [Neural Estimation for Scaling Entropic Multimarginal Optimal Transport](https://mlsanity.com/paper/2506.00573/) (2025)
- [Soft Quantization using Entropic Regularization](https://mlsanity.com/paper/2309.04428/) (2023)
- [HOT-POT: Optimal Transport for Sparse Stereo Matching](https://mlsanity.com/paper/2601.12423/) (2026)

## Abstract (arXiv)

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 by non-uniform fast Fourier methods. Each step of the proposed accelerated Sinkhorn algorithm with a tree-structured cost function has a complexity of mathcal O(K N) instead of the classical mathcal O(K N2) for straightforward matrix-vector operations, where K is the number of marginals and each marginal measure is supported on at most N points. In case of a circle-structured cost function, the complexity improves from mathcal O(K N3) to mathcal O(K N2). This is confirmed by numerical experiments.