Sparse PCA: Optimal rates and adaptive estimation

By Tommaso Cai, Zongming Ma, Yihong Wu. 2012

343 citations recorded by the source corpus.

Principal component analysis (PCA) is one of the most commonly used statistical procedures with a wide range of applications. This paper considers both minimax and adaptive estimation of the principal subspace in the high dimensional setting. Under mild technical conditions, we first establish the optimal rates of convergence for estimating the principal subspace which are sharp with respect to all the parameters, thus providing a complete characterization of the difficulty of the estimation problem in term of the convergence rate. The lower bound is obtained by calculating the local metric entropy and an application of Fano's lemma. The rate optimal estimator is constructed using aggregation, which, however, might not be computationally feasible. We then introduce an adaptive procedure for estimating the principal subspace which is fully data driven and can be computed efficiently. It is shown that the estimator attains the optimal rates of convergence simultaneously over a large collection of the parameter spaces. A key idea in our construction is a reduction scheme which reduces the sparse PCA problem to a high-dimensional multivariate regression problem. This method is potentially also useful for other related problems.

Subfields: Computational Mechanics, Statistics and Probability, Signal Processing

View Paper: https://www.semanticscholar.org/paper/08b9817a7b13edae02891af2fc8996cea53a762b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

In Signal Processing

Citations in the corpus

Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics (2016, background): “…Candès and Tao, 2010; Keshavan et al., 2010; Gross, 2011; Chatterjee, 2014), principle component analysis (Anderson, 2003; Johnstone and Lu, 2009; Cai et al., 2013, 2015b), canonical correlation analysis (Hotelling, 1936; Hardoon et al., 2004; Gao et al., 2014, 2015), community detection (von…”
Global Testing and Large-Scale Multiple Testing for High-Dimensional Covariance Structures (2017, methodology): “…(2009), Ravikumar et al. (2011), and Chandrasekaran et al. (2012), regularizing principal components in Johnstone and Lu (2009), Zou et al. (2006), Cai et al. (2013, 2015), Fan et al. (2013), and Vu and Lei (2013), and penalized regression for precision matrix estimation, Gaussian graphical…”
The Fast Convergence of Incremental PCA (2013, background): “There is an extensive line of work analyzing PCA from the statistical perspective, in which the convergence of various estimators is characterized under certain conditions, including generative models of the data [5] and various assumptions on the covariance matrix spectrum [14, 4] and eigenvalue sp”
Normal approximation and concentration of spectral projectors of sample covariance (2015, unknown): “A closely related loss function is defined by L′(a, b) := ‖a ⊗ a − b ⊗ b‖(2)2 = 2(1 −〈a, b〉2); see, for instance, [3, 18, 21].”
Random matrix theory in statistics: A review (2014, methodology): “A different two-stage estimation scheme, based on a regression framework, has been proposed by Cai et al. (2012).”
An Overview on the Estimation of Large Covariance and Precision Matrices (2015, unknown): “See, for example, Candès and Recht (2009); Koltchinskii et al. (2011); Fan et al. (2011); Negahban and Wainwright (2011); Cai et al. (2013); Ma (2013).”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “optimal(uptoalogarithmicfactor)withrespectton,d,k aswellastherankr;forinstance,seethepaper[59,15],wheretheupperboundisachievedusing computationallyintractableestimators. Similarerrorratesareobtainedin[14,48,62]usingmore sophisticatedalgorithms,butunderascalingofthesamplesize—inparticularonethatisqua”
Robust covariance and scatter matrix estimation under Huber’s contamination model (2015, background): “[27, 32, 46, 7], and is different from the notion of degree sparsity studied in [2, 5].”
The spectral norm of random inner-product kernel matrices (2015, methodology): “Computationally-efficient procedures for estimating sparse principal components include diagonal thresholding [31, 32, 9], `1- and model-selection-penalization approaches [33, 62, 21, 49, 60, 12], iterative thresholding via the QR method [40], approximate message passing [22], and covariance thresho”
Estimating structured high-dimensional covariance and precision matrices: Optimal rates and adaptive estimation (2016, methodology): “…studied by several papers under the sparse principal component analysis setting, including Paul (2007), Nadler (2008), Johnstone and Lu (2009), Amini andWainwright (2009), Birnbaum et al. (2013), Ma (2013), Vu and Lei (2013), Cai et al. (2013), Berthet and Rigollet (2013) and Cai et al. (2015).”
Robust Covariance Matrix Estimation via Matrix Depth (2015, background): “[27, 32, 46, 7], and is different from the notion of degree sparsity studied in [2, 5].”
ECA: High-Dimensional Elliptical Component Analysis in Non-Gaussian Distributions (2013, methodology): “and sub-Gaussian assumptions (Jung and Marron, 2009; Amini and Wainwright, 2009; Shen et al., 2011; Ma, 2013; Vu and Lei, 2012, 2013; Berthet and Rigollet, 2013; Lounici, 2013; Birnbaum et al., 2013; Cai et al., 2013). In particular, Vu and Lei (2012) showed that the rate of convergence O ( p s log ”
Nonasymptotic upper bounds for the reconstruction error of PCA (2016, background): “in Mas and Ruymgaart [25] in a functional setting and in Vu and Lei [34] and Cai, Ma, and Wu [8] in a high-dimensional sparse setting.”
Asymptotics and Concentration Bounds for Bilinear Forms of Spectral Projectors of Sample Covariance (2014, background): “hors considered the loss function L(a,b) := 2(1−| a,bi|),where a,b∈ Rpare unit vectors. It is closely related to the loss function L′(a,b) := ka⊗a−b⊗bk2 2 = 2(1−ha,bi2), that is used, forinstance, in [8, 20, 32]. Forthe spikedcovariancemodel described above, where s1 >··· >sm >0, σ2 = 1 and”
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016, background): “The prototypical example is the estimation of a covariance matrix under sparsity constraints (sparse PCA) [51], [13], [12], where a nearly-quadratic gap between informationtheoretic and computational sample complexity has been established (see [8], [74]) – assuming the computational hardness of the ”