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

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, A transportation \(L^p\) distance for signal analysis, Convergence rate of general entropic optimal transport costs, A multi-objective interpretation of optimal transport, Entropy martingale optimal transport and nonlinear pricing-hedging duality, Geodesic PCA versus Log-PCA of Histograms in the Wasserstein Space, Wide consensus aggregation in the Wasserstein space. Application to location-scatter families, Displacement Interpolation Using Monotone Rearrangement, An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems, Simple approximative algorithms for free-support Wasserstein barycenters, An optimal transport approach for the Schrödinger bridge problem and convergence of Sinkhorn algorithm, Characterization of barycenters in the Wasserstein space by averaging optimal transport maps, Crowd motion and evolution PDEs under density constraints, Wasserstein discriminant analysis, Misfit function for full waveform inversion based on the Wasserstein metric with dynamic formulation, Elements of Statistical Inference in 2-Wasserstein Space, Entropic regularization of continuous optimal transport problems, Optimal partial transport problem with Lagrangian costs, Sampling of probability measures in the convex order by Wasserstein projection, Alternating minimization methods for strongly convex optimization, 3/4-Discrete Optimal Transport, Optimal transport: discretization and algorithms, Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm, Fréchet means and Procrustes analysis in Wasserstein space, On Geometric Prototype and Applications, Computation of Cournot-Nash equilibria by entropic regularization, Tomographic reconstruction from a few views: a multi-marginal optimal transport approach, Variational methods for tomographic reconstruction with few views, Incorporation of a deformation prior in image reconstruction, Projection-based reduced order models for a cut finite element method in parametrized domains, Towards a central limit theorem in the Wasserstein space?, Computation of optimal transport and related hedging problems via penalization and neural networks, Unnamed Item, On the computational complexity of finding a sparse Wasserstein barycenter, Wasserstein Dictionary Learning: Optimal Transport-Based Unsupervised Nonlinear Dictionary Learning, Generalized Sinkhorn Iterations for Regularizing Inverse Problems Using Optimal Mass Transport, Ground metric learning on graphs, Fast Entropic Regularized Optimal Transport Using Semidiscrete Cost Approximation, A Smoothed Dual Approach for Variational Wasserstein Problems, Convolutional wasserstein distances, On the computation of Wasserstein barycenters, Around the entropic talagrand inequality, Small noise limit and convexity for generalized incompressible flows, Schrödinger problems, and optimal transport, Clustering patterns connecting COVID-19 dynamics and human mobility using optimal transport, Generalized compressible flows and solutions of the \(H(\text{div})\) geodesic problem, Computational methods for martingale optimal transport problems, Optimal transport, mean partition, and uncertainty assessment in cluster analysis, Multi-species optimal transportation, An entropy minimization approach to second-order variational mean-field games, On clustering uncertain and structured data with Wasserstein barycenters and a geodesic criterion for the number of clusters, Geometry-Sensitive Ensemble Mean Based on Wasserstein Barycenters: Proof-of-Concept on Cloud Simulations, Causal optimal transport and its links to enlargement of filtrations and continuous-time stochastic optimization, Reduced-order model for the BGK equation based on POD and optimal transport, Hardness results for multimarginal optimal transport problems, Algorithm for Hamilton-Jacobi equations in density space via a generalized Hopf formula, Robust Pricing and Hedging of Options on Multiple Assets and Its Numerics, Applications of weak transport theory, Stochastic Control Liaisons: Richard Sinkhorn Meets Gaspard Monge on a Schrödinger Bridge, Second-order models for optimal transport and cubic splines on the Wasserstein Space, Robust clustering tools based on optimal transportation, Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem, Kantorovich-Rubinstein distance and barycenter for finitely supported measures: foundations and algorithms, A hierarchically low-rank optimal transport dissimilarity measure for structured data, Entropic optimal transport: geometry and large deviations

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