Subspace Robust Wasserstein Distances

Making sense of Wasserstein distances between discrete measures in high-dimensional settings re-mains a challenge. Recent work has advocated a two-step approach to improve robustness and facilitate the computation of optimal transport, us-ing for instance projections on random real lines, or a preliminary quantization of the measures to reduce the size of their support. We propose in this work a “max-min” robust variant of the Wasserstein distance by considering the maximal possible distance that can be realized between two measures, assuming they can be projected or-thogonally on a lower k-dimensional subspace. Alternatively, we show that the corresponding “min-max” OT problem has a tight convex relax-ation which can be cast as that of finding an opti-mal transport plan with a low transportation cost, where the cost is alternatively defined as the sum of the k largest eigenvalues of the second order moment matrix of the displacements (or match-ings) corresponding to that plan (the usual OT def-inition only considers the trace of that matrix). We show that both quantities inherit several favorable properties from the OT geometry. We propose two algorithms to compute the latter formulation using entropic regularization, and illustrate the interest of this approach empirically.