Approximate Algorithms For-Sparse Wasserstein Barycenter With Outliers

Qingyuan Yang, Hu DingarXiv 2024 · arXiv · OpenReview

Abstract

Wasserstein Barycenter (WB) is one of the most fundamental optimization problems in optimal transportation. Given a set of distributions, the goal of WB is to find a new distribution that minimizes the average Wasserstein distance to them. The problem becomes even harder if we restrict the solution to be "$k$-sparse". In this paper, we study the $k$-sparse WB problem in the presence of outliers, which is a more practical setting since real-world data often contains noise. Existing WB algorithms cannot be directly extended to handle the case with outliers, and thus it is urgently needed to develop some novel ideas. First, we investigate the relation between $k$-sparse WB with outliers and the clustering (with outliers) problems. In particular, we propose a clustering based LP method that yields constant approximation factor for the $k$-sparse WB with outliers problem. Further, we utilize the coreset technique to achieve the $(1+\epsilon)$-approximation factor for any $\epsilon>0$, if the dimensionality is not high. Finally, we conduct the experiments for our proposed algorithms and illustrate their efficiencies in practice.

Introduction

The Wasserstein Barycenter (WB) is a powerful tool for finding the representative "average" of multiple probability distributions. For instance, given several variations of a handwritten digit, the WB identifies a single distribution that captures the collective structure. However, real-world applications face two significant challenges: $k$-sparsity and outliers.

  1. $k$-sparsity: To ensure the barycenter is interpretable and computationally manageable, it is often restricted to a support of size $k$. Finding this optimal $k$-sparse representation is NP-hard.
  2. Outliers: Real-world data is frequently corrupted by noise. Standard WB algorithms attempt to incorporate these outliers into the average, leading to distorted results.

This research presents the first approximate algorithms to address both $k$-sparsity and outliers simultaneously, bridging the gap between optimal transport and robust clustering.

Methodology

The authors propose two primary algorithmic frameworks to solve the $k$-sparse WB problem with outliers.

Clustering-based LP Algorithm

The core innovation lies in identifying a mathematical connection between $k$-sparse WB and $k$-means clustering. The problem is framed as a "fair" version of $k$-means, where the barycenter must represent a proportional mass from every input distribution.

  • Candidate Selection: The algorithm first runs an approximate clustering on each input distribution to identify candidate centers.
  • Linear Programming (LP): These centers serve as a fixed support, and LP is used to determine optimal weights.
  • Dummy Point Mechanism: To handle outliers, a virtual "dummy point" is introduced to "absorb" distant noise, preventing it from skewing the barycenter.

Coreset-based Approximation

For low-dimensional data (e.g., 2D or 3D), the authors employ a coreset technique. By constructing a non-uniform grid of "anchor points" around the data, they achieve a $(1 + \epsilon)$-approximation, providing a result within a provable margin of the mathematical optimum.

Experimental Evaluation

The algorithms were tested on synthetic data (Gaussian distributions with up to 15% outliers) and real-world datasets from the UCI repository, including Bank (3D), Adult (5D), and Credit Card (14D).

Key Results

The robust algorithms demonstrated significant performance gains over standard methods. On real-world datasets, ignoring outliers resulted in nearly double the cost compared to the proposed robust approach, even with minimal noise (5%).

Cost vs. k for the Bank dataset, demonstrating algorithm efficiency

In visual tests using the MNIST dataset, the algorithm successfully extracted the "essence" of digits (0–9) using only 40 points, effectively filtering out random noise. The resulting images were significantly cleaner than those produced by standard methods that do not account for outliers.

Sparse Wasserstein Barycenters of MNIST digits 0-4 extracted from noisy data

Conclusion

This work provides the first theoretical and practical framework for robust, sparse Wasserstein Barycenters. While the coreset-based approach faces the "curse of dimensionality" in high-dimensional spaces, the clustering-based LP method offers a reliable constant approximation factor. Future research may explore the possibility of a Polynomial Time Approximation Scheme (PTAS) for low-dimensional settings.

Summary updated

Abstract

Wasserstein Barycenter (WB) is one of the most fundamental optimization problems in optimal transportation. Given a set of distributions, the goal of WB is to find a new distribution that minimizes the average Wasserstein distance to them. The problem becomes even harder if we restrict the solution to be ``$k$-sparse''. In this paper, we study the $k$-sparse WB problem in the presence of outliers, which is a more practical setting since real-world data often contains noise. Existing WB algorithms cannot be directly extended to handle the case with outliers, and thus it is urgently needed to develop some novel ideas. First, we investigate the relation between $k$-sparse WB with outliers and the clustering (with outliers) problems. In particular, we propose a clustering based LP method that yields constant approximation factor for the $k$-sparse WB with outliers problem. Further, we utilize the coreset technique to achieve the $(1+\epsilon)$-approximation factor for any $\epsilon>0$, if the dimensionality is not high. Finally, we conduct the experiments for our proposed algorithms and illustrate their efficiencies in practice.
BibTeX
@misc{yang2024approximate,
  author = {Qingyuan Yang and Hu Ding},
  title = {{Approximate Algorithms For-Sparse Wasserstein Barycenter With Outliers}},
  year = {2024},
  eprint = {2404.13401},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.13401},
}
Figure