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.

arXiv commentPublished 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 (15)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Covariance regularization by thresholding
• Generalized power method for sparse principal component analysis
• Estimation of high-dimensional low-rank matrices
• Sparse principal component analysis and iterative thresholding
• Optimal rates of convergence for covariance matrix estimation
• PCA consistency in high dimension, low sample size context
• Optimal detection of sparse principal components in high dimension
• Truncated Power Method for Sparse Eigenvalue Problems
• 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 (108)

• Optimal detection of sparse principal components in high dimension
• Truncated Power Method for Sparse Eigenvalue Problems
• 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
• Sparse PCA through Low-rank Approximations
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Sparse CCA via Precision Adjusted Iterative Thresholding
• Minimax estimation in sparse canonical correlation analysis
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Sparsistency and agnostic inference in sparse PCA
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Sparse and Functional Principal Components Analysis
• Geometric Inference for General High-Dimensional Linear Inverse Problems
• Distributed Estimation of Principal Eigenspaces
• Large Covariance Estimation through Elliptical Factor Models
• 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
• Sparse PCA with Oracle Property
• Rate-optimal posterior contraction for sparse PCA
• Convergence of eigenvector empirical spectral distribution of sample covariance matrices
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• Subexponential-Time Algorithms for Sparse PCA
• Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics
• Sparse PCA via Bipartite Matchings
• Convergence rates of eigenvector empirical spectral distribution of large dimensional sample covariance matrix
• 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
• 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
• Selective Factor Extraction in High Dimensions
• Optimal Estimation of Bacterial Growth Rates Based on Permuted Monotone Matrix
• Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices
• Bayesian Estimation of Sparse Spiked Covariance Matrices in High Dimensions
• Power Iteration for Tensor PCA
• Volume Ratio, Sparsity, and Minimaxity under Unitarily Invariant Norms
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Scalable Interpretable Multi-Response Regression via SEED
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• Linear spectral statistics of eigenvectors of anisotropic sample covariance matrices
• Uniform bounds for invariant subspace perturbations
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Bayesian inference for spectral projectors of the covariance matrix
• A useful variant of the Davis--Kahan theorem for statisticians
• Distributed Estimation for Principal Component Analysis: an Enlarged Eigenspace Analysis
• Adversarially Robust Low Dimensional Representations
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Heterogeneity Adjustment with Applications to Graphical Model Inference
• A greedy anytime algorithm for sparse PCA
• Optimal convex lifted sparse phase retrieval and PCA with an atomic matrix norm regularizer
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Subspace Perspective on Canonical Correlation Analysis: Dimension Reduction and Minimax Rates
• Sparse GCA and Thresholded Gradient Descent
• Optimal Bayesian Estimation for Random Dot Product Graphs
• 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
• Long Random Matrices and Tensor Unfolding
• Euclidean Representation of Low-Rank Matrices and Its Statistical Applications
• How well can we learn large factor models without assuming strong factors?
• Streaming Linear System Identification with Reverse Experience Replay
• Integrative Factor Regression and Its Inference for Multimodal Data Analysis
• Empirical Bayes PCA in high dimensions
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• ReFACTor: Practical Low-Rank Matrix Estimation Under Column-Sparsity
• Optimal Sparse Singular Value Decomposition for High-dimensional High-order Data
• Testing Simultaneous Diagonalizability
• Impact of regularization on spectral clustering under the mixed membership stochastic block model
• Non-Sparse PCA in High Dimensions via Cone Projected Power Iteration
• The critical threshold level on Kendall's tau statistic concerning minimax estimation of sparse correlation matrices
• Matrix Recovery from Rank-One Projection Measurements via Nonconvex Minimization
• Convergence Rate of Krasulina Estimator
• Sparse Generalized Principal Component Analysis for Large-scale Applications beyond Gaussianity
• Estimation of matrices with row sparsity
• A New Basis for Sparse Principal Component Analysis
• Individual-centered partial information in social networks
• On spectral properties of high-dimensional spatial-sign covariance matrices in elliptical distributions with applications
• An Inexact Riemannian Proximal Gradient Method
• 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
• Low-Rank Principal Eigenmatrix Analysis
• Finite sample Bernstein-von Mises theorems for functionals and spectral projectors of the covariance matrix