# Scaling Algorithms for Unbalanced Transport Problems

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

## Key facts

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

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

- [Unbalanced Optimal Transport, from Theory to Numerics](https://mlsanity.com/paper/2211.08775/) (2022)
- [Unbalanced Feature Transport for Exemplar-based Image Translation](https://mlsanity.com/paper/2106.10482/) (2021)
- [GMLight: Lighting Estimation via Geometric Distribution Approximation](https://mlsanity.com/paper/2102.10244/) (2021)
- [SCOOP: Self-Supervised Correspondence and Optimization-Based Scene Flow](https://mlsanity.com/paper/2211.14020/) (2022)
- [Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe](https://mlsanity.com/paper/2201.00730/) (2022)
- [Sparse Needlets for Lighting Estimation with Spherical Transport Loss](https://mlsanity.com/paper/2106.13090/) (2021)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity](https://mlsanity.com/paper/2108.07992/) (2021)
- [On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods](https://mlsanity.com/paper/2312.13970/) (2023)
- [Unbalanced Optimal Transport for Unbalanced Word Alignment](https://mlsanity.com/paper/2306.04116/) (2023)
- [Optimal Transport on the Lie Group of Roto-translations](https://mlsanity.com/paper/2402.15322/) (2024)
- [USIGAN: Unbalanced Self-Information Feature Transport for Weakly Paired Image IHC Virtual Staining](https://mlsanity.com/paper/2507.05843/) (2025)
- [Averaging Spatio-temporal Signals using Optimal Transport and Soft Alignments](https://mlsanity.com/paper/2203.05813/) (2022)
- [PROTOCOL: Partial Optimal Transport-enhanced Contrastive Learning for Imbalanced Multi-view Clustering](https://mlsanity.com/paper/2506.12408/) (2025)
- [Beyond Continuity: Simulation-free Reconstruction of Discrete Branching Dynamics from Single-cell Snapshots](https://mlsanity.com/paper/2605.00545/) (2026)
- [Distributionally-Constrained Policy Optimization via Unbalanced Optimal Transport](https://mlsanity.com/paper/2102.07889/) (2021)
- [On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gaps](https://mlsanity.com/paper/2205.13846/) (2022)
- [Biomechanical-phase based Temporal Segmentation in Sports Videos: a Demonstration on Javelin-Throw](https://mlsanity.com/paper/2509.24606/) (2025)
- [Reweighted Flow Matching via Unbalanced OT for Label-free Long-tailed Generation](https://mlsanity.com/paper/2509.25713/) (2025)
- [Robust Sublinear Convergence Rates for Iterative Bregman Projections](https://mlsanity.com/paper/2602.01372/) (2026)
- [TransSplat: Unbalanced Semantic Transport for Language-Driven 3DGS Editing](https://mlsanity.com/paper/2604.19571/) (2026)
- [Bridging Vision and Language Concepts through Optimal Transport Semantic Flow](https://mlsanity.com/paper/2606.26891/) (2026)
- [Benchmarking Clinical Decision Pathway Adherence in Large Language Models](https://mlsanity.com/paper/2608.26592/) (2026)
- [Safe Screening for Unbalanced Optimal Transport](https://mlsanity.com/paper/2307.00247/) (2023)
- [Randomized Transport Plans via Hierarchical Fully Probabilistic Design](https://mlsanity.com/paper/2408.02701/) (2024)
- [On Barycenter Computation: Semi-Unbalanced Optimal Transport-based Method on Gaussians](https://mlsanity.com/paper/2410.08117/) (2024)
- [New Insights into Optimal Alignment of Acoustic and Linguistic Representations for Knowledge Transfer in ASR](https://mlsanity.com/paper/2509.05609/) (2025)
- [Accelerated Sinkhorn Algorithms for Partial Optimal Transport](https://mlsanity.com/paper/2601.17196/) (2026)
- [Grammatical Error Correction Evaluation by Optimally Transporting Edit Representation](https://mlsanity.com/paper/2602.05419/) (2026)
- [Unbalanced Optimal Transport Dictionary Learning for Unsupervised Hyperspectral Image Clustering](https://mlsanity.com/paper/2603.10132/) (2026)

## Abstract (arXiv)

This article introduces a new class of fast algorithms to approximate variational problems involving unbalanced optimal transport. While classical optimal transport considers only normalized probability distributions, it is important for many applications to be able to compute some sort of relaxed transportation between arbitrary positive measures. A generic class of such "unbalanced" optimal transport problems has been recently proposed by several authors. In this paper, we show how to extend the, now classical, entropic regularization scheme to these unbalanced problems. This gives rise to fast, highly parallelizable algorithms that operate by performing only diagonal scaling (i.e. pointwise multiplications) of the transportation couplings. They are generalizations of the celebrated Sinkhorn algorithm. We show how these methods can be used to solve unbalanced transport, unbalanced gradient flows, and to compute unbalanced barycenters. We showcase applications to 2-D shape modification, color transfer, and growth models.