0.5 1 1.5 2 2.5 3 −18 −16 −14 −12 −10 −8 −6 −4 −2 0 2 Measurement ratio   = n/m Median NSE (dB) Linear MMSE Lasso Relaxed BP Opt. MMSE 2 4 6 8 10 −16 −14 −12 −10 −8 −6 −4 Iteration num Median NSE (dB) beta=2 5 10 15 20 −16 −14 −12 −10 −8 −6 −4 Iteration num beta=3 sim n=100 sim n=500 pred (SE) sim n=100 sim n=500 pred (SE) 9 RANGAN Fig. 6. Performance comparison of relaxed BP with other sparse estimation methods. Fig. 4. State evolution prediction. The normalized squared-error as predicted by the state evolution equations (37) as a function of the iteration number is compared against the simulated value for n = 100 and 500 . The simulation is based on a sparse Gauss-Bernoulli model. See text for details. B. Comparison to Other Sparse Detection Methods −20 −15 −10 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 NSE (dB) Cumm prob beta=2 −20 −15 −10 −5 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 NSE (dB) beta=3 n=100 n=500 SE lim n=100 n=500 SE lim Fig. 6 plots the squared-error performance of the relaxed BP algorithm varying the measurement ratio β = n/m and holding n = 100 . For each value of β , the points labeled “relaxed BP” show the median NSE after 20 iterations of the relaxed BP algorithm. Also plotted is the theoretical optimal MMSE performance as predicted by the lower bound, Theorem 1(c). In this experiment, we observed only one fixed point for the SE equations for all the values of β . So the lower bound on the MSE in Theorem 1(c) equals the theoretical asymptotic performance of relaxed BP given in Theorem 1(b). We see that the relaxed BP algorithm at n = 100 performs very close to the asymptotic optimal performance for values of β up to approximately 2 . For larger values of β , there is a small gap between the performance of the relaxed BP algorithm and the optimal performance. The gap grows to 0.8 dB at β = 3 . As discussed in Fig. 4, this gap decreases at higher values of n . Fig. 6 also shows the performance of two other simple algorithms. The top curve is the median NSE for optimal linear MMSE estimation, and the curve labeled “lasso” is the MSE from the lasso algorithm of [30]. The lasso method is based on an ℓ$_{1}$ -relaxation of the optimal estimator and is widely-used for sparse estimation problems in compressed sensing. In this experiment, the regularization weighting in the lasso estimator was optimized as described in [28]. Fig. 5. Performance variation. Plotted is the simulated CDF of the NSE, averaged over the components in the vector x , but accounting for variations in the random problem parameters. The CDF for the value of n = 500 shows less variation than n = 100 and closer to concentration around the state evolution limit (SE lim). We see that the relaxed BP algorithm offers some gain over either of these methods. Of course, with the interest in compressed sensing, there is now a plethora of methods for estimating sparse vectors. It is likely that other methods, including possible modifications of lasso, can obtain a similar performance as relaxed BP. A complete comparison of relaxed BP against these methods is beyond the scope of this work. What is important is that relaxed BP provides a unified, systematic method for a large class of problems, such that when applied to certain compressed sensing problems, it gives near optimal performance. good, there is still a significant chance that the algorithm could perform well below the median on any particular realization. As one might expect, at the higher dimension of n = 500 , the level of variability is reduced and performance begins to concentrate around the density evolution limit. However, even at n = 500 , the variation is not insignificant. As a result, caution should be exercised in using the SE predictions with short to medium block lengths.