Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
arXiv:1701.05823 · doi:10.1109/TIT.2020.2990880
Abstract
We consider the estimation of a signal from the knowledge of its noisy linear random Gaussian projections. A few examples where this problem is relevant are compressed sensing, sparse superposition codes, and code division multiple access. There has been a number of works considering the mutual information for this problem using the replica method from statistical physics. Here we put these considerations on a firm rigorous basis. First, we show, using a Guerra-Toninelli type interpolation, that the replica formula yields an upper bound to the exact mutual information. Secondly, for many relevant practical cases, we present a converse lower bound via a method that uses spatial coupling, state evolution analysis and the I-MMSE theorem. This yields a single letter formula for the mutual information and the minimal-mean-square error for random Gaussian linear estimation of all discrete bounded signals. In addition, we prove that the low complexity approximate message-passing algorithm is optimal outside of the so-called hard phase, in the sense that it asymptotically reaches the minimal-mean-square error. In this work spatial coupling is used primarily as a proof technique. However our results also prove two important features of spatially coupled noisy linear random Gaussian estimation. First there is no algorithmically hard phase. This means that for such systems approximate message-passing always reaches the minimal-mean-square error. Secondly, in a proper limit the mutual information associated to such systems is the same as the one of uncoupled linear random Gaussian estimation.
References in corpus (24)
- Message Passing Algorithms for Compressed Sensing
- The dynamics of message passing on dense graphs, with applications to compressed sensing
- Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so well over the BEC
- The Thermodynamic Limit in Mean Field Spin Glass Models
- Boolean Compressed Sensing and Noisy Group Testing
- Universality in polytope phase transitions and message passing algorithms
- Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
- Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
- Statistical physics-based reconstruction in compressed sensing
- A typical reconstruction limit of compressed sensing based on Lp-norm minimization
- Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
- Approximate message-passing decoder and capacity-achieving sparse superposition codes
- Tight bounds for LDPC and LDGM codes under MAP decoding
- Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- Mutual Information in Rank-One Matrix Estimation
- The Mutual Information in Random Linear Estimation
- Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
- A note on classical ground state energies
- The adaptive interpolation method for proving replica formulas. Applications to the Curie-Weiss and Wigner spike models
- Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
- Sparse Regression Codes
- Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems
- Sharp Bounds for Optimal Decoding of Low Density Parity Check Codes
Cited by in corpus (10)
- SPARCs for Unsourced Random Access
- Unsourced Multiuser Sparse Regression Codes achieve the Symmetric MAC Capacity
- Phase transition in random tensors with multiple independent spikes
- Near-Optimal Coding for Many-user Multiple Access Channels
- Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures
- Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
- Mismatched Data Detection in Massive MU-MIMO
- Exact results on high-dimensional linear regression via statistical physics
- Optimal Data Detection and Signal Estimation in Systems with Input Noise
- Remarks on the interpolation method