Statistical mechanics of the maximum-average submatrix problem
share
We study the maximum-average submatrix problem, in which given an N × N matrix J one needs to find the k × k submatrix with the largest average of entries. We study the problem for random matrices J whose entries are i.i.d. random variables by mapping it to a variant of the Sherrington-Kirkpatrick spin-glass model at fixed magnetization. We characterize analytically the phase diagram of the model as a function of the submatrix average and the size of the submatrix k in the limit N→∞. We consider submatrices of size k = m N with 0 < m < 1. We find a rich phase diagram, including dynamical, static one-step replica symmetry breaking and full-step replica symmetry breaking. In the limit of m → 0, we find a simpler phase diagram featuring a frozen 1-RSB phase, where the Gibbs measure is composed of exponentially many pure states each with zero entropy.
READ FULL TEXT