Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models

Abstract

A central problem of random matrix theory is to understand the eigenvalues of spiked random matrix models, introduced by Johnstone, in which a prominent eigenvector (or "spike") is planted into a random matrix. These distributions form natural statistical models for principal component analysis (PCA) problems throughout the sciences. Baik, Ben Arous and Peche showed that the spiked Wishart ensemble exhibits a sharp phase transition asymptotically: when the spike strength is above a critical threshold, it is possible to detect the presence of a spike based on the top eigenvalue, and below the threshold the top eigenvalue provides no information. Such results form the basis of our understanding of when PCA can detect a low-rank signal in the presence of noise. However, under structural assumptions on the spike, not all information is necessarily contained in the spectrum. We study the statistical limits of tests for the presence of a spike, including non-spectral tests. Our results leverage Le Cam's notion of contiguity, and include: i) For the Gaussian Wigner ensemble, we show that PCA achieves the optimal detection threshold for certain natural priors for the spike. ii) For any non-Gaussian Wigner ensemble, PCA is sub-optimal for detection. However, an efficient variant of PCA achieves the optimal threshold (for natural priors) by pre-transforming the matrix entries. iii) For the Gaussian Wishart ensemble, the PCA threshold is optimal for positive spikes (for natural priors) but this is not always the case for negative spikes.

arXiv comment67 pages, 3 figures. This is the journal version of part I of arXiv:1609.05573, accepted to the Annals of Statistics. This version includes the supplementary material as appendices

References in corpus (30)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Higher criticism for detecting sparse heterogeneous mixtures
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Sparse principal component analysis and iterative thresholding
• Sparse PCA: Optimal rates and adaptive estimation
• Optimal detection of sparse principal components in high dimension
• Finite sample approximation results for principal component analysis: a matrix perturbation approach
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations
• Detection of an anomalous cluster in a network
• Nonconvex phase synchronization
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Asymptotic power of sphericity tests for high-dimensional data
• Computational barriers in minimax submatrix detection
• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Phase Transitions in Semidefinite Relaxations
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Cramér-Rao bounds for synchronization of rotations
• Mutual Information in Rank-One Matrix Estimation
• Estimation and confidence sets for sparse normal mixtures
• Phase Transitions in Sparse PCA
• Information-theoretic thresholds for community detection in sparse networks
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Detection of correlations
• Sharp detection in PCA under correlations: all eigenvalues matter
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
• Detecting Rare and Weak Spikes in Large Covariance Matrices

Cited by in corpus (16)

• Algorithmic thresholds for tensor PCA
• Computational Barriers to Estimation from Low-Degree Polynomials
• Fundamental limits of detection in the spiked Wigner model
• Statistical limits of dictionary learning: random matrix theory and the spectral replica method
• HyperPCA: a Powerful Tool to Extract Elemental Maps from Noisy Data Obtained in LIBS Mapping of Materials
• Signal detection in nearly continuous spectra and symmetry breaking
• Bose-Einstein-Like condensation of deformed random matrix: A replica approach
• Field theoretical approach for signal detection in nearly continuous positive spectra I: Matricial data
• Free energy fluctuations of the $2$-spin spherical SK model at critical temperature
• An Information-Percolation Bound for Spin Synchronization on General Graphs
• Weak detection in the spiked Wigner model
• Signal Recovery Using a Spiked Mixture Model
• Functional Renormalization Group Approach for Signal Detection
• Free Energy Subadditivity for Symmetric Random Hamiltonians
• Precise Error Rates for Computationally Efficient Testing
• Linear Operator Approximate Message Passing (OpAMP)