Title: Smooth and Sparse Optimal Transport,
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 $2$-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 $2$-norm than
with entropic regularization. We showcase our proposed framework on the task of
color transfer.