Generalized Power Method for Sparse Principal Component Analysis

By Michel Journée, Yurii E. Nesterov, Peter Richtárik, Rodolphe Sepulchre. 2008

683 citations recorded by the source corpus.

In this paper we develop a new approach to sparse principal component analysis (sparse PCA). We propose two single-unit and two block optimization formulations of the sparse PCA problem, aimed at extracting a single sparse dominant principal component of a data matrix, or more components at once, respectively. While the initial formulations involve nonconvex functions, and are therefore computationally intractable, we rewrite them into the form of an optimization program involving maximization of a convex function on a compact set. The dimension of the search space is decreased enormously if the data matrix has many more columns (variables) than rows. We then propose and analyze a simple gradient method suited for the task. It appears that our algorithm has best convergence properties in the case when either the objective function or the feasible set are strongly convex, which is the case with our single-unit formulations and can be enforced in the block case. Finally, we demonstrate numerically on a set of random and gene expression test problems that our approach outperforms existing algorithms both in quality of the obtained solution and in computational speed.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Signal Processing

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 Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, neutral): “Such results appear for instance in [Journ´ee et al. 2010] when ω is the ℓ 2 norm.”
Truncated power method for sparse eigenvalue problems (2011, methodology): “More recently, d’Aspremont et al. (2008) proposed the use of greedy forward selection with a certiﬁcate of optimality, and Journ´ee et al. (2010) studied a generalized power method to solve sparse PCA with a certain dual reformulation of the problem.”
Linear dimensionality reduction: survey, insights, and generalizations (2014, methodology): “…this method Orthogonal CCA, maximizing the correlation ρ (ya, yb) objective directly over orthogonal matrices: maximize tr ( M>a XaX > b Mb )√ tr (M>a XaX > a Ma) tr ( M>b XbX > b Mb ) subject to Ma ∈ Oda×r Mb ∈ Odb×r. (10) The resulting low-dimensional mappings are then the orthogonal…”
Manopt, a matlab toolbox for optimization on manifolds (2013, methodology): “Journ´ee et al. (2010) show how optimizing over the ﬁxed-rank spectrahedron can lead to eﬃcient algorithms for sparse PCA.”
MINIMAX SPARSE PRINCIPAL SUBSPACE ESTIMATION IN HIGH DIMENSIONS (2012, methodology): “…methodology that applies the concept of sparsity to the estimation of individual eigenvectors [examples include Jolliﬀe, Trendaﬁlov and Uddin (2003), d’Aspremont et al. (2007), Zou, Hastie and Tibshirani (2006), Shen and Huang (2008), Witten, Tibshirani and Hastie (2009), Journ´ee et al. (2010)].”
Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning (2017, methodology): “A gradient method has been proposed and analyzed in [37] to solve (62), which falls into the category of MM.”
Sparse PCA: Optimal rates and adaptive estimation (2012, background): “constraint reduces the eﬀective number of parameters and facilitates interpretation. Various regularized estimators of the leading eigenvectors have been proposed in the literature. See, for example, [26, 56, 16, 46, 49, 53, 27]. Theoretical analysis has so far mainly focused on the rank-one case, i”
Overview and comparative study of dimensionality reduction techniques for high dimensional data (2020, neutral): “Journée et al. [52] developed a Generalized Power method for Sparse PCA (GP-SPCA) to overcome the curse of dimensionality issue.”
Projection-Free Optimization on Uniformly Convex Sets (2020, background): “The proof follows exactly that of (Journée et al., 2010, Theorem 12), replacing || x − y || 2 with || x − y || r .”
Minimization Over the Nonconvex Sparsity Constraint Using A Hybrid First-order method (2021, methodology): “We estimate it approximately using the power method [28].”
ECA: High-Dimensional Elliptical Component Analysis in Non-Gaussian Distributions (2013, background): “Journée et al. (2010) and Zhang and El Ghaoui (2011) proposed greedily searching the principal submatrices of the covariance matrix.”
Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets (2014, methodology): “The following lemma is taken from (Journée et al., 2010) (Theorem 12).”