The Overlap Gap Property in Principal Submatrix Recovery

Understand

We study support recovery for a $k \times k$ principal submatrix with elevated mean $\lambda/N$, hidden in an $N\times 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}.