MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel

Abstract

This paper considers probabilistic estimation of a low-rank matrix from non-linear element-wise measurements of its elements. We derive the corresponding approximate message passing (AMP) algorithm and its state evolution. Relying on non-rigorous but standard assumptions motivated by statistical physics, we characterize the minimum mean squared error (MMSE) achievable information theoretically and with the AMP algorithm. Unlike in related problems of linear estimation, in the present setting the MMSE depends on the output channel only trough a single parameter - its Fisher information. We illustrate this striking finding by analysis of submatrix localization, and of detection of communities hidden in a dense stochastic block model. For this example we locate the computational and statistical boundaries that are not equal for rank larger than four.

10 pages, Allerton Conference on Communication, Control, and Computing 2015

References in corpus (6)

• Graph spectra and the detectability of community structure in networks
• Finding large average submatrices in high dimensional data
• Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Phase Transitions in Sparse PCA
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model

Cited by in corpus (42)

• Statistical physics of inference: Thresholds and algorithms
• Phase Transitions in Semidefinite Relaxations
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Mutual Information in Rank-One Matrix Estimation
• Message-passing algorithms for synchronization problems over compact groups
• Statistical and computational phase transitions in spiked tensor estimation
• Computational Barriers to Estimation from Low-Degree Polynomials
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Finite Sample Analysis of Approximate Message Passing Algorithms
• Fundamental limits of low-rank matrix estimation: the non-symmetric case
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Approximate Survey Propagation for Statistical Inference
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering
• Subexponential-Time Algorithms for Sparse PCA
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
• Statistical mechanics of low-rank tensor decomposition
• Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method
• Weighted Community Detection and Data Clustering Using Message Passing
• Detection limits in the high-dimensional spiked rectangular model
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
• Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
• Universality of Computational Lower Bounds for Submatrix Detection
• Spectral Method for Multiplexed Phase Retrieval and Application in Optical Imaging in Complex Media
• Counterexamples to the Low-Degree Conjecture
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• On the Randomized Complexity of Minimizing a Convex Quadratic Function
• Adapting to Unknown Noise Distribution in Matrix Denoising
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
• Weak detection in the spiked Wigner model
• Application of information-percolation method to reconstruction problems on graphs
• Detection of Signal in the Spiked Rectangular Models
• Bayesian reconstruction of memories stored in neural networks from their connectivity
• Spherical Integrals of Sublinear Rank
• Mismatched Estimation of rank-one symmetric matrices under Gaussian noise
• The planted matching problem: Sharp threshold and infinite-order phase transition
• Hypothesis testing with low-degree polynomials in the Morris class of exponential families
• Empirical Bayes PCA in high dimensions
• Dense Limit of the Dawid-Skene Model for Crowdsourcing and Regions of Sub-optimality of Message Passing Algorithms
• Low-rank Matrix Estimation with Inhomogeneous Noise
• Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions