IMPORTANT NOTICE

The AMS website will be down for maintenance on May 23 between 6:00am - 8:00am EDT. For questions please contact AMS Customer Service at cust-serv@ams.org or (800) 321-4267 (U.S. & Canada), (401) 455-4000 (Worldwide).

 

Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Scaling algorithms for unbalanced optimal transport problems


Authors: Lénaïc Chizat, Gabriel Peyré, Bernhard Schmitzer and François-Xavier Vialard
Journal: Math. Comp.
MSC (2010): Primary 90C25; Secondary 65K10, 68U10
DOI: https://doi.org/10.1090/mcom/3303
Published electronically: February 6, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C25, 65K10, 68U10

Retrieve articles in all journals with MSC (2010): 90C25, 65K10, 68U10


Additional Information

Lénaïc Chizat
Affiliation: CEREMADE, CNRS, Université Paris-Dauphine, INRIA Project team Mokaplan, France
Email: chizat@ceremade.dauphine.fr

Gabriel Peyré
Affiliation: CNRS and DMA, École Normale Supérieure, INRIA Project team Mokaplan, France
Email: gabriel.peyre@ens.fr

Bernhard Schmitzer
Affiliation: CEREMADE, CNRS, Université Paris-Dauphine, INRIA Project team Mokaplan, France
Email: schmitzer@ceremade.dauphine.fr

François-Xavier Vialard
Affiliation: CEREMADE, CNRS, Université Paris-Dauphine, INRIA Project team Mokaplan, France
Email: vialard@ceremade.dauphine.fr

DOI: https://doi.org/10.1090/mcom/3303
Keywords: Optimal transport, Wasserstein distance, unbalanced transport, Bregman projections, Wasserstein barycenters
Received by editor(s): October 25, 2016
Received by editor(s) in revised form: May 22, 2017
Published electronically: February 6, 2018
Article copyright: © Copyright 2018 American Mathematical Society

American Mathematical Society