Entropic Wasserstein Component Analysis

Antoine Collas, Titouan Vayer, Rémi Flamary, Arnaud Breloy

Abstract

Principal Component Analysis (PCA) is a cornerstone of high-dimensional data analysis, yet its global objective often fails to preserve local neighborhood structures and distinct clusters. We present Entropic Wasserstein Component Analysis (EWCA), a novel linear dimension reduction framework that reformulates PCA through the lens of Optimal Transport (OT). By incorporating entropic regularization into the projection objective, EWCA effectively captures local manifold structures while maintaining the interpretability of a linear projection. Our results on high-dimensional biological datasets demonstrate that EWCA significantly improves cluster preservation and classification accuracy compared to standard PCA, particularly in settings where $d \gg k$.

Introduction

Principal Component Analysis (PCA) is the ubiquitous first step for dimensionality reduction, seeking to maximize captured variance or minimize global reconstruction error. However, PCA’s purely global focus can be a liability when dealing with complex, clustered data common in fields like genomics or image processing. Because PCA prioritizes the directions of maximum global variance, it may inadvertently "squash" distinct clusters together if their separation does not align with those global directions.

To address this, researchers have often turned to non-linear manifold learning techniques like t-SNE or UMAP. While powerful, these methods lack the interpretability and simplicity of a linear projection. Entropic Wasserstein Component Analysis (EWCA) bridges this gap by providing a "cluster-aware" linear projection that respects neighborhood relationships in the high-dimensional space.

Methodology

The Optimal Transport Formulation

The core innovation of EWCA is the reformulation of the projection problem as an Optimal Transport task. Rather than simply projecting points onto a subspace, the framework defines a cost for transporting the original data points to their projected counterparts.

Entropic Regularization

The "secret sauce" of EWCA is the addition of an entropic regularization term to the OT problem, similar to the approach used in Sinkhorn distances. While standard PCA effectively assumes a rigid one-to-one mapping between a point and its projection, entropic OT allows for "soft" assignments. This allows the optimization process to consider the relationships between all pairs of points, naturally encoding neighborhood information into the resulting subspace projection.

Optimization over the Stiefel Manifold

Solving the EWCA objective is computationally challenging because it requires optimization over the Stiefel manifold—the set of all orthogonal projection bases. The authors propose two distinct solvers to handle different data scales:

  1. Block Coordinate Descent (BCD): This algorithm alternates between updating the transport plan (via the Sinkhorn algorithm) and updating the subspace (via eigen-decomposition).
  2. Block-Majorization-Minimization (Block-MM): Designed specifically for high-dimensional data where the number of features ($d$) greatly exceeds the number of samples ($n$), such as gene expression profiles. Block-MM utilizes a surrogate function to avoid the cubic scaling of $d \times d$ matrix operations, ensuring computational feasibility for modern biological datasets.

Experimental Results

Dataset Evaluation

The authors evaluated EWCA on two high-dimensional biological datasets where the preservation of biological subtypes (clusters) is critical:

  • Breast: A gene expression dataset (151 samples, 54,675 dimensions) categorized into 6 breast cancer subtypes.
  • Khan2001: A dataset (63 samples, 2,308 dimensions) used to classify 4 types of childhood tumors.

Performance Metrics

Using a simple 1-Nearest Neighbor (1-NN) classifier on the reduced data, EWCA demonstrated superior performance over PCA. On the Breast dataset, the misclassification rate was reduced from 14% (PCA) to 8% (EWCA) at $k=5$. Similarly, on the Khan2001 dataset, the error rate dropped from 11% to 7.5%. These results suggest that EWCA's subspace better preserves the semantic boundaries between classes.

Computational Efficiency

The Block-MM solver proved essential for high-dimensional applications. While the standard BCD approach's cost scales cubically with dimensionality, Block-MM remained efficient even as $d$ exceeded 2,000, making it a practical tool for genomic research.

Discussion and Insights

PCA as a Limit Case

A key theoretical contribution of the paper is the proof that EWCA is a principled generalization of PCA. Specifically, as the entropy regularization parameter ($\epsilon$) approaches zero, EWCA recovers the standard PCA solution. This provides a rigorous foundation for the method, positioning it as an evolution of classical techniques.

Unsupervised Cluster Discovery

Interestingly, the "transport plan" ($\pi$) learned by EWCA often becomes block-diagonal during optimization, even without the use of class labels. This indicates that the algorithm inherently discovers underlying clusters in the data simply by seeking an optimal transport-based projection. By allowing points to interact during the projection phase, EWCA effectively "pulls" similar points together in the subspace, leading to clearer separation than the "blind" global projection of PCA.

Conclusion and Future Work

EWCA offers a compelling middle ground between global linear projections and local manifold learning. While it remains a linear method—and thus cannot capture highly complex non-linear manifolds as effectively as UMAP—it provides a significant boost in cluster preservation over PCA while maintaining interpretability.

Future research may involve extending this OT-based framework to non-linear settings or integrating EWCA as a cluster-preserving layer within deep learning architectures. For now, it serves as a powerful alternative for researchers needing a robust, cluster-aware "first step" in high-dimensional data analysis.

Summary updated

BibTeX
@inproceedings{collas2023entropic,
  author = {Antoine Collas and Titouan Vayer and Rémi Flamary and Arnaud Breloy},
  title = {{Entropic Wasserstein Component Analysis}},
  booktitle = {MLSP},
  year = {2023},
  url = {https://openreview.net/forum?id=00iutEIsE5},
}
Figure