MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
arXiv:1507.03857 · doi:10.1109/ALLERTON.2015.7447070
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.
arXiv comment10 pages, Allerton Conference on Communication, Control, and Computing 2015
References in corpus (13)
- Message Passing Algorithms for Compressed Sensing
- The dynamics of message passing on dense graphs, with applications to compressed sensing
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- 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
- Computational barriers in minimax submatrix detection
- Phase transitions and sample complexity in Bayes-optimal matrix factorization
- Scalable Recommendation with Poisson Factorization
- Phase Transitions in Sparse PCA
- Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
- Dynamical critical exponents for the mean-field Potts glass
Cited by in corpus (43)
- Statistical physics of inference: Thresholds and algorithms
- Phase transitions and sample complexity in Bayes-optimal matrix factorization
- 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
- Weighted Community Detection and Data Clustering Using Message Passing
- Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method
- Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
- Detection limits in the high-dimensional spiked rectangular model
- Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
- Universality of Computational Lower Bounds for Submatrix Detection
- Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
- Counterexamples to the Low-Degree Conjecture
- Adapting to Unknown Noise Distribution in Matrix Denoising
- Spectral Method for Multiplexed Phase Retrieval and Application in Optical Imaging in Complex Media
- On the Randomized Complexity of Minimizing a Convex Quadratic Function
- 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
- Spherical Integrals of Sublinear Rank
- Bayesian reconstruction of memories stored in neural networks from their connectivity
- The planted matching problem: Sharp threshold and infinite-order phase transition
- Detection of Signal in the Spiked Rectangular Models
- Mismatched Estimation of rank-one symmetric matrices under Gaussian noise
- Empirical Bayes PCA in high dimensions
- Low-rank Matrix Estimation with Inhomogeneous Noise
- Dense Limit of the Dawid-Skene Model for Crowdsourcing and Regions of Sub-optimality of Message Passing Algorithms
- Hypothesis testing with low-degree polynomials in the Morris class of exponential families
- Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions