sum-of-squares

Breaking (*) the curse of dimension in smooth optimal transport

We show how to break the curse of dimension for the estimation of optimal transport distance between two smooth distributions for the Euclidean squared distance. The approach relies on essentially one tool: represent inequality constraints in the dual formulation of OT by equality constraints with a sum of squares in reproducing kernel Hilbert space. By showing this representation is tight in the variational formulation, one can then leverage smoothness to break the curse. (*) However, the constants associated with the algorithm a priori scale exponentially with the dimension.