Subexponential-Time Algorithms for Sparse PCA

Abstract

We study the computational cost of recovering a unit-norm sparse principal component $x\in {\mathbb{R}}^n$ planted in a random matrix, in either the Wigner or Wishart spiked model (observing either $W+\lambda x{x}^{\top }$ with $W$ drawn from the Gaussian orthogonal ensemble, or $N$ independent samples from $\mathcal{N}(0,I_n+\beta x{x}^{\top })$, respectively). Prior work has shown that when the signal-to-noise ratio ($\lambda$ or $\beta \sqrt{N/n}$, respectively) is a small constant and the fraction of nonzero entries in the planted vector is $\Vert x{\Vert }_0/n=\rho$, it is possible to recover $x$ in polynomial time if $\rho \lesssim 1/\sqrt{n}$. While it is possible to recover $x$ in exponential time under the weaker condition $\rho \ll 1$, it is believed that polynomial-time recovery is impossible unless $\rho \lesssim 1/\sqrt{n}$. We investigate the precise amount of time required for recovery in the "possible but hard" regime $1/\sqrt{n}\ll \rho \ll 1$ by exploring the power of subexponential-time algorithms, i.e., algorithms running in time $\exp (n^{\delta })$ for some constant $\delta \in (0,1)$. For any $1/\sqrt{n}\ll \rho \ll 1$, we give a recovery algorithm with runtime roughly $\exp ({\rho }^{2}n)$, demonstrating a smooth tradeoff between sparsity and runtime. Our family of algorithms interpolates smoothly between two existing algorithms: the polynomial-time diagonal thresholding algorithm and the $\exp (\rho n)$-time exhaustive search algorithm. Furthermore, by analyzing the low-degree likelihood ratio, we give rigorous evidence suggesting that the tradeoff achieved by our algorithms is optimal.

44 pages

References in corpus (17)

• Phase transition in the detection of modules in sparse networks
• Sparse Principal Components Analysis
• A direct formulation for sparse PCA using semidefinite programming
• A statistical model for tensor PCA
• Augmented sparse principal component analysis for high dimensional data
• Computational Lower Bounds for Sparse PCA
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Tensor principal component analysis via sum-of-squares proofs
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Fundamental limits of low-rank matrix estimation: the non-symmetric case
• Fundamental limits of detection in the spiked Wigner model
• Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• Finite Size Corrections and Likelihood Ratio Fluctuations in the Spiked Wigner Model
• Bayesian estimation from few samples: community detection and related problems
• A greedy anytime algorithm for sparse PCA
• Sparse PCA from Sparse Linear Regression

Cited by in corpus (8)

• Computational Barriers to Estimation from Low-Degree Polynomials
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Counterexamples to the Low-Degree Conjecture
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property
• A greedy anytime algorithm for sparse PCA
• Hypothesis testing with low-degree polynomials in the Morris class of exponential families
• Average-Case Integrality Gap for Non-Negative Principal Component Analysis
• Logspace Reducibility From Secret Leakage Planted Clique