Mutual information in rank-one matrix estimation

We consider the estimation of a n-dimensional vector x from the knowledge of noisy and possibility non-linear element-wise measurements of xx T , a very generic problem that contains, e.g. stochastic 2-block model, submatrix localization or the spike perturbation of random matrices. Using an interpolation method proposed by Guerra 1 and later refined by Korada and Macris 2, we prove that the Bethe mutual information (related to the Bethe free energy and conjectured to be exact by Lesieur et al. 3 on the basis of the non-rigorous cavity method) always yields an upper bound to the exact mutual information. A lower bound is also provided using a similar technique. For concreteness, we illustrate our findings on the sparse PCA problem, and observe that (a) our bounds match for a large region of parameters and (b) that there exists a phase transition in a region where the spectrum remains uninformative. While we present only the case of rank-one symmetric matrix estimation, our proof technique is readily extendable to low-rank symmetric matrix or low-rank symmetric tensor estimation.