Polynomial-time support-recovery barrier for sparse PCA

Consider the single-spike model with dimension $p$, sample size $n$, spike support size $k$, and signal strength $\beta$. Let $\mathbf{z}$ denote the sparse spike, and let $p/n\to c$. Polynomial-time support-recovery barrier conjecture. For fixed signal strength satisfying

$$\beta\leq\sqrt{p/n},$$

and fixed $\varepsilon>0$, if

$$k=n^{0.5+\varepsilon},$$

then no polynomial-time algorithm can recover the support of $\mathbf{z}$ with probability tending to one as $(n,p,k)\to\infty$. This sharpens the preceding computational-barrier claim to support recovery in a specified asymptotic regime and is motivated by the failure of sophisticated SDP-based estimation methods.