The mutual information in random linear estimation
Autor: | Nicolas Macris, Mohamad Dia, Florent Krzakala, Jean Barbier |
---|---|
Rok vydání: | 2016 |
Předmět: |
FOS: Computer and information sciences
Basis (linear algebra) Computer science Computer Science - Information Theory Information Theory (cs.IT) Gaussian FOS: Physical sciences 020206 networking & telecommunications Mathematical Physics (math-ph) 02 engineering and technology Mutual information 010501 environmental sciences 01 natural sciences Upper and lower bounds Superposition principle symbols.namesake Compressed sensing Bounded function 0202 electrical engineering electronic engineering information engineering symbols Algorithm Mathematical Physics 0105 earth and related environmental sciences Interpolation |
Zdroj: | Allerton |
Popis: | 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. Comment: Presented at the 54th Annual Allerton Conference on Communication, Control, and Computing, 2016 |
Databáze: | OpenAIRE |
Externí odkaz: |