# Nonequispaced Fast Fourier Transform Boost for the Sinkhorn Algorithm

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

## Key facts

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

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

- [Fast rigid alignment of heterogeneous images in sliced Wasserstein distance](https://mlsanity.com/paper/2503.13756/) (2025)
- [A Sinkhorn-type Algorithm for Constrained Optimal Transport](https://mlsanity.com/paper/2403.05054/) (2024)
- [Soft Quantization using Entropic Regularization](https://mlsanity.com/paper/2309.04428/) (2023)
- [FlashSinkhorn 2: Block-Sparse Entropic Optimal Transport](https://mlsanity.com/paper/2610.02395/) (2026)

## Abstract (arXiv)

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 mathcal O(nlog 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.