Optimal transport with $f$-divergence regularization and generalized
  Sinkhorn algorithm
  Entropic regularization provides a generalization of the original optimal
transport problem. It introduces a penalty term defined by the Kullback-Leibler
divergence, making the problem more tractable via the celebrated Sinkhorn
algorithm. Replacing the Kullback-Leibler divergence with a general
$f$-divergence leads to a natural generalization. Using convex analysis, we
extend the theory developed so far to include $f$-divergences defined by
functions of Legendre type, and prove that under some mild conditions, strong
duality holds, optimums in both the primal and dual problems are attained, the
generalization of the $c$-transform is well-defined, and we give sufficient
conditions for the generalized Sinkhorn algorithm to converge to an optimal
solution. We propose a practical algorithm for computing the regularized
optimal transport cost and its gradient via the generalized Sinkhorn algorithm.
Finally, we present experimental results on synthetic 2-dimensional data,
demonstrating the effects of using different $f$-divergences for
regularization, which influences convergence speed, numerical stability and
sparsity of the optimal coupling.
