Generalized power method for sparse principal component analysis

Michel Journée, Yurii Nesterov, Peter Richtarik and Rodolphe Sepulchre
Additional contact information
Michel Journée: ---
Yurii Nesterov: Université catholique de Louvain (UCL). Center for Operations Research and Econometrics (CORE)
Peter Richtarik: Université catholique de Louvain (UCL). Center for Operations Research and Econometrics (CORE)

No 2008070, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: 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.

Keywords: sparse PCA; power method; gradient ascent; strongly convex sets; block algorithms. (search for similar items in EconPapers)
Date: 2008-11-01
New Economics Papers: this item is included in nep-cmp and nep-ecm
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2008.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2008070

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().