Scaling Algorithms for Unbalanced Transport Problems

Abstract

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.

References in corpus (4)

• A Sparse Multi-Scale Algorithm for Dense Optimal Transport
• An Interpolating Distance between Optimal Transport and Fisher-Rao
• Convex Color Image Segmentation with Optimal Transport Distances
• Discretization of functionals involving the Monge-Ampère operator

Cited by in corpus (31)

• Sinkhorn Divergences for Unbalanced Optimal Transport
• The quadratic Wasserstein metric for earthquake location
• Nonlinear model reduction on metric spaces. Application to one-dimensional conservative PDEs in Wasserstein spaces
• Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation
• On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm
• Wasserstein regularization for sparse multi-task regression
• Ground Metric Learning on Graphs
• Debiased Sinkhorn barycenters
• Scalable Unbalanced Optimal Transport using Generative Adversarial Networks
• The data-driven Schroedinger bridge
• Adaptive Similar Triangles Method: a Stable Alternative to Sinkhorn's Algorithm for Regularized Optimal Transport
• A superposition principle for the inhomogeneous continuity equation with Hellinger-Kantorovich-regular coefficients
• On the Computation of Kantorovich-Wasserstein Distances between 2D-Histograms by Uncapacitated Minimum Cost Flows
• Optimal Transport losses and Sinkhorn algorithm with general convex regularization
• Distributional Sliced-Wasserstein and Applications to Generative Modeling
• Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Support
• Gini-regularized Optimal Transport with an Application to Spatio-Temporal Forecasting
• Spatio-Temporal Alignments: Optimal transport through space and time
• Computing Kantorovich-Wasserstein Distances on $d$-dimensional histograms using $(d+1)$-partite graphs
• Parallel Unbalanced Optimal Transport Regularization for Large Scale Imaging Problems
• Stochastic control liaisons: Richard Sinkhorn meets Gaspard Monge on a Schroedinger bridge
• A Transportation $L^p$ Distance for Signal Analysis
• Traversing the Schroedinger Bridge strait: Robert Fortet's marvelous proof redux
• Minimal convex extensions and finite difference discretization of the quadratic Monge-Kantorovich problem
• Computation of Cournot-Nash equilibria by entropic regularization
• Aggregation-Diffusion to Constrained Interaction: Minimizers & Gradient Flows in the Slow Diffusion Limit
• Group level MEG/EEG source imaging via optimal transport: minimum Wasserstein estimates
• Distributionally-Constrained Policy Optimization via Unbalanced Optimal Transport
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity
• Dual Regularized Optimal Transport
• Relaxed Schroedinger bridges and robust network routing