# Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems

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

## Key facts

- Cited by 73 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2016.

## Built on by (most cited first, 30 of 73)

- [Conditional Adapters: Parameter-efficient Transfer Learning with Fast Inference](https://mlsanity.com/paper/2304.04947/) (2023)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Accurate Point Cloud Registration with Robust Optimal Transport](https://mlsanity.com/paper/2111.00648/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Using Optimal Transport as Alignment Objective for fine-tuning Multilingual Contextualized Embeddings](https://mlsanity.com/paper/2110.02887/) (2021)
- [Wassmap: Wasserstein Isometric Mapping for Image Manifold Learning](https://mlsanity.com/paper/2204.06645/) (2022)
- [Unbalanced Optimal Transport: A Unified Framework for Object Detection](https://mlsanity.com/paper/2307.02402/) (2023)
- [Learning Revenue-Maximizing Auctions With Differentiable Matching](https://mlsanity.com/paper/2106.07877/) (2021)
- [Rethinking Initialization of the Sinkhorn Algorithm](https://mlsanity.com/paper/2206.07630/) (2022)
- [Fast and Scalable Optimal Transport for Brain Tractograms](https://mlsanity.com/paper/2107.02010/) (2021)
- [Lower Complexity Adaptation for Empirical Entropic Optimal Transport](https://mlsanity.com/paper/2306.13580/) (2023)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [FlashSinkhorn: IO-Aware Entropic Optimal Transport on GPU](https://mlsanity.com/paper/2602.03067/) (2026)
- [Differentiable Transportation Pruning](https://mlsanity.com/paper/2307.08483/) (2023)
- [Progressive Entropic Optimal Transport Solvers](https://mlsanity.com/paper/2406.05061/) (2024)
- [OTSeg: Multi-prompt Sinkhorn Attention for Zero-Shot Semantic Segmentation](https://mlsanity.com/paper/2403.14183/) (2024)
- [An Exploration of Learnt Representations of W Jets](https://mlsanity.com/paper/2109.10919/) (2021)
- [Hilbert's projective metric for functions of bounded growth and exponential convergence of Sinkhorn's algorithm](https://mlsanity.com/paper/2311.04041/) (2023)
- [Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients](https://mlsanity.com/paper/2307.08507/) (2023)
- [Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing](https://mlsanity.com/paper/2408.11620/) (2024)
- [Calibrating Expressions of Certainty](https://mlsanity.com/paper/2410.04315/) (2024)
- [Learning to Generate Wasserstein Barycenters](https://mlsanity.com/paper/2102.12178/) (2021)
- [Unbalanced CO-Optimal Transport](https://mlsanity.com/paper/2205.14923/) (2022)
- [Manifold learning in Wasserstein space](https://mlsanity.com/paper/2311.08549/) (2023)
- [A Truncated Newton Method for Optimal Transport](https://mlsanity.com/paper/2504.02067/) (2025)
- [Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport](https://mlsanity.com/paper/2110.12678/) (2021)
- [Partial Wasserstein Adversarial Network for Non-rigid Point Set Registration](https://mlsanity.com/paper/2203.02227/) (2022)
- [PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport](https://mlsanity.com/paper/2502.03749/) (2025)
- [Order Constraints in Optimal Transport](https://mlsanity.com/paper/2110.07275/) (2021)
- [Structure-Aware E(3)-Invariant Molecular Conformer Aggregation Networks](https://mlsanity.com/paper/2402.01975/) (2024)

## Abstract (arXiv)

Scaling algorithms for entropic transport-type problems have become a very popular numerical method, encompassing Wasserstein barycenters, multi-marginal problems, gradient flows and unbalanced transport. However, a standard implementation of the scaling algorithm has several numerical limitations: the scaling factors diverge and convergence becomes impractically slow as the entropy regularization approaches zero. Moreover, handling the dense kernel matrix becomes unfeasible for large problems. To address this, we combine several modifications: A log-domain stabilized formulation, the well-known epsilon-scaling heuristic, an adaptive truncation of the kernel and a coarse-to-fine scheme. This permits the solution of larger problems with smaller regularization and negligible truncation error. A new convergence analysis of the Sinkhorn algorithm is developed, working towards a better understanding of epsilon-scaling. Numerical examples illustrate efficiency and versatility of the modified algorithm.