# A Decomposition Framework for Certifiably Optimal Orthogonal Sparse PCA

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 1 Mar 2026.

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

- [Sparse PCA through Low-rank Approximations](https://mlsanity.com/paper/1303.0551/) (2013)
- [NP-Hardness and Inapproximability of Sparse PCA](https://mlsanity.com/paper/1502.05675/) (2015)
- [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)
- [Sparse PCA via Bipartite Matchings](https://mlsanity.com/paper/1508.00625/) (2015)
- [On the Worst-Case Approximability of Sparse PCA](https://mlsanity.com/paper/1507.05950/) (2015)
- [Sparse PCA With Multiple Components](https://mlsanity.com/paper/2209.14790/) (2022)
- [Efficient Sparse PCA via Block-Diagonalization](https://mlsanity.com/paper/2410.14092/) (2024)
- [Fast Density Estimation for Density-based Clustering Methods](https://mlsanity.com/paper/2109.11383/) (2021)
- [The Sparse Principal Component Analysis Problem: Optimality Conditions and Algorithms](https://mlsanity.com/paper/1507.08029/) (2015)

## Abstract (arXiv)

Sparse Principal Component Analysis (SPCA) is an important technique for high-dimensional data analysis, improving interpretability by imposing sparsity on principal components. However, existing methods often fail to simultaneously guarantee sparsity, orthogonality, and optimality of the principal components. To address this challenge, this work introduces a novel Sparse Principal Component Analysis (SPCA) algorithm called textscGS-SPCA (SPCA with Gram-Schmidt Orthogonalization), which simultaneously enforces sparsity, orthogonality, and optimality. However, the original GS-SPCA algorithm is computationally expensive due to the inherent ℓ0-norm constraint. To address this issue, we propose two acceleration strategies: First, we combine Branch-and-Bound with the GS-SPCA algorithm. By incorporating this strategy, we are able to obtain varepsilon-optimal solutions with a trade-off between precision and efficiency, significantly improving computational speed. Second, we propose a decomposition framework for efficiently solving multiple principal components. This framework approximates the covariance matrix using a block-diagonal matrix through a thresholding method, reducing the original SPCA problem to a set of block-wise subproblems on approximately block-diagonal matrices.