Optimal detection of sparse principal components in high dimension

Abstract

We perform a finite sample analysis of the detection levels for sparse principal components of a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse eigenvalue statistic. Alas, computing this test is known to be NP-complete in general, and we describe a computationally efficient alternative test using convex relaxations. Our relaxation is also proved to detect sparse principal components at near optimal detection levels, and it performs well on simulated datasets. Moreover, using polynomial time reductions from theoretical computer science, we bring significant evidence that our results cannot be improved, thus revealing an inherent trade off between statistical and computational performance.

Published in at http://dx.doi.org/10.1214/13-AOS1127 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (19)

• Covariance regularization by thresholding
• Generalized power method for sparse principal component analysis
• Sparse principal component analysis and iterative thresholding
• Optimal rates of convergence for covariance matrix estimation
• Sparse PCA: Optimal rates and adaptive estimation
• Structured Sparse Principal Component Analysis
• Operator norm consistent estimation of large-dimensional sparse covariance matrices
• Finite sample approximation results for principal component analysis: a matrix perturbation approach
• Computational and Statistical Tradeoffs via Convex Relaxation
• Certifying the restricted isometry property is hard
• Asymptotic power of sphericity tests for high-dimensional data
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Augmented sparse principal component analysis for high dimensional data
• Sparsity and Robustness in Face Recognition
• Spectrum estimation for large dimensional covariance matrices using random matrix theory
• Convex Relaxations for Subset Selection
• Consistency of Sparse PCA in High Dimension, Low Sample Size Contexts
• Hidden cliques and the certification of the restricted isometry property
• Alternating Direction Method of Multipliers for Sparse Principal Component Analysis

Cited by in corpus (94)

• Sparse PCA: Optimal rates and adaptive estimation
• Incoherence-Optimal Matrix Completion
• Asymptotic power of sphericity tests for high-dimensional data
• Computational barriers in minimax submatrix detection
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Algorithmic thresholds for tensor PCA
• Message-passing algorithms for synchronization problems over compact groups
• Computational Lower Bounds for Sparse PCA
• Statistical and computational trade-offs in estimation of sparse principal components
• Sparse CCA: Adaptive Estimation and Computational Barriers
• Statistical analysis of latent generalized correlation matrix estimation in transelliptical distribution
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Mixed Membership Estimation for Social Networks
• Sum-of-Squares Lower Bounds for Sparse PCA
• Fundamental limits of detection in the spiked Wigner model
• Sparse PCA through Low-rank Approximations
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
• Sparse and Functional Principal Components Analysis
• Sparsistency and agnostic inference in sparse PCA
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Testing High Dimensional Covariance Matrices, with Application to Detecting Schizophrenia Risk Genes
• Large Covariance Estimation through Elliptical Factor Models
• Asymptotics of Empirical Eigen-structure for Ultra-high Dimensional Spiked Covariance Model
• Optimal Covariance Change Point Localization in High Dimension
• Sparse PCA with Oracle Property
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• Subexponential-Time Algorithms for Sparse PCA
• Detecting positive correlations in a multivariate sample
• Finite Size Corrections and Likelihood Ratio Fluctuations in the Spiked Wigner Model
• Sparse PCA via Bipartite Matchings
• An ${\ell }_{\infty }$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation
• De-biased sparse PCA: Inference and testing for eigenstructure of large covariance matrices
• The estimation error of general first order methods
• Spherical Cap Packing Asymptotics and Rank-Extreme Detection
• Homotopy Analysis for Tensor PCA
• Estimation of functionals of sparse covariance matrices
• Semi-device-dependent blind quantum tomography
• Detection limits in the high-dimensional spiked rectangular model
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
• Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality
• Universality of Computational Lower Bounds for Submatrix Detection
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Gaussian Determinantal Processes: a new model for directionality in data
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Detecting Rare and Weak Spikes in Large Covariance Matrices
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices
• Optimal link prediction with matrix logistic regression
• Balancing Gaussian vectors in high dimension
• Clustering a Mixture of Gaussians with Unknown Covariance
• Jointly Clustering Rows and Columns of Binary Matrices: Algorithms and Trade-offs
• Generalized Four Moment Theorem and an Application to CLT for Spiked Eigenvalues of Large-dimensional Covariance Matrices
• High-Temperature Structure Detection in Ferromagnets
• Bayesian inference for spectral projectors of the covariance matrix
• Robust Covariance Estimation for Approximate Factor Models
• Learning non-smooth models: instrumental variable quantile regressions and related problems
• A greedy anytime algorithm for sparse PCA
• Finding a Large Submatrix of a Gaussian Random Matrix
• Active Sampling for the Quickest Detection of Markov Networks
• Tensor SVD: Statistical and Computational Limits
• The Spectral Norm of Random Inner-Product Kernel Matrices
• Statistical Limits of Convex Relaxations
• Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation
• On the Worst-Case Approximability of Sparse PCA
• The limits of the sample spiked eigenvalues for a high-dimensional generalized Fisher matrix and its applications
• How well can we learn large factor models without assuming strong factors?
• Sparse Phase Retrieval via Sparse PCA Despite Model Misspecification: A Simplified and Extended Analysis
• Euclidean Representation of Low-Rank Matrices and Its Statistical Applications
• Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems
• Using L1-relaxation and integer programming to obtain dual bounds for sparse PCA
• Sequential Subspace Change-Point Detection
• Sparse spectral estimation with missing and corrupted measurements
• The Nonconvex Geometry of Linear Inverse Problems
• Classification of high-dimensional data with spiked covariance matrix structure
• Detection of Correlations with Adaptive Sensing
• Generalized Four Moment Theorem with an application to the CLT for the spiked eigenvalues of high-dimensional general Fisher-matrices
• Global testing under the sparse alternatives for single index models
• Logspace Reducibility From Secret Leakage Planted Clique
• Detection of Planted Solutions for Flat Satisfiability Problems
• Near-Optimal Procedures for Model Discrimination with Non-Disclosure Properties
• A New Basis for Sparse Principal Component Analysis
• Finite sample Bernstein-von Mises theorems for functionals and spectral projectors of the covariance matrix
• Low-Rank Principal Eigenmatrix Analysis
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Proximal Distance Algorithms: Theory and Examples
• High Dimensional Semiparametric Scale-Invariant Principal Component Analysis
• Sequential detection of low-rank changes using extreme eigenvalues
• The critical threshold level on Kendall's tau statistic concerning minimax estimation of sparse correlation matrices