Subexponential-Time Algorithms for Sparse PCA

Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein +1

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 (…