Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
From MaRDI portal
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.
Recommendations
- On mutual information estimation for mixed-pair random variables
- A computationally efficient estimator for mutual information
- Mutual Information, Relative Entropy and Estimation Error in Semi-Martingale Channels
- On the optimality and practicability of mutual information analysis in some scenarios
- Gradient of mutual information in linear vector Gaussian channels
- Mutual Information, Relative Entropy, and Estimation in the Poisson Channel
- Mutual information of several random variables and its estimation via variation
- A Finite-Sample, Distribution-Free, Probabilistic Lower Bound on Mutual Information
- Mutual Information and Minimum Mean-Square Error in Gaussian Channels
Cited in
(21)- The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning
- The all-or-nothing phenomenon in sparse linear regression
- Fundamental barriers to high-dimensional regression with convex penalties
- Strong replica symmetry in high-dimensional optimal Bayesian inference
- Phase transition in random tensors with multiple independent spikes
- The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference
- Phase transition in the spiked random tensor with Rademacher prior
- Fundamental limits of weak recovery with applications to phase retrieval
- Some relations between mutual information and estimation error in Wiener space
- Remarks on the interpolation method
- Approximate Solutions of Lagrange Multipliers for Information-Theoretic Random Field Models
- On the Information Loss of the Max-Log Approximation in BICM Systems
- A Bregman Matrix and the Gradient of Mutual Information for Vector Poisson and Gaussian Channels
- Gradient of mutual information in linear vector Gaussian channels
- Mutual Information, Relative Entropy and Estimation Error in Semi-Martingale Channels
- Information theoretic limits of learning a sparse rule
- Individually Conditional Individual Mutual Information Bound on Generalization Error
- Semi-analytic resampling in Lasso
- The TAP free energy for high-dimensional linear regression
- Fluctuations in random field Ising models
- An estimate of mutual information that permits closed-form optimisation
This page was built for publication: Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124430)
