  We develop a novel theoretical framework for understating OT schemes
respecting a class structure. For this purpose, we propose a convex OT program
with a sum-of-norms regularization term, which provably recovers the underlying
class structure under geometric assumptions. Furthermore, we derive an
accelerated proximal algorithm with a closed-form projection and proximal
operator scheme, thereby affording a more scalable algorithm for computing
optimal transport plans. We provide a novel argument for the uniqueness of the
optimum even in the absence of strong convexity. Our experiments show that the
new regularizer not only results in a better preservation of the class
structure in the data but also yields additional robustness to the data
geometry, compared to previous regularizers.
