A direct formulation for sparse PCA using semidefinite programming

Abstract

We examine the problem of approximating, in the Frobenius-norm sense, a positive, semidefinite symmetric matrix by a rank-one matrix, with an upper bound on the cardinality of its eigenvector. The problem arises in the decomposition of a covariance matrix into sparse factors, and has wide applications ranging from biology to finance. We use a modification of the classical variational representation of the largest eigenvalue of a symmetric matrix, where cardinality is constrained, and derive a semidefinite programming based relaxation for our problem. We also discuss Nesterov's smooth minimization technique applied to the SDP arising in the direct sparse PCA method.

Final version, to appear in SIAM review

Cited by in corpus (26)

• C-HiLasso: A Collaborative Hierarchical Sparse Modeling Framework
• Sparse Principal Component Analysis via Variable Projection
• Model Selection Through Sparse Maximum Likelihood Estimation
• A greedy approach to sparse canonical correlation analysis
• Hybrid quantum-classical optimization for financial index tracking
• Quantum Interior Point Methods for Semidefinite Optimization
• Subexponential-Time Algorithms for Sparse PCA
• Sparse Covariance Selection via Robust Maximum Likelihood Estimation
• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization
• On the Quality of a Semidefinite Programming Bound for Sparse Principal Component Analysis
• On Polyhedral and Second-Order Cone Decompositions of Semidefinite Optimization Problems
• Exact and Approximation Algorithms for Sparse PCA
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Supervised Learning for Multi-Block Incomplete Data
• PCA by Optimisation of Symmetric Functions has no Spurious Local Optima
• Empirical Bayes PCA in high dimensions
• Supervised Quantile Normalization for Low-rank Matrix Approximation
• Efficient Semidefinite Programming with approximate ADMM
• A Framework for Private Matrix Analysis
• An $\tilde{\mathcal{O}}(m/{\epsilon }^{3.5})$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints
• The Nonconvex Geometry of Linear Inverse Problems
• Estimating Principal Components under Adversarial Perturbations
• Low-Rank Reorganization via Proportional Hazards Non-negative Matrix Factorization Unveils Survival Associated Gene Clusters
• A Decomposition Algorithm for the Sparse Generalized Eigenvalue Problem
• Sufficient principal component regression for pattern discovery in transcriptomic data