Projection Robust Wasserstein Barycenters
arXiv:2102.03390
Abstract
Collecting and aggregating information from several probability measures or histograms is a fundamental task in machine learning. One of the popular solution methods for this task is to compute the barycenter of the probability measures under the Wasserstein metric. However, approximating the Wasserstein barycenter is numerically challenging because of the curse of dimensionality. This paper proposes the projection robust Wasserstein barycenter (PRWB) that has the potential to mitigate the curse of dimensionality. Since PRWB is numerically very challenging to solve, we further propose a relaxed PRWB (RPRWB) model, which is more tractable. The RPRWB projects the probability measures onto a lower-dimensional subspace that maximizes the Wasserstein barycenter objective. The resulting problem is a max-min problem over the Stiefel manifold. By combining the iterative Bregman projection algorithm and Riemannian optimization, we propose two new algorithms for computing the RPRWB. The complexity of arithmetic operations of the proposed algorithms for obtaining an -stationary solution is analyzed. We incorporate the RPRWB into a discrete distribution clustering algorithm, and the numerical results on real text datasets confirm that our RPRWB model helps improve the clustering performance significantly.
References in corpus (8)
- Fast Computation of Wasserstein Barycenters
- Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
- Global rates of convergence for nonconvex optimization on manifolds
- Subspace Robust Wasserstein Distances
- Stochastic Wasserstein Barycenters
- Multilevel Clustering via Wasserstein Means
- On the Complexity of Approximating Wasserstein Barycenter
- A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance