Subexponential hardness of strong detection below the BBP transition
Fix constants γ>0\gamma > 0γ>0, β>−1\beta > -1β>−1, and ρ∈(0,1)\rho \in (0,1)ρ∈(0,1). Let N=N(n)N=N(n)N=N(n) satisfy n/N→γn/N \to \gamman/N→γ as n→∞n \to \inftyn→∞. In the spiked Wishart model, under Q\mathbb{Q}Q the observa…