# Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering

arXiv: https://arxiv.org/abs/2102.12293 · HTML: https://mlsanity.com/paper/2102.12293/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 27 references that are in the map.
- First posted on arXiv 24 Feb 2021.

## Builds on (most cited first, 9 of 9)

- [Large Scale GAN Training for High Fidelity Natural Image Synthesis](https://mlsanity.com/paper/1809.11096/) (2018)
- [High-dimensional dynamics of generalization error in neural networks](https://mlsanity.com/paper/1710.03667/) (2017)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [On the Spectrum of Random Features Maps of High Dimensional Data](https://mlsanity.com/paper/1805.11916/) (2018)
- [The Dynamics of Learning: A Random Matrix Approach](https://mlsanity.com/paper/1805.11917/) (2018)
- [Sketching for Large-Scale Learning of Mixture Models](https://mlsanity.com/paper/1606.02838/) (2016)
- [Empirical Bayes PCA in high dimensions](https://mlsanity.com/paper/2012.11676/) (2020)
- [A random matrix analysis and improvement of semi-supervised learning for large dimensional data](https://mlsanity.com/paper/1711.03404/) (2017)
- [Large Dimensional Analysis and Improvement of Multi Task Learning](https://mlsanity.com/paper/2009.01591/) (2020)

## Built on by (most cited first, 7 of 7)

- [Random matrices in service of ML footprint: ternary random features with no performance loss](https://mlsanity.com/paper/2110.01899/) (2021)
- [Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs](https://mlsanity.com/paper/2103.03561/) (2021)
- [PCA-based Multi Task Learning: a Random Matrix Approach](https://mlsanity.com/paper/2111.00924/) (2021)
- [Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser](https://mlsanity.com/paper/2305.06541/) (2023)
- [Asymptotic Gaussian Fluctuations of Eigenvectors in Spectral Clustering](https://mlsanity.com/paper/2402.12302/) (2024)
- [Performance of Rank-One Tensor Approximation on Incomplete Data](https://mlsanity.com/paper/2504.07818/) (2025)
- [High-Dimensional Partial Least Squares: Spectral Analysis and Fundamental Limitations](https://mlsanity.com/paper/2512.15684/) (2025)

## Abstract (arXiv)

The article introduces an elementary cost and storage reduction method for spectral clustering and principal component analysis. The method consists in randomly "puncturing" both the data matrix X∈mathbbCp× n (or ℝp× n) and its corresponding kernel (Gram) matrix K through Bernoulli masks: S∈0,1p× n for X and B∈0,1n× n for K. The resulting "two-way punctured" kernel is thus given by K=frac1p[(X odot S)sf H (X odot S)] odot B. We demonstrate that, for X composed of independent columns drawn from a Gaussian mixture model, as n,p→∞ with p/n→ c0∈(0,∞), the spectral behavior of K -- its limiting eigenvalue distribution, as well as its isolated eigenvalues and eigenvectors -- is fully tractable and exhibits a series of counter-intuitive phenomena. We notably prove, and empirically confirm on GAN-generated image databases, that it is possible to drastically puncture the data, thereby providing possibly huge computational and storage gains, for a virtually constant (clustering of PCA) performance. This preliminary study opens as such the path towards rethinking, from a large dimensional standpoint, computational and storage costs in elementary machine learning models.