Scaling Algorithms for Unbalanced Transport Problems

By Lénaïc Chizat, G. Peyr'e, Bernhard Schmitzer, Franccois-Xavier Vialard. 2016

154 citations recorded by the source corpus.

This article introduces a new class of fast algorithms to approx-imate 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 re-laxed 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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Wasserstein Adversarial Examples via Projected Sinkhorn Iterations (2019, background): “Our work can be viewed as a special case of unbalanced optimal transport (Chizat et al., 2016), however in the context of projected gradient descent instead of gradient flows.”
Computational Optimal Transport (2018, methodology): “10: Unbalanced OT gradient flow to solve the Hele-Shaw equation (from [Chizat et al., 2017]).”
A Fast Proximal Point Method for Computing Exact Wasserstein Distance (2018, methodology): “Besides proposed IPOT algorithm (see Algorithm 1 with L = 1), the Sinkhorn algorithm follows Cuturi (2013) and the stabilized Sinkhorn algorithm follows Chizat et al. (2018).”
A Fast Proximal Point Method for Computing Wasserstein Distance (2018, methodology): “The difference lies in IPOT is a principled way to avoid underﬂow and can converge to arbitrarily small regularization, while Sinkhorn always causes numerical difﬁculty when (cid:15) → 0 , even with scheduled decreasing (cid:15) like [6].”
Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation (2020, background): “Two popular ones include entropy regularization [8, 3] and marginal relaxation [13, 6, 7, 9, 12].”
GAN and VAE from an Optimal Transport Point of View (2017, background): “So following [4], it makes sense to consider a relaxed “unbalanced” formulation (in the sense of [5]) of the form where D ( ·|· ) is some distance or divergence between positive measures on Z and λ > 0 a relaxation parameter.”