mlsanityData to 14 Oct 2026

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

arXiv 2307.13535 ↗First posted 25 Jul 2023stat.ML cs.LGcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper 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

24 of 70 references.

References · 24

  1. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  2. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 51
  3. 2019Subexponential-Time Algorithms for Sparse PCAcited by 41
  4. 2018Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structurecited by 35
  5. 2019Computational Hardness of Certifying Bounds on Constrained PCA Problemscited by 30
  6. 2014Statistical and computational trade-offs in estimation of sparse principal componentscited by 26
  7. 2014Sparse CCA: Adaptive Estimation and Computational Barrierscited by 25
  8. 2013Sparse PCA via Covariance Thresholdingcited by 22
  9. 2015How Robust are Reconstruction Thresholds for Community Detection?cited by 20
  10. 2019Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardnesscited by 13
  11. 2022Generative Principal Component Analysiscited by 12
  12. 2015Sum-of-Squares Lower Bounds for Sparse PCAcited by 10
12 more
  1. 2013Do semidefinite relaxations solve sparse PCA up to the information limit?cited by 9
  2. 2018Sparse Principal Component Analysis via Variable Projectioncited by 9
  3. 2018Using L1-relaxation and integer programming to obtain dual bounds for sparse PCAcited by 8
  4. 2020Exact and Approximation Algorithms for Sparse PCAcited by 8
  5. 2020Solving sparse principal component analysis with global supportcited by 8
  6. 2020A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysiscited by 7
  7. 2020Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Ratescited by 5
  8. 2019Supervised Discriminative Sparse PCA for Com-Characteristic Gene Selection and Tumor Classification on Multiview Biological Datacited by 3
  9. 2015Stay on path: PCA along graph pathscited by 2
  10. 2019Tensor Sparse PCA and Face Recognition: A Novel Approachcited by 2
  11. 2020Non-Sparse PCA in High Dimensions via Cone Projected Power Iterationcited by 2
  12. 2021Multiple Support Recovery Using Very Few Measurements Per Samplecited by 1

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Computationally efficient reductions between some statistical modelscited by 0