Back to Search
Start Over
Subexponential-Time Algorithms for Sparse PCA.
- Source :
- Foundations of Computational Mathematics; Jun2024, Vol. 24 Issue 3, p865-914, 50p
- Publication Year :
- 2024
-
Abstract
- We study the computational cost of recovering a unit-norm sparse principal component x ∈ R n planted in a random matrix, in either the Wigner or Wishart spiked model (observing either W + λ x x ⊤ with W drawn from the Gaussian orthogonal ensemble, or N independent samples from N (0 , I n + β x x ⊤) , respectively). Prior work has shown that when the signal-to-noise ratio (λ or β N / n , respectively) is a small constant and the fraction of nonzero entries in the planted vector is ‖ x ‖ 0 / n = ρ , it is possible to recover x in polynomial time if ρ ≲ 1 / n . While it is possible to recover x in exponential time under the weaker condition ρ ≪ 1 , it is believed that polynomial-time recovery is impossible unless ρ ≲ 1 / n . We investigate the precise amount of time required for recovery in the "possible but hard" regime 1 / n ≪ ρ ≪ 1 by exploring the power of subexponential-time algorithms, i.e., algorithms running in time exp (n δ) for some constant δ ∈ (0 , 1) . For any 1 / n ≪ ρ ≪ 1 , we give a recovery algorithm with runtime roughly exp (ρ 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 (ρ 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 16153375
- Volume :
- 24
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Foundations of Computational Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 177925640
- Full Text :
- https://doi.org/10.1007/s10208-023-09603-0