## 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 language | English (US) |
---|---|

Title of host publication | 44th Annual Allerton Conference on Communication, Control, and Computing 2006 |

Publisher | University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering |

Pages | 926-935 |

Number of pages | 10 |

Volume | 2 |

ISBN (Electronic) | 9781604237924 |

State | Published - Jan 1 2006 |

Event | 44th Annual Allerton Conference on Communication, Control, and Computing 2006 - Monticello, United States Duration: Sep 27 2006 → Sep 29 2006 |

### Other

Other | 44th Annual Allerton Conference on Communication, Control, and Computing 2006 |
---|---|

Country | United States |

City | Monticello |

Period | 9/27/06 → 9/29/06 |

## ASJC Scopus subject areas

- Computer Science Applications
- Computer Networks and Communications