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 = (w ij ) n i,j=1 of the pair-wise product of the components of a vector s = (s 1 , . . . , s n ) ∈ R n with i.i.d components distributed as S i ∼ P 0 , i = 1, . . . , n. The entries of w are observed through a noisy element-wise (possibly non-linear) output probabilistic channel P out (w ij |s i s j / √ n). The goal is to estimate the vector s from w assuming that both P 0 and P out are known and independent of n (noise is symmetric so that w ij = w ji ). Many important problems in statistics and machine learning can be expressed in this way, such as sparse PCA [1], the Wigner spiked model [2,3], community detection [4] or matrix completion [5].
Proving a result initially derived by a heuristic method from statistical physics, we give an explicit expression for the mutual information (MI) and the information theoretic minimal mean-square-error (MMSE) in the asymptotic n → ∞ limit. Our results imply that for a large region of parameters, the posterior marginal expectations of the underlying signal components (often assumed intractable 30th Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain.
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 = (w ij ) n i,j=1 of the pair-wise product of the components of a vector s = (s 1 , . . . , s n ) ∈ R n with i.i.d components distributed as S i ∼ P 0 , i = 1, . . . , n. The entries of w are observed through a noisy element-wise (possibly non-linear) output probabilistic channel P out (w ij |s i s j / √ n). The goal is to estimate the vector s from w assuming that both P 0 and P out are known and independent of n (noise is symmetric so that w ij = w ji ). Many important problems in statistics and machine learning can be expressed in this way, such as sparse PCA [1], the Wigner spiked model [2,3], community detection [4] or matrix completion [5].
to compute) can be obtained in the leading order in n using a polynomial-time algorithm called approximate message-passing (AMP) [6,3,4,7]. We also demonstrate the existence of a region where both AMP and spectral methods [8] 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.
The paper considers the estimation of a vector S by observing noisy versions W_{ij} of its coordinate-wise product terms s_i.s_j normalized by \sqrt{n}, under additive Gaussian noise of variance \Delta. The main result is a formula for the limit  (1) \lim_{n --> \infty} 1/n I(S; W)  in terms of the replica symmetric potential function i_{RS}(E, \Delta), which, as a corollary (using the I-MMSE relation), shows that MMSE(\Delta) for the estimation problem above is given by the minimizer E^* of i_{RS}(E, \Delta). As a further corollary it is shown that Approximate Message Passing (AMP), which is known to converge to a stationary point of i_{RS}(E, \Delta) when \Delta is in appropriate range, yields MMSE in the same range. The proof of (1) is the main contribution of the paper. The proof is based on establishing an equality of the two regions over an appropriate interval and then extending it to a larger region over which the (complex extensions of the) two sides are analytic. A key step is to show that the analytic threshold for the left-side of (1), termed \Delta_{OPT}, is at least as much as that for the right-side, \Delta_{RS}. This is facilitated by relating the two thresholds to the threshold for a spatially coupled construction of W_{ij} (which is done in Lemma 3.1 and Lemma 3.2).  
The paper addresses an important topic, namely that of providing formal guarantees for algorithms derived from heuristics in statistical physics. The approach proposed in the paper is very interesting and perhaps novel, at to this reviewer it is, wherein the gap in the thresholds for information theoretic performance and the performance of AMP is bridged by connecting the information theoretic threshold and that for AMP to that of a spatially coupled model. This relation in turn relies on the equality of the threshold for spatially coupled construction and the optimal information theoretic threshold, a phenomenon that has led to a recent breakthrough capacity achieving construction in information theory and is proved here again via Lemma 3.1. Another key step is to show that \Delta_{RS} does not exceed the threshold for the spatially coupled  construction with AMP; this is  the content of Lemma 3.2. While only a sketch of proof is presented, the approach looks convincing and indeed very interesting. The analysis proposed in the paper, if rigorously correct, leads to an interest approach for analyzing the performance of AMP by bringing in a spatially coupled system to relate various thresholds. Whether this contribution is new is beyond the knowledge of this reviewer. Nevertheless, this overall approach is very fascinating.   In addition to the general comments above, I have the following specific comments:  1. The paper and the contribution is rather difficult to follow. The authors mention the connection of their results to several problems  but then only present two applications via examples in Section 2 without clarifying the exact implication of their approach for these examples. In particular, what was the state-of-the-art before this paper and how has this paper furthered the analysis of these applications? Also, I suggest that the authors spend some more space in explaining the connection between the formula derived here and the general inference problem. Perhaps the relation of the left-side to information theoretic threshold and the right-side to the threshold of AMP (via the replica symmetric potential function) can be mentioned at the outset without much details.  2. The proof sketch is very difficult to follow. The authors should first summarize the plan before getting to the details. I have written above what I could follow, which might be wrong. However, a similar description in words of the proof idea of the authors will be very useful.   3. The sentence leading to (8) and the one following it are unclear to me.  In particular, I couldn't follow the observation "so the left hand side of (7) is equal to the derivative of \min_{E}i_{RS(E, \Delta) w.r.t. \Delta^{-1}". Does the other term in i_{RS}(E, \Delta) equals 0 at the min? Also, in the sentence after (8), it seems you interchanged the limit and the integral. If you justify this interchange in a complete version, at least point-out in the sketch that it needs to be done. Finally, understanding the proof sketch of Lemma 3.2 seems beyond the scope of a non-expert.   4. The extensions claimed in 135-39 seem to be much more interesting than the simple case here. If the authors indeed have these extensions available, why not motivate the paper by these extended results. If such extensions are not available as of now, please modify the claim above to be clear about it.