mlsanityData to 7 Oct 2026

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

arXiv 2507.09148 ↗First posted 12 Jul 2025stat.ML cs.LG math.OCcited by 0

Not on the map. Why?

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.

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

Builds on

24 of 47 references.

References · 24

  1. 2019Subexponential-Time Algorithms for Sparse PCAcited by 41
  2. 2014Statistical and computational trade-offs in estimation of sparse principal componentscited by 26
  3. 2018A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimizationcited by 23
  4. 2013Sparse PCA via Covariance Thresholdingcited by 21
  5. 2020Sparse PCA: Algorithms, Adversarial Perturbations and Certificatescited by 18
  6. 2013Sparse PCA through Low-rank Approximationscited by 11
  7. 2013Computational Lower Bounds for Sparse PCAcited by 11
  8. 2020Solving Large-Scale Sparse PCA to Certifiable (Near) Optimalitycited by 11
  9. 2019A Conditional Gradient-Based Augmented Lagrangian Frameworkcited by 10
  10. 2013Do semidefinite relaxations solve sparse PCA up to the information limit?cited by 9
  11. 2015NP-Hardness and Inapproximability of Sparse PCAcited by 8
  12. 2018Using L1-relaxation and integer programming to obtain dual bounds for sparse PCAcited by 8
12 more
  1. 2019On the Burer-Monteiro method for general semidefinite programscited by 8
  2. 2020Exact and Approximation Algorithms for Sparse PCAcited by 8
  3. 2020Solving sparse principal component analysis with global supportcited by 8
  4. 2019On the tightness of SDP relaxations of QCQPscited by 7
  5. 2015Sparse PCA via Bipartite Matchingscited by 6
  6. 2022Sparse PCA: a Geometric Approachcited by 6
  7. 2022Sparse PCA on fixed-rank matricescited by 5
  8. 2017Sparse principal component analysis and its l1-relaxationcited by 4
  9. 2024Efficient Sparse PCA via Block-Diagonalizationcited by 4
  10. 2020Approximation Algorithms for Sparse Principal Component Analysiscited by 3
  11. 2022Accelerated first-order methods for a class of semidefinite programscited by 2
  12. 2019Convexification of Permutation-Invariant Sets and an Application to Sparse PCAcited by 1

Built on by

Not cited yet.