# A fast approach to optimal transport: The back-and-forth method

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2019.

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

- [On amortizing convex conjugates for optimal transport](https://mlsanity.com/paper/2210.12153/) (2022)
- [Neural Optimal Transport with Lagrangian Costs](https://mlsanity.com/paper/2406.00288/) (2024)
- [Efficient Natural Gradient Descent Methods for Large-Scale PDE-Based Optimization Problems](https://mlsanity.com/paper/2202.06236/) (2022)
- [Tangential Wasserstein Projections](https://mlsanity.com/paper/2207.14727/) (2022)
- [Training Wasserstein GANs without gradient penalties](https://mlsanity.com/paper/2110.14150/) (2021)
- [Information Geometry of Wasserstein Statistics on Shapes and Affine Deformations](https://mlsanity.com/paper/2307.12508/) (2023)
- [Physics Informed Convex Artificial Neural Networks (PICANNs) for Optimal Transport based Density Estimation](https://mlsanity.com/paper/2104.01194/) (2021)
- [A new method for determining Wasserstein 1 optimal transport maps from Kantorovich potentials, with deep learning applications](https://mlsanity.com/paper/2211.00820/) (2022)
- [A Natural Primal-Dual Hybrid Gradient Method for Adversarial Neural Network Training on Solving Partial Differential Equations](https://mlsanity.com/paper/2411.06278/) (2024)
- [Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization](https://mlsanity.com/paper/2501.14635/) (2025)
- [Sobolev Gradient Ascent for Optimal Transport: Barycenter Optimization and Convergence Analysis](https://mlsanity.com/paper/2505.13660/) (2025)
- [Wasserstein Archetypal Analysis](https://mlsanity.com/paper/2210.14298/) (2022)
- [Collective Counterfactual Explanations: Balancing Individual Goals and Collective Dynamics](https://mlsanity.com/paper/2402.04579/) (2024)
- [Statistical Inference for Optimal Transport Maps: Recent Advances and Perspectives](https://mlsanity.com/paper/2506.19025/) (2025)
- [Sum-of-Squares Programming for Ma-Trudinger-Wang Regularity of Optimal Transport Maps](https://mlsanity.com/paper/2412.13372/) (2024)
- [Designing Algorithms for Entropic Optimal Transport from an Optimisation Perspective](https://mlsanity.com/paper/2507.12246/) (2025)

## Abstract (arXiv)

We present an iterative method to efficiently solve the optimal transportation problem for a class of strictly convex costs which includes quadratic and p-power costs. Given two probability measures supported on a discrete grid with n points, we compute the optimal map using O(n) storage space and O(n log(n)) operations per iteration, with an approximately exponential convergence rate. Our approach allows us to solve optimal transportation problems on spatial grids as large as 4096x4096 and 384x384x384 in a matter of minutes.