Subspace Robust Wasserstein Distances

Abstract

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.

Cited by in corpus (36)

• Entropic Optimal Transport between Unbalanced Gaussian Measures has a Closed Form
• Unbalanced minibatch Optimal Transport; applications to Domain Adaptation
• Minimax Confidence Intervals for the Sliced Wasserstein Distance
• Sliced Gromov-Wasserstein
• Statistical and Topological Properties of Sliced Probability Divergences
• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Two-sample Test using Projected Wasserstein Distance
• Wasserstein GANs Work Because They Fail (to Approximate the Wasserstein Distance)
• Projection-Free Optimization on Uniformly Convex Sets
• Re-evaluating Word Mover's Distance
• Distributional Sliced-Wasserstein and Applications to Generative Modeling
• A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance
• Asymptotic Guarantees for Learning Generative Models with the Sliced-Wasserstein Distance
• Strong equivalence between metrics of Wasserstein type
• A contribution to Optimal Transport on incomparable spaces
• Set Representation Learning with Generalized Sliced-Wasserstein Embeddings
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Sliced Iterative Normalizing Flows
• Augmented Sliced Wasserstein Distances
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification
• On Transportation of Mini-batches: A Hierarchical Approach
• Projection Robust Wasserstein Barycenters
• Feature Robust Optimal Transport for High-dimensional Data
• Flow-based Alignment Approaches for Probability Measures in Different Spaces
• Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport
• Equitable and Optimal Transport with Multiple Agents
• Learning with symmetric positive definite matrices via generalized Bures-Wasserstein geometry
• Manifold optimization for non-linear optimal transport problems
• Partial Wasserstein and Maximum Mean Discrepancy distances for bridging the gap between outlier detection and drift detection
• Tessellated Wasserstein Auto-Encoders
• On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport
• Soft and subspace robust multivariate rank tests based on entropy regularized optimal transport
• Separation Results between Fixed-Kernel and Feature-Learning Probability Metrics
• Heterogeneous Wasserstein Discrepancy for Incomparable Distributions
• A Pseudo-Metric between Probability Distributions based on Depth-Trimmed Regions
• Optimal estimation of high-dimensional location Gaussian mixtures