Asymptotic Mean-Square Optimality of Belief Propagation for Sparse Linear Systems
This paper studies the estimation of a highdimensional vector signal where the observation is a known sparse linear transformation of the signal corrupted by additive Gaussian noise. A paradigm of such a linear system is codedivision multiple access (CDMA) channel with sparse spreading matrix. Assuming a semi-regular ensemble of sparse matrix linear transformations, where the bi-partite graph describing the system is asymptotically cycle-free, it is shown that belief propagation (BP) achieves the minimum mean-square error (MMSE) in estimating the transformation of the input vector in the large-system limit. The result holds regardless of the the distribution and power of the input symbols. Furthermore,the mean squared error of estimating each symbol of the input vector using BP is proved to be equal to the MMSE of estimating the same symbol through a scalar Gaussian channel with some degradation in the signal-to-noise ratio (SNR). The degradation,called the efficiency, is determined from a fixed-point equation formula to arbitrary prior distributions.
Dongning Guo Chih-Chun Wang
Dept.of Electrical Engineering & Computer Science Northwestern University, Evanston, IL 60208, USA School of Electrical & Computer Engineering Purdue University, West Lafayette, IN 47907, USA
国际会议
2006年IEEE信息理论国际会议(Proceedings of 2006 IEEE Information Theory Workshop ITW06)
成都
英文
194-198
2006-10-22（万方平台首次上网日期，不代表论文的发表时间）