# Do algorithms and barriers for sparse principal component analysis extend to other structured settings?

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 70 references that are in the map.
- First posted on arXiv 25 Jul 2023.

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

- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [Statistical and computational trade-offs in estimation of sparse principal components](https://mlsanity.com/paper/1408.5369/) (2014)
- [Sparse CCA: Adaptive Estimation and Computational Barriers](https://mlsanity.com/paper/1409.8565/) (2014)
- [Sparse PCA via Covariance Thresholding](https://mlsanity.com/paper/1311.5179/) (2013)
- [How Robust are Reconstruction Thresholds for Community Detection?](https://mlsanity.com/paper/1511.01473/) (2015)
- [Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness](https://mlsanity.com/paper/1902.07380/) (2019)
- [Generative Principal Component Analysis](https://mlsanity.com/paper/2203.09693/) (2022)
- [Sum-of-Squares Lower Bounds for Sparse PCA](https://mlsanity.com/paper/1507.06370/) (2015)
- [Do semidefinite relaxations solve sparse PCA up to the information limit?](https://mlsanity.com/paper/1306.3690/) (2013)
- [Sparse Principal Component Analysis via Variable Projection](https://mlsanity.com/paper/1804.00341/) (2018)
- [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)
- [A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis](https://mlsanity.com/paper/2007.09524/) (2020)
- [Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates](https://mlsanity.com/paper/2002.07624/) (2020)
- [Supervised Discriminative Sparse PCA for Com-Characteristic Gene Selection and Tumor Classification on Multiview Biological Data](https://mlsanity.com/paper/1905.11837/) (2019)
- [Stay on path: PCA along graph paths](https://mlsanity.com/paper/1506.02344/) (2015)
- [Tensor Sparse PCA and Face Recognition: A Novel Approach](https://mlsanity.com/paper/1904.08496/) (2019)
- [Non-Sparse PCA in High Dimensions via Cone Projected Power Iteration](https://mlsanity.com/paper/2005.07587/) (2020)
- [Multiple Support Recovery Using Very Few Measurements Per Sample](https://mlsanity.com/paper/2105.09855/) (2021)

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

- [Computationally efficient reductions between some statistical models](https://mlsanity.com/paper/2402.07717/) (2024)

## Abstract (arXiv)

We study a principal component analysis problem under the spiked Wishart model in which the structure in the signal is captured by a class of union-of-subspace models. This general class includes vanilla sparse PCA as well as its variants with graph sparsity. With the goal of studying these problems under a unified statistical and computational lens, we establish fundamental limits that depend on the geometry of the problem instance, and show that a natural projected power method exhibits local convergence to the statistically near-optimal neighborhood of the solution. We complement these results with end-to-end analyses of two important special cases given by path and tree sparsity in a general basis, showing initialization methods and matching evidence of computational hardness. Overall, our results indicate that several of the phenomena observed for vanilla sparse PCA extend in a natural fashion to its structured counterparts.