Published on Fri Feb 03 2012

Minimax Rates of Estimation for Sparse PCA in High Dimensions

Vincent Q. Vu, Jing Lei

We study sparse principal components analysis in the high-dimensional setting. We prove optimal, non-asymptotic lower and upper bounds on the minimax estimation error for the leading eigenvector.

0
0
0
Abstract

We study sparse principal components analysis in the high-dimensional setting, where (the number of variables) can be much larger than (the number of observations). We prove optimal, non-asymptotic lower and upper bounds on the minimax estimation error for the leading eigenvector when it belongs to an ball for . Our bounds are sharp in and for all over a wide class of distributions. The upper bound is obtained by analyzing the performance of -constrained PCA. In particular, our results provide convergence rates for -constrained PCA.

Fri Nov 02 2012
Machine Learning
Minimax sparse principal subspace estimation in high dimensions
We study sparse principal components analysis in high dimensions. We prove nonasymptotic lower and upper bounds on the minimax estimation error. The bounds are optimal for row and column sparse subspaces. They apply to general classes of covariance matrices.
0
0
0
Fri Aug 22 2014
Machine Learning
Statistical and computational trade-offs in estimation of sparse principal components
In recent years, sparse principal component analysis has emerged as an extremely popular dimension reduction technique for high-dimensional data. We show that there is a fundamental trade-off between statistical and computational performance in this problem.
0
0
0
Sun Mar 01 2015
Machine Learning
Phase Transitions in Sparse PCA
We study optimal estimation for sparse principal component analysis when the number of non-zero elements is small but on the same order as the dimension of the data. We employ approximate message passing (AMP) algorithm to analyze what is the information theoretically minimal mean-squared error.
0
0
0
Thu Jul 23 2015
Machine Learning
Sum-of-Squares Lower Bounds for Sparse PCA
This paper establishes a statistical versus computational trade-off for solving a basic high-dimensional machine learning problem via a basic convex relaxation method. It was well known that in large dimension , a planted -sparse unit vector can be detected using only $n \approx
0
0
0
Thu Feb 23 2012
Machine Learning
Optimal detection of sparse principal components in high dimension
We perform a finite sample analysis of the detection levels for sparse principal components of a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse eigenvalue statistic. We describe a computationally efficient alternative test using convex relaxations.
0
0
0
Tue Jun 23 2020
Machine Learning
Approximation Algorithms for Sparse Principal Component Analysis
0
0
0