Papers › Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering
Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering
Romain Couillet, Florent Chatelain, Nicolas Le Bihan
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∈ℂ^(p×n) (or ℝ^(p×n)) and its corresponding kernel (Gram) matrix K through Bernoulli masks: S∈{0,1}^(p×n) for X and B∈{0,1}^(n×n) for K. The resulting "two-way punctured" kernel is thus given by K=1/p[(X ⊙S)ᴴ (X ⊙S)] ⊙B. We demonstrate that, for X composed of independent columns drawn from a Gaussian mixture model, as n,p→∞ with p/n→c₀∈(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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections