Dimensionality Reduction for Wasserstein Barycenter

Zachary Izzo, Sandeep Silwal, Samson Zhou

Introduction

Finding the "average" of several probability distributions—known as the Wasserstein barycenter—is a powerful geometric construct with widespread applications in machine learning, from image processing to clustering. However, computing this barycenter is computationally brutal in high dimensions. Standard algorithms suffer from an exponential dependence on the dimension $d$ of the underlying space, a classic manifestation of the "curse of dimensionality."

This paper demonstrates that high-dimensional data can be projected into a drastically smaller space—whose dimension is proportional only to the logarithm of the barycenter's support size—while nearly preserving the optimal solution. By doing so, the authors effectively break the curse of dimensionality for the Wasserstein barycenter problem.

The Challenge: High-Dimensional Bottlenecks

The Wasserstein barycenter (WB) summarizes data by finding a single point cloud that sits geometrically "in the middle" of several input distributions. While theoretically elegant, practical implementation hits a wall when data lives in high-dimensional spaces. For instance, finding the barycenter of images represented in a 4096-dimensional space becomes impossibly slow for standard solvers. Researchers have long sought ways to reduce the dimensionality of the data prior to processing without losing the geometric essence required to compute an accurate barycenter.

Methodology: Project, Solve, and Reconstruct

To overcome this bottleneck, the authors propose a framework utilizing randomized dimensionality reduction, specifically leveraging random projections akin to the Johnson-Lindenstrauss lemma. Their approach follows a streamlined three-step pipeline:

  1. Project: Map the input distributions from a high-dimensional space $\mathbb{R}^d$ to a low-dimensional space $\mathbb{R}^m$ using a random matrix.
  2. Solve: Utilize any existing barycenter algorithm to compute a solution within this new, low-dimensional space.
  3. Reconstruct: "Lift" the low-dimensional solution back to the original high-dimensional space. Because the underlying $L_p$ objective is convex, this reconstruction step is computationally efficient.

The theoretical foundation of this pipeline relies heavily on the Kirszbraun Theorem (a Lipschitz extension theorem). The authors use this to prove that a solution optimized in the compressed space remains a highly accurate approximation when pulled back to the original space.

Additionally, the paper introduces a coreset construction method. By using importance sampling, this technique reduces the number of input distributions ($k$) to a smaller, representative subset, compounding the computational speedups.

Key Theoretical Insights

The paper introduces several counter-intuitive and mathematically rigorous insights:

  • Independence from $k$: The most surprising theoretical result is that the required reduced dimension $m$ depends only on the support size of the barycenter ($n$), and is entirely independent of the number of input distributions ($k$). Standard projection lemmas usually scale with the total number of points in the dataset, making this a significant departure.
  • Tight, Optimal Bounds: The authors prove that their $O(\log n)$ target dimension is mathematically optimal. Projecting into a lower dimension risks a severe degradation in the quality of the resulting barycenter.
  • Robust Extensions: To achieve the $k$-independent bound, the authors adapted a "robust" version of the Kirszbraun theorem. This adaptation successfully handles edge cases where a small fraction of pairwise distances are distorted by the random projection, ensuring they do not corrupt the overall cost function.

Empirical Results

The theoretical claims were validated using two well-known high-dimensional datasets: the FACES dataset (698 images, dimension 4096) and the MNIST dataset (10,000 handwritten digits, dimension 784).

  • Massive Compression with High Fidelity: On both datasets, the authors successfully reduced dimensionality by one to two orders of magnitude (e.g., compressing 4096 dimensions down to just 30). Despite this drastic reduction, the cost of the resulting barycenter increased by only about 5%.
  • Dramatic Speedups: The computational savings were immense. For the FACES dataset, computing the barycenter in the reduced 30-dimensional space took only 9% of the time required for the full-dimensional baseline.
  • Coreset Efficiency: The proposed sensitivity-based coreset method significantly outperformed simple uniform sampling, achieving lower error rates using far fewer samples.

Limitations and Future Directions

While this dimensionality reduction framework makes previously intractable problems manageable, the core task of finding a Wasserstein barycenter remains NP-hard. The proposed method shrinks the input, but practitioners still require a robust (and likely approximate) solver for the low-dimensional problem. Furthermore, the theoretical guarantees assume the barycenter has a restricted support size $n$; bounds may degrade if a very high-resolution barycenter is required.

Future research may explore integrating these dimensionality reduction techniques directly into the iterative loops of popular "Sinkhorn-style" barycenter algorithms to unlock even faster convergence rates.

Summary updated

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 \emph{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.
BibTeX
@inproceedings{izzo2021dimensionality,
  author = {Zachary Izzo and Sandeep Silwal and Samson Zhou},
  title = {{Dimensionality Reduction for Wasserstein Barycenter}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=RGcqlmCgHEP},
}
Figure