Mutual Information in Rank-One Matrix Estimation

Abstract

We consider the estimation of a n-dimensional vector x from the knowledge of noisy and possibility non-linear element-wise measurements of xxT , a very generic problem that contains, e.g. stochastic 2-block model, submatrix localization or the spike perturbation of random matrices. We use an interpolation method proposed by Guerra and later refined by Korada and Macris. We prove that the Bethe mutual information (related to the Bethe free energy and conjectured to be exact by Lesieur et al. on the basis of the non-rigorous cavity method) always yields an upper bound to the exact mutual information. We also provide a lower bound 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 it exists a phase transition in a region where the spectum 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

8 pages, 1 figures

References in corpus (2)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Mutual Information in Rank-One Matrix Estimation

Cited by in corpus (32)

• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• Information-theoretic thresholds from the cavity method
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Mutual Information in Rank-One Matrix Estimation
• The Mutual Information in Random Linear Estimation
• Message-passing algorithms for synchronization problems over compact groups
• Statistical and computational phase transitions in spiked tensor estimation
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Fundamental limits of low-rank matrix estimation: the non-symmetric case
• Fundamental limits of detection in the spiked Wigner model
• Estimation in the spiked Wigner model: A short proof of the replica formula
• Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering
• Subexponential-Time Algorithms for Sparse PCA
• Finite Size Corrections and Likelihood Ratio Fluctuations in the Spiked Wigner Model
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation
• The Overlap Gap Property in Principal Submatrix Recovery
• 0-1 phase transitions in sparse spiked matrix estimation
• Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method
• Detection limits in the high-dimensional spiked rectangular model
• Universality of Computational Lower Bounds for Submatrix Detection
• Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
• On the Randomized Complexity of Minimizing a Convex Quadratic Function
• Mutual information for low-rank even-order symmetric tensor estimation
• Streaming Bayesian inference: theoretical limits and mini-batch approximate message-passing
• Phase transition in the spiked random tensor with Rademacher prior
• Application of information-percolation method to reconstruction problems on graphs
• Local convexity of the TAP free energy and AMP convergence for Z2-synchronization
• Spherical Integrals of Sublinear Rank
• Low-rank Matrix Estimation with Inhomogeneous Noise
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• Universality of Approximate Message Passing Algorithms