# Sparse PCA With Multiple Components

arXiv: https://arxiv.org/abs/2209.14790 · HTML: https://mlsanity.com/paper/2209.14790/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 64 references that are in the map.
- First posted on arXiv 29 Sep 2022.

## Builds on (most cited first, 23 of 23)

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [European Union regulations on algorithmic decision-making and a "right to explanation"](https://mlsanity.com/paper/1606.08813/) (2016)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Generalized Low Rank Models](https://mlsanity.com/paper/1410.0342/) (2014)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Practical sketching algorithms for low-rank matrix approximation](https://mlsanity.com/paper/1609.00048/) (2016)
- [Sparse Regression: Scalable algorithms and empirical performance](https://mlsanity.com/paper/1902.06547/) (2019)
- [A unified approach to mixed-integer optimization problems with logical constraints](https://mlsanity.com/paper/1907.02109/) (2019)
- [Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods](https://mlsanity.com/paper/2203.07305/) (2022)
- [Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints](https://mlsanity.com/paper/2009.10395/) (2020)
- [Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality](https://mlsanity.com/paper/2005.05195/) (2020)
- [Using L1-relaxation and integer programming to obtain dual bounds for sparse PCA](https://mlsanity.com/paper/1810.09062/) (2018)
- [Exact and Approximation Algorithms for Sparse PCA](https://mlsanity.com/paper/2008.12438/) (2020)
- [Solving sparse principal component analysis with global support](https://mlsanity.com/paper/2010.11152/) (2020)
- [The Backbone Method for Ultra-High Dimensional Sparse Machine Learning](https://mlsanity.com/paper/2006.06592/) (2020)
- [Sparse PCA via Bipartite Matchings](https://mlsanity.com/paper/1508.00625/) (2015)
- [Beyond Symmetry: Best Submatrix Selection for the Sparse Truncated SVD](https://mlsanity.com/paper/2105.03179/) (2021)
- [Orthogonal Sparse PCA and Covariance Estimation via Procrustes Reformulation](https://mlsanity.com/paper/1602.03992/) (2016)
- [Sparse PCA on fixed-rank matrices](https://mlsanity.com/paper/2201.02487/) (2022)
- [Optimization over Structured Subsets of Positive Semidefinite Matrices via Column Generation](https://mlsanity.com/paper/1512.05402/) (2015)
- [Mixed-integer convex representability](https://mlsanity.com/paper/1706.05135/) (2017)
- [Compact Disjunctive Approximations to Nonconvex Quadratically Constrained Programs](https://mlsanity.com/paper/1811.08122/) (2018)
- [On Polyhedral and Second-Order Cone Decompositions of Semidefinite Optimization Problems](https://mlsanity.com/paper/1910.03143/) (2019)

## Built on by (most cited first, 4 of 4)

- [Efficient Sparse PCA via Block-Diagonalization](https://mlsanity.com/paper/2410.14092/) (2024)
- [BackboneLearn: A Library for Scaling Mixed-Integer Optimization-Based Machine Learning](https://mlsanity.com/paper/2311.13695/) (2023)
- [A Decomposition Framework for Certifiably Optimal Orthogonal Sparse PCA](https://mlsanity.com/paper/2603.01144/) (2026)
- [Video-based detection of cessation of breathing in pre-term infants using machine learning](https://mlsanity.com/paper/2607.05230/) (2026)

## Abstract (arXiv)

Sparse Principal Component Analysis (sPCA) is a cardinal technique for obtaining combinations of features, or principal components (PCs), that explain the variance of high-dimensional datasets in an interpretable manner. This involves solving a sparsity and orthogonality constrained convex maximization problem, which is extremely computationally challenging. Most existing works address sparse PCA via methods-such as iteratively computing one sparse PC and deflating the covariance matrix-that do not guarantee the orthogonality, let alone the optimality, of the resulting solution when we seek multiple mutually orthogonal PCs. We challenge this status by reformulating the orthogonality conditions as rank constraints and optimizing over the sparsity and rank constraints simultaneously. We design tight semidefinite relaxations to supply high-quality upper bounds, which we strengthen via additional second-order cone inequalities when each PC's individual sparsity is specified. Further, we derive a combinatorial upper bound on the maximum amount of variance explained as a function of the support. We exploit these relaxations and bounds to propose exact methods and rounding mechanisms that, together, obtain solutions with a bound gap on the order of 0%-15% for real-world datasets with p = 100s or 1000s of features and r ∈ 2, 3 components. Numerically, our algorithms match (and sometimes surpass) the best performing methods in terms of fraction of variance explained and systematically return PCs that are sparse and orthogonal. In contrast, we find that existing methods like deflation return solutions that violate the orthogonality constraints, even when the data is generated according to sparse orthogonal PCs. Altogether, our approach solves sparse PCA problems with multiple components to certifiable (near) optimality in a practically tractable fashion.