2016

Regularized Optimal Transport and the Rot Mover's Distance

Dessein, Arnaud, Papadakis, Nicolas, Rouas, Jean-Luc

Understand

This paper presents a unified framework for smooth convex regularization of discrete optimal transport problems.

In this context, the regularized optimal transport turns out to be equivalent to a matrix nearness problem with respect to Bregman divergences.
Our framework thus naturally generalizes a previously proposed regularization based on the Boltzmann-Shannon entropy related to the Kullback-Leibler divergence, and solved with the Sinkhorn-Knopp algorithm.
We call the regularized optimal transport distance the rot mover's distance in reference to the classical earth mover's distance.

Built on

Concerning nonnegative matrices and doubly stochastic matrices
R. Sinkhorn and P. Knopp · 1967
Earlier work this paper cites.
Network Flows: Theory, Algorithms and Applications
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin · 1993
Earlier work this paper cites.
Dual coordinate ascent methods for non-strictly convex minimization
P. Tseng · 1993
Earlier work this paper cites.
Asymptotic analysis of the exponential penalty trajectory in linear programming
R. Cominetti and J. San Martín · 1994
Earlier work this paper cites.
Methods of Information Geometry
S.-i. Amari and H. Nagaoka · 2000
Earlier work this paper cites.
Dykstra’s algorithm with Bregman projections: A convergence proof
H. H. Bauschke and A. S. Lewis · 2000
Earlier work this paper cites.
The earth mover’s distance as a metric for image retrieval
Y. Rubner, C. Tomasi, and L. J. Guibas · 2000
Earlier work this paper cites.
Fast image retrieval via embeddings
P. Indyk and N. Thaper · 2003
Earlier work this paper cites.
A study on sigmoid kernels for SVM and the training of non-PSD kernels by SMO-type methods
H.-T. Lin and C.-J. Lin · 2003
Earlier work this paper cites.
Fast contour matching using approximate earth mover’s distance
K. Grauman and T. Darrell · 2004
Earlier work this paper cites.
Global convergence of Newton’s method on an interval
L. Thorlund-Petersen · 2004
Earlier work this paper cites.
Feature space interpretation of SVMs with indefinite kernels
B. Haasdonk · 2005
Earlier work this paper cites.
Matrix nearness problems with Bregman divergences
I. S. Dhillon and J. A. Tropp · 2007
Earlier work this paper cites.
Small Manhattan networks and algorithmic applications for the earth mover’s distance
J. Gudmundsson, O. Klein, C. Knauer, and M. Smid · 2007
Earlier work this paper cites.
An efficient earth mover’s distance algorithm for robust histogram comparison
H. Ling and K. Okada · 2007
Earlier work this paper cites.
Planar earthmover is not in l 1 l_{1}
A. Naor and G. Schechtman · 2007
Earlier work this paper cites.
Multiplicative updates for nonnegative quadratic programming
F. Sha, Y. Lin, L. K. Saul, and D. D. Lee · 2007
Earlier work this paper cites.
A linear time histogram metric for improved SIFT matching
O. Pele and M. Werman · 2008
Earlier work this paper cites.
Approximate earth mover’s distance in linear time
S. Shirdhonkar and D. W. Jacobs · 2008
Earlier work this paper cites.

Similar

Fast and robust earth mover’s distances
O. Pele and M. Werman · 2009
Cited alongside, same era.
A statistical approach to the matching of local features
J. Rabin, J. Delon, and Y. Gousseau · 2009
Cited alongside, same era.
Optimal Transport: Old and New
C. Villani · 2009
Cited alongside, same era.
Displacement interpolation using lagrangian mass transport
N. Bonneel, M. van de Panne, S. Paris, and W. Heidrich · 2011
Cited alongside, same era.
Geodesic PCA in the Wasserstein space
Original
J. Bigot, R. Gouet, T. Klein, and A. López · 2013
Cited alongside, same era.
Sinkhorn distances: Lightspeed computation of optimal transport
M. Cuturi · 2013
Cited alongside, same era.
Support vector machines with indefinite kernels
I. Alabdulmohsin, X. Gao, and X. Zhang · 2014
Cited alongside, same era.
Ground metric learning
M. Cuturi and D. Avis · 2014
Cited alongside, same era.
Regularized discrete optimal transport
S. Ferradans, N. Papadakis, G. Peyré, and J.-F. Aujol · 2014
Cited alongside, same era.
Wasserstein propagation for semi-supervised learning
J. Solomon, R. M. Rustamov, L. Guibas, and A. Butscher · 2014
Cited alongside, same era.
Simultaneous ground metric learning and matrix factorization with earth mover’s distance
G. Zen, E. Ricci, and N. Sebe · 2014
Cited alongside, same era.
Iterative Bregman projections for regularized transportation problems
J.-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, and G. Peyré · 2015
Cited alongside, same era.

Then

Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains
J. Solomon, F. de Goes, G. Peyré, M. Cuturi, A. Butscher, A. Nguyen, T. Du, and L. Guibas · 2015
Later among the works it cites.
A smoothed dual approach for variational Wasserstein problems
M. Cuturi and G. Peyré · 2016
Closest in time.
A review of matrix scaling and Sinkhorn’s normal form for matrices and positive maps
Original
M. Idel · 2016
Closest in time.
TUT database for acoustic scene classification and sound event detection
A. Mesaros, T. Heittola, and T. Virtanen · 2016
Closest in time.
Wasserstein training of restricted Boltzmann machines
G. Montavon, K.-R. Müller, and M. Cuturi · 2016
Closest in time.
Fast dictionary learning with a smoothed Wasserstein loss
A. Rolet, M. Cuturi, and G. Peyré · 2016
Closest in time.
A sparse multi-scale algorithm for dense optimal transport
B. Schmitzer · 2016
Closest in time.
Stabilized sparse scaling algorithms for entropy regularized transport problems
Original
B. Schmitzer · 2016
Closest in time.
Wasserstein GAN
Original
M. Arjovsky, S. Chintala, and L. Bottou · 2017
Closest in time.
Inference in generative models using the Wasserstein distance
Original
E. Bernton, P. E. Jacob, M. Gerber, and C. P. Robert · 2017
Closest in time.
Smooth and sparse optimal transport
Original
M. Blondel, V. Seguy, and A. Rolet · 2017
Closest in time.
From optimal transport to generative modeling: the VEGAN cookbook
Original
O. Bousquet, S. Gelly, I. Tolstikhin, C.-J. Simon-Gabriel, and B. Schölkopf · 2017
Closest in time.
Log-PCA versus geodesic PCA of histograms in the Wasserstein space
Original
E. Cazelles, V. Seguy, J. Bigot, M. Cuturi, and N. Papadakis · 2017
Closest in time.
Parameter estimation in finite mixture models by regularized optimal transport: A unified framework for hard and soft clustering
Original
A. Dessein, N. Papadakis, and C.-A. Deledalle · 2017
Closest in time.
GAN and VAE from an optimal transport point of view
Original
A. Genevay, G. Peyré, and M. Cuturi · 2017
Closest in time.
Overrelaxed sinkhorn-knopp algorithm for regularized optimal transport
Original
A. Thibault, L. Chizat, C. Dossal, and N. Papadakis · 2017
Closest in time.
Tsallis regularized optimal transport and ecological inference
B. Muzellec, R. Nock, G. Patrini, and F. Nielsen · 2018
Closest in time.
Wasserstein dictionary learning: Optimal transport-based unsupervised non-linear dictionary learning
M. A. Schmitz, M. Heitz, N. Bonneel, F. Ngolè, D. Coeurjolly, M. Cuturi, P. Gabriel, and J.-L. Starck · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…