Scaling algorithms for unbalanced optimal transport problems
From MaRDI portal
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.
Recommendations
- Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
- Iterative Bregman projections for regularized transportation problems
- Unnormalized optimal transport
- Eulerian models and algorithms for unbalanced optimal transport
- Computational optimal transport. With applications to data sciences
Cites work
- A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
- A finite-volume method for nonlinear nonlocal equations with a gradient flow structure
- A generalized model for optimal transport of images including dissipation and density modulation
- A JKO splitting scheme for Kantorovich-Fisher-Rao gradient flows
- A MACROSCOPIC CROWD MOTION MODEL OF GRADIENT FLOW TYPE
- A mixed finite element method for nonlinear diffusion equations
- A new optimal transport distance on the space of finite Radon measures
- A numerical algorithm for \(L_2\) semi-discrete optimal transport in 3D
- A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
- A sparse multiscale algorithm for dense optimal transport
- A survey of the Schrödinger problem and some of its connections with optimal transport
- An Algorithm for Restricted Least Squares Regression
- An augmented Lagrangian approach to Wasserstein gradient flows and applications
- An interpolating distance between optimal transport and Fisher-Rao metrics
- Assignment Problems
- Barycenters in the Wasserstein space
- Convergence of entropic schemes for optimal transport and gradient flows
- Convex color image segmentation with optimal transport distances
- Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
- Discretization of functionals involving the Monge-Ampère operator
- Duality and stability in extremum problems involving convex functions
- Duality Relationships for Entropy-Like Minimization Problems
- Dykstras algorithm with bregman projections: A convergence proof
- Entropic approximation of Wasserstein gradient flows
- Free boundaries in optimal transport and Monge-Ampère obstacle problems
- From the Schrödinger problem to the Monge-Kantorovich problem
- Generalized Wasserstein distance and its application to transport equations with source
- Gradient flows in metric spaces and in the space of probability measures
- Handling congestion in crowd motion modeling
- scientific article; zbMATH DE number 3582778 (Why is no real title available?)
- scientific article; zbMATH DE number 1174325 (Why is no real title available?)
- scientific article; zbMATH DE number 3001084 (Why is no real title available?)
- scientific article; zbMATH DE number 3296905 (Why is no real title available?)
- scientific article; zbMATH DE number 3099866 (Why is no real title available?)
- Integrals which are convex functionals
- Iterative Bregman projections for regularized transportation problems
- Kantorovich-Rubinstein Norm and Its Application in the Theory of Lipschitz Spaces
- Minkowski-type theorems and least-squares clustering
- Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
- On a Least Squares Adjustment of a Sampled Frequency Table When the Expected Marginal Totals are Known
- On Certain Contraction Mappings in a Partially Ordered Vector Space
- On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes
- On the ergodic convergence rates of a first-order primal-dual algorithm
- On the scaling of multidimensional matrices
- Optimal Transport
- Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
- Optimal transport for particle image velocimetry
- Optimal transport in competition with reaction: the Hellinger-Kantorovich distance and geodesic curves
- Optimal transport with proximal splitting
- Optimal transportation and applications. Lectures given at the C. I. M. E. summer school, Martina Franca, Italy, September 2--8, 2001
- Polar factorization and monotone rearrangement of vector‐valued functions
- Regularized regression and density estimation based on optimal transport
- Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
- The auction algorithm for the transportation problem
- The earth mover's distance as a metric for image retrieval
- THE GEOMETRY OF DISSIPATIVE EVOLUTION EQUATIONS: THE POROUS MEDIUM EQUATION
- The Hele-Shaw asymptotics for mechanical models of tumor growth
- The invisible hand algorithm: solving the assignment problem with statistical physics
- The optimal partial transport problem
- The Variational Formulation of the Fokker--Planck Equation
- Total Variation Projection With First Order Schemes
- Transport distances and geodesic convexity for systems of degenerate diffusion equations
- Tropical scaling of polynomial matrices
- Unbalanced optimal transport: dynamic and Kantorovich formulations
- Variational Analysis
Cited in
(99)- Unbalanced and partial \(L_1\) Monge-Kantorovich problem: a scalable parallel first-order method
- A transportation \(L^p\) distance for signal analysis
- Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm
- Ground metric learning on graphs
- A quotient space formulation for generative statistical analysis of graphical data
- Asymptotic distribution and convergence rates of stochastic algorithms for entropic optimal transportation between probability measures
- Transfer operators from optimal transport plans for coherent set detection
- Kantorovich-Rubinstein distance and barycenter for finitely supported measures: foundations and algorithms
- Generalized unnormalized optimal transport and its fast algorithms
- The square root normal field distance and unbalanced optimal transport
- Primal dual methods for Wasserstein gradient flows
- Hessian informed mirror descent
- An optimal transport approach for the Schrödinger bridge problem and convergence of Sinkhorn algorithm
- Unnormalized optimal transport
- The Schrödinger problem on the non-commutative Fisher-Rao space
- Entropic regularization of continuous optimal transport problems
- Aggregation-diffusion to constrained interaction: minimizers \& gradient flows in the slow diffusion limit
- The quadratic Wasserstein metric for earthquake location
- Traversing the Schrödinger bridge strait: Robert Fortet's marvelous proof redux
- A Wasserstein-Type Distance in the Space of Gaussian Mixture Models
- Barycenters for the Hellinger-Kantorovich distance over \(\mathbb{R}^d\)
- Eulerian models and algorithms for unbalanced optimal transport
- Vector and matrix optimal mass transport: theory, algorithm, and applications
- Optimal partial transport problem with Lagrangian costs
- Generalized Sinkhorn iterations for regularizing inverse problems using optimal mass transport
- An entropy minimization approach to second-order variational mean-field games
- Stochastic control liaisons. Richard Sinkhorn meets Gaspard Monge on a Schrödinger bridge
- Nonlinear model reduction on metric spaces. Application to one-dimensional conservative PDEs in Wasserstein spaces
- The Linearized Hellinger--Kantorovich Distance
- A superposition principle for the inhomogeneous continuity equation with Hellinger–Kantorovich-regular coefficients
- Supervised optimal transport
- Asymptotics for semidiscrete entropic optimal transport
- The Most Likely Evolution of Diffusing and Vanishing Particles: Schrödinger Bridges with Unbalanced Marginals
- Entropic Regularization of NonGradient Systems
- An unbalanced optimal transport splitting scheme for general advection-reaction-diffusion problems
- Dynamic models of Wasserstein-1-type unbalanced transport
- On the computation of Kantorovich-Wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows
- Geometry of graph partitions via optimal transport
- Discretization of flux-limited gradient flows: -convergence and numerical schemes
- Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
- Minimal convex extensions and finite difference discretisation of the quadratic Monge-Kantorovich problem
- Iterative Bregman projections for regularized transportation problems
- Learning to match via inverse optimal transport
- Convergence of entropic schemes for optimal transport and gradient flows
- A tumor growth model of Hele-Shaw type as a gradient flow
- The Wasserstein-Fisher-Rao Metric for Waveform Based Earthquake Location
- Graph-Based Equilibrium Metrics for Dynamic Supply–Demand Systems With Applications to Ride-sourcing Platforms
- Optimal transportation, modelling and numerical simulation
- Semi-discrete optimal transport: hardness, regularization and numerical solution
- A non-commutative entropic optimal transport approach to quantum composite systems at positive temperature
- A fast solver for generalized optimal transport problems based on dynamical system and algebraic multigrid
- Location Problems with Cutoff
- On the Convergence of Continuous and Discrete Unbalanced Optimal Transport Models for 1-Wasserstein Distance
- Square Root Normal Fields for Lipschitz Surfaces and the Wasserstein Fisher Rao Metric
- Toward a mathematical theory of trajectory inference
- Limit distributions and sensitivity analysis for empirical entropic optimal transport on countable spaces
- Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification
- Unbalanced multi-marginal optimal transport
- Matrix Balancing Based Interior Point Methods for Point Set Matching Problems
- Toric geometry of entropic regularization
- Dispersion-constrained martingale Schrödinger problems and the exact joint S\&P 500/VIX smile calibration puzzle
- Line planning for different demand periods
- Linearized optimal transport on manifolds
- Randomized methods for computing optimal transport without regularization and their convergence analysis
- A relaxation viewpoint to unbalanced optimal transport: duality, optimality and Monge formulation
- Graph-structured tensor optimization for nonlinear density control and mean field games
- Moment-SoS methods for optimal transport problems
- On the convergence of discrete dynamic unbalanced transport models
- Unbalanced optimal transport and maximum mean discrepancies: interconnections and rapid evaluation
- From optimal transport to discrepancy
- Distributionally robust optimization using optimal transport for Gaussian mixture models
- Positional relation contextual mixing for imbalanced classification
- Computation of Cournot-Nash equilibria by entropic regularization
- Interpolating between optimal transport and KL regularized optimal transport using Rényi divergences
- On a general matrix-valued unbalanced optimal transport problem
- Computing the distance between unbalanced distributions: the flat metric
- The double regularization method for capacity constrained optimal transport
- Computation of robust option prices via structured multimarginal martingale optimal transport
- Unbalanced optimal transport, from theory to numerics
- Optimal survival strategies for diffusive flows: a Schrödinger bridge approach to unbalanced transport
- Classification of symmetric attractors based on optimal transport theory
- Semi-unbalanced optimal transport for reference-based image restoration and synthesis
- Regularity theory and geometry of unbalanced optimal transport
- Partial transport for point-cloud registration
- Unbalanced Kantorovich-Rubinstein distance, plan, and barycenter on finite spaces: a statistical perspective
- Optimal transport on the Lie group of roto-translations
- Convergence of the Sinkhorn algorithm when the Schrödinger problem has no solution
- Supervised Gromov-Wasserstein optimal transport with metric-preserving constraints
- Synchronized optimal transport for joint modeling of dynamics across multiple spaces
- Sparsification techniques for large-scale optimal transport problems
- Domain decomposition for entropic unbalanced optimal transport
- Sharp convergence rates of empirical unbalanced optimal transport for spatio-temporal point processes
- Flows on measure spaces and applications in machine learning. Abstracts from the workshop held March 22--27, 2026
- LLOT: application of Laplacian linear optimal transport in spatial transcriptome reconstruction
- HV metric for time-domain full-waveform inversion
- Fisher information regularization schemes for Wasserstein gradient flows
- A mean field game model for the evolution of cities
- A new transportation distance with bulk/interface interactions and flux penalization
- Metrics and barycenters for point pattern data
This page was built for publication: Scaling algorithms for unbalanced optimal transport problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177709)
