# A greedy anytime algorithm for sparse PCA

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2019.

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

- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [The Complexity of Sparse Tensor PCA](https://mlsanity.com/paper/2106.06308/) (2021)
- [SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More](https://mlsanity.com/paper/2412.21203/) (2024)
- [Sparse PCA Beyond Covariance Thresholding](https://mlsanity.com/paper/2302.10158/) (2023)
- [On the Equality of the ELBO to a Sum of Entropies at Stationary Points of Learning](https://mlsanity.com/paper/2209.03077/) (2022)

## Abstract (arXiv)

The taxing computational effort that is involved in solving some high-dimensional statistical problems, in particular problems involving non-convex optimization, has popularized the development and analysis of algorithms that run efficiently (polynomial-time) but with no general guarantee on statistical consistency. In light of the ever-increasing compute power and decreasing costs, a more useful characterization of algorithms is by their ability to calibrate the invested computational effort with various characteristics of the input at hand and with the available computational resources. For example, design an algorithm that always guarantees statistical consistency of its output by increasing the running time as the SNR weakens. We propose a new greedy algorithm for the ℓ0-sparse PCA problem which supports the calibration principle. We provide both a rigorous analysis of our algorithm in the spiked covariance model, as well as simulation results and comparison with other existing methods. Our findings show that our algorithm recovers the spike in SNR regimes where all polynomial-time algorithms fail while running in a reasonable parallel-time on a cluster.