Minimax Rates of Estimation for Sparse PCA in High Dimensions

Vincent Vu, Jing Lei
; Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:1278-1286, 2012.

Abstract

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 ∈[0,1]. Our bounds are tight in p and n for all q ∈[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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v22-vu12, title = {Minimax Rates of Estimation for Sparse PCA in High Dimensions}, author = {Vincent Vu and Jing Lei}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {1278--1286}, year = {2012}, editor = {Neil D. Lawrence and Mark Girolami}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/vu12/vu12.pdf}, url = {http://proceedings.mlr.press/v22/vu12.html}, abstract = {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 ∈[0,1]. Our bounds are tight in p and n for all q ∈[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.} }
Endnote
%0 Conference Paper %T Minimax Rates of Estimation for Sparse PCA in High Dimensions %A Vincent Vu %A Jing Lei %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-vu12 %I PMLR %J Proceedings of Machine Learning Research %P 1278--1286 %U http://proceedings.mlr.press %V 22 %W PMLR %X 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 ∈[0,1]. Our bounds are tight in p and n for all q ∈[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.
RIS
TY - CPAPER TI - Minimax Rates of Estimation for Sparse PCA in High Dimensions AU - Vincent Vu AU - Jing Lei BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics PY - 2012/03/21 DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-vu12 PB - PMLR SP - 1278 DP - PMLR EP - 1286 L1 - http://proceedings.mlr.press/v22/vu12/vu12.pdf UR - http://proceedings.mlr.press/v22/vu12.html AB - 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 ∈[0,1]. Our bounds are tight in p and n for all q ∈[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. ER -
APA
Vu, V. & Lei, J.. (2012). Minimax Rates of Estimation for Sparse PCA in High Dimensions. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in PMLR 22:1278-1286

Related Material