Sparsity of Quadratically Regularized Optimal Transport: Scalar Case

Abstract.

The quadratically regularized optimal transport problem is empirically known to have sparse solutions: its optimal coupling [Formula: see text] has sparse support for small regularization parameter [Formula: see text], in contrast to entropic regularization whose solutions have full support for any [Formula: see text]. Focusing on continuous and scalar marginals, we provide the first precise description of this sparsity. Namely, we show that the support of [Formula: see text] shrinks to the Monge graph at the sharp rate [Formula: see text]. This result is based on a detailed analysis of the dual potential [Formula: see text] for small [Formula: see text]. In particular, we prove that [Formula: see text] is twice differentiable a.s. and bound the second derivative uniformly in [Formula: see text], showing that [Formula: see text] is uniformly strongly convex. Convergence rates for [Formula: see text] and its derivative are also obtained.