Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
Jean Barbier, Nicolas Macris, Mohamad Dia and Florent Krzakala J. Barbier is with The Abdus Salam International Center for Theoretical Physics, Trieste, Italy. Macris is with the Laboratoire de Théorie des Communications, Faculté Informatique et Communications, Ecole Polytechnique Fédérale de Lausanne, Switzerland. Dia is with the Institute for Data Science (i4DS), University of Applied Sciences Northwestern, Switzerland. Krzakala is with the Laboratoire de Physique de l’École normale supérieure, PSL Reseach University, Sorbonne Universités, UMR 8550 CNRS、UPMC, Université Pierre et Marie Curie, CNRS, France. (c) 2017 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to paper was presented in part at the 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2016.
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.
中文速览
含噪声的随机线性投影下如何精确重建信号，是压缩感知、CDMA通信、稀疏叠加码等领域共同面临的核心问题，而物理学中的"复本方法（replica method）"虽早已给出互信息和最小均方误差（MMSE）的预测公式，却一直缺乏严格的数学证明。这篇论文通过两步走完成了这一证明：先借助Guerra-Toninelli插值方法证明复本公式给出互信息的上界，再利用"空间耦合（spatial coupling）"构造、状态演化（state evolution）分析以及I-MMSE定理建立匹配的下界，从而严格确认复本公式对所有离散有界信号均精确成立。在算法层面，论文还证明了低复杂度的近似消息传递算法（AMP）在"困难相（hard phase）"之外能够渐近达到最优MMSE，而空间耦合系统则彻底消除了困难相，使AMP在任意信噪比下均可达到信息论最优性能。这一结果不仅为大量此前依赖物理直觉的工程结论提供了坚实的数学基础，也为矩阵分解等更广泛的估计问题的严格化分析开辟了通用路径。
原文 arXiv:1701.05823;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1701.05823v2