Iterative Bregman Projections for Regularized Transportation Problems

DOI10.1137/141000439zbMath1319.49073arXiv1412.5154OpenAlexW2036996178MaRDI QIDQ5254485

Luca Nenna, Gabriel Peyré, Marco Cuturi, Guillaume Carlier, Jean-David Benamou

Publication date: 9 June 2015

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.5154

zbMATH Keywords

convex optimizationincompressible Euler equationsoptimal transportWasserstein barycenterentropy regularizationiterative Bregman projections

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Numerical optimization and variational techniques (65K10) Numerical methods based on nonlinear programming (49M37) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Variational problems in a geometric measure-theoretic setting (49Q20) Existence theories for optimal control problems involving partial differential equations (49J20) Euler equations (35Q31)

Related Items (only showing first 100 items - show all)

The Wasserstein-Fisher-Rao Metric for Waveform Based Earthquake Location ⋮ Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems ⋮ Optimal transportation, modelling and numerical simulation ⋮ Regularization via Mass Transportation ⋮ Time-symmetric optimal stochastic control problems in space-time domains ⋮ Supervised Optimal Transport ⋮ Stochastic approximation versus sample average approximation for Wasserstein barycenters ⋮ Asymptotics for Semidiscrete Entropic Optimal Transport ⋮ Wasserstein Barycenters Are NP-Hard to Compute ⋮ Randomized Wasserstein Barycenter Computation: Resampling with Statistical Guarantees ⋮ Time discretizations of Wasserstein–Hamiltonian flows ⋮ Constrained overdamped Langevin dynamics for symmetric multimarginal optimal transportation ⋮ On the Linear Convergence of the Multimarginal Sinkhorn Algorithm ⋮ Semi-discrete optimal transport: hardness, regularization and numerical solution ⋮ Polynomial-time algorithms for multimarginal optimal transport problems with structure ⋮ Nonlinear Perron--Frobenius Theorems for Nonnegative Tensors ⋮ <scp>SISTA</scp>: Learning Optimal Transport Costs under Sparsity Constraints ⋮ Template-based CT reconstruction with optimal transport and total generalized variation ⋮ A fast solver for generalized optimal transport problems based on dynamical system and algebraic multigrid ⋮ Perturbation analysis of sub/super hedging problems ⋮ The GenCol Algorithm for High-Dimensional Optimal Transport: General Formulation and Application to Barycenters and Wasserstein Splines ⋮ Sliced optimal transport on the sphere ⋮ Weak Optimal Transport with Unnormalized Kernels ⋮ Wasserstein barycenter regression for estimating the joint dynamics of renewable and fossil fuel energy indices ⋮ Estimating pollution spread in water networks as a Schrödinger bridge problem with partial information ⋮ A family of pairwise multi-marginal optimal transports that define a generalized metric ⋮ The dynamical Schrödinger problem in abstract metric spaces ⋮ Sinkhorn Algorithm for Lifted Assignment Problems ⋮ Discrete Optimal Transport with Independent Marginals is #P-Hard ⋮ The method of randomized Bregman projections for stochastic feasibility problems ⋮ Unbalanced multi-marginal optimal transport ⋮ Learning to generate Wasserstein barycenters ⋮ Matrix Balancing Based Interior Point Methods for Point Set Matching Problems ⋮ Low-Rank Tensor Approximations for Solving Multimarginal Optimal Transport Problems ⋮ A graph space optimal transport distance as a generalization of L ^p distances: application to a seismic imaging inverse problem ⋮ Generalized Wasserstein barycenters between probability measures living on different subspaces ⋮ Quantitative stability of barycenters in the Wasserstein space ⋮ SAMPLING OF ONE-DIMENSIONAL PROBABILITY MEASURES IN THE CONVEX ORDER AND COMPUTATION OF ROBUST OPTION PRICE BOUNDS ⋮ Approximation of optimal transport problems with marginal moments constraints ⋮ Multilevel Optimal Transport: A Fast Approximation of Wasserstein-1 Distances ⋮ A Distributed Framework for the Construction of Transport Maps ⋮ Information Geometry for Regularized Optimal Transport and Barycenters of Patterns ⋮ Entropic-Wasserstein Barycenters: PDE Characterization, Regularity, and CLT ⋮ A Smoothed Dual Approach for Variational Wasserstein Problems ⋮ Convergence of Entropic Schemes for Optimal Transport and Gradient Flows ⋮ An introduction to continuous optimization for imaging ⋮ Turbulence of generalised flows in two dimensions ⋮ An entropic Landweber method for linear ill-posed problems ⋮ On the Existence of a Scalar Pressure Field in the Brödinger Problem ⋮ A Differential Approach to the Multi-Marginal Schrödinger System ⋮ Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems ⋮ The Escalator Boxcar Train Method for a System of Age-Structured Equations in the Space of Measures ⋮ The contractivity of cone-preserving multilinear mappings ⋮ Minimal convex extensions and finite difference discretisation of the quadratic Monge–Kantorovich problem ⋮ Quantum entropic regularization of matrix-valued optimal transport ⋮ Extended Mean Field Control Problems: Stochastic Maximum Principle and Transport Perspective ⋮ Minimal Geodesics Along Volume-Preserving Maps, Through Semidiscrete Optimal Transport ⋮ A tumor growth model of Hele-Shaw type as a gradient flow ⋮ Unnamed Item ⋮ Shared Prior Learning of Energy-Based Models for Image Reconstruction ⋮ The Linearized Hellinger--Kantorovich Distance ⋮ SCOTT: Shape-Location Combined Tracking with Optimal Transport ⋮ Empirical Regularized Optimal Transport: Statistical Theory and Applications ⋮ Inverse reflector design for a point source and far-field target ⋮ A mean field game model for the evolution of cities ⋮ A fixed-point approach to barycenters in Wasserstein space ⋮ Orlicz space regularization of continuous optimal transport problems ⋮ Applications of optimal transportation in the natural sciences. Abstracts from the workshop held February 21--27, 2021 (online meeting) ⋮ An efficient algorithm for matrix-valued and vector-valued optimal mass transport ⋮ A Framework for Wasserstein-1-Type Metrics ⋮ Quadratically Regularized Optimal Transport on Graphs ⋮ Entropic Approximation of Wasserstein Gradient Flows ⋮ Primal dual methods for Wasserstein gradient flows ⋮ Scaling algorithms for unbalanced optimal transport problems ⋮ Entropic and Displacement Interpolation: A Computational Approach Using the Hilbert Metric ⋮ Vector and Matrix Optimal Mass Transport: Theory, Algorithm, and Applications ⋮ Semidual Regularized Optimal Transport ⋮ A sparse multiscale algorithm for dense optimal transport ⋮ When optimal transport meets information geometry ⋮ Optimal transport problems regularized by generic convex functions: a geometric and algorithmic approach ⋮ Entropy-regularized 2-Wasserstein distance between Gaussian measures ⋮ Measure-Valued Spline Curves: An Optimal Transport Viewpoint ⋮ Approximate Wasserstein attraction flows for dynamic mass transport over networks ⋮ Stochastic saddle-point optimization for the Wasserstein barycenter problem ⋮ The Entropic Regularization of the Monge Problem on the Real Line ⋮ On the Wasserstein distance between mutually singular measures ⋮ Numerical solution of Monge-Kantorovich equations via a dynamic formulation ⋮ A proof of the Caffarelli contraction theorem via entropic regularization ⋮ About the analogy between optimal transport and minimal entropy ⋮ A second order equation for Schrödinger bridges with applications to the hot gas experiment and entropic transportation cost ⋮ Traversing the Schrödinger bridge strait: Robert Fortet's marvelous proof redux ⋮ PI-VAE: physics-informed variational auto-encoder for stochastic differential equations ⋮ The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation ⋮ Numerical analysis of a robust free energy diminishing finite volume scheme for parabolic equations with gradient structure ⋮ The Sinkhorn algorithm, parabolic optimal transport and geometric Monge-Ampère equations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A column generation approach to the discrete barycenter problem ⋮ Stochastic distance transform: theory, algorithms and applications ⋮ A spatial Pareto exchange economy problem

Uses Software

• EMD

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Numerical solution of the optimal transportation problem using the Monge-Ampère equation
• A survey of the Schrödinger problem and some of its connections with optimal transport
• Tomographic reconstruction from a few views: a multi-marginal optimal transport approach
• On the local structure of optimal measures in the multi-marginal optimal transportation problem
• The dual least action problem for an ideal, incompressible fluid
• Matching for teams
• Hedonic price equilibria, stable matching, and optimal transport: Equivalence, topology, and uniqueness
• The optimal partial transport problem
• Generalized solutions and hydrostatic approximation of the Euler equations
• Free boundaries in optimal transport and Monge-Ampère obstacle problems
• Geodesics in the space of measure-preserving maps and plans
• On pairs of multidimensional matrices
• An iterative procedure for obtaining I-projections onto the intersection of convex sets
• On the scaling of multidimensional matrices
• D//\(1AD_ 2 \)theorems for multidimensional matrices
• I-divergence geometry of probability distributions and minimization problems
• Asymptotic analysis of the exponential penalty trajectory in linear programming
• Numerical solution of the Monge--Ampère equation by a Newton's algorithm
• The earth mover's distance as a metric for image retrieval
• Convergence of the iterative proportional fitting procedure
• A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
• An iterative procedure for general probability measures to obtain \(I\)-projections onto intersections of convex sets
• Concerning nonnegative matrices and doubly stochastic matrices
• Dykstras algorithm with bregman projections: A convergence proof
• Optimal Transport with Proximal Splitting
• Synthesizing and Mixing Stationary Gaussian Texture Models
• A Mumford–Shah-Like Method for Limited Data Tomography with an Application to Electron Tomography
• Uniqueness and Monge Solutions in the Multimarginal Optimal Transportation Problem
• Barycenters in the Wasserstein Space
• An Algorithm for Restricted Least Squares Regression
• THE MULTI-MARGINAL OPTIMAL PARTIAL TRANSPORT PROBLEM
• Numerical methods for matching for teams and Wasserstein barycenters
• The Least Action Principle and the Related Concept of Generalized Flows for Incompressible Perfect Fluids
• Assignment Problems
• Minimal geodesics on groups of volume-preserving maps and generalized solutions of the Euler equations
• Optimal maps for the multidimensional Monge-Kantorovich problem
• Density Functional Theory and Optimal Transportation with Coulomb Cost
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• Optimal transportation with capacity constraints
• Estimating Nonnegative Matrices from Marginal Data
• Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
• On a Least Squares Adjustment of a Sampled Frequency Table When the Expected Marginal Totals are Known

This page was built for publication: Iterative Bregman Projections for Regularized Transportation Problems