Abstract
The Wasserstein barycenter is a geometric construct which captures the notion of centrality among probability distributions, and which has found many applications in machine learning. However, most algorithms for finding even an approximate barycenter suffer an exponential dependence on the dimension $d$ of the underlying space of the distributions. In order to cope with this "curse of dimensionality," we study dimensionality reduction techniques for the Wasserstein barycenter problem. When the barycenter is restricted to support of size $n$, we show that randomized dimensionality reduction can be used to map the problem to a space of dimension $O(\log n)$ independent of both $d$ and $k$, and that any solution found in the reduced dimension will have its cost preserved up to arbitrary small error in the original space. We provide matching upper and lower bounds on the size of the reduced dimension, showing that our methods are optimal up to constant factors. We also provide a coreset construction for the Wasserstein barycenter problem that significantly decreases the number of input distributions. The coresets can be used in conjunction with random projections and thus further improve computation time. Lastly, our experimental results validate the speedup provided by dimensionality reduction while maintaining solution quality.
Introduction
The Wasserstein barycenter (WB) is a powerful tool in machine learning, computer graphics, and statistics for finding the "center" of a collection of point clouds or probability distributions. Because it relies on optimal transport (Earth Mover's Distance), it captures the underlying geometry of data much better than simple Euclidean averages.
However, computing the WB is NP-hard, and most algorithms suffer from the "curse of dimensionality"—their runtimes scale exponentially with the ambient dimension $d$ of the data. This paper addresses this computational bottleneck by investigating whether random dimensionality reduction can project the data into a much smaller space while maintaining high accuracy in the original space.
Methodology
The authors employ two distinct strategies to compress the problem: dimensionality reduction (reducing dimension $d$) and coresets (reducing the number of input distributions $k$).
Dimensionality Reduction
A standard application of the Johnson-Lindenstrauss (JL) lemma would allow projecting the data to $O(\log(nk))$ dimensions, where $k$ is the number of distributions and $n$ is the support size of the barycenter. The authors push past this naive bound to achieve $O(\log n)$ dimensions. They adapt a "robust" Kirszbraun (Lipschitz extension) theorem to construct a "distortion graph" of pairwise distances, proving that even if a random projection distorts some distances, the overall cost of the Wasserstein barycenter is preserved.
Coresets
To reduce $k$, the authors use a "sensitivity sampling" framework. This importance sampling technique samples distributions based on their maximum potential contribution to the total cost. This allows swapping a massive dataset of $k$ distributions for a small, weighted subset (a coreset).
Crucially, dimensionality reduction acts as a pre-processing step. Data is projected, a WB algorithm is run in the low-dimensional space, and a simple convex optimization step lifts the result back to the original dimension.
Key Insights
- Independence from $k$: The target dimension $O(\log n)$ is independent of the number of input distributions $k$. This means that even when averaging millions of distributions, the projection depends only on the complexity of the output (the barycenter's support size $n$).
- Separation from Standard Optimal Transport: The authors prove a lower bound showing that for standard optimal transport between two distributions, the standard JL bound cannot be beaten. However, for the Wasserstein barycenter problem, it can, revealing a fundamental geometric separation between the two problems.
- Connection to Low-Rank Approximation: The authors demonstrate that computing a Wasserstein barycenter can be mathematically formulated as a constrained low-rank approximation problem, linking it to techniques like SVD and $k$-means clustering.
Experimental Results
The methods were evaluated on real-world (FACES, MNIST) and synthetic datasets.
- Theoretical Guarantees: Projecting to $m = O(\log n / \epsilon^2)$ dimensions preserves the objective cost within a $(1 \pm \epsilon)$ factor. This bound is mathematically proven to be tight.
- Dimensionality Reduction Performance: On the FACES dataset (4096 dimensions), reducing the dimension to $d=30$ (a ~136x reduction) increased the solution cost by only 5%.
- Computational Speedups: Running the WB algorithm in the reduced 30-dimensional space took only 9% of the original time for FACES and 73% for MNIST.
- Coreset Efficiency: In synthetic tests, sensitivity sampling achieved a 0.004% error using just 10 samples, whereas uniform sampling yielded a ~1% error even with 1000 samples.
Discussion and Future Work
While the coreset size is polynomial with respect to $n$ and $d$, the current theoretical bounds are loose (e.g., $O(n^8 d^4)$). However, the practical performance is significantly better than these bounds suggest. The theoretical guarantees apply specifically to algorithms restricting the barycenter to a discrete support of size $n$. The newly discovered connection to constrained low-rank approximation suggests that future breakthroughs in that field could directly improve Wasserstein barycenter solvers.
Summary updated