Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula

Factorizing low-rank matrices has many applications in machine learning and statistics. For probabilistic models in the Bayes optimal setting, a general expression for the mutual information has been proposed using heuristic statistical physics computations, and proven in few specific cases. Here, we show how to rigorously prove the conjectured formula for the symmetric rank-one case. This allows to express the minimal mean-square-error and to characterize the detectability phase transitions in a large set of estimation problems ranging from community detection to sparse PCA. We also show that for a large set of parameters, an iterative algorithm called approximate message-passing is Bayes optimal. There exists, however, a gap between what currently known polynomial algorithms can do and what is expected information theoretically. Additionally, the proof technique has an interest of its own and exploits three essential ingredients: the interpolation method introduced in statistical physics by Guerra, the analysis of the approximate message-passing algorithm and the theory of spatial coupling and threshold saturation in coding. Our approach is generic and applicable to other open problems in statistical estimation where heuristic statistical physics predictions are available. Consider the following probabilistic rank-one matrix estimation problem: one has access to noisy observations w=(wij)i,j=1 of the pair-wise product of the components of a vector s=(s1, . . . , sn)∈R with i.i.d components distributed as Si∼P0, i=1, . . . , n. The entries of w are observed through a noisy element-wise (possibly non-linear) output probabilistic channel Pout(wij |sisj/ √ n). The goal is to estimate the vector s from w assuming that both P0 and Pout are known and independent of n (noise is symmetric so that wij =wji). Many important problems in statistics and machine learning can be expressed in this way, such as sparse PCA [Zou et al. (2006)], the Wigner spike model [Johnstone and Lu (2012); Deshpande and Montanari (2014)], community detection [Deshpande et al. (2015)] or matrix completion [Candès and Recht (2009)]. Proving a result initially derived by a heuristic method from statistical physics, we give an explicit expression for the mutual information and the information theoretic minimal mean-square-error (MMSE) in the asymptotic n→+∞ limit. Our results imply that for 1 ar X iv :1 60 6. 04 14 2v 1 [ cs .I T ] 1 3 Ju n 20 16 a large region of parameters, the posterior marginal expectations of the underlying signal components (often assumed intractable to compute) can be obtained in the leading order in n using a polynomial-time algorithm called approximate message-passing (AMP) [Rangan and Fletcher (2012); Deshpande and Montanari (2014); Deshpande et al. (2015); Lesieur et al. (2015b)]. We also demonstrate the existence of a region where both AMP and spectral methods [Baik et al. (2005)] fail to provide a good answer to the estimation problem, while it is nevertheless information theoretically possible to do so. We illustrate our theorems with examples and also briefly discuss the implications in terms of computational complexity. 1. Setting and main results 1.1 The additive white Gaussian noise setting A standard and natural setting is the case of additive white Gaussian noise (AWGN) of known variance ∆, wij = sisj √ n + zij √ ∆, (1) where z=(zij)i,j=1 is a symmetric matrix with i.i.d entries Zij∼N (0, 1), 1≤ i≤j≤n. Perhaps surprisingly, it turns out that this Gaussian setting is sufficient to completely characterize all the problems discussed in the introduction, even if these have more complicated output channels. This is made possible by a theorem of channel universality [Krzakala et al. (2016)] (already proven for community detection in [Deshpande et al. (2015)] and conjectured in [Lesieur et al. (2015a)]). This theorem states that given an output channel Pout(w|y), such that logPout(w|y = 0) is three times differentiable with bounded second and third derivatives, then the mutual information satisfies I(S;W)=I(S;SST/ √ n+Z √ ∆)+O( √ n), where ∆ is the inverse Fisher information (evaluated at y = 0) of the output channel: ∆−1 := EPout(w|0)[(∂y logPout(W |y)|y=0)]. Informally, this means that we only have to compute the mutual information for an AWGN channel to take care of a wide range of problems, which can be expressed in terms of their Fisher information. In this paper we derive rigorously, for a large class of signal distributions P0, an explicit one-letter formula for the mutual information per variable I(S;W)/n in the asymptotic limit n→+∞.