Timezone: »

 
Poster
Subspace Robust Wasserstein Distances
François-Pierre Paty · Marco Cuturi

Tue Jun 11 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #260
in Posters Tue »

Making sense of Wasserstein distances between discrete measures in high-dimensional settings remains a challenge. Recent work has advocated a two-step approach to improve robustness and facilitate the computation of optimal transport, using 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 orthogonally on a lower k-dimensional subspace. Alternatively, we show that the correspondingmin-max'' OT problem has a tight convex relaxation which can be cast as that of finding an optimal 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 matchings) corresponding to that plan (the usual OT definition 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.

Keywords: Convex Optimization · Dimensionality Reduction · Metric Learning · Optimization - Others

Author Information

François-Pierre Paty (ENSAE Paris)
Marco Cuturi (Google and CREST/ENSAE)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors