# Efficient Sparse PCA via Block-Diagonalization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 18 Oct 2024.

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

- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Sparse PCA via Covariance Thresholding](https://mlsanity.com/paper/1311.5179/) (2013)
- [Selective inference for k-means clustering](https://mlsanity.com/paper/2203.15267/) (2022)
- [Sparse PCA: Algorithms, Adversarial Perturbations and Certificates](https://mlsanity.com/paper/2011.06585/) (2020)
- [Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions](https://mlsanity.com/paper/1708.09479/) (2017)
- [Sparse PCA through Low-rank Approximations](https://mlsanity.com/paper/1303.0551/) (2013)
- [Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality](https://mlsanity.com/paper/2005.05195/) (2020)
- [NP-Hardness and Inapproximability of Sparse PCA](https://mlsanity.com/paper/1502.05675/) (2015)
- [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)
- [Sparse PCA via Bipartite Matchings](https://mlsanity.com/paper/1508.00625/) (2015)
- [Block-diagonal covariance selection for high-dimensional Gaussian graphical models](https://mlsanity.com/paper/1511.04033/) (2015)
- [Optimal estimation of the null distribution in large-scale inference](https://mlsanity.com/paper/2401.06350/) (2024)
- [Sparse PCA on fixed-rank matrices](https://mlsanity.com/paper/2201.02487/) (2022)
- [Learning Large-Scale MTP2 Gaussian Graphical Models via Bridge-Block Decomposition](https://mlsanity.com/paper/2309.13405/) (2023)
- [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)
- [Approximation Algorithms for Sparse Principal Component Analysis](https://mlsanity.com/paper/2006.12748/) (2020)
- [Sparsity meets correlation in Gaussian sequence model](https://mlsanity.com/paper/2312.09356/) (2023)
- [Projection Algorithms for Non-Convex Minimization with Application to Sparse Principal Component Analysis](https://mlsanity.com/paper/1404.4132/) (2014)

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

- [sparseGeoHOPCA: A Geometric Solution to Sparse Higher-Order PCA Without Covariance Estimation](https://mlsanity.com/paper/2506.08670/) (2025)
- [A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation](https://mlsanity.com/paper/2507.09148/) (2025)
- [A Decomposition Framework for Certifiably Optimal Orthogonal Sparse PCA](https://mlsanity.com/paper/2603.01144/) (2026)
- [Combinatorial Sparse PCA Beyond the Spiked Identity Model](https://mlsanity.com/paper/2603.02607/) (2026)

## Abstract (arXiv)

Sparse Principal Component Analysis (Sparse PCA) is a pivotal tool in data analysis and dimensionality reduction. However, Sparse PCA is a challenging problem in both theory and practice: it is known to be NP-hard and current exact methods generally require exponential runtime. In this paper, we propose a novel framework to efficiently approximate Sparse PCA by (i) approximating the general input covariance matrix with a re-sorted block-diagonal matrix, (ii) solving the Sparse PCA sub-problem in each block, and (iii) reconstructing the solution to the original problem. Our framework is simple and powerful: it can leverage any off-the-shelf Sparse PCA algorithm and achieve significant computational speedups, with a minor additive error that is linear in the approximation error of the block-diagonal matrix. Suppose g(k, d) is the runtime of an algorithm (approximately) solving Sparse PCA in dimension d and with sparsity constant k. Our framework, when integrated with this algorithm, reduces the runtime to Oleft(fracdd^star · g(k, d^star) + d2right), where d^star ≤ d is the largest block size of the block-diagonal matrix. For instance, integrating our framework with the Branch-and-Bound algorithm reduces the complexity from g(k, d) = O(k3· dk) to O(k3· d · (d^star)k-1), demonstrating exponential speedups if d^star is small. We perform large-scale evaluations on many real-world datasets: for exact Sparse PCA algorithm, our method achieves an average speedup factor of 100.50, while maintaining an average approximation error of 0.61%; for approximate Sparse PCA algorithm, our method achieves an average speedup factor of 6.00 and an average approximation error of -0.91%, meaning that our method oftentimes finds better solutions.