Optimal Solutions for Sparse Principal Component Analysis

Abstract

Given a sample covariance matrix, we examine the problem of maximizing the variance explained by a linear combination of the input variables while constraining the number of nonzero coefficients in this combination. This is known as sparse principal component analysis and has a wide array of applications in machine learning and engineering. We formulate a new semidefinite relaxation to this problem and derive a greedy algorithm that computes a full set of good solutions for all target numbers of non zero coefficients, with total complexity O(n^3), where n is the number of variables. We then use the same relaxation to derive sufficient conditions for global optimality of a solution, which can be tested in O(n^3) per pattern. We discuss applications in subset selection and sparse recovery and show on artificial examples and biological data that our algorithm does provide globally optimal solutions in many cases.

Revised journal version. More efficient optimality conditions and new examples in subset selection and sparse recovery. Original version is in ICML proceedings

Cited by in corpus (68)

• Generalized power method for sparse principal component analysis
• Linear Dimensionality Reduction: Survey, Insights, and Generalizations
• Structured Sparse Principal Component Analysis
• Optimal detection of sparse principal components in high dimension
• Truncated Power Method for Sparse Eigenvalue Problems
• OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage
• Sparse Principal Component Analysis via Variable Projection
• An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA
• Bayesian orthogonal component analysis for sparse representation
• Orthogonal Sparse PCA and Covariance Estimation via Procrustes Reformulation
• Sparse eigenbasis approximation: multiple feature extraction across spatiotemporal scales with application to coherent set identification
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Phase Transitions in Sparse PCA
• Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
• Sparse PCA via Covariance Thresholding
• Sparse PCA through Low-rank Approximations
• Compressed Sensing of Simultaneous Low-Rank and Joint-Sparse Matrices
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Sparse and Functional Principal Components Analysis
• Sparsistency and agnostic inference in sparse PCA
• High Dimensional Robust Sparse Regression
• Covariance Eigenvector Sparsity for Compression and Denoising
• Robust PCA in High-dimension: A Deterministic Approach
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Regularized Principal Component Analysis for Spatial Data
• Optimal linear estimation under unknown nonlinear transform
• Tight convex relaxations for sparse matrix factorization
• Bayesian Variable Selection for Globally Sparse Probabilistic PCA
• Sparse PCA with Oracle Property
• Subexponential-Time Algorithms for Sparse PCA
• Average-case Hardness of RIP Certification
• Sparse PCA via Bipartite Matchings
• Simultaneously Structured Models with Application to Sparse and Low-rank Matrices
• A generalization of regularized dual averaging and its dynamics
• Group Lasso estimation of high-dimensional covariance matrices
• Convex Relaxations for Subset Selection
• Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality
• A D.C. Programming Approach to the Sparse Generalized Eigenvalue Problem
• On the Certification of the Restricted Isometry Property
• An Alternating Manifold Proximal Gradient Method for Sparse PCA and Sparse CCA
• Exact and Approximation Algorithms for Sparse PCA
• Scalable Spectral Algorithms for Community Detection in Directed Networks
• Sparse Canonical Correlation Analysis via Concave Minimization
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• Comparison of several reweighted l1-algorithms for solving cardinality minimization problems
• Factor modelling for high-dimensional functional time series
• An Extension of Fast Iterative Shrinkage-thresholding to Riemannian Optimization for Sparse Principal Component Analysis
• Approximation Algorithms for Sparse Principal Component Analysis
• Learning Feature Sparse Principal Components
• Sparse Generalized Eigenvalue Problem: Optimal Statistical Rates via Truncated Rayleigh Flow
• A recursive divide-and-conquer approach for sparse principal component analysis
• Prescriptive PCA: Dimensionality Reduction for Two-stage Stochastic Optimization
• Sparse Principal Component Analysis for High Dimensional Vector Autoregressive Models
• Sparse Phase Retrieval via Sparse PCA Despite Model Misspecification: A Simplified and Extended Analysis
• Alternating direction method of multipliers for penalized zero-variance discriminant analysis
• An Inverse-free Truncated Rayleigh-Ritz Method for Sparse Generalized Eigenvalue Problem
• Using L1-relaxation and integer programming to obtain dual bounds for sparse PCA
• Solving the k-sparse Eigenvalue Problem with Reinforcement Learning
• Projection Algorithms for Non-Convex Minimization with Application to Sparse Principal Component Analysis
• High Dimensional Process Monitoring Using Robust Sparse Probabilistic Principal Component Analysis
• Sparse Principal Component Analysis: a Least Squares approximation approach
• A Survey on Nonconvex Regularization Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning
• An iterative coordinate descent algorithm to compute sparse low-rank approximations
• Supervised Discriminative Sparse PCA for Com-Characteristic Gene Selection and Tumor Classification on Multiview Biological Data
• The Sparse Principal Component Analysis Problem: Optimality Conditions and Algorithms
• A Decomposition Algorithm for the Sparse Generalized Eigenvalue Problem
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems
• Stay on path: PCA along graph paths