Research map / Learning theory and algorithms / Clustering
Capturing the denoising effect of PCA via compression ratio
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes the PCA "compression ratio" metric and a variance-of-compression outlier detector, with theory under a random vector mixture model and experiments on single-cell RNA-seq clustering.
Problem
PCA's denoising effect on high-dimensional noisy data with community structure is not well quantified outside specific clustering settings; outlier detection in such data is also needed.
Approach
Defines the compression ratio (pre-PCA distance over post-PCA distance) for point pairs; shows intra-community pairs get higher compression than inter-community pairs under a random vector mixture model, and uses the variance of a point's compression ratios as an outlier score (low variance indicates outlier).
Key results
- Average intra-community compression ratio exceeds inter-community compression ratio in all 9 single-cell datasets (e.g., Kumar 14.811 vs 1.969).
- Variance-of-compression method gives the highest NMI improvement in 5 of 9 datasets at 10% removal and ranks best in 4 of 6 settings in the average-rank table.
- In simulations with outliers, the variance-of-compression method attains the highest AUROC, with the gap over PCA+KNN-dist widening as noise increases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| remove outlier-like points using variance of compression ratio | PCA+K-Means · single-cell RNA-seq datasets | NMI improvement | Helped |
| remove outlier-like points using variance of compression ratio | PCA+K-Means · single-cell RNA-seq datasets; aggregate settings | average rank of clustering improvement: 2.111; 2.778; 3.222; 2.111; 2.667; 3.111 | Helped |
| use PCA compression ratio to compare pairs within versus across communities | PCA · 8 single-cell RNA-seq datasets and their communities | compression ratio | Helped |
| remove higher-variance outliers with variance of compression | outlier detection · simulations with higher variance-based outliers | AUROC | Mixed |
| increase the overall noise level | variance-of-compression outlier detection versus PCA+KNN-dist · simulated equal- and unequal-noise settings | AUROC gap | Helped |
| increase PCA projection dimension from k - 1 to 2k | variance-of-compression outlier removal with PCA+K-Means · single-cell RNA-seq datasets | clustering improvement | Helped |
Surprising findings
- Using PCA dimension 2k rather than k-1 gave comparatively better clustering improvements than k-1 in the reported experiments.
- Highly unbalanced communities are a weakness: a very small community shows lower variance of compression, so the method may mislabel it as outliers.
Limitations
- Requires choosing a removal percentage, which may vary across datasets.
- Performs poorly on highly unbalanced communities, as small communities show low compression variance.
- In the low-noise setting with high-variance outliers, it underperforms LOF and other baselines.
Experimental setup
Datasets: Koh Kumar Simkumar4easy Simkumar4hard Simkumar8hard Trapnell Zheng4eq Zheng4uneq Zheng8eq
Benchmarks: simulated random vector mixture model data single-cell RNA-seq benchmark datasets (9 datasets)
Metrics: AUROC NMI purity average rank compression ratio
Baselines: LOF KNN-dist Isolation Forest ECOD PCA+LOF PCA+KNN-dist PCA+Isolation Forest PCA+ECOD
Builds on: Davis-Kahan theorem K-Means PCA clustering analysis Local Outlier Factor
Closest papers by meaning
- Coherence Pursuit: Fast, Simple, and Robust Subspace Recovery (ICML 2017 · similarity 0.88)
- Residual-Based Sampling for Online Outlier-Robust PCA (ICML 2022 · similarity 0.88)
- Correlated-PCA: Principal Components' Analysis when Data and Noise are Correlated (NeurIPS 2016 · similarity 0.88)
- Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA (ICML 2023 · similarity 0.87)
- Efficient Sparse PCA via Block-Diagonalization (ICLR 2025 · similarity 0.86)
- Fast and Provable Algorithms for Sparse PCA with Improved Sample Complexity (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.