Do semidefinite relaxations solve sparse PCA up to the information limit?

DOI10.1214/15-AOS1310zbMath1320.62138arXiv1306.3690OpenAlexW3100498669MaRDI QIDQ2352742

Dan Vilenchik, Robert Krauthgamer, Boaz Nadler

Publication date: 6 July 2015

Published in: The Annals of Statistics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.3690

zbMATH Keywords

semidefinite programmingprincipal component analysisrandom matricesspectral analysisconvex relaxationsparsityhigh-dimensional statisticsintegrality gapspiked covariance ensemblesWishart ensembles

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Factor analysis and principal components; correspondence analysis (62H25)

Related Items

Solving sparse principal component analysis with global support ⋮ Compressive phase retrieval: Optimal sample complexity with deep generative priors ⋮ Mean estimation with sub-Gaussian rates in polynomial time ⋮ Dynamic Principal Component Analysis in High Dimensions ⋮ The spectral norm of random inner-product kernel matrices ⋮ Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications ⋮ Extreme point inequalities and geometry of the rank sparsity ball ⋮ Sparse power factorization: balancing peakiness and sample complexity ⋮ Optimality and sub-optimality of PCA. I: Spiked random matrix models ⋮ Sparsistency and agnostic inference in sparse PCA ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ Computational barriers in minimax submatrix detection

Uses Software

• SeDuMi
• PMA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse principal component analysis and iterative thresholding
• Minimax bounds for sparse PCA with noisy high-dimensional data
• Optimal detection of sparse principal components in high dimension
• An augmented Lagrangian approach for sparse principal component analysis
• Nuclear norm minimization for the planted clique and biclique problems
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Sparse principal component analysis via regularized low rank matrix approximation
• Finite sample approximation results for principal component analysis: A matrix perturbation approach
• Adaptive estimation of a quadratic functional by model selection.
• On the distribution of the largest eigenvalue in principal components analysis
• Some hypothesis tests for the covariance matrix when the dimension is large compared to the sample size
• Principal component analysis.
• Sparsistency and agnostic inference in sparse PCA
• Minimax sparse principal subspace estimation in high dimensions
• Sparse PCA: optimal rates and adaptive estimation
• Regularized estimation of large covariance matrices
• Eigenvalues of large sample covariance matrices of spiked population models
• Low-Rank Approximations with Sparse Factors I: Basic Algorithms and Error Analysis
• First-Order Methods for Sparse Covariance Selection
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Sparse Approximate Solutions to Linear Systems
• Finding and certifying a large hidden clique in a semirandom graph
• On Consistency and Sparsity for Principal Components Analysis in High Dimensions
• Finding Hidden Cliques in Linear Time with High Probability
• A Direct Formulation for Sparse PCA Using Semidefinite Programming