We study support recovery for a $k times k$ principal submatrix with elevated mean $lambda/N$, hidden in an $Ntimes N$ symmetric mean zero Gaussian matrix. Here $lambda>0$ is a universal constant, and we assume $k = N rho$ for some constant $rho in (0,1)$. We establish that {there exists a constant $C>0$ such that} the MLE recovers a constant proportion of the hidden submatrix if $lambda {geq C} sqrt{frac{1}{rho} log frac{1}{rho}}$, {while such recovery is information theoretically impossible if $lambda = o( sqrt{frac{1}{rho} log frac{1}{rho}} )$}. The MLE is computationally intractable in general, and in fact, for $rho>0$ sufficiently small, this problem is conjectured to exhibit a emph{statistical-computational gap}. To provide rigorous evidence for this, we study the likelihood landscape for this problem, and establish that for some $varepsilon>0$ and $sqrt{frac{1}{rho} log frac{1}{rho} } ll lambda ll frac{1}{rho^{1/2 + varepsilon}}$, the problem exhibits a variant of the emph{Overlap-Gap-Property (OGP)}. As a direct consequence, we establish that a family of local MCMC based algorithms do not achieve optimal recovery. Finally, we establish that for $lambda > 1/rho$, a simple spectral method recovers a constant proportion of the hidden submatrix.
Download