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\in\mathbb{C}^{p\times n}$ (or
$\mathbb{R}^{p\times n}$) and its corresponding kernel (Gram) matrix $K$
through Bernoulli masks: $S\in\{0,1\}^{p\times n}$ for $X$ and
$B\in\{0,1\}^{n\times n}$ for $K$. The resulting "two-way punctured" kernel is
thus given by $K=\frac{1}{p}[(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\to\infty$ with $p/n\to c_0\in(0,\infty)$, 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.

本文介绍了一种基本的计算和存储降低方法，用于光谱聚类和主成分分析。该方法可以大幅度减少数据矩阵和其相应内核（Gram）矩阵的计算复杂度和存储需求，而仍然能保持一定的性能。