Fast PCA in 1-D Wasserstein Spaces via B-splines Representation and Metric Projection

Matteo Pegoraro, Mario BerahaAAAI 2021 · DOI

Abstract

This paper introduces a high-speed framework for performing Principal Component Analysis (PCA) on probability distributions using the 2-Wasserstein metric. By representing distributions as quadratic B-splines, the authors transform complex functional optimization problems into manageable vector operations. They introduce "Projected PCA," a method that projects standard $L_2$ PCA results onto a convex set of valid quantile functions. Experimental results demonstrate that this approach is orders of magnitude faster than existing geodesic methods while maintaining comparable accuracy in reconstruction and classification tasks.

Introduction

Standard PCA operates in Euclidean space, which often fails to capture the inherent geometry of probability distributions (e.g., image intensities or census data). Using Euclidean averages for shifted distributions typically results in artifacts, such as a bimodal "average" of two unimodal curves. The Wasserstein distance provides a more natural comparison by accounting for horizontal shifts and scaling, but performing PCA in this space is traditionally computationally grueling. Existing methods like Geodesic PCA require solving non-convex optimization problems that do not scale well. This work aims to make Wasserstein PCA both accurate and fast enough for large-scale data applications.

Methodology

The authors' approach relies on two key innovations:

B-spline Representation

Quantile functions of distributions are represented using quadratic B-splines. Because quantile functions must be non-decreasing, the authors utilize a property of quadratic splines: the function is monotonic if and only if its spline coefficients are monotonic. This turns a functional constraint into a simple linear constraint (a convex polytope) in a finite-dimensional vector space, making optimization significantly more efficient.

Projected PCA

Instead of searching for the optimal geodesic directly, the authors propose a two-step shortcut called "Projected PCA." First, standard PCA is performed in the Hilbert space of quantile functions ($L_2$). Second, the results are projected onto the convex set of valid (non-decreasing) quantile functions. This can be solved almost instantly as a generalized eigenvalue problem.

Key Results and Performance

The method was evaluated using synthetic Gaussians, Dirichlet Process Mixtures, and real-world US COVID-19 mortality data.

Computational Efficiency

Using the B-spline formulation, the authors achieved a 30–35x speedup for Geodesic PCA compared to previous implementations. Projected PCA is even more efficient, with a complexity of $O(J^3)$ (where $J$ is the number of spline bases), making it essentially instantaneous for typical problems.

Comparison of reconstruction error and runtime across different PCA methods.

Classification Accuracy

In binary classification tasks using Support Vector Machines (SVMs) on PCA scores, the Wasserstein-based methods achieved 86% accuracy, significantly outperforming standard functional data analysis techniques which ranged from 71% to 75%.

Classification accuracy of various PCA-based methods on the COVID-19 dataset.

Conclusion

The paper reinforces that Wasserstein-based PCA captures "displacement" (shifting and scaling) far better than Functional PCA (FPCA). The strategic choice of quadratic B-splines makes the monotonicity constraint computationally "cheap," allowing for a fast black-box tool that yields high-quality results. While currently limited to 1-D distributions, this framework provides a foundation for extending other statistical tools, such as linear regression, into Wasserstein space.

Summary updated

BibTeX
@inproceedings{pegoraro2021fast,
  author = {Matteo Pegoraro and Mario Beraha},
  title = {{Fast PCA in 1-D Wasserstein Spaces via B-splines Representation and Metric Projection}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i10.17126},
}
Figure