Generalized power method for sparse principal component analysis

2008/11/28 by Michel Journée, Journée, Michel, Yurii Nesterov +5 · 38 citations
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Image and Signal Denoising Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Statistical and numerical algorithms

paper · pdf · doi:10.48550/arxiv.0811.4724

openalex publication_date 2008/11/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

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.

Citations

• Sparse Principal Component Analysis
• Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems
• A Gene-Expression Signature as a Predictor of Survival in Breast Cancer

Cited by

• A Single-loop Stochastic Riemannian ADMM for Nonsmooth Optimization
• Unsupervised Feature Selection via Robust Autoencoder and Adaptive Graph Learning
• Quantum mechanics-based multitensor AI/ML uniquely able to discover, validate, and interpret predictors from small-cohort noisy high-dimensional multiomic data
• Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing
• Rethinking PCA Through Duality
• Random Matrix Theory-guided sparse PCA for single-cell RNA-seq data
• Self-Expressive Decompositions for Matrix Approximation and Clustering
• Convex relaxations of structured matrix factorizations
• An Inexact Proximal Framework for Nonsmooth Riemannian Difference-of-Convex Optimization
• Sparse PCA with Oracle Property
• Truncated Power Method for Sparse Eigenvalue Problems
• Dimensionality Reduction of Massive Sparse Datasets Using Coresets
• Regularized Tensor Factorizations and Higher-Order Principal Components Analysis
• Compressed Sensing: How sharp is the Restricted Isometry Property
• Hyperspectral Imaging and Analysis for Sparse Reconstruction and Recognition
• Risk Bounds and Calibration for a Smart Predict-then-Optimize Method
• On the Worst-Case Approximability of Sparse PCA
• An Inverse Power Method for Nonlinear Eigenproblems with Applications in\n 1-Spectral Clustering and Sparse PCA
• Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets
• An Inverse-free Truncated Rayleigh-Ritz Method for Sparse Generalized\n Eigenvalue Problem
• The Sparse Principal Component of a Constant-rank Matrix
• Solving the k-sparse Eigenvalue Problem with Reinforcement Learning
• Quadratic Optimization with Orthogonality Constraints: Explicit Lojasiewicz Exponent and Linear Convergence of Line-Search Methods
• Simultaneously Structured Models with Application to Sparse and Low-rank\n Matrices
• Bridging Bayesian and Minimax Mean Square Error Estimation via Wasserstein Distributionally Robust Optimization
• Robust Principal Component Analysis Based On Maximum Correntropy Power\n Iterations
• How Powerful is Graph Convolution for Recommendation?
• Projection Algorithms for Non-Convex Minimization with Application to Sparse Principal Component Analysis
• Large-Scale Sparse Principal Component Analysis with Application to Text Data
• PCA by Optimisation of Symmetric Functions has no Spurious Local Optima
• Alternating Direction Method of Multipliers for Sparse Principal Component Analysis
• Second-order methods for provably escaping strict saddle points in composite nonconvex and nonsmooth optimization
• Inexact Proximal Gradient Methods for Non-convex and Non-smooth Optimization
• Exact and Approximation Algorithms for Sparse PCA
• Sparse PCA via Bipartite Matchings
• Approximation Algorithms for Sparse Principal Component Analysis
• An Alternating Manifold Proximal Gradient Method for Sparse PCA and Sparse CCA
• A Non-monotone Linear Search Method with Mixed Direction on Stiefel Manifold

Related

• Gradient-based Sparse Principal Component Analysis with Extensions to Online Learning
• Sparse Principal Component Analysis: a Least Squares approximation approach
• Optimal Solutions for Sparse Principal Component Analysis
• Sparse PCA: Convex Relaxations, Algorithms and Applications
• The Sparse Principal Component Analysis Problem: Optimality Conditions and Algorithms