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 = {Vu, Vincent and Lei, Jing}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {1278--1286}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, 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 = {https://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 %P 1278--1286 %U https://proceedings.mlr.press/v22/vu12.html %V 22 %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 DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-vu12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 1278 EP - 1286 L1 - http://proceedings.mlr.press/v22/vu12/vu12.pdf UR - https://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 Proceedings of Machine Learning Research 22:1278-1286 Available from https://proceedings.mlr.press/v22/vu12.html.

Related Material