• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

Iterative Bregman Projections for Regularized Transportation Problems

Benamou, Jean-David; Carlier, Guillaume; Cuturi, Marco; Nenna, Luca; Peyré, Gabriel (2015), Iterative Bregman Projections for Regularized Transportation Problems, SIAM Journal on Scientific Computing, 37, 2, p. A1111–A1138. 10.1137/141000439

Type
Article accepté pour publication ou publié
External document link
https://arxiv.org/abs/1412.5154v1
Date
2015
Journal name
SIAM Journal on Scientific Computing
Volume
37
Number
2
Publisher
SIAM - Society for Industrial and Applied Mathematics
Published in
Paris
Pages
A1111–A1138
Publication identifier
10.1137/141000439
Metadata
Show full item record
Author(s)
Benamou, Jean-David
Carlier, Guillaume
Cuturi, Marco
Nenna, Luca
Peyré, Gabriel
Abstract (EN)
This article details a general numerical framework to approximate so-lutions to linear programs related to optimal transport. The general idea is to introduce an entropic regularization of the initial linear program. This regularized problem corresponds to a Kullback-Leibler Bregman di-vergence projection of a vector (representing some initial joint distribu-tion) on the polytope of constraints. We show that for many problems related to optimal transport, the set of linear constraints can be split in an intersection of a few simple constraints, for which the projections can be computed in closed form. This allows us to make use of iterative Bregman projections (when there are only equality constraints) or more generally Bregman-Dykstra iterations (when inequality constraints are in-volved). We illustrate the usefulness of this approach to several variational problems related to optimal transport: barycenters for the optimal trans-port metric, tomographic reconstruction, multi-marginal optimal trans-port and in particular its application to Brenier's relaxed solutions of in-compressible Euler equations, partial un-balanced optimal transport and optimal transport with capacity constraints.
Subjects / Keywords
Kullback-Leibler Bregman divergence projection; Transportation Problems; Iterative Bregman Projections

Related items

Showing items related by title and author.

  • Thumbnail
    A Numerical Method to Solve Multi-Marginal Optimal Transport Problems with Coulomb Cost 
    Benamou, Jean-David; Carlier, Guillaume; Nenna, Luca (2017) Chapitre d'ouvrage
  • Thumbnail
    Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm 
    Benamou, Jean-David; Carlier, Guillaume; Nenna, Luca (2019) Article accepté pour publication ou publié
  • Thumbnail
    An entropy minimization approach to second-order variational mean-field games 
    Benamou, Jean-David; Carlier, Guillaume; Marino, Simone; Nenna, Luca (2019) Article accepté pour publication ou publié
  • Thumbnail
    Augmented Lagrangian Methods for Transport Optimization, Mean Field Games and Degenerate Elliptic Equations 
    Benamou, Jean-David; Carlier, Guillaume (2015) Article accepté pour publication ou publié
  • Thumbnail
    A numerical solution to Monge's problem with a Finsler distance as cost 
    Benamou, Jean-David; Carlier, Guillaume; Hatchi, Roméo (2018) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo