Minimax-Optimal Sparse PCA: Computational–Statistical Gap

Computational Lower Bounds for Sparse PCA

Quentin Berthet, Philippe Rigollet (2013)

Conference on Learning Theory (COLT)

📍 Section 5 (Complexity Theoretic Lower Bounds), opening paragraph immediately before Section 5.1 (“It is legitimate to wonder … is this gap intrinsic to the problem?”), p. 8

Minimax bounds for sparse PCA with noisy high-dimensional data

Aharon Birnbaum, Iain M. Johnstone, Boaz Nadler, Debashis Paul (2013)

Annals of Statistics

On the distribution of the largest eigenvalue in principal components analysis

Iain M. Johnstone (2001)

Annals of Statistics

📍 Section 1 (Introduction), formulation of the spiked covariance model Σ = I + θvvᵀ and Tracy–Widom limit for the largest eigenvalue, pp. 295–298.

PCA in high dimensions: An orientation

Iain M. Johnstone, Debashis Paul (2018)

Proceedings of the IEEE

📍 Section V (Sparse PCA), discussion of the computational–statistical gap between k log p / n and k² / n rates, pp. 11–14.