Subspace Robust Wasserstein distances

By François-Pierre Paty, Marco Cuturi. 2019

181 citations recorded by the source corpus.

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 corresponding "min-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.

Subfields: Applied Mathematics, Civil and Structural Engineering, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Civil and Structural Engineering

In Mathematical Optimization

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, background): “…Peyre et al. 2017; Miech x k +1 = (1 − γ t ) x k + γ k v k ⊲ Convex update 5: end for et al. 2018; Lacoste-Julien et al. 2015b; Courty et al. 2016; Paty et al. 2019; Luise et al. 2019]; however, many open questions remain in designing such optimal algorithmic schemes ( e.g. [Braun et al. 2017;…”
Generalized Sliced Wasserstein Distances (2019, methodology): “This idea was for instance used in [28, 35, 36].”
Projection-Free Optimization on Uniformly Convex Sets (2020, background): “…rules in RKHS (Bach et al., 2012; Lacoste-Julien et al., 2015; Futami et al., 2019), optimal transport (Courty et al., 2016; Vayer et al., 2018; Paty and Cuturi, 2019; Luise et al., 2019), and many others. x t +1 = (1 − γ t ) x t + γ t v t (cid:46) Convex update 5: end for Uniform Convexity.”