# A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 47 references that are in the map.
- First posted on arXiv 12 Jul 2025.

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

- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Statistical and computational trade-offs in estimation of sparse principal components](https://mlsanity.com/paper/1408.5369/) (2014)
- [A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization](https://mlsanity.com/paper/1803.02924/) (2018)
- [Sparse PCA via Covariance Thresholding](https://mlsanity.com/paper/1311.5179/) (2013)
- [Sparse PCA: Algorithms, Adversarial Perturbations and Certificates](https://mlsanity.com/paper/2011.06585/) (2020)
- [Sparse PCA through Low-rank Approximations](https://mlsanity.com/paper/1303.0551/) (2013)
- [Computational Lower Bounds for Sparse PCA](https://mlsanity.com/paper/1304.0828/) (2013)
- [Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality](https://mlsanity.com/paper/2005.05195/) (2020)
- [A Conditional Gradient-Based Augmented Lagrangian Framework](https://mlsanity.com/paper/1901.04013/) (2019)
- [Do semidefinite relaxations solve sparse PCA up to the information limit?](https://mlsanity.com/paper/1306.3690/) (2013)
- [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)
- [On the Burer-Monteiro method for general semidefinite programs](https://mlsanity.com/paper/1904.07147/) (2019)
- [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)
- [On the tightness of SDP relaxations of QCQPs](https://mlsanity.com/paper/1911.09195/) (2019)
- [Sparse PCA via Bipartite Matchings](https://mlsanity.com/paper/1508.00625/) (2015)
- [Sparse PCA: a Geometric Approach](https://mlsanity.com/paper/2210.06590/) (2022)
- [Sparse PCA on fixed-rank matrices](https://mlsanity.com/paper/2201.02487/) (2022)
- [Sparse principal component analysis and its l1-relaxation](https://mlsanity.com/paper/1712.00800/) (2017)
- [Efficient Sparse PCA via Block-Diagonalization](https://mlsanity.com/paper/2410.14092/) (2024)
- [Approximation Algorithms for Sparse Principal Component Analysis](https://mlsanity.com/paper/2006.12748/) (2020)
- [Accelerated first-order methods for a class of semidefinite programs](https://mlsanity.com/paper/2206.00224/) (2022)
- [Convexification of Permutation-Invariant Sets and an Application to Sparse PCA](https://mlsanity.com/paper/1910.02573/) (2019)

## Abstract (arXiv)

Sparse Principal Component Analysis (SPCA) is a fundamental technique for dimensionality reduction, and is NP-hard. In this paper, we introduce a randomized approximation algorithm for SPCA, which is based on the basic SDP relaxation. Our algorithm takes an (approximate) SDP solution, constructs one deterministic sparse solution and several randomized solutions, and outputs the best among them. Our algorithm has an approximation ratio of at most the sparsity constant with high probability, if called enough times. Under a technical assumption, which is consistently satisfied in our numerical tests, the average approximation ratio is also bounded by O(logd), where d is the number of features. We show that this technical assumption is satisfied if the SDP solution is low-rank, or has exponentially decaying eigenvalues. We then present two classes of instances for which this technical assumption holds. We also demonstrate that in a covariance model, which generalizes the spiked Wishart model, the deterministic solution in our algorithm achieves a near-optimal approximation ratio. We demonstrate the efficacy of our algorithm through numerical tests on real-world datasets.