The Mutual Information in Random Linear Estimation

Abstract

We consider the estimation of a signal from the knowledge of its noisy linear random Gaussian projections, a problem relevant in compressed sensing, sparse superposition codes or code division multiple access just to cite few. There has been a number of works considering the mutual information for this problem using the heuristic replica method from statistical physics. Here we put these considerations on a firm rigorous basis. First, we show, using a Guerra-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, in particular, a single letter formula for the mutual information and the minimal-mean-square error for random Gaussian linear estimation of all discrete bounded signals.

Presented at the 54th Annual Allerton Conference on Communication, Control, and Computing, 2016

References in corpus (15)

• 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
• Boolean Compressed Sensing and Noisy Group Testing
• Universality in polytope phase transitions and message passing algorithms
• 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
• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels
• Mutual Information in Rank-One Matrix Estimation
• Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
• Non-adaptive pooling strategies for detection of rare faulty items

Cited by in corpus (22)

• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Entropy and mutual information in models of deep neural networks
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Fundamental limits of many-user MAC with finite payloads and fading
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• The adaptive interpolation method for proving replica formulas. Applications to the Curie-Weiss and Wigner spike models
• The Mutual Information in Random Linear Estimation Beyond i.i.d. Matrices
• Bilinear Recovery using Adaptive Vector-AMP
• Performance Limits for Noisy Multi-Measurement Vector Problems
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation
• Rigorous Dynamics of Expectation-Propagation-Based Signal Recovery from Unitarily Invariant Measurements
• Phase transition in random tensors with multiple independent spikes
• Generalized Approximate Message-Passing Decoder for Universal Sparse Superposition Codes
• On the Universality of Noiseless Linear Estimation with Respect to the Measurement Matrix
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
• Phase transition in the spiked random tensor with Rademacher prior
• Capacity Optimality of AMP in Coded Systems
• Bayes-Optimal Convolutional AMP
• Remarks on the interpolation method
• Fundamental limits and algorithms for sparse linear regression with sublinear sparsity
• A simple bound on the BER of the MAP decoder for massive MIMO systems