Minimax sparse principal subspace estimation in high dimensions

Abstract

We study sparse principal components analysis in high dimensions, where $p$ (the number of variables) can be much larger than $n$ (the number of observations), and analyze the problem of estimating the subspace spanned by the principal eigenvectors of the population covariance matrix. We introduce two complementary notions of ${\ell }_q$ subspace sparsity: row sparsity and column sparsity. We prove nonasymptotic lower and upper bounds on the minimax subspace estimation error for $0\le q\le 1$. The bounds are optimal for row sparse subspaces and nearly optimal for column sparse subspaces, they apply to general classes of covariance matrices, and they show that ${\ell }_q$ constrained estimates can achieve optimal minimax rates without restrictive spiked covariance conditions. Interestingly, the form of the rates matches known results for sparse regression when the effective noise variance is defined appropriately. Our proof employs a novel variational $\sin \Theta$ theorem that may be useful in other regularized spectral estimation problems.

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

References in corpus (5)

• The composite absolute penalties family for grouped and hierarchical variable selection
• Generalized power method for sparse principal component analysis
• Finite sample approximation results for principal component analysis: a matrix perturbation approach
• Coordinate-independent sparse sufficient dimension reduction and variable selection
• High-dimensional analysis of semidefinite relaxations for sparse principal components

Cited by in corpus (15)

• Consistency of spectral clustering in stochastic block models
• Statistical and computational trade-offs in estimation of sparse principal components
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Minimax estimation in sparse canonical correlation analysis
• Sparsistency and agnostic inference in sparse PCA
• Bayesian Variable Selection for Globally Sparse Probabilistic PCA
• Rate-optimal posterior contraction for sparse PCA
• Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise
• Nearly Optimal Stochastic Approximation for Online Principal Subspace Estimation
• Factor modelling for high-dimensional functional time series
• On the Optimality of the Oja's Algorithm for Online PCA
• Overlapping community detection in networks via sparse spectral decomposition
• Co-factor analysis of citation networks
• Sufficient principal component regression for pattern discovery in transcriptomic data