RELAXED BELIEF PROPAGATION 2 mixing estimation problem. Section III reviews how to apply standard BP to estimation with linear mixing. The relaxed BP algorithm is introduced in Section IV. The large sparse limit analysis is described in Section V. Section VI presents some simple simulations of the algorithm to validate the analytic results. All the proofs are developed in appendices. The linear mixing model is extremely general and can be applied in a range of circumstances. We illustrate some simple examples for both the measurement channel and prior on x . II. EXAMPLES AND APPLICATIONS A. Measurement Channel Examples Fig. 1. Linear mixing estimation problem. A random input vector x is transformed by a matrix Φ , and the transformed vector z is passed through a separable measurement channel yielding a final output vector y . The linear mixing estimation problem is to estimate the input vector x from the output vector y given the transform matrix Φ , prior p$_{X}$ ( x$_{j}$ ) and measurement channel transition distribution p$_{Y}$$_{|}$$_{Z}$ ( y$_{i}$ | z$_{i}$ ) . a) AWGN output channel: For an additive white Gaus- sian noise (AWGN) output channel, the output vector y can be written as enables the study of non-Gaussian noise processes, as well as discrete output channels that arise, for example, in pattern classification problems. We suggest some possible applications in Section II. where w is a zero mean, Gaussian i.i.d. random vector independent of x . For this case, the corresponding channel transition probability distribution is given by where µ$_{w}$ > 0 is the variance of the components of w and φ ( v ; µ ) is the Gaussian distribution, y = z + w = Φ x + w , (3) p$_{Y}$$_{|}$$_{Z}$ ( y$_{i}$ | z$_{i}$ ) = φ ( y$_{i}$ − z$_{i}$ ; µ$_{w}$ ) , (4) φ ( v ; µ ) = 1 √ 2 πµ exp$^{(}$ − 1 2 µ | v | 2 ) . (5) The AWGN channel is precisely the model considered by Guo and Wang in their original relaxed BP paper [13]. b) Non-Gaussian noise models: Since the output channel can incorporate an arbitrary separable distribution, the linear mixing model can also include the model (3) with non- Gaussian noise vectors w , provided the components of w are i.i.d. One interesting application for a non-Gaussian noise model is to study the bounded noise that arises in quantization. We will consider this application in the numerical simulations in Section VI-C c) Logistic channels: A quite different channel is based on a logistic output. In this model, each output y$_{i}$ is 0 or 1 , where the probability that y$_{i}$ = 1 is given by some sigmoidal function such as for some constant a > 0 . Thus, larger values of z$_{i}$ result in a higher probability that y$_{i}$ = 1 . This logistic model can be used in classification problems as follows [23]: Suppose one is given m samples, with each sample being labeled as belonging to one of two classes. Let y$_{i}$ = 0 or 1 denote the class of sample i . Also, suppose that the i th row of the transform matrix Φ contains a vector of n data values associated with the i th sample. Then, using a logistic channel model such as (6), the problem of estimating the vector x from the labels y and data Φ is equivalent to finding a linear dependence on the data that classifies the samples between the two classes. This problem is often referred to as logistic regression and the resulting vector x is called the The remainder of this paper is organized as follows. In Section II, we introduce some specific examples of the linear A. Organization An algorithm closely related to relaxed BP is the recently developed approximate message passing (AMP) method pro- posed in [11] and analyzed further in [22]. The AMP algorithm generalizes the relaxed BP method and analysis in the special case of AWGN measurements. Unlike relaxed BP, the AMP algorithm can be applied with an arbitrary scalar estimation function so that the prior on the components of x do not need to be known. Also, as we will discuss in Section V, the analysis of relaxed BP is only valid under a certain large sparse limit model. This model is an approximation to the case where Φ is dense. The analysis of the AMP algorithm in [22] provides rigorous results for dense measurement matrices. An interesting open problem is whether the analysis of AMP can be extended to general output channels considered here. p$_{Y}$$_{|}$$_{Z}$ ( y$_{i}$ = 1 | z$_{i}$ ) = 1 1 + a exp( − z$_{i}$ ) , (6) • Applications to compressed sensing and bounded noise estimation: Although relaxed BP was originally devel- oped for CDMA multiuser detection, the method can be applied to non-Gaussian estimation in a variety of applications. In this paper, we simulate relaxed BP for compressed sensing and estimation with bounded noise. • Improved convergence analysis: A key result of Guo and Wang’s state evolution (SE) analysis in [13] and [14] is that, when the measurement ratio β = m/n is sufficiently small, relaxed BP asymptotically achieves the minimum mean-squared error (MSE) in the limit of large sparse random mixing matrices. Moreover, this minimum MSE is described by a unique fixed point to the SE equations. In this work, we extend the analysis to general β . Specif- ically, we show that for any β , there are upper and lower fixed point solutions to the SE equations. The asymptotic MSE of the relaxed BP method always converges to the upper fixed point, while the lower fixed point always provides a lower bound to the MSE of any estimator. Hence, in the case that the fixed point solution is unique, relaxed BP is asymptotically optimal.