Fast and Provable Algorithms for Sparse PCA with Improved Sample Complexity

Information-theoretic sample complexity is n = Ω(k log p) * . Existing polynomial-time algorithms require at least O(k 2 ) samples for successful recovery (Deshpande and Montanari, 2016), highlighting a significant gap in sample efficiency. Reductions from the planted-clique conjecture imply that, without further assumptions, no polynomial-time algorithm can attain the information-theoretic sample complexity † . Question: Can we design a polynomial-time algorithm to bridge the gap under some assumption of the model (1)?