Abstract
In this paper we take a step towards understanding the impact of principle component analysis (PCA) in the context of unsupervised clustering beyond a dimensionality reduction tool. We explore another property of PCA in vector clustering problems, which we call compressibility. This phenomenon shows that PCA significantly reduces the distance of data points belonging to the same clusters, while reducing inter-cluster distances relatively mildly. This gap explains many empirical observations found in practice. For example, in single-cell RNA-sequencing analysis, which is an application of vector clustering in biology, it has been observed that applying PCA on datasets significantly improves the accuracy of classical clustering algorithms such as K-means. We study this compression gap in both theory and practice. On the theoretical side, we analyze PCA in a fairly general probabilistic setup, which we call the random vector model. In terms of practice, we verify the compressibility of PCA on multiple single-cell RNA-seq datasets.
Introduction
Principal Component Analysis (PCA) is a staple in data science, primarily recognized for dimensionality reduction. However, its role as a "denoiser" has often been described qualitatively. This paper formalizes this effect by introducing the concept of compressibility. In high-dimensional, noisy environments—such as single-cell RNA-sequencing (scRNA-seq)—outliers and experimental artifacts can severely degrade clustering performance. The authors demonstrate that PCA selectively reduces distances between points within the same cluster more significantly than between points in different clusters, providing a geometric foundation for its denoising capabilities.
The Compression Ratio and Methodology
The core metric proposed is the Compression Ratio, defined as the ratio of the distance between two points before PCA to their distance after PCA projection.
- Theoretical Foundation: Using a random vector mixture model (signal + noise), the authors prove that intra-community points experience a high compression ratio, while inter-community points experience a much milder reduction. This creates a quantifiable "compression gap."
- Variance of Compression (VoC): This insight leads to a new outlier detection algorithm. A "clean" point exhibits high variance in its compression ratios (high with neighbors, low with others). Conversely, an outlier, lacking shared signal with any group, shows a more uniform, low-variance set of compression ratios.
Experimental Setup
The framework was validated using both synthetic and real-world data:
- Synthetic Simulations: 1000-dimensional datasets with 3000 points and varying Bernoulli noise levels to test theoretical limits.
- Real-World scRNA-seq Data: Eight benchmark datasets (e.g., Koh, Kumar, Trapnell, and Zheng) with 15,000 to 48,000 dimensions and known cell-type labels.
Key Results
The empirical results confirm the theoretical "compression gap." In the Kumar dataset, for instance, the average intra-cluster compression ratio was 14.81, compared to an inter-cluster ratio of just 1.96. This selective filtering allows for superior outlier detection.
As shown in the performance benchmarks, the "Variance of Compression" method achieved the highest AUROC across various noise levels, particularly outperforming PCA-enhanced versions of Local Outlier Factor (LOF) and K-Nearest Neighbors (KNN). Furthermore, removing the top 10% of outliers identified by this metric improved K-Means clustering accuracy (Normalized Mutual Information) in 5 out of 9 real-world datasets, proving the metric captures biological reality rather than just mathematical noise.
Discussion and Conclusion
The compression ratio provides a built-in normalization that makes it robust across clusters with varying internal noise levels. While the method currently requires a user-defined outlier removal rate, it represents a significant step toward algorithm-independent denoising. Future work may involve integrating the compression ratio directly into clustering objectives to further enhance high-dimensional data analysis.
Summary updated