RELAXED BELIEF PROPAGATION 10 0.1 0.2 0.3 0.4 0.5 −15 −14 −13 −12 −11 −10 −9 −8 Measuerment ratio    = n/m Median NSE (dB) Linear MMSE Linear MMSE + Proj Relaxed BP Opt MMSE theoretical asymptotic minimum squared error. We see that the median squared error of relaxed BP at n = 50 matches the theoretical asymptotic performance well. Fig. 7 also compares the relaxed BP method to two other simple algorithms. One is the linear MMSE estimator  which is equivalent to the MMSE estimator assuming Gaussian noise. The second estimator  shown in the curve labeled “Linear MMSE + Proj ” is the linear MMSE estimate followed by a projection step. A key observation of the work [33]  [34] is that any estimate (including the linear MMSE estimate) can be improved by simply projecting the estimate onto the set of vectors x consistent with the bounded noise. An estimate ̂ x is consistent with the noise if ‖ y − Φ$_{̂}$ x ‖$_{∞}$ ≤ δ . The works [33]  [34] show that projecting to a consistent estimate always reduces the squared-error and can offer significant gains at low values of β (what is called high oversampling). Similar results and algorithms have been reported elsewhere [35]–[37]. The figure shows that projecting the linear MMSE estimate does indeed offer reductions in the squared error  especially for small β . However  the relaxed BP algorithm  in comparison  is even better. Fig. 7. Relaxed BP algorithm with a Gaussian prior and bounded noise output channel. The plot compares the simulated relaxed BP performance against the predicted performance based on density evolution. Also shown is the performance of the linear MMSE estimator with and without projection to the consistent set. The reason that the relaxed BP algorithm shows a perfor- mance improvement over the projected linear MMSE estimate is that projecting the linear MMSE estimate will generally result in a point only on the boundary of the consistent set. In contrast  the relaxed BP algorithm will attempt to find the centroid of the consistent region  which will likely have a smaller error variance. To validate the relaxed BP method and analysis for non- AWGN output channels  we next considered a bounded  uniform noise channel. Specifically  we assumed that the output channel is given by (3) where the components of the noise vector w are i.i.d. and uniformly distributed in an interval [ − δ  δ ] for some δ > 0 . Among other applications  this bounded noise model arises in the study of subtractive dithered quantization [31]  [32]  where the uncertainty interval corresponds to a quantization region. C. Estimation with Bounded Noise VII. CONCLUSIONS We have presented an extension to Guo and Wang’s relaxed BP method in [13] to non-AWGN measurements. The algo- rithm applies to a large class of estimation problems involving linear mixing and arbitrary separable input and output distri- butions. Unlike standard BP  relaxed BP is computationally tractable even for dense measurement matrices. Our main result shows that  in the large sparse limit  relaxed BP achieves the same asymptotic behavior as standard BP as described in [14]. In particular  when certain state evolution equations have unique fixed points  relaxed BP is mean-square optimal. Given the generality of the algorithm  its computational simplicity and provable performance guarantees  we believe that relaxed BP can have wide ranging applications. We have demonstrated the algorithm in two well-known NP-hard problems: com- pressed sensing and estimation with bounded noise. Unfortunately  optimal MMSE estimation with bounded uniform noise involves an integration over an n -dimensional polytope  which is generally computationally intractable. How- ever  the relaxed BP algorithm can be readily applied to the relaxed BP problem with bounded noise providing a simple  computationally-tractable algorithm for this problem. Fig. 7 shows a simulation of the relaxed BP algorithm with a bounded uniform output noise channel. The simulation used a vector x with n = 50 zero-mean i.i.d. Gaussian components. Similar to the previous experiment  we again used a measurement matrix Φ with Gaussian i.i.d. components. Also  bounded uniform noise in the interval [ − δ  δ ] results in a noise variance of µ$_{w}$ = δ $^{2}$/ 3 . In this experiment  the noise level δ was adjusted such that SNR$_{0}$ in (46) was equal to 10 dB. We varied the values of the measurement ratio β = n/m   and for each value of β   the points labeled “Relaxed BP” in Fig. 7 plots the median NSE over 1000 Monte Carlo trials of the relaxed BP algorithm  using 20 iterations in each relaxed BP run. The main theoretical limitation of the work is that it applies to large sparse random matrices  where the density of the measurement matrix must grow at a much slower rate than the matrix dimension. An interesting avenue of future work would be to see if the dense matrix analysis of the AMP algorithm in [11] and [22] can be extended to relaxed BP. Before proving our main result  the next number of ap- pendices develop some preliminary results. We begin in this appendix with some simple extensions to the Law of Large As in the previous experiment  the SE equations have a unique fixed point  and thus relaxed BP is theoretically asymptotically optimal with a minimum variance predicted by the SE fixed point. The curve labeled “Opt MMSE” shows this APPENDIX A PRELIMINARY CONVERGENCE RESULTS