The mutual information in random linear estimation

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.

• Publication year

  2016

• Venue

  Allerton Conference on Communication, Control, and Computing

• Publication date

  2016-07-08

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1109/ALLERTON.2016.7852290arXiv 1607.02335
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula

  2016cited by this paper
• Threshold saturation of spatially coupled sparse superposition codes for all memoryless channels

  2016cited by this paper
• The replica-symmetric prediction for compressed sensing with Gaussian matrices is exact

  2016cited by this paper
• Mutual information in rank-one matrix estimation

  2016cited by this paper
• Proof of threshold saturation for spatially coupled sparse superposition codes

  2016cited by this paper
• Approximate Message-Passing Decoder and Capacity Achieving Sparse Superposition Codes

  2015cited by this paper
• Capacity-Achieving Sparse Superposition Codes via Approximate Message Passing Decoding

  2015cited by this paper
• Random matrices.

  2015cited by this paper
• Replica analysis and approximate message passing decoder for superposition codes

  2014cited by this paper
• Non-adaptive pooling strategies for detection of rare faulty items

  2013cited by this paper
• Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing

  2013cited by this paper
• Threshold Saturation for Spatially Coupled LDPC and LDGM Codes on BMS Channels

  2013cited by this paper
• A simple proof of threshold saturation for coupled scalar recursions

  2012cited by this paper
• Universality in Polytope Phase Transitions and Message Passing Algorithms

  2012cited by this paper
• An Iterative Construction of Solutions of the TAP Equations for the Sherrington–Kirkpatrick Model

  2012cited by this paper
• Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices

  2012cited by this paper
• Optimal Phase Transitions in Compressed Sensing

  2011cited by this paper
• Improvement of BP-based CDMA multiuser detection by spatial coupling

  2011cited by this paper
• Statistical physics-based reconstruction in compressed sensing

  2011cited by this paper
• Support recovery with sparsely sampled free random matrices

  2011cited by this paper
• Coupled graphical models and their thresholds

  2010cited by this paper
• The effect of spatial coupling on compressive sensing

  2010cited by this paper
• Statistical mechanics of compressed sensing.

  2010cited by this paper
• Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform So Well over the BEC

  2010cited by this paper
• Toward fast reliable communication at rates near capacity with Gaussian noise

  2010cited by this paper
• The dynamics of message passing on dense graphs, with applications to compressed sensing

  2010cited by this paper
• A single-letter characterization of optimal noisy compressed sensing

  2009cited by this paper
• Asymptotic Analysis of MAP Estimation via the Replica Method and Compressed Sensing

  2009cited by this paper
• Message-passing algorithms for compressed sensing

  2009cited by this paper
• A typical reconstruction limit for compressed sensing based on Lp-norm minimization

  2009cited by this paper
• Boolean Compressed Sensing and Noisy Group Testing

  2009cited by this paper
• Tight Bounds on the Capacity of Binary Input Random CDMA Systems

  2008cited by this paper
• On the concentration of the capacity for a code division multiple access system

  2007cited by this paper
• On the Capacity of a Code Division Multiple Access System

  2007cited by this paper
• Course 5 – An Introduction to Mean Field Spin Glas Theory: Methods and Results

  2006cited by this paper
• Analysis of Belief Propagation for Non-Linear Problems: The Example of CDMA (or: How to Prove Tanaka's Formula)

  2006cited by this paper
• Randomly spread CDMA: asymptotics via statistical physics

  2005cited by this paper
• Random Matrices

  2005cited by this paper
• Mutual information and MMSE in gaussian channels

  2004cited by this paper
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

  2004cited by this paper
• Mutual information and minimum mean-square error in Gaussian channels

  2004cited by this paper
• Random Matrix Theory and Wireless Communications

  2004cited by this paper
• Multiuser Detection and Statistical Mechanics

  2003cited by this paper
• A CDMA multiuser detection algorithm on the basis of belief propagation

  2003cited by this paper
• A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors

  2002cited by this paper
• Spectral Efficiency of CDMA with Random Spreading

  1999cited by this paper
• Time-varying periodic convolutional codes with low-density parity-check matrix

  1999cited by this paper
• The space of interactions in neural networks: Gardner's computation with the cavity method

  1989cited by this paper
• The space of interactions in neural network models

  1988cited by this paper
• Optimal storage properties of neural network models

  1988cited by this paper
• Spin Glass Theory and Beyond

  1987cited by this paper
• Extensions of Lipschitz mappings into Hilbert space

  1984cited by this paper
• Solution of 'Solvable model of a spin glass'

  1977cited by this paper

• Information-Theoretic Limits and Approximate Message-Passing for High-Dimensional Time Series

  2025cites this paper
• Bayes-optimal learning of an extensive-width neural network from quadratically many samples

  2024cites this paper
• Bayes Optimal Learning in High-Dimensional Linear Regression With Network Side Information

  2023cites this paper
• Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models

  2023cites this paper
• Secure Coding via Gaussian Random Fields

  2022cites this paper
• On Linear Model with Markov Signal Priors

  2022cites this paper
• Bayesian Inference With Nonlinear Generative Models: Comments on Secure Learning

  2022cites this paper
• Random linear estimation with rotationally-invariant designs: Asymptotics at high temperature

  2022cites this paper
• Near-optimal multiple testing in Bayesian linear models with finite-sample FDR control

  2022cites this paper
• Adaptive Path Interpolation Method for Sparse Systems: Application to a Censored Block Model

  2021cites this paper
• Capacity Optimality of AMP in Coded Systems

  2021influential citation
• PR ] 1 0 N ov 2 02 1 PERFORMANCE OF BAYESIAN LINEAR REGRESSION IN A MODEL WITH MISMATCH B

  2021cites this paper
• Performance of Bayesian linear regression in a model with mismatch

  2021cites this paper
• Fundamental limits and algorithms for sparse linear regression with sublinear sparsity

  2021influential citation
• The fundamental limits of sparse linear regression with sublinear sparsity

  2021influential citation
• Replica analysis of overfitting in generalized linear regression models

  2020cites this paper
• Replica Analysis of the Linear Model With Markov or Hidden Markov Signal Priors

  2020cites this paper
• Asymptotic Errors for High-Dimensional Convex Penalized Linear Regression beyond Gaussian Matrices

  2020influential citation
• Information theoretic limits of learning a sparse rule

  2020cites this paper
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation

  2020cites this paper
• Information-Theoretic Limits for the Matrix Tensor Product

  2020cites this paper
• Information-theoretic limits of a multiview low-rank symmetric spiked matrix model

  2020cites this paper
• Strong Replica Symmetry in High-Dimensional Optimal Bayesian Inference

  2020cites this paper
• TRAMP: Compositional Inference with TRee Approximate Message Passing

  2020cites this paper
• Remarks on the Interpolation Method

  2020cites this paper
• Bayes-Optimal Convolutional AMP

  2020cites this paper
• Semi-analytic approximate stability selection for correlated data in generalized linear models

  2020cites this paper
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices.

  2020cites this paper
• Rigorous Dynamics of Expectation-Propagation-Based Signal Recovery from Unitarily Invariant Measurements

  2020cites this paper
• Fundamental Limits of Many-User MAC With Finite Payloads and Fading

  2019cites this paper
• The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models

  2019cites this paper
• Capacity Optimality of AMP in Coded Systems

  2019cites this paper
• The Replica-Symmetric Prediction for Random Linear Estimation With Gaussian Matrices Is Exact

  2019cites this paper
• A Simple Bound on the BER of the Map Decoder for Massive MIMO Systems

  2019influential citation
• The All-or-Nothing Phenomenon in Sparse Linear Regression

  2019influential citation
• Fundamental barriers to high-dimensional regression with convex penalties

  2019cites this paper
• Overlap matrix concentration in optimal Bayesian inference

  2019cites this paper
• On the universality of noiseless linear estimation with respect to the measurement matrix

  2019cites this paper
• Understanding Phase Transitions via Mutual Information and MMSE

  2019cites this paper
• A Simple Derivation of AMP and its State Evolution via First-Order Cancellation

  2019cites this paper
• Concentration of the Matrix-Valued Minimum Mean-Square Error in Optimal Bayesian Inference

  2019cites this paper
• Energy Efficient Coded Random Access for the Wireless Uplink

  2019cites this paper
• Inference With Deep Generative Priors in High Dimensions

  2019cites this paper
• Exact asymptotics for phase retrieval and compressed sensing with random generative priors

  2019cites this paper
• All-or-Nothing Phenomena: From Single-Letter to High Dimensions

  2019cites this paper
• Statistical Physics Methods for Community Detection

  2019cites this paper
• SLOPE for Sparse Linear Regression: Asymptotics and Optimal Regularization

  2019cites this paper
• Phase transition in random tensors with multiple independent spikes

  2018cites this paper
• Bilinear Recovery Using Adaptive Vector-AMP

  2018cites this paper
• Phase transition in random tensors with multiple spikes

  2018cites this paper
• Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method

  2018influential citation
• Single Letter Formulas for Quantized Compressed Sensing with Gaussian Codebooks

  2018cites this paper
• Mutual Information as a Function of Matrix SNR for Linear Gaussian Channels

  2018cites this paper
• Adaptive Path Interpolation for Sparse Systems: Application to a Simple Censored Block Model

  2018cites this paper
• Entropy and mutual information in models of deep neural networks

  2018cites this paper
• The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference

  2018influential citation
• High-Dimensional Inference on Dense Graphs with Applications to Coding Theory and Machine Learning

  2018cites this paper
• The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference

  2018influential citation
• The Mutual Information in Random Linear Estimation Beyond i.i.d. Matrices

  2018cites this paper
• The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning

  2018influential citation
• Additivity of information in multilayer networks via additive Gaussian noise transforms

  2017cites this paper
• Compressed sensing under optimal quantization

  2017cites this paper
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis

  2017cites this paper
• Dynamical functional theory for compressed sensing

  2017cites this paper
• Aalborg Universitet Dynamical Functional Theory for Compressed Sensing

  2017cites this paper
• Inference in Deep Networks in High Dimensions

  2017cites this paper
• I-MMSE relations in random linear estimation and a sub-extensive interpolation method

  2017cites this paper
• Multi-layer generalized linear estimation

  2017cites this paper
• Generalized approximate message-passing decoder for universal sparse superposition codes

  2017cites this paper
• Statistical Physics and Information Theory Perspectives on Linear Inverse Problems

  2017cites this paper
• Phase Transitions, Optimal Errors and Optimality of Message-Passing in Generalized Linear Models

  2017cites this paper
• Universal Sparse Superposition Codes With Spatial Coupling and GAMP Decoding

  2017cites this paper
• Rigorous dynamics of expectation-propagation-based signal recovery from unitarily invariant measurements

  2017cites this paper
• Phase transition in the spiked random tensor with Rademacher prior

  2017cites this paper
• Fundamental Limits of Compressed Sensing under Optimal Quantization

  2017cites this paper
• Optimal errors and phase transitions in high-dimensional generalized linear models

  2017cites this paper
• The layered structure of tensor estimation and its mutual information

  2017cites this paper
• A Universal Analysis of Large-Scale Regularized Least Squares Solutions

  2017cites this paper
• The Mutual information of LDGM codes

  2017cites this paper
• The stochastic interpolation method: A simple scheme to prove replica formulas in Bayesian inference

  2017influential citation
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation

  2017cites this paper
• Rigorous Dynamics and Consistent Estimation in Arbitrarily Conditioned Linear Systems

  2017cites this paper
• Learning and free energies for vector approximate message passing

  2016cites this paper
• Statistical Mechanics of MAP Estimation: General Replica Ansatz

  2016cites this paper
• Performance Limits for Noisy Multimeasurement Vector Problems

  2016cites this paper
• Approximate Message-Passing Decoder and Capacity Achieving Sparse Superposition Codes

  2015influential citation
• Hybrid Approximate Message Passing

  2011cites this paper