Smooth and Sparse Optimal Transport
arXiv:1710.06276
Abstract
Entropic regularization is quickly emerging as a new standard in optimal transport (OT). It enables to cast the OT computation as a differentiable and unconstrained convex optimization problem, which can be efficiently solved using the Sinkhorn algorithm. However, entropy keeps the transportation plan strictly positive and therefore completely dense, unlike unregularized OT. This lack of sparsity can be problematic in applications where the transportation plan itself is of interest. In this paper, we explore regularizing the primal and dual OT formulations with a strongly convex term, which corresponds to relaxing the dual and primal constraints with smooth approximations. We show how to incorporate squared -norm and group lasso regularizations within that framework, leading to sparse and group-sparse transportation plans. On the theoretical side, we bound the approximation error introduced by regularizing the primal and dual formulations. Our results suggest that, for the regularized primal, the approximation error can often be smaller with squared -norm than with entropic regularization. We showcase our proposed framework on the task of color transfer.
arXiv commentAccepted to AISTATS 2018
Cited by in corpus (33)
- On the regularization of Wasserstein GANs
- Large-Scale Optimal Transport and Mapping Estimation
- On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
- Efficient and Modular Implicit Differentiation
- Wasserstein Adversarial Imitation Learning
- Regularized Optimal Transport and the Rot Mover's Distance
- Screening Sinkhorn Algorithm for Regularized Optimal Transport
- 2-Wasserstein Approximation via Restricted Convex Potentials with Application to Improved Training for GANs
- Learning with minibatch Wasserstein : asymptotic and gradient properties
- Minibatch optimal transport distances; analysis and applications
- Doubly Stochastic Subspace Clustering
- Adversarial Computation of Optimal Transport Maps
- Blind Source Separation with Optimal Transport Non-negative Matrix Factorization
- Scalable Unbalanced Optimal Transport using Generative Adversarial Networks
- Debiased Sinkhorn barycenters
- An explicit analysis of the entropic penalty in linear programming
- Orlicz space regularization of continuous optimal transport problems
- Optimal Transport losses and Sinkhorn algorithm with general convex regularization
- Learning with Fenchel-Young Losses
- Score-based Generative Neural Networks for Large-Scale Optimal Transport
- Projection Robust Wasserstein Distance and Riemannian Optimization
- Feature Robust Optimal Transport for High-dimensional Data
- Unbalanced Optimal Transport through Non-negative Penalized Linear Regression
- Orlicz-space regularization for optimal transport and algorithms for quadratic regularization
- Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport
- Approximation of Wasserstein distance with Transshipment
- Order Constraints in Optimal Transport
- Learning Generalized Gumbel-max Causal Mechanisms
- Sinkhorn Divergence of Topological Signature Estimates for Time Series Classification
- Optimal transport weights for causal inference
- Dual Regularized Optimal Transport
- Entropy-regularized optimal transport on multivariate normal and q-normal distributions
- Optimal transport with -divergence regularization and generalized Sinkhorn algorithm