Statistical Optimal Transport via Factored Couplings

Abstract

We propose a new method to estimate Wasserstein distances and optimal transport plans between two probability distributions from samples in high dimension. Unlike plug-in rules that simply replace the true distributions by their empirical counterparts, our method promotes couplings with low transport rank, a new structural assumption that is similar to the nonnegative rank of a matrix. Regularizing based on this assumption leads to drastic improvements on high-dimensional data for various tasks, including domain adaptation in single-cell RNA sequencing data. These findings are supported by a theoretical analysis that indicates that the transport rank is key in overcoming the curse of dimensionality inherent to data-driven optimal transport.

29 pages, 3 figures

Cited by in corpus (16)

• Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections
• Massively scalable Sinkhorn distances via the Nyström method
• Approximating the Quadratic Transportation Metric in Near-Linear Time
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
• Statistical Optimal Transport posed as Learning Kernel Embedding
• Projection Robust Wasserstein Distance and Riemannian Optimization
• MREC: a fast and versatile framework for aligning and matching point clouds with applications to single cell molecular data
• Optimal Transport for Stationary Markov Chains via Policy Iteration
• Making transport more robust and interpretable by moving data through a small number of anchor points
• Optimal Transport Relaxations with Application to Wasserstein GANs
• Order Constraints in Optimal Transport
• Approximating Optimal Transport via Low-rank and Sparse Factorization
• Approximation of Wasserstein distance with Transshipment
• A Pseudo-Metric between Probability Distributions based on Depth-Trimmed Regions
• Efficient estimates of optimal transport via low-dimensional embeddings
• Low-Rank Sinkhorn Factorization