 ~ ( ) j X j x p x ~ (0, ), ( 1) / j j q j j v t s     ˆ ( , ) ( ) ( , ) ( ) j in j x j in j j j F q t q t x        ~ ( ) j S j s p s j q RELAXED BELIEF PROPAGATION 8 A. Gauss-Bernoulli Prior with an AWGN Output Channel In the first experiment, the vector x was generated with i.i.d. components x$_{j}$ with a Gauss-Bernoulli distribution given by Here ρ is the sparsity ratio and represents the average fraction of non-zero components in x . The experiments below used the value ρ = 0 . 1 . We chose this Gaussian mixture model since it is a simple example of a sparse prior used in compressed sensing. This prior is also used in the numerical validation of the replica method in [28]. Fig. 3. Equivalent scalar model of the relaxed BP algorithm. The asymptotic behavior of the relaxed BP estimate ̂ x$_{j}$ ( t ) of a component x$_{j}$ is identical to the output of an MMSE estimator with AWGN noise. The effective noise is scaled by the factor s$_{j}$ corresponding to the component x$_{j}$ . The components of the measurement matrix Φ were gener- ated as i.i.d. zero-mean Gaussians. Even though this matrix is dense, we will see that the large sparse limit analysis predicts the behavior of the relaxed BP estimator well. For the measurement channel in this first experiment, we assumed an AWGN output channel (3), where the noise w also has i.i.d. zero-mean Gaussian components. The noise variance, µ$_{w}$ , of the components of w was selected such that SNR$_{0}$ = 10 dB, where SNR$_{0}$ is the signal-to-noise ratio, C. Convergence over Iteration and Mean-Square Optimality Theorem 1 describes the asymptotic behavior of the relaxed BP algorithm for a fixed iteration number t . Our second result describes the behavior of the relaxed BP estimates as t → ∞ . Theorem 2: Consider the state evolution equations (37). Suppose that E$_{in}$ ( µ ) and E$_{out}$ ( µ ) are continuous. Then, the SE equations have at least one fixed point with 0 ≤ µ z ≤ µ z $_{init}$. Also: As discussed in [28], SNR$_{0}$ is the effective SNR that an estimator would see in estimating any one component of x$_{j}$ with the other n − 1 components of x known. Fig. 4 shows the median normalized squared-error (NSE) as a function of the iteration number in the relaxed BP algorithm for this model. In all the numerical experiments, we used the relaxed BP algorithm with the simplifications described in Section IV-D. The simulation was conducted with 1000 random realizations of the problem, and for each realization, we measured the NSE given by The theorem is similar to the convergence result in [13] except that it applies to all β . The importance of the result is that it shows that relaxed BP provably converges in the limit of large iterations, and the asymptotic error variance of relaxed BP and the corresponding error lower bounds are both fixed points of the SE equations. A corollary of this result is that, when the fixed points of the SE equations (37) are unique, the error variance of relaxed BP and the corresponding lower bound agree. The result thus gives an easily verifiable condition under which relaxed BP is asymptotically mean- square optimal. where ̂ x is the estimate of x . The NSE represents the average error over the n components of x . Fig. 4 plots the median of these NSE values over the 1000 Monte Carlo trials. The figure shows the median NSE for vector dimensions n = 100 and 500 and β = n/m = 2 and 3 . The points marked “pred (SE)” are the NSE values as predicted by the state evolution equations (37). We see that the state evolution equations, which are theoretically exact for infinite n , provide an excellent match (within 0 . 1 dB) with the simulated values when n = 500 . At the shorter length of n = 100 , the SE equations still provide a good match, although there is a small steady error of about 0.2 dB when β = 2 and 0.8 dB when β = 3 . The large sparse limit analysis of the relaxed BP algorithm in Section V is theoretically exact only in the asymptotic limit of large dimensions. Also, the analysis assumes a certain scaling where the measurement matrix Φ remains sparse. To test the accuracy of the large sparse limit model for finite problems with dense Φ , we conducted the following simple numerical experiments. In Fig. 4, we plotted the median NSE since there is actually considerable variation in the NSE over the random realizations of the problem parameters. To illustrate the degree of variability, Fig. 5 shows the CDF of the NSE values over the 1000 Monte Carlo trials. We see that there is a large variation in the NSE, especially at the smaller dimension n = 100 . This means that although the median performance may be VI. NUMERICAL SIMULATIONS (b) With the “lo” initial condition, µ $^{z}$(1) = µ z $_{lo}$(1) = 0 , the sequences µ z $_{lo}$( t ) , µ x $_{lo}$( t, s ) and µ q $_{lo}$( t ) increase monotoni- cally to the smallest fixed point of the SE equations (37). (a) With the “hi” initial condition, µ $^{z}$(1) = µ z $_{hi}$(1) = µ z $_{init}$, the sequences µ z $_{hi}$( t ) , µ x $_{hi}$( t, s ) and µ q $_{hi}$( t ) decrease mono- tonically to the largest fixed point of the SE equations (37). Proof: See Appendix G. NSE = 10 log$_{10}$$^{(}$ ‖$_{̂}$ x − x ‖ 2 E ‖ x ‖ 2 ) , SNR$_{0}$ = 10 log$_{10}$$^{(}$ E ‖ Φ x ‖ 2 nµ$_{w}$ ) . (46) x$_{j}$ ∼ { N (0 , 1 /ρ ) with prob = ρ, 0 with prob = 1 − ρ. (45)