RELAXED BELIEF PROPAGATION 18 where P$_{z}$ ( µ ) is defined in (36). Now, the Fisher information satisfies F ($_{̂}$ Z$_{i}$, Y | U = 0) ( a ) = − E$^{[}$ ∂ 2 ∂u 2 log p$_{̂}$ Z$_{i}$,Y | $_{U}$($_{̂}$ z$_{i}$, y | u )$^{∣}$ ∣ ∣ u = 0$^{]}$ . ( b ) = − E$^{[}$ ∂ 2 ∂u 2 log p$_{Y}$$_{|}$$_{U,}$$_{̂}$ $_{Z$_{i}$}$( y | u, ̂ z$_{i}$ )$^{∣}$ ∣ ∣ u = 0$^{]}$ . ( c ) = E [ D$_{2}$ ( y, ̂ z$_{i}$, µ$_{i}$ )] . ( d ) = 1 E$_{out}$ ( µ$_{i}$ ) (91) log p$_{̂}$ Z$_{i}$,Y | $_{U}$($_{̂}$ z$_{i}$, y | u ) = log p$_{Y}$$_{|}$$_{̂}$ Z$_{i}$$_{,U}$( y | u, ̂ z$_{i}$ ) + log p$_{̂}$ Z$_{i}$ | $_{U}$($_{̂}$ z$_{i}$ | u ) REFERENCES ACKNOWLEDGMENTS where (a) follows from the definition of the Fisher information in (86); (b) follows from the fact that and ̂ z$_{i}$ is independent of u ; (c) is the definition of D$_{r}$ ( y, ̂ z, µ ) in (16); and (d) follows from the definition of E$_{out}$ ( µ ) in (34). Equations (90) and (34) together now show that E$_{out}$ ( µ ) is monotonically increasing in µ . Since E$_{in}$ ( µ ) is also monoton- ically increasing in µ , so is G ( µ ) . Lemma 9 thus shows that µ z $_{hi}$( t ) converges to the largest fixed point solution of the equation µ = G ( µ ) and µ z $_{lo}$( t ) converges to the smallest fixed point. The author particularly thanks Dongning Guo and Chih- Chun Wang, whose ideas are the basis of this work, and Vivek Goyal for their feedback. The author also thanks Dror Baron, Andrea Montanari, Phil Schniter, John Sun, Lav Varshney and Martin Wainwright for their careful reading of the manuscript and Amin Shokrollahi and Martin Vetterli for their generous support at the Summer Research Institute at EPFL, 2009, where this research was initiated. [1] J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference . San Mateo, CA: Morgan Kaufmann Publ., 1988. [2] M. J. Wainwright and M. I. Jordan, Graphical Models, Exponential Families, and Variational Inference , ser. Foundations and Trends in Machine Learning. Hanover, MA: NOW Publishers, 2008, vol. 1. [3] R. J. McEliece, D. J. C. MacKay, and J.-F. Cheng, “Turbo decoding as an instance of Pearl’s ‘belief propagation’ algorithm,” IEEE J. Sel. Areas Comm. , vol. 16, no. 2, pp. 140–152, Feb. 1988. [4] D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory , vol. 45, no. 3, pp. 399–431, Mar. 1999. [5] D. J. C. MacKay and R. M. Neal, “Near shannon limit performance of low density parity check codes,” Electron. Letters , vol. 33. [6] M. Yoshida and T. Tanaka, “Analysis of sparsely-spread CDMA via statistical mechanics,” in Proc. IEEE Int. Symp. Inform. Th. , Seattle, WA, Jun. 2006, pp. 2378–2382. [7] G. Guo and C. C. Wang, “Multiuser detection of sparsely spread CDMA,” IEEE J. Sel. Areas Comm. , vol. 26, no. 3, p. 421431, Mar. 2008. [8] M. F. N. Sommer and O. Shalvi, “Low-density lattice codes,” IEEE Trans. Inform. Theory , vol. 54, no. 4, pp. 1561–1585, Apr. 2008. [9] D. Baron, S. Sarvotham, and R. G. Baraniuk, “Bayesian compressive sensing via belief propagation,” IEEE Trans. Signal Process. , vol. 58, no. 1, pp. 269–280, Jan. 2010. [35] ——, “Lower bound on the mean-squared error in oversampled quan- tization of periodic signals using vector quantization analysis,” IEEE Trans. Inform. Theory , vol. 42, no. 2, pp. 469–479, Mar. 1996. [34] ——, “Deterministic analysis of oversampled A/D conversion and de- coding improvement based on consistent estimates,” IEEE Trans. Signal Process. , vol. 42, no. 3, pp. 519–531, Mar. 1994. [33] N. T. Thao and M. Vetterli, “Reduction of the MSE in R -times oversampled A/D conversion from O (1 /R ) to O (1 /R $^{2}$) ,” IEEE Trans. Signal Process. , vol. 42, no. 1, pp. 200–203, Jan. 1994. [32] S. P. Lipshitz, R. A. Wannamaker, and J. Vanderkooy, “Quantization and dither: A theoretical survey,” J. Audio Eng. Soc. , vol. 40, no. 5, pp. 355–375, May 1992. [31] R. M. Gray, “Quantization noise spectra,” IEEE Trans. Inform. Theory , vol. 36, no. 6, pp. 1220–1244, Nov. 1990. [30] R. Tibshirani, “Regression shrinkage and selection via the lasso,” J. Royal Stat. Soc., Ser. B , vol. 58, no. 1, pp. 267–288, 1996. [29] Y. Kabashima, T. Wadayama, and T. Tanaka, “Typical reconstruc- tion limit of compressed sensing based on l$_{p}$ -norm minimization,” arXiv:0907.0914 [cs.IT]., Jun. 2009. [28] S. Rangan, A. Fletcher, and V. K. Goyal, “Asymptotic analysis of MAP estimation via the replica method and applications to compressed sensing,” arXiv:0906.3234v2 [cs.IT]., Aug. 2009. [27] J. Yedidia, W. T. Freeman, and Y. Weiss, Understanding belief propaga- tion and its generalizations , ser. Exploring Artificial Intelligence in the New Millenium. San Francisco, CA: Morgan Kaufmann, 2003, ch. 8, pp. 239–269. [26] E. J. Cand`es and T. Tao, “Near-optimal signal recovery from random projections: Universal encoding strategies?” IEEE Trans. Inform. The- ory , vol. 52, no. 12, pp. 5406–5425, Dec. 2006. [25] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inform. Theory , vol. 52, no. 4, pp. 1289–1306, Apr. 2006. [24] E. J. Cand`es, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency informa- tion,” IEEE Trans. Inform. Theory , vol. 52, no. 2, pp. 489–509, Feb. 2006. [23] C. M. Bishop, Pattern Recognition and Machine Learning , ser. Infor- mation Science and Statistics. New York, NY: Springer, 2006. [22] M. Bayati and A. Montanari, “The dynamics of message pass- ing on dense graphs, with applications to compressed sensing,” arXiv:1001.3448v1 [cs.IT], Jan. 2010. [21] L. R. Varshney, “Performance of LDPC codes under noisy message- passing decoding,” in Proc. Inform. Th. Workshop , Lake Tahoe, CA, Sep. 2007, pp. 178–183. [20] S.-Y. Chung, T. J. Richardson, and R. L. Urbanke, “Analysis of sum- product decoding of low-density parity-check codes using a Gaussian approximation,” IEEE Trans. Inform. Theory , vol. 47, no. 2, pp. 657– 670, Feb. 2001. [19] J. P. Neirotti and D. Saad, “Improved message passing for inference in densely connected systems,” Europhys. Lett. , vol. 71, no. 5, p. 866872, Sep. 2005. [18] T. Tanaka and M. Okada, “Approximate belief propagation, density evolution, and neurodynamics for CDMA multiuser detection,” IEEE Trans. Inform. Theory , vol. 51, no. 2, pp. 700–706, Feb. 2005. [17] Y. Kabashima, “A CDMA multiuser detection algorithm on the basis of belief propagation,” J. Phys. A: Math. Gen , vol. 36. [16] D. Guo and S. Verd´u, “Randomly spread CDMA: Asymptotics via statistical physics,” IEEE Trans. Inform. Theory , vol. 51, no. 6, pp. 1983–2010, Jun. 2005. [15] T. Tanaka, “A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors,” IEEE Trans. Inform. Theory , vol. 48, no. 11, pp. 2888– 2910, Nov. 2002. [14] ——, “Random sparse linear systems observed via arbitrary channels: A decoupling principle,” in Proc. IEEE Int. Symp. Inform. Th. , Nice, France, Jun. 2007, pp. 946 – 950. [13] D. Guo and C.-C. Wang, “Asymptotic mean-square optimality of belief propagation for sparse linear systems,” in ”Proc. Inform. Th. Workshop” , Chengdu, China, Oct. 2006, pp. 194–198. [12] A. Montanari and D. Tse, “Analysis of belief propagation for non-linear problems: The example of CDMA (or: How to prove Tanaka’s formula),” arXiv:cs/0602028v1 [cs.IT]., Feb. 2006. [11] D. L. Donoho, A. Maleki, and A. Montanari, “Message passing algo- rithms for compressed sensing,” arXiv:0907.3574v1 [cs.IT], Jul. 2009. [10] D. Guo, D. Baron, and S. Shamai, “A single-letter characterization of optimal noisy compressed sensing,” in Proc. 47st Ann. Allerton Conf. on Commun., Control and Comp. , Monticello, IL, Sep. 2009.