Sparse PCA: Phase Transitions in the Critical Regime

Abstract

This work studies sparse principal component analysis (PCA) in high dimensions. Given <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> independent <inline-formula> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula>-dimensional Gaussian samples with covariance <inline-formula> <tex-math notation="LaTeX">$ {\boldsymbol {\Sigma } }:= (\lambda -1) {\boldsymbol {v}}{\boldsymbol {v}} ^{\top } + {\mathbf {I}}_{p}$ </tex-math></inline-formula>, our goal is to estimate <inline-formula> <tex-math notation="LaTeX">$\boldsymbol {v}$ </tex-math></inline-formula> under the assumption of sparsity. On the one hand, if the sparsity level <inline-formula> <tex-math notation="LaTeX">$m:= \|{\boldsymbol {v}}\|_{0}$ </tex-math></inline-formula> satisfies <inline-formula> <tex-math notation="LaTeX">$m \lesssim \sqrt {n}$ </tex-math></inline-formula>, algorithms such as covariance thresholding consistently outperform PCA. On the other hand, if <inline-formula> <tex-math notation="LaTeX">$m \gg \sqrt {n}$ </tex-math></inline-formula>, it is conjectured that no polynomial-time algorithm can recover <inline-formula> <tex-math notation="LaTeX">$\boldsymbol {v}$ </tex-math></inline-formula> below the detection threshold of PCA. We investigate the “critical” high-dimensional regime, where <inline-formula> <tex-math notation="LaTeX">$n, p, m \rightarrow \infty $ </tex-math></inline-formula> with <inline-formula> <tex-math notation="LaTeX">$m/\sqrt {n} \rightarrow \beta $ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$p/n \rightarrow \gamma $ </tex-math></inline-formula>, and study estimators based on kernel PCA, generalizing covariance thresholding. Within this framework, we achieve a fine-grained understanding of signal detection and recovery. Our main result establishes a detection phase transition, analogous to the Baik–Ben Arous–Péché (BBP) transition for PCA: above a signal strength threshold—depending on the kernel function, <inline-formula> <tex-math notation="LaTeX">$\gamma $ </tex-math></inline-formula>, and <inline-formula> <tex-math notation="LaTeX">$\beta $ </tex-math></inline-formula>—kernel PCA is informative. Conversely, below the threshold, kernel principal components are asymptotically orthogonal to the signal. Notably, 1) above this threshold, consistent support recovery is possible with high probability, 2) for all <inline-formula> <tex-math notation="LaTeX">$\beta \in (0, \infty)$ </tex-math></inline-formula>, kernel PCA strictly outperforms PCA, and 3) as <inline-formula> <tex-math notation="LaTeX">$\beta \rightarrow \infty $ </tex-math></inline-formula>, kernel PCA and PCA coincide. We identify optimal kernel functions for detection and support recovery, and numerical calculations suggest that soft thresholding is nearly optimal. Our key technical contribution is approximation guarantees for deterministic equivalents of kernel random matrices, which enable sharp estimates of coordinate fluctuations of kernel principal components.