  In this paper, we study the problems of detection and recovery of hidden
submatrices with elevated means inside a large Gaussian random matrix. We
consider two different structures for the planted submatrices. In the first
model, the planted matrices are disjoint, and their row and column indices can
be arbitrary. Inspired by scientific applications, the second model restricts
the row and column indices to be consecutive. In the detection problem, under
the null hypothesis, the observed matrix is a realization of independent and
identically distributed standard normal entries. Under the alternative, there
exists a set of hidden submatrices with elevated means inside the same standard
normal matrix. Recovery refers to the task of locating the hidden submatrices.
For both problems, and for both models, we characterize the statistical and
computational barriers by deriving information-theoretic lower bounds,
designing and analyzing algorithms matching those bounds, and proving
computational lower bounds based on the low-degree polynomials conjecture. In
particular, we show that the space of the model parameters (i.e., number of
planted submatrices, their dimensions, and elevated mean) can be partitioned
into three regions: the impossible regime, where all algorithms fail; the hard
regime, where while detection or recovery are statistically possible, we give
some evidence that polynomial-time algorithm do not exist; and finally the easy
regime, where polynomial-time algorithms exist.
