Source-linked AI summary
Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
Jean Barbier, Mohamad Dia, Nicolas Macris, Florent Krzakala, Thibault Lesieur, Lenka Zdeborova
TL;DR
The paper studies asymptotic mutual information and estimation in the additive white Gaussian noise setting. It proves a replica-symmetric formula under a discrete-prior condition, derives MMSE and phase-transition results, and characterizes when AMP achieves Bayes-optimal performance.
Problem
The paper addresses computing asymptotic mutual information per variable in the additive white Gaussian noise setting, where this quantity determines information-theoretic thresholds and MMSE.
Method
The paper proves the mutual-information formula through the replica-symmetric potential iRS(E; ∆), relating its stationary-point equation to AMP state evolution.
Results
Under a discrete P0 with at most three stationary points, the theorem gives the asymptotic mutual-information formula and associated MMSE characterization; AMP reaches the asymptotic MMSE iff ∆<∆AMP or ∆>∆RS.
Takeaways & Limitations
The analysis identifies three phase-transition scenarios and an algorithmic gap when ∆AMP<∆RS, while AMP is Bayes optimal outside the intermediate interval.
Takeaways & Limitations
The treatment assumes at most three stationary points; cases with more than three stationary points and multiple phase transitions require further work.
Abstract
from arXiv · showhide
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.
1. Setting and main results
The paper rigorously derives the replica-symmetric formula for asymptotic mutual information and MMSE in symmetric rank-one matrix estimation. It also characterizes AMP optimality, phase-transition thresholds, and computational gaps under stated assumptions.
- Main result: Channel universality reduces a broad class of output channels to an AWGN problem whose effective noise is determined by inverse Fisher information.The reduction applies under smoothness and bounded-derivative conditions on log Pout(w|y=0).
- Main result: Theorem 1 proves an explicit one-letter formula for asymptotic mutual information per variable using the replica-symmetric potential iRS(E; ∆).The theorem assumes the signal distribution is discrete and that the potential has at most three stationary points.
- Main result: The asymptotic matrix-MMSE is v2−(v−argmin_E iRS(E; ∆))2 for ∆ ≠ ∆RS, while the complete vector-MMSE identity is not proved in every regime.The vector-MMSE conclusion is established in the regimes ∆<∆AMP or ∆>∆RS.
- Discussion: AMP reaches Bayes-optimal matrix- and vector-MMSE exactly when ∆<∆AMP or ∆>∆RS, but an information-theoretic gap remains between these thresholds in the first-order transition regime.In the intermediate region, AMP can be trapped by a locally stable bad solution even though the global optimum is information-theoretically attainable.
- Discussion: The analysis identifies three possible phase-transition scenarios and is readily extendable beyond rank-one symmetric matrix estimation, although more than three stationary points require additional work.The proof combines interpolation, AMP analysis, and spatial coupling or threshold-saturation ideas.
2. Two examples: Wigner spike model and community detection
The examples apply the replica formula to spiked Wigner and asymmetric community-detection models, revealing regions where information-theoretic recovery exceeds AMP and spectral methods. They also connect the low-density Wigner regime to a balanced planted-clique problem.
- Spiked Wigner model: For sparse Bernoulli spiked Wigner models, the results rigorously determine the MMSE for ρ≤0.041(1) and identify a computational gap when ∆AMP < ∆ < ∆Opt = ∆RS.The global minimum gives the MMSE, while AMP can be trapped by a different local minimum.
- Phase diagrams: The phase diagram compares noise variance ∆ against density ρ for spiked Wigner and asymmetric community detection, with AMP optimal except between blue and red lines in the Wigner plot.The figure also shows a large gap between AMP and spectral methods in the Wigner setting.
- Asymmetric community detection: When ρ<ρc, a computational gap ∆AMP < ∆Opt = ∆RS appears because AMP and spectral methods miss overlap that is information-theoretically attainable for ∆>1.The balanced model has identical degree distributions across groups, making them harder to distinguish.
- Asymmetric community detection: For asymmetric community detection with ρc = 1/2−1/12, recovery better than chance is information-theoretically possible iff ∆<1 when ρ>ρc.For ρ<ρc, estimation remains information-theoretically possible at larger noise, while AMP and spectral methods retain the transition ∆<1.
- Spiked Wigner model: At very low density, the information-theoretic transition scales as ∆Opt(ρ →0) = 1/(4ρ| log ρ|).The passage presents persistence of this scaling for ρ=O(1) as a speculation.
- Spiked Wigner model: In the balanced planted-clique correspondence, AMP and spectral methods detect cliques above np/(1−p), whereas the information-theoretic threshold is 4p log(n)/(1−p).The balanced setting makes the AMP and spectral limits coincide.
3. Proofs
The proof combines spatial coupling, interpolation, and AMP state evolution to connect the coupled system’s algorithmic threshold with the replica-symmetric threshold. Equality of coupled and original mutual informations then yields the replica formula and its MMSE consequences.
- Spatial coupling: The coupled construction uses a ring of blocks with neighboring interactions controlled by a coupling window w.The coupling matrix is translation-invariant, supported within distance w, smooth, doubly stochastic, and has non-negative Fourier transform.
- Spatial coupling: Spatial coupling preserves the asymptotic mutual information per variable between the coupled and original systems.This also preserves their non-analyticity points and gives ∆Opt,coup = ∆Opt.
- AMP analysis: AMP performance on the coupled system is characterized by state evolution, which tracks blockwise vector-MSE through scalar AWGN systems.The blockwise errors form a monotone sequence converging to a limit that defines the coupled algorithmic threshold.
- Threshold saturation: Threshold saturation gives ∆AMP,coup ≥ ∆RS, while mutual-information preservation identifies ∆Opt,coup with ∆Opt.Together with the threshold ordering used in the proof, these inequalities force ∆Opt = ∆RS.
- Replica formula: For ∆≤∆AMP, AMP reaches the good stationary point and the I-MMSE relation integrates the replica-symmetric expression from the zero-noise limit.The argument extends across the intermediate range by analyticity and then uses the bad global minimum for ∆>∆RS.
- Consequences and limitations: The MMSE proof identifies the limiting matrix-MMSE with the replica-symmetric minimizer, but equality between matrix- and vector-MMSE remains technically incomplete in part of the transition region.Nishimori identities and concentration give an inequality; the authors state that technicalities prevent completing equality in general.