Minimax Rates of Estimation for Sparse PCA in High Dimensions
Vincent Vu, Jing Lei ; JMLR W&CP 22: 1278-1286, 2012.
We study sparse principal components analysis in the high-dimensional setting, where $p$ (the number of variables) can be much larger than $n$ (the number of observations). We prove optimal minimax lower and upper bounds on the estimation error for the first leading eigenvector when it belongs to an $\ell_q$ ball for $q \in [0,1]$. Our bounds are tight in $p$ and $n$ for all $q \in [0, 1]$ over a wide class of distributions. The upper bound is obtained by analyzing the performance of $\ell_q$-constrained PCA. In particular, our results provide convergence rates for $\ell_1$-constrained PCA. Our methods and arguments are also extendable to multi-dimensional subspace estimation.