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