Wasserstein Archetypal Analysis

Katy Craig, Braxton Osting, Dong Wang, Yiming XuarXiv 2022 · DOI · arXiv

Abstract

Archetypal Analysis (AA) is a popular unsupervised learning method for identifying extreme representative points in a dataset. However, traditional AA, which relies on Euclidean distances, is sensitive to outliers and often ill-posed for distributions with infinite support. This paper introduces Wasserstein Archetypal Analysis (WAA), a robust framework that utilizes the 2-Wasserstein metric to find a convex polytope whose uniform distribution best approximates the data distribution. We provide theoretical guarantees for existence and consistency, and demonstrate WAA's effectiveness on synthetic and real-world COVID-19 positivity rate data.

Introduction

Data summarization often involves finding "archetypes"—pure types or extreme observations that define the boundary of a dataset's convex hull. Traditional Archetypal Analysis (AA) minimizes the squared Euclidean distance between data points and their reconstruction as convex combinations of these archetypes. While effective, this approach suffers from significant sensitivity to outliers and instability when applied to data from distributions with unbounded support, such as Gaussian distributions.

To overcome these limitations, we propose Wasserstein Archetypal Analysis (WAA). By reframing the problem through the lens of Optimal Transport, WAA seeks a convex $k$-gon $\Omega$ such that the uniform measure on $\Omega$ is closest to the data distribution $\mu$ in the 2-Wasserstein sense.

Methodology

The WAA objective is formulated as: $$\min_{\Omega \in S_k} W_2(\mu, 1_\Omega/|\Omega|)$$ where $S_k$ is the set of convex $k$-gons in $\mathbb{R}^d$.

Addressing the Collapse Challenge

A significant theoretical hurdle in WAA is ensuring that the optimal polytope does not collapse into a lower-dimensional set, such as a line or a point, during optimization. This "collapse" phenomenon is illustrated in the sequence of shapes shown below.

Illustration of a sequence of polytopes collapsing from a triangle ($\Omega_2$) to a line segment ($\Omega_0$).

To prevent this, we introduce a regularization term based on $m$-Rényi entropy. This ensures the existence of a non-degenerate solution in any dimension.

Optimization via Semi-Discrete Optimal Transport

Since the data is typically discrete while the target polytope is continuous, we employ a semi-discrete optimal transport formulation. This involves partitioning the space using weighted Voronoi tessellations (power diagrams). We solve the problem using an alternating gradient algorithm:

  1. Dual Step (Gradient Ascent): For a fixed polytope, find the optimal transport map by optimizing the dual variables $\nu$.
  2. Primal Step (Gradient Descent): Update the vertices of the polytope to minimize the Wasserstein distance.
Visualization of the dual potential $\nu_2$ defined over the archetypal polytope $\Omega_2$.

Experiments and Results

We evaluated WAA on synthetic distributions and real-world time-series data.

Synthetic Analysis

In experiments with a uniform distribution on a unit disk, WAA archetypes were found to lie outside the disk. This "extrinsic" behavior is a natural consequence of the Wasserstein metric: to represent a uniform mass effectively, the corners of the polytope must be positioned to "pull" mass toward the edges.

COVID-19 Positivity Rates

WAA was applied to a dataset of COVID-19 positivity rates across 50 U.S. states. After reducing the high-dimensional time series to 2D using PCA, WAA identified three stable archetypes corresponding to distinct regional patterns: early sharp peaks (Northeastern states), mid-summer second waves (Southern states), and slow, steady increases (Rural states). WAA demonstrated superior stability compared to traditional AA, particularly in handling the tails of the data distribution.

Conclusion

Wasserstein Archetypal Analysis provides a theoretically sound and robust alternative to traditional data summarization techniques. By considering the entire distribution of mass rather than individual point distances, WAA is naturally resistant to outliers. Future work will focus on addressing the non-convexity of the energy landscape and improving computational scalability for higher-dimensional datasets.

Summary updated

BibTeX
@misc{craig2022wasserstein,
  author = {Katy Craig and Braxton Osting and Dong Wang and Yiming Xu},
  title = {{Wasserstein Archetypal Analysis}},
  year = {2022},
  eprint = {2210.14298},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.14298},
}
Figure