Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization

Abstract

A central problem of random matrix theory is to understand the eigenvalues of spiked random matrix models, in which a prominent eigenvector 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 Péché showed that the spiked Wishart ensemble exhibits a sharp phase transition asymptotically: when the signal 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, not all the information about the spike is necessarily contained in the spectrum. We study the fundamental limitations of statistical methods, including non-spectral ones. Our results include: I) For the Gaussian Wigner ensemble, we show that PCA achieves the optimal detection threshold for a variety of benign priors for the spike. We extend previous work on the spherically symmetric and i.i.d. Rademacher priors through an elementary, unified analysis. II) For any non-Gaussian Wigner ensemble, we show that PCA is always suboptimal for detection. However, a variant of PCA achieves the optimal threshold (for benign priors) by pre-transforming the matrix entries according to a carefully designed function. This approach has been stated before, and we give a rigorous and general analysis. III) For both the Gaussian Wishart ensemble and various synchronization problems over groups, we show that inefficient procedures can work below the threshold where PCA succeeds, whereas no known efficient algorithm achieves this. This conjectural gap between what is statistically possible and what can be done efficiently remains open.

58 pages, 5 figures. This version adds improved results for the Wishart model

References in corpus (23)

• Message Passing Algorithms for Compressed Sensing
• Higher criticism for detecting sparse heterogeneous mixtures
• Sparse principal component analysis and iterative thresholding
• Sparse PCA: Optimal rates and adaptive estimation
• Optimal detection of sparse principal components in high dimension
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• The largest eigenvalue of rank one deformation of large Wigner matrices
• Detection of an anomalous cluster in a network
• Sparse Principal Components Analysis
• 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
• 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
• Information-theoretic thresholds for community detection in sparse networks
• Sharp detection in PCA under correlations: all eigenvalues matter
• Synchronization over $Z_2$ and community detection in multiplex signed networks with constraints
• 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 (26)

• Near-optimal bounds for phase synchronization
• Algorithmic thresholds for tensor PCA
• Message-passing algorithms for synchronization problems over compact groups
• Estimation under group actions: recovering orbits from invariants
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Fundamental limits of low-rank matrix estimation: the non-symmetric case
• Fundamental limits of detection in the spiked Wigner model
• Subexponential-Time Algorithms for Sparse PCA
• Finite Size Corrections and Likelihood Ratio Fluctuations in the Spiked Wigner Model
• Robust Sparse Estimation Tasks in High Dimensions
• Homotopy Analysis for Tensor PCA
• Phase transition in random tensors with multiple independent spikes
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Adapting to Unknown Noise Distribution in Matrix Denoising
• Spectral Method for Multiplexed Phase Retrieval and Application in Optical Imaging in Complex Media
• An Information-Percolation Bound for Spin Synchronization on General Graphs
• Uniform bounds for invariant subspace perturbations
• Provable benefits of representation learning
• Phase transition in the spiked random tensor with Rademacher prior
• Asymptotic normality and analysis of variance of log-likelihood ratios in spiked random matrix models
• Asymptotic mutual information in quadratic estimation problems over compact groups
• Long Random Matrices and Tensor Unfolding
• An ${\ell }_p$ theory of PCA and spectral clustering
• Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
• Statistical thresholds for Tensor PCA