Phase Transitions in Sparse PCA

Abstract

We study optimal estimation for sparse principal component analysis when the number of non-zero elements is small but on the same order as the dimension of the data. We employ approximate message passing (AMP) algorithm and its state evolution to analyze what is the information theoretically minimal mean-squared error and the one achieved by AMP in the limit of large sizes. For a special case of rank one and large enough density of non-zeros Deshpande and Montanari [1] proved that AMP is asymptotically optimal. We show that both for low density and for large rank the problem undergoes a series of phase transitions suggesting existence of a region of parameters where estimation is information theoretically possible, but AMP (and presumably every other polynomial algorithm) fails. The analysis of the large rank limit is particularly instructive.

6 pages, 3 figures

References in corpus (1)

• High-dimensional analysis of semidefinite relaxations for sparse principal components

Cited by in corpus (18)

• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Mutual Information in Rank-One Matrix Estimation
• Finding One Community in a Sparse Graph
• Message-passing algorithms for synchronization problems over compact groups
• Statistical and computational phase transitions in spiked tensor estimation
• Computational Barriers to Estimation from Low-Degree Polynomials
• Fundamental limits of detection in the spiked Wigner model
• Estimation in the spiked Wigner model: A short proof of the replica formula
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• The Error Probability of Sparse Superposition Codes with Approximate Message Passing Decoding
• Performance Limits for Noisy Multi-Measurement Vector Problems
• The Overlap Gap Property in Principal Submatrix Recovery
• Statistical mechanics of low-rank tensor decomposition
• High-dimensional Asymptotics of VAEs: Threshold of Posterior Collapse and Dataset-Size Dependence of Rate-Distortion Curve
• Automatic Hyperparameter Tuning in Sparse Matrix Factorization
• Precise Error Rates for Computationally Efficient Testing