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

Abstract

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.

References in corpus (2)

• Mutual Information in Rank-One Matrix Estimation
• Computational Lower Bounds for Sparse PCA

Cited by in corpus (32)

• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• The Mutual Information in Random Linear Estimation
• Message-passing algorithms for synchronization problems over compact groups
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• Fundamental limits of detection in the spiked Wigner model
• Statistical limits of dictionary learning: random matrix theory and the spectral replica method
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Subexponential-Time Algorithms for Sparse PCA
• Hamilton-Jacobi equations for mean-field disordered systems
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation
• The Overlap Gap Property in Principal Submatrix Recovery
• Phase transition in random tensors with multiple independent spikes
• Detection limits in the high-dimensional spiked rectangular model
• Predicting Different Types of Subtle Toxicity in Unhealthy Online Conversations
• Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
• Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures
• Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization
• Adapting to Unknown Noise Distribution in Matrix Denoising
• Weak Detection in the Spiked Wigner Model with General Rank
• Weak detection in the spiked Wigner model
• Inference and mutual information on random factor graphs
• Local convexity of the TAP free energy and AMP convergence for Z2-synchronization
• Application of information-percolation method to reconstruction problems on graphs
• Mutual Information for the Stochastic Block Model by the Adaptive Interpolation Method
• Spherical Integrals of Sublinear Rank
• Gauge theory for mixed $p$-spin glasses
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Asymptotic mutual information in quadratic estimation problems over compact groups
• Low-rank Matrix Estimation with Inhomogeneous Noise
• Empirical Bayes PCA in high dimensions
• Universality of Approximate Message Passing Algorithms