Generalized power method for sparse principal component analysis

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.

Submitted

References in corpus (1)

• Optimal Solutions for Sparse Principal Component Analysis

Cited by in corpus (124)

• Manopt, a Matlab toolbox for optimization on manifolds
• Linear Dimensionality Reduction: Survey, Insights, and Generalizations
• Sparse PCA: Optimal rates and adaptive estimation
• Optimal detection of sparse principal components in high dimension
• Truncated Power Method for Sparse Eigenvalue Problems
• A generalized power iteration method for solving quadratic problem on the Stiefel manifold
• Sparse Principal Component Analysis via Variable Projection
• Sparse Representation for 3D Shape Estimation: A Convex Relaxation Approach
• Nonconvex phase synchronization
• An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA
• Minimax sparse principal subspace estimation in high dimensions
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• Sparse Generalized Eigenvalue Problem via Smooth Optimization
• Statistical and computational trade-offs in estimation of sparse principal components
• Riemannian preconditioning
• Orthogonal Sparse PCA and Covariance Estimation via Procrustes Reformulation
• Sparse eigenbasis approximation: multiple feature extraction across spatiotemporal scales with application to coherent set identification
• Statistical analysis of latent generalized correlation matrix estimation in transelliptical distribution
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• Tensor Networks for Big Data Analytics and Large-Scale Optimization Problems
• Introduction to Nonnegative Matrix Factorization
• Sparse PCA through Low-rank Approximations
• Dimensionality Reduction of Massive Sparse Datasets Using Coresets
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Sparsistency and agnostic inference in sparse PCA
• Sparse and Functional Principal Components Analysis
• Convex relaxations of structured matrix factorizations
• Bayesian Variable Selection for Globally Sparse Probabilistic PCA
• Tight convex relaxations for sparse matrix factorization
• Optimal linear estimation under unknown nonlinear transform
• Regularized Tensor Factorizations and Higher-Order Principal Components Analysis
• Sparse PCA with Oracle Property
• Large-Scale Sparse Principal Component Analysis with Application to Text Data
• Sparse PCA via Bipartite Matchings
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• A generalization of regularized dual averaging and its dynamics
• Simultaneously Structured Models with Application to Sparse and Low-rank Matrices
• The estimation error of general first order methods
• Quadratic Optimization with Orthogonality Constraints: Explicit Lojasiewicz Exponent and Linear Convergence of Line-Search Methods
• Self-Expressive Decompositions for Matrix Approximation and Clustering
• Classical and strong convexity of sublevel sets and application to attainable sets of nonlinear systems
• Projection-Free Optimization on Uniformly Convex Sets
• Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality
• Inexact Proximal Gradient Methods for Non-convex and Non-smooth Optimization
• RankMap: A Platform-Aware Framework for Distributed Learning from Dense Datasets
• 3D Shape Estimation from 2D Landmarks: A Convex Relaxation Approach
• Complete Dictionary Learning via ${\ell }_p$-norm Maximization
• Selective Factor Extraction in High Dimensions
• Improved Bounds on Restricted Isometry Constants for Gaussian Matrices
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• Compressed Sensing: How sharp is the Restricted Isometry Property
• An Alternating Manifold Proximal Gradient Method for Sparse PCA and Sparse CCA
• Online Learning with Continuous Variations: Dynamic Regret and Reductions
• Exact and Approximation Algorithms for Sparse PCA
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• Provable Sample-Efficient Sparse Phase Retrieval Initialized by Truncated Power Method
• Sparse Canonical Correlation Analysis via Concave Minimization
• Conditional Gradient Algorithms for Rank-One Matrix Approximations with a Sparsity Constraint
• Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold
• Online Learning for Sparse PCA in High Dimensions: Exact Dynamics and Phase Transitions
• Risk Bounds and Calibration for a Smart Predict-then-Optimize Method
• Unique sparse decomposition of low rank matrices
• Efficient Sparse Coding using Hierarchical Riemannian Pursuit
• Analysis of the Optimization Landscapes for Overcomplete Representation Learning
• Stochastic Primal-Dual Method on Riemannian Manifolds with Bounded Sectional Curvature
• High Dimensional Semiparametric Latent Graphical Model for Mixed Data
• Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets
• Generalized Left-Localized Cayley Parametrization for Optimization with Orthogonality Constraints
• Approximation Algorithms for Sparse Principal Component Analysis
• An Extension of Fast Iterative Shrinkage-thresholding to Riemannian Optimization for Sparse Principal Component Analysis
• Universal Collaboration Strategies for Signal Detection: A Sparse Learning Approach
• Principal Component Analysis (PCA)-based Massive-MIMO Channel Feedback
• Iteration complexity analysis of random coordinate descent methods for ${\ell }_0$ regularized convex problems
• Bounds on restricted isometry constants of random matrices
• Sparse Principal Component Analysis for High Dimensional Vector Autoregressive Models
• Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method
• A new envelope function for nonsmooth DC optimization
• Alternating Direction Method of Multipliers for Sparse Principal Component Analysis
• A recursive divide-and-conquer approach for sparse principal component analysis
• Multi-Rank Sparse and Functional PCA: Manifold Optimization and Iterative Deflation Techniques
• Learning Feature Sparse Principal Components
• Alternating direction method of multipliers for penalized zero-variance discriminant analysis
• PCA by Optimisation of Symmetric Functions has no Spurious Local Optima
• A Framework of Constraint Preserving Update Schemes for Optimization on Stiefel Manifold
• An Inverse-free Truncated Rayleigh-Ritz Method for Sparse Generalized Eigenvalue Problem
• SIMPCA: A framework for rotating and sparsifying principal components
• On the Worst-Case Approximability of Sparse PCA
• Kurdyka-Lojasiewicz Property of Zero-Norm Composite Functions
• Using L1-relaxation and integer programming to obtain dual bounds for sparse PCA
• An Optimization Framework with Flexible Inexact Inner Iterations for Nonconvex and Nonsmooth Programming
• Generalized Two-Dimensional Quaternion Principal Component Analysis with Weighting for Color Image Recognition
• Structured Channel Covariance Estimation from Limited Samples for Large Antenna Arrays
• How Powerful is Graph Convolution for Recommendation?
• Projection Algorithms for Non-Convex Minimization with Application to Sparse Principal Component Analysis
• Efficient coordinate-descent for orthogonal matrices through Givens rotations
• Solving the k-sparse Eigenvalue Problem with Reinforcement Learning
• Robust Principal Component Analysis Based On Maximum Correntropy Power Iterations
• Monocular 3D Pose Recovery via Nonconvex Sparsity with Theoretical Analysis
• De-Hashing: Server-Side Context-Aware Feature Reconstruction for Mobile Visual Search
• Sparse Principal Component Analysis: a Least Squares approximation approach
• A Compressed PCA Subspace Method for Anomaly Detection in High-Dimensional Data
• A Survey on Nonconvex Regularization Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning
• A Non-monotone Linear Search Method with Mixed Direction on Stiefel Manifold
• Information based Deep Clustering: An experimental study
• A New Basis for Sparse Principal Component Analysis
• Projection Sparse Principal Component Analysis: an efficient least squares method
• A Fast deflation Method for Sparse Principal Component Analysis via Subspace Projections
• Hyperspectral Imaging and Analysis for Sparse Reconstruction and Recognition
• Regularized Consensus PCA
• KL property of exponent $1/2$ of quadratic functions under nonnegative zero-norm constraints and applications
• BLOCCS: Block Sparse Canonical Correlation Analysis With Application To Interpretable Omics Integration
• An active-set algorithm for norm constrained quadratic problems
• Supervised Discriminative Sparse PCA for Com-Characteristic Gene Selection and Tumor Classification on Multiview Biological Data
• Sparse Joint Transmission for Cloud Radio Access Networks with Limited Fronthaul Capacity
• Learning Random Fourier Features by Hybrid Constrained Optimization
• A Decomposition Algorithm for the Sparse Generalized Eigenvalue Problem
• Practical and Fast Momentum-Based Power Methods
• An iterative coordinate descent algorithm to compute sparse low-rank approximations
• High Dimensional Semiparametric Scale-Invariant Principal Component Analysis
• The Sparse Principal Component Analysis Problem: Optimality Conditions and Algorithms
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems
• The Sparse Principal Component of a Constant-rank Matrix
• Dictionary learning under global sparsity constraint