Skip to main content

Optimal detection of sparse principal components in high dimension

Author(s): Berthet, Quentin; Rigollet, Philippe

To refer to this page use:
Abstract: We perform a finite sample analysis of the detection levels for sparse principal components of a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse eigenvalue statistic. Alas, computing this test is known to be NP-complete in general, and we describe a computationally efficient alternative test using convex relaxations. Our relaxation is also proved to detect sparse principal components at near optimal detection levels, and it performs well on simulated datasets. Moreover, using polynomial time reductions from theoretical computer science, we bring significant evidence that our results cannot be improved, thus revealing an inherent trade off between statistical and computational performance.
Publication Date: Aug-2013
Citation: Berthet, Quentin, Rigollet, Philippe. (2013). Optimal detection of sparse principal components in high dimension. The Annals of Statistics, 41 (4), 1780 - 1815. doi:10.1214/13-AOS1127
DOI: doi:10.1214/13-AOS1127
ISSN: 0090-5364
Pages: 1780 - 1815
Type of Material: Journal Article
Journal/Proceeding Title: The Annals of Statistics
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.