# Sparse PCA on fixed-rank matrices

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 37 references that are in the map.
- First posted on arXiv 7 Jan 2022.

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

- [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)
- [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)
- [The Sparse Principal Component of a Constant-rank Matrix](https://mlsanity.com/paper/1312.5891/) (2013)

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

- [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)
- [A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering](https://mlsanity.com/paper/2403.11351/) (2024)
- [Learning with Covariance Matrices: Principal Component Analysis Meets Learning with Graphs](https://mlsanity.com/paper/2609.10490/) (2026)
- [A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation](https://mlsanity.com/paper/2507.09148/) (2025)

## Abstract (arXiv)

Sparse PCA is the optimization problem obtained from PCA by adding a sparsity constraint on the principal components. Sparse PCA is NP-hard and hard to approximate even in the single-component case. In this paper we settle the computational complexity of sparse PCA with respect to the rank of the covariance matrix. We show that, if the rank of the covariance matrix is a fixed value, then there is an algorithm that solves sparse PCA to global optimality, whose running time is polynomial in the number of features. We also prove a similar result for the version of sparse PCA which requires the principal components to have disjoint supports.