Sparse PCA via Covariance Thresholding

In sparse principal component analysis we are given noisy observations of a low-rank matrix of dimension n x p and seek to reconstruct it under additional sparsity assumptions. In particular, we assume here that the principal components v1,..., vr have at most k1, · · · , kq non-zero entries respectively, and study the high-dimensional regime in which p is of the same order as n. In an influential paper, Johnstone and Lu [JL04] introduced a simple algorithm that estimates the support of the principal vectors v1,..., vr by the largest entries in the diagonal of the empirical covariance. This method can be shown to succeed with high probability if kq ≤ C1 √n/ log p, and to fail with high probability if kq ≥ C2 √n/ log p for two constants 0 < C1, C2 < ∞. Despite a considerable amount of work over the last ten years, no practical algorithm exists with provably better support recovery guarantees. Here we analyze a covariance thresholding algorithm that was recently proposed by Krauthgamer, Nadler and Vilenchik [KNV13]. We confirm empirical evidence presented by these authors and rigorously prove that the algorithm succeeds with high probability for k of order √n. Recent conditional lower bounds [BR13] suggest that it might be impossible to do significantly better. The key technical component of our analysis develops new bounds on the norm of kernel random matrices, in regimes that were not considered before.

• Publication year

  2013

• Venue

  Journal of machine learning research

• Publication date

  2013-11-20

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1311.5179
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Probability theory

  2020cited by this paper
• The spectral norm of random inner-product kernel matrices

  2015cited by this paper
• Sum-of-Squares Lower Bounds for Sparse PCA

  2015cited by this paper
• Journal of Computational and Graphical Statistics

  2014cited by this paper
• Statistical and computational trade-offs in estimation of sparse principal components

  2014cited by this paper
• Computational Barriers in Minimax Submatrix Detection

  2013cited by this paper
• Computational Lower Bounds for Sparse PCA

  2013cited by this paper
• DO SEMIDEFINITE RELAXATIONS SOLVE SPARSE PCA UP TO THE INFORMATION LIMIT

  2013cited by this paper
• Minimax Rates of Estimation for Sparse PCA in High Dimensions

  2012cited by this paper
• THE SPECTRUM OF RANDOM INNER-PRODUCT KERNEL MATRICES

  2012influential reference
• OPTIMAL RATES OF CONVERGENCE FOR SPARSE COVARIANCE MATRIX ESTIMATION

  2012cited by this paper
• Sparse PCA: Optimal rates and adaptive estimation

  2012cited by this paper
• The Isotropic Semicircle Law and Deformation of Wigner Matrices

  2011cited by this paper
• On information plus noise kernel random matrices

  2010cited by this paper
• The spectrum of kernel random matrices

  2010cited by this paper
• Introduction to the non-asymptotic analysis of random matrices

  2010influential reference
• Optimal rates of convergence for covariance matrix estimation

  2010cited by this paper
• Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$ -Constrained Quadratic Programming (Lasso)

  2009cited by this paper
• A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis.

  2009cited by this paper
• Sparse Principal Components Analysis

  2009influential reference
• On Consistency and Sparsity for Principal Components Analysis in High Dimensions

  2009cited by this paper
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices

  2009cited by this paper
• Covariance regularization by thresholding

  2009influential reference
• Operator norm consistent estimation of large-dimensional sparse covariance matrices

  2008cited by this paper
• High-dimensional analysis of semidefinite relaxations for sparse principal components

  2008influential reference
• Regularized estimation of large covariance matrices

  2008cited by this paper
• Optimal Solutions for Sparse Principal Component Analysis

  2007cited by this paper
• The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations.

  2007cited by this paper
• ASYMPTOTICS OF SAMPLE EIGENSTRUCTURE FOR A LARGE DIMENSIONAL SPIKED COVARIANCE MODEL

  2007cited by this paper
• The Largest Eigenvalue of Rank One Deformation of Large Wigner Matrices

  2006cited by this paper
• High-dimensional graphs and variable selection with the Lasso

  2006cited by this paper
• Sparse Principal Component Analysis

  2006cited by this paper
• Spectral Bounds for Sparse PCA: Exact and Greedy Algorithms

  2005cited by this paper
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices

  2004cited by this paper
• A Direct Formulation for Sparse PCA Using Semidefinite Programming

  2004cited by this paper
• The concentration of measure phenomenon

  2001cited by this paper
• ADAPTIVE ESTIMATION OF A QUADRATIC FUNCTIONAL BY MODEL SELECTION

  2001cited by this paper
• Adapting to Unknown Smoothness via Wavelet Shrinkage

  1995cited by this paper
• Minimax Risk over l p-Balls for l q-error

  1994cited by this paper
• Minimax risk overlp-balls forlp-error

  1994cited by this paper
• The Rotation of Eigenvectors by a Perturbation. III

  1970cited by this paper
• Some Limit Theorems for Large Deviations

  1965cited by this paper
• Probability theory

  1963cited by this paper
• The rotation of eigenvectors by a perturbation

  1963cited by this paper
• Journal of the American Statistical Association Adaptive Thresholding for Sparse Covariance Matrix Estimation Adaptive Thresholding for Sparse Covariance Matrix Estimation

  year unknowncited by this paper

• Sparse Canonical Correlation Analysis With Preserved Sparsity

  2026cites this paper
• BBP Phase Transition for a Doubly Sparse Deformed Model

  2026cites this paper
• Combinatorial Sparse PCA Beyond the Spiked Identity Model

  2026influential citation
• Computational bottlenecks for denoising diffusions

  2025cites this paper
• A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation

  2025cites this paper
• Efficient Covariance Estimation for Sparsified Functional Data

  2025cites this paper
• Theoretical Guarantees for Sparse Principal Component Analysis Based on the Elastic Net

  2025influential citation
• Extremal Eigenvalues of Random Kernel Matrices with Polynomial Scaling

  2024influential citation
• SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More

  2024cites this paper
• Sparse Covariance Neural Networks

  2024influential citation
• Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data

  2024cites this paper
• OPIT: A Simple but Effective Method for Sparse Subspace Tracking in High-Dimension and Low-Sample-Size Context

  2024cites this paper
• Sharp Analysis of Power Iteration for Tensor PCA

  2024cites this paper
• Efficient Sparse PCA via Block-Diagonalization

  2024cites this paper
• Sparse PCA Beyond Covariance Thresholding

  2023influential citation
• Do Algorithms and Barriers for Sparse Principal Component Analysis Extend to Other Structured Settings?

  2023cites this paper
• Subspace Change Point Detection Under Spiked Wigner Model

  2023cites this paper
• Sparse higher order partial least squares for simultaneous variable selection, dimension reduction, and tensor denoising

  2023cites this paper
• Low-rank matrix estimation with inhomogeneous noise

  2022cites this paper
• Generative Principal Component Analysis

  2022cites this paper
• Theoretical Guarantees for Sparse Principal Component Analysis based on the Elastic Net

  2022influential citation
• Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis

  2022influential citation
• LDA-CNN: Linear Discriminant Analysis Convolution Neural Network for Periocular Recognition in the Wild

  2022cites this paper
• Higher degree sum-of-squares relaxations robust against oblivious outliers

  2022cites this paper
• An equivalence principle for the spectrum of random inner-product kernel matrices with polynomial scalings

  2022cites this paper
• De-Biased Sparse PCA: Inference for Eigenstructure of Large Covariance Matrices

  2021cites this paper
• Dynamic Principal Component Analysis in High Dimensions

  2021cites this paper
• Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity

  2021cites this paper
• Overparameterization Improves Robustness to Covariate Shift in High Dimensions

  2021cites this paper
• Covariance structure estimation with Laplace approximation

  2021cites this paper
• Data‐driven sparse partial least squares

  2021cites this paper
• Sparse PCA: A New Scalable Estimator Based On Integer Programming

  2021influential citation
• On Support Recovery With Sparse CCA: Information Theoretic and Computational Limits

  2021influential citation
• Rank-one matrix estimation with groupwise heteroskedasticity

  2021cites this paper
• The Complexity of Sparse Tensor PCA

  2021influential citation
• No Statistical-Computational Gap in Spiked Matrix Models with Generative Network Priors

  2021cites this paper
• The estimation error of general first order methods

  2020cites this paper
• Information-theoretic limits of a multiview low-rank symmetric spiked matrix model

  2020cites this paper
• Computationally efficient sparse clustering

  2020cites this paper
• Information-Theoretic Limits for the Matrix Tensor Product

  2020cites this paper
• Nonasymptotic Guarantees for Low-Rank Matrix Recovery with Generative Priors

  2020influential citation
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation

  2020cites this paper
• Free Energy Wells and Overlap Gap Property in Sparse PCA

  2020cites this paper
• Upper bounds for Model-Free Row-Sparse Principal Component Analysis

  2020cites this paper
• Compressive phase retrieval: Optimal sample complexity with deep generative priors

  2020cites this paper
• Solving row-sparse principal component analysis via convex integer programs

  2020cites this paper
• Precise Statistical Analysis of Classification Accuracies for Adversarial Training

  2020cites this paper
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors

  2020cites this paper
• Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems

  2020cites this paper
• Sparse PCA: Algorithms, Adversarial Perturbations and Certificates

  2020cites this paper
• Solving sparse principal component analysis with global support

  2020cites this paper
• 0-1 Phase Transitions in Sparse Spiked Matrix Estimation

  2019cites this paper
• More Supervision, Less Computation: Statistical-Computational Tradeoffs in Weakly Supervised Learning

  2019cites this paper
• Subexponential-Time Algorithms for Sparse PCA

  2019cites this paper
• Computational Hardness of Certifying Bounds on Constrained PCA Problems

  2019cites this paper
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness

  2019cites this paper
• Sparse Principal Component Analysis With Preserved Sparsity Pattern

  2019cites this paper
• A GREEDY ANYTIME ALGORITHM FOR SPARSE PCA By

  2019cites this paper
• Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio

  2019cites this paper
• A Kernel Random Matrix-Based Approach for Sparse PCA

  2019influential citation
• ST ] 2 6 Ju l 2 01 9 Subexponential-Time Algorithms for Sparse PCA

  2019cites this paper
• A greedy anytime algorithm for sparse PCA

  2019cites this paper
• The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve

  2019cites this paper
• Supervised Learning for Multi-Block Incomplete Data

  2019influential citation
• The Spiked Matrix Model With Generative Priors

  2019cites this paper
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval

  2018cites this paper
• De-biased sparse PCA: Inference and testing for eigenstructure of large covariance matrices

  2018influential citation
• ST ] 1 3 Ju l 2 01 8 Submitted to the Annals of Statistics OPTIMALITY AND SUB-OPTIMALITY OF PCA I : SPIKED RANDOM MATRIX MODELS By

  2018influential citation
• Sparse PCA from Sparse Linear Regression

  2018cites this paper
• A KERNEL RANDOM MATRIX-BASED APPROACH

  2018cites this paper
• Sparse Power Factorization With Refined Peakiness Conditions

  2018cites this paper
• Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

  2018cites this paper
• Phase transitions in spiked matrix estimation: information-theoretic analysis

  2018cites this paper
• Statistical Inference and the Sum of Squares Method

  2018influential citation
• The spectral norm of random inner-product kernel matrices

  2018influential citation
• Sparse power factorization: balancing peakiness and sample complexity

  2018cites this paper
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models

  2018influential citation
• Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization

  2018cites this paper
• Estimating the Number of Sources in Magnetoencephalography Using Spiked Population Eigenvalues

  2017cites this paper
• On the Equivalence of Sparse Statistical Problems

  2017cites this paper
• Structured Signal Recovery From Quadratic Measurements: Breaking Sample Complexity Barriers via Nonconvex Optimization

  2017cites this paper
• ReFACTor: Practical Low-Rank Matrix Estimation Under Column-Sparsity

  2017cites this paper
• There and Back Again: A General Approach to Learning Sparse Models

  2017cites this paper
• Asymptotic Inference in Sparse High-dimensional Models

  2017cites this paper
• Identifying correlated components in high-dimensional multivariate Gaussian models

  2017cites this paper
• A Provable Approach for Double-Sparse Coding

  2017cites this paper
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications

  2017cites this paper
• Using multiple power spectrum measurements to sense signals with partial spectral overlap

  2017cites this paper
• Compressed Factorization: Fast and Accurate Low-Rank Factorization of Compressively-Sensed Data

  2017cites this paper
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization

  2016influential citation
• L0-norm Sparse Graph-regularized SVD for Biclustering

  2016cites this paper
• On the Approximability of Sparse PCA

  2016cites this paper
• Mean-field message-passing equations in the Hopfield model and its generalizations.

  2016cites this paper
• Estimation of Correlated Components in Multivariate Gaussian Models

  2016cites this paper
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization

  2016cites this paper
• Spectral methods and computational trade-offs in high-dimensional statistical inference

  2016cites this paper
• Sparse PCA via Bipartite Matchings

  2015cites this paper
• Detection of correlated components in multivariate Gaussian models

  2015cites this paper
• Sum-of-Squares Lower Bounds for Sparse PCA

  2015cites this paper
• The spectral norm of random inner-product kernel matrices

  2015influential citation