# A Fast and Accurate Splitting Method for Optimal Transport: Analysis and Implementation

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 35 references that are in the map.
- First posted on arXiv 22 Oct 2021.

## Builds on (most cited first, 12 of 12)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [OSQP: An Operator Splitting Solver for Quadratic Programs](https://mlsanity.com/paper/1711.08013/) (2017)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [Screening Sinkhorn Algorithm for Regularized Optimal Transport](https://mlsanity.com/paper/1906.08540/) (2019)
- [Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness](https://mlsanity.com/paper/2105.12715/) (2021)
- [Nonsmoothness in Machine Learning: specific structure, proximal identification, and applications](https://mlsanity.com/paper/2010.00848/) (2020)
- [COSMO: A conic operator splitting method for convex conic problems](https://mlsanity.com/paper/1901.10887/) (2019)
- [Projecting onto rectangular matrices with prescribed row and column sums](https://mlsanity.com/paper/2105.12222/) (2021)

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

- [A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2303.06595/) (2023)
- [Bringing regularized optimal transport to lightspeed: a splitting method adapted for GPUs](https://mlsanity.com/paper/2305.18483/) (2023)
- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)
- [Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2205.08115/) (2022)
- [TSENOR: Highly-Efficient Algorithm for Finding Transposable N:M Sparse Masks](https://mlsanity.com/paper/2505.23949/) (2025)
- [Finding Structure in Continual Learning](https://mlsanity.com/paper/2602.04555/) (2026)
- [Task Switching Without Forgetting via Proximal Decoupling](https://mlsanity.com/paper/2604.18857/) (2026)
- [Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory](https://mlsanity.com/paper/2609.33814/) (2026)
- [GPU-Accelerated Bregman Douglas-Rachford Splitting for Discrete Optimal Transport](https://mlsanity.com/paper/2610.04715/) (2026)

## Abstract (arXiv)

We develop a fast and reliable method for solving large-scale optimal transport (OT) problems at an unprecedented combination of speed and accuracy. Built on the celebrated Douglas-Rachford splitting technique, our method tackles the original OT problem directly instead of solving an approximate regularized problem, as many state-of-the-art techniques do. This allows us to provide sparse transport plans and avoid numerical issues of methods that use entropic regularization. The algorithm has the same cost per iteration as the popular Sinkhorn method, and each iteration can be executed efficiently, in parallel. The proposed method enjoys an iteration complexity O(1/ε) compared to the best-known O(1/ε2) of the Sinkhorn method. In addition, we establish a linear convergence rate for our formulation of the OT problem. We detail an efficient GPU implementation of the proposed method that maintains a primal-dual stopping criterion at no extra cost. Substantial experiments demonstrate the effectiveness of our method, both in terms of computation times and robustness.