1 RELAXED BELIEF PROPAGATION arXiv:1001.2228v2 [cs.IT] 18 May 2010 Estimation with Random Linear Mixing, Belief Propagation and Compressed Sensing Sundeep Rangan BP is best known for its connections to iterative decoding in turbo and LDPC codes [3]–[5]. However, while turbo and LDPC codes typically involve computations over finite fields, BP has also been successfully applied in a number of problems with linear real-valued mixing, including CDMA multiuser detection [6], [7], lattice codes [8] and compressed sensing [9]–[11]. Abstract —We apply Guo and Wang’s relaxed belief propaga- tion (BP) method to the estimation of a random vector from linear measurements followed by a componentwise probabilistic measurement channel. Relaxed BP uses a Gaussian approxima- tion in standard BP to obtain significant computational savings for dense measurement matrices. The main contribution of this paper is to extend the relaxed BP method and analysis to general (non-AWGN) output channels. Specifically, we present detailed equations for implementing relaxed BP for general channels and show that relaxed BP has an identical asymptotic large sparse limit behavior as standard BP, as predicted by the Guo and Wang’s state evolution (SE) equations. Applications are presented to compressed sensing and estimation with bounded noise. Index Terms —Non-Gaussian estimation, belief propagation, density evolution, compressed sensing, sparsity, bounded noise. A key theoretical justification for applying BP to the specific problem of linear mixing estimation came with the work of Montanari and Tse [12]. That worked considered BP estima- tion of binary ± 1 vectors with AWGN measurements and large sparse random mixing matrices. In this setting, Montanari and Tse derived state evolution (SE) equations for the mean- squared error of BP as a function of the iteration number. Their analysis revealed that BP is asymptotically optimal in mean- square when the SE equations have a unique fixed point. The large sparse limit analysis was extended by Guo and Wang first to general priors and power levels [13], and then to arbitrary (non-AWGN) output channels [14]. These results provided the first rigorous conditions for the optimality of BP for estimation with linear mixing and confirmed earlier predictions given by the replica method from statistical physics [15], [16]. Consider the problem of estimating a random vector x ∈$_{R}$ n from the vector y ∈ R m shown in Fig. 1. As depicted in the figure, the input vector x is first passed through a linear transform, where Φ ∈ R m × n is a known transform matrix, and then passed through an output channel or measurement channel described by a conditional distribution p$_{Y}$$_{|}$$_{Z}$ ( y | z ) . Suppose that the distributions of both the input vector x and output channel are separable in that the probability distributions factor as Guo and Wang’s work [13] also presented the important result that the mean-square optimality of BP could be achieved by a significantly simpler algorithm that they called relaxed BP . One of the problems of applying standard BP to the linear mixing estimation problem is that the computations grow exponentially with the density of the transform matrix Φ . Relaxed BP overcomes this problem by using a Gaussian approximation of the messages to linearize the computations at the output nodes. Gaussian approximations had been used in earlier BP-based methods in CDMA multiuser detection [17]– [19] and also occasionally appear in the analysis and design of LDPC codes [20], [21]. where p$_{X}$ ( x$_{j}$ ) and p$_{Y}$$_{|}$$_{Z}$ ( y$_{i}$ | z$_{i}$ ) are scalar distribution func- tions, and x$_{j}$ , y$_{i}$ and z$_{i}$ are the components of the vectors x , y and z , respectively. The main contribution of this paper is to extend the relaxed BP method and analysis: If m = n and the mixing matrix Φ is the identity matrix, then the problem of estimating the input vector x from the out- put vector y reduces to n scalar estimation problems. However, for general Φ , optimal estimation of x is usually intractable because the transform matrix Φ “couples” or “mixes” the n components of x into the m components of the output vector y . We thus call the problem of estimating the vector x from the coupled output vector y the linear mixing estimation problem . One natural approach to the linear mixing estimation prob- lem is belief propagation (BP), which iteratively updates estimates of the variables based on message passing along a graph [1], [2]. In communications and signal processing, S. Rangan (email: srangan@poly.com) is with Polytechnic Institute of New York University, Brooklyn, NY. • Extensions to non-AWGN output channels: The relaxed BP algorithm described in Guo and Wang’s first paper [13] considers only AWGN output channels. The sec- ond paper [14] considers arbitrary output channels, but focuses on standard BP and only briefly mentions how to apply the relaxed BP approximations. In this paper, we work out the relaxed BP equations in full detail for general (non-AWGN) channels. Moreover, we offer some additional simplifications (see Section IV-D) to reduce the computations of relaxed BP even further. The ability to incorporate non-AWGN channels extends the scope of the relaxed BP method significantly. For example, it I. INTRODUCTION z = Φ x , (1) p$_{X}$ ( x ) = n ∏ j =1 p$_{X}$ ( x$_{j}$ ) , p$_{Y}$$_{|}$$_{Z}$ ( y | z ) = m ∏ i =1 p$_{Y}$$_{|}$$_{Z}$ ( y$_{i}$ | z$_{i}$ ) , (2)