Sparse PCA: Optimal rates and adaptive estimation

Abstract

Principal component analysis (PCA) is one of the most commonly used statistical procedures with a wide range of applications. This paper considers both minimax and adaptive estimation of the principal subspace in the high dimensional setting. Under mild technical conditions, we first establish the optimal rates of convergence for estimating the principal subspace which are sharp with respect to all the parameters, thus providing a complete characterization of the difficulty of the estimation problem in term of the convergence rate. The lower bound is obtained by calculating the local metric entropy and an application of Fano's lemma. The rate optimal estimator is constructed using aggregation, which, however, might not be computationally feasible. We then introduce an adaptive procedure for estimating the principal subspace which is fully data driven and can be computed efficiently. It is shown that the estimator attains the optimal rates of convergence simultaneously over a large collection of the parameter spaces. A key idea in our construction is a reduction scheme which reduces the sparse PCA problem to a high-dimensional multivariate regression problem. This method is potentially also useful for other related problems.

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

References in corpus (9)

• Covariance regularization by thresholding
• Generalized power method for sparse principal component analysis
• Optimal rates of convergence for covariance matrix estimation
• Finite sample approximation results for principal component analysis: a matrix perturbation approach
• Optimal rates of convergence for sparse covariance matrix estimation
• Adaptive covariance matrix estimation through block thresholding
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices
• Minimax bounds for sparse PCA with noisy high-dimensional data

Cited by in corpus (106)

• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Sparse Principal Component Analysis via Variable Projection
• Projected principal component analysis in factor models
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• ROP: Matrix recovery via rank-one projections
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Normal approximation and concentration of spectral projectors of sample covariance
• Computational Lower Bounds for Sparse PCA
• Statistical and computational trade-offs in estimation of sparse principal components
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Sparse CCA: Adaptive Estimation and Computational Barriers
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Statistical analysis of latent generalized correlation matrix estimation in transelliptical distribution
• Sparse PCA via Covariance Thresholding
• Averaging Stochastic Gradient Descent on Riemannian Manifolds
• Mixed Membership Estimation for Social Networks
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Sparse PCA through Low-rank Approximations
• Sparse CCA via Precision Adjusted Iterative Thresholding
• Minimax estimation in sparse canonical correlation analysis
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Sparse and Functional Principal Components Analysis
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Sparsistency and agnostic inference in sparse PCA
• Large Covariance Estimation through Elliptical Factor Models
• Distributed Estimation of Principal Eigenspaces
• Geometric Inference for General High-Dimensional Linear Inverse Problems
• Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices
• Optimal linear estimation under unknown nonlinear transform
• Multivariate Analysis of Nonparametric Estimates of Large Correlation Matrices
• Rate-optimal posterior contraction for sparse PCA
• Sparse PCA with Oracle Property
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• Convergence of eigenvector empirical spectral distribution of sample covariance matrices
• Subexponential-Time Algorithms for Sparse PCA
• Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics
• Convergence rates of eigenvector empirical spectral distribution of large dimensional sample covariance matrix
• Sparse PCA via Bipartite Matchings
• Limiting Laws for Divergent Spiked Eigenvalues and Largest Non-spiked Eigenvalue of Sample Covariance Matrices
• A generalization of regularized dual averaging and its dynamics
• De-biased sparse PCA: Inference and testing for eigenstructure of large covariance matrices
• The generalized orthogonal Procrustes problem in the high noise regime
• Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise
• Estimation of functionals of sparse covariance matrices
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• Optimal Permutation Recovery in Permuted Monotone Matrix Model
• Consistent estimation of high-dimensional factor models when the factor number is over-estimated
• On the optimality of sliced inverse regression in high dimensions
• Selective Factor Extraction in High Dimensions
• An Overview on the Estimation of Large Covariance and Precision Matrices
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Optimal Estimation of Bacterial Growth Rates Based on Permuted Monotone Matrix
• Power Iteration for Tensor PCA
• Volume Ratio, Sparsity, and Minimaxity under Unitarily Invariant Norms
• Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices
• Bayesian Estimation of Sparse Spiked Covariance Matrices in High Dimensions
• Linear spectral statistics of eigenvectors of anisotropic sample covariance matrices
• Scalable Interpretable Multi-Response Regression via SEED
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Uniform bounds for invariant subspace perturbations
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Heterogeneity Adjustment with Applications to Graphical Model Inference
• Bayesian inference for spectral projectors of the covariance matrix
• A useful variant of the Davis--Kahan theorem for statisticians
• Adversarially Robust Low Dimensional Representations
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Distributed Estimation for Principal Component Analysis: an Enlarged Eigenspace Analysis
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• A greedy anytime algorithm for sparse PCA
• Optimal convex lifted sparse phase retrieval and PCA with an atomic matrix norm regularizer
• Subspace Perspective on Canonical Correlation Analysis: Dimension Reduction and Minimax Rates
• Optimal Bayesian Estimation for Random Dot Product Graphs
• Sparse GCA and Thresholded Gradient Descent
• Learning Feature Sparse Principal Components
• Tensor SVD: Statistical and Computational Limits
• Sparse Generalized Eigenvalue Problem: Optimal Statistical Rates via Truncated Rayleigh Flow
• Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering
• Eigen selection in spectral clustering: a theory guided practice
• Integrative Factor Regression and Its Inference for Multimodal Data Analysis
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• Empirical Bayes PCA in high dimensions
• Euclidean Representation of Low-Rank Matrices and Its Statistical Applications
• Streaming Linear System Identification with Reverse Experience Replay
• Long Random Matrices and Tensor Unfolding
• How well can we learn large factor models without assuming strong factors?
• Impact of regularization on spectral clustering under the mixed membership stochastic block model
• Non-Sparse PCA in High Dimensions via Cone Projected Power Iteration
• ReFACTor: Practical Low-Rank Matrix Estimation Under Column-Sparsity
• Testing Simultaneous Diagonalizability
• Optimal Sparse Singular Value Decomposition for High-dimensional High-order Data
• Slicing-free Inverse Regression in High-dimensional Sufficient Dimension Reduction
• Interpretable Network Representation Learning with Principal Component Analysis
• Principal component analysis for high-dimensional compositional data
• Matrix Recovery from Rank-One Projection Measurements via Nonconvex Minimization
• Convergence Rate of Krasulina Estimator
• Finite sample Bernstein-von Mises theorems for functionals and spectral projectors of the covariance matrix
• A New Basis for Sparse Principal Component Analysis
• Individual-centered partial information in social networks
• Low-Rank Principal Eigenmatrix Analysis
• Estimation of matrices with row sparsity
• On spectral properties of high-dimensional spatial-sign covariance matrices in elliptical distributions with applications
• The critical threshold level on Kendall's tau statistic concerning minimax estimation of sparse correlation matrices
• Sparse Generalized Principal Component Analysis for Large-scale Applications beyond Gaussianity
• An Inexact Riemannian Proximal Gradient Method