Semidual regularized optimal transport

DOI10.1137/18M1208654zbMATH Open1402.49037arXiv1811.05527WikidataQ128981351 ScholiaQ128981351MaRDI QIDQ4554909FDOQ4554909

Authors: Marco Cuturi, Gabriel Peyré 

Publication date: 12 November 2018

Published in: SIAM Review (Search for Journal in Brave)

Abstract: Variational problems that involve Wasserstein distances and more generally optimal transport (OT) theory are playing an increasingly important role in data sciences. Such problems can be used to form an examplar measure out of various probability measures, as in the Wasserstein barycenter problem, or to carry out parametric inference and density fitting, where the loss is measured in terms of an optimal transport cost to the measure of observations. Despite being conceptually simple, such problems are computationally challenging because they involve minimizing over quantities (Wasserstein distances) that are themselves hard to compute. Entropic regularization has recently emerged as an efficient tool to approximate the solution of such variational Wasserstein problems. In this paper, we give a thorough duality tour of these regularization techniques. In particular, we show how important concepts from classical OT such as c-transforms and semi-discrete approaches translate into similar ideas in a regularized setting. These dual formulations lead to smooth variational problems, which can be solved using smooth, differentiable and convex optimization problems that are simpler to implement and numerically more stable that their un-regularized counterparts. We illustrate the versatility of this approach by applying it to the computation of Wasserstein barycenters and gradient flows of spatial regularization functionals.

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

Recommendations

• A smoothed dual approach for variational Wasserstein problems
• A smoothed dual approach for variational Wasserstein problems
• Semi-discrete optimal transport: hardness, regularization and numerical solution
• Regularized regression and density estimation based on optimal transport
• Quadratically regularized optimal transport

zbMATH Keywords

convex optimizationoptimal transportgradient flowsWasserstein barycenterSinkhorn algorithmentropic regularization

Mathematics Subject Classification ID

Convex programming (90C25) Variational problems in a geometric measure-theoretic setting (49Q20) Computing methodologies for image processing (68U10) Regularity of solutions in optimal control (49N60) Existence theories for optimal control problems involving partial differential equations (49J20) Optimal stochastic control (93E20) Numerical approximation and computational geometry (primarily algorithms) (65D99)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• The earth mover's distance as a metric for image retrieval
• Title not available (Why is that?)
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• Convex analysis and monotone operator theory in Hilbert spaces
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Barycenters in the Wasserstein space
• Optimal Transport
• Clustering with Bregman divergences.
• Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
• Learning the parts of objects by non-negative matrix factorization
• The Wasserstein gradient flow of the Fisher information and the quantum drift-diffusion equation
• THE GEOMETRY OF DISSIPATIVE EVOLUTION EQUATIONS: THE POROUS MEDIUM EQUATION
• The Discontinuity Set of Solutions of the TV Denoising Problem and Some Extensions
• The Variational Formulation of the Fokker--Planck Equation
• On the numerical solution of the equation \(\frac{\partial ^ 2z\partial ^ 2z}{\partial x^ 2\partial y^ 2}-(\frac{\partial ^ 2z}{\partial x\partial y})^ 2=f\) and its discretizations. I
• Minkowski-type theorems and least-squares clustering
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• A class of Cartesian grid embedded boundary algorithms for incompressible flow with time-varying complex geometries
• Numerical methods for matching for teams and Wasserstein barycenters
• Power Diagrams: Properties, Algorithms and Applications
• Iterative Bregman projections for regularized transportation problems
• Sliced and Radon Wasserstein barycenters of measures
• A survey of the Schrödinger problem and some of its connections with optimal transport
• On the scaling of multidimensional matrices
• Convex variational image restoration with histogram priors
• Regularized regression and density estimation based on optimal transport
• A generalized model for optimal transport of images including dissipation and density modulation
• A fast algorithm for matrix balancing
• Tomographic reconstruction from a few views: a multi-marginal optimal transport approach
• A numerical algorithm for \(L_2\) semi-discrete optimal transport in 3D
• Asymptotic analysis of the exponential penalty trajectory in linear programming
• Entropic approximation of Wasserstein gradient flows
• Robust and scalable Bayes via a median of subset posterior measures
• Synthesizing and mixing stationary Gaussian texture models
• Regularized barycenters in the Wasserstein space
• A smoothed dual approach for variational Wasserstein problems
• Non-convex relaxation of optimal transport for color transfer between images
• Imaging with Kantorovich-Rubinstein discrepancy
• On the total variation Wasserstein gradient flow and the TV-JKO scheme

Cited In (27)

• Computational optimal transport. With applications to data sciences
• Optimal transport: discretization and algorithms
• Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems
• Generalized Sinkhorn iterations for regularizing inverse problems using optimal mass transport
• A geometric perspective on regularized optimal transport
• A smoothed dual approach for variational Wasserstein problems
• Efficient and exact multimarginal optimal transport with pairwise costs
• Regularized regression and density estimation based on optimal transport
• Semi-discrete optimal transport: hardness, regularization and numerical solution
• A smoothed dual approach for variational Wasserstein problems
• Bilevel optimization of the Kantorovich problem and its quadratic regularization. II: Convergence analysis
• Supervised optimal transport
• Fast entropic regularized optimal transport using semidiscrete cost approximation
• Regularization for Wasserstein distributionally robust optimization
• The total variation-Wasserstein problem: a new derivation of the Euler-Lagrange equations
• Positive and free energy satisfying schemes for diffusion with interaction potentials
• Iterative Bregman projections for regularized transportation problems
• Quadratically regularized optimal transport on graphs
• Quadratically regularized optimal transport
• Entropic regularization of continuous optimal transport problems
• A kernel formula for regularized Wasserstein proximal operators
• Domain decomposition for entropy regularized optimal transport
• Solving large-scale optimization problems with a convergence rate independent of grid size
• Regularized optimal transport and the rot mover's distance
• A geometric view of optimal transportation and generative model
• Computations of optimal transport distance with Fisher information regularization
• A multiscale analysis of multi-agent coverage control algorithms

Uses Software

• EMD

This page was built for publication: Semidual regularized optimal transport

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554909)