Metadata only
Date
2019Type
- Working Paper
ETH Bibliography
no
Altmetrics
Abstract
We study the computational cost of recovering a unit-norm sparse principal component x∈ℝn planted in a random matrix, in either the Wigner or Wishart spiked model (observing either W+λxx⊤ with W drawn from the Gaussian orthogonal ensemble, or N independent samples from (0,In+βxx⊤), 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(ρ2n), 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. Show more
Publication status
publishedExternal links
Journal / series
arXivPages / Article No.
Publisher
Cornell UniversityOrganisational unit
09679 - Bandeira, Afonso / Bandeira, Afonso
Related publications and datasets
Is previous version of: http://hdl.handle.net/20.500.11850/601169
More
Show all metadata
ETH Bibliography
no
Altmetrics