Sparse PCA via Covariance Thresholding

2013/11/20 by Deshpande, Yash, Montanari, Andrea · 2 citations
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1311.5179

Abstract

In sparse principal component analysis we are given noisy observations of a low-rank matrix of dimension n× p and seek to reconstruct it under additional sparsity assumptions. In particular, we assume here each of the principal components v₁,…,v_r has at most s₀ non-zero entries. We are particularly interested in the high dimensional regime wherein p is comparable to, or even much larger than n. In an influential paper, \citejohnstone2004sparse introduced a simple algorithm that estimates the support of the principal vectors v₁,…,v_r by the largest entries in the diagonal of the empirical covariance. This method can be shown to identify the correct support with high probability if s₀≤ K₁√(n/log p), and to fail with high probability if s₀≥ K₂ √(n/log p) for two constants 0

Cited by

• Efficient Covariance Estimation for Sparsified Functional Data
• A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation

Related

• De-biased sparse PCA: Inference and testing for eigenstructure of large covariance matrices
• Sparse PCA: Phase Transitions in the Critical Regime
• Sparse PCA with Oracle Property
• Minimax bounds for sparse PCA with noisy high-dimensional data
• Approximation Algorithms for Sparse Principal Component Analysis