  This paper studies the minimax detection of a small submatrix of elevated
mean in a large matrix contaminated by additive Gaussian noise. To investigate
the tradeoff between statistical performance and computational cost from a
complexity-theoretic perspective, we consider a sequence of discretized models
which are asymptotically equivalent to the Gaussian model. Under the hypothesis
that the planted clique detection problem cannot be solved in randomized
polynomial time when the clique size is of smaller order than the square root
of the graph size, the following phase transition phenomenon is established:
when the size of the large matrix $p\to\infty$, if the submatrix size
$k=\Theta(p^{\alpha})$ for any $\alpha\in(0,{2}/{3})$, computational complexity
constraints can incur a severe penalty on the statistical performance in the
sense that any randomized polynomial-time test is minimax suboptimal by a
polynomial factor in $p$; if $k=\Theta(p^{\alpha})$ for any
$\alpha\in({2}/{3},1)$, minimax optimal detection can be attained within
constant factors in linear time. Using Schatten norm loss as a representative
example, we show that the hardness of attaining the minimax estimation rate can
crucially depend on the loss function. Implications on the hardness of support
recovery are also obtained.
