Belief propagation is asymptotically equivalent to MAP estimation for sparse linear systems

Chih Chun Wang, Dongning Guo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

This paper addresses the relationship between belief propagation (BP) and the optimal maximum a posteriori (MAP) detection for large linear systems with Gaussian noise. Assuming an input vector of independent symbols with arbitrary distribution, it is proved that BP is asymptotically equivalent to MAP as long as the linear system is "sparse" and "semi-regular" in some sense where the probability of seeing short cycles in the factor graph which describes the system vanishes, and that the aspect ratio of the linear system is below a certain threshold. Moreover, the problem of estimating each input symbol through the sparse linear system is shown to be asymptotically equivalent to that of estimating the same symbol through a scalar Gaussian channel with some degradation in the signal-to-noise ratio (SNR), known as the efficiency of the system. The efficiency has been previously shown to satisfy a fixed-point equation by Guo and Verd'u using non-rigorous statistical physics techniques in the context of code-division multiple access (CDMA) with no requirement of sparsity. This paper establishes a rigorous proof of the result in the special case of sparse systems, and henceforth fully characterizes the performance of such systems.

Original languageEnglish (US)
Title of host publication44th Annual Allerton Conference on Communication, Control, and Computing 2006
PublisherUniversity of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
Pages926-935
Number of pages10
Volume2
ISBN (Electronic)9781604237924
StatePublished - Jan 1 2006
Event44th Annual Allerton Conference on Communication, Control, and Computing 2006 - Monticello, United States
Duration: Sep 27 2006Sep 29 2006

Other

Other44th Annual Allerton Conference on Communication, Control, and Computing 2006
CountryUnited States
CityMonticello
Period9/27/069/29/06

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Belief propagation is asymptotically equivalent to MAP estimation for sparse linear systems'. Together they form a unique fingerprint.

Cite this