Statistical mechanics of the maximum-average submatrix problem

03/09/2023
by   Vittorio Erba, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset