Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality

Abstract

Sparse principal component analysis (PCA) is a popular dimensionality reduction technique for obtaining principal components which are linear combinations of a small subset of the original features. Existing approaches cannot supply certifiably optimal principal components with more than $p=100s$ of variables. By reformulating sparse PCA as a convex mixed-integer semidefinite optimization problem, we design a cutting-plane method which solves the problem to certifiable optimality at the scale of selecting k=5 covariates from p=300 variables, and provides small bound gaps at a larger scale. We also propose a convex relaxation and greedy rounding scheme that provides bound gaps of $1-2\%$ in practice within minutes for $p=100$s or hours for $p=1,000$s and is therefore a viable alternative to the exact method at scale. Using real-world financial and medical datasets, we illustrate our approach's ability to derive interpretable principal components tractably at scale.

arXiv commentRevision submitted to JMLR

References in corpus (10)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Generalized power method for sparse principal component analysis
• Optimal detection of sparse principal components in high dimension
• Optimal Solutions for Sparse Principal Component Analysis
• Truncated Power Method for Sparse Eigenvalue Problems
• An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA
• Sparse Classification: a scalable discrete optimization perspective
• Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection
• A unified approach to mixed-integer optimization problems with logical constraints
• On Polyhedral and Second-Order Cone Decompositions of Semidefinite Optimization Problems

Cited by in corpus (5)

• A unified approach to mixed-integer optimization problems with logical constraints
• A new perspective on low-rank optimization
• Prescriptive PCA: Dimensionality Reduction for Two-stage Stochastic Optimization
• Principal Component Hierarchy for Sparse Quadratic Programs
• Convexification of Permutation-Invariant Sets and an Application to Sparse PCA