Estimating random variables from random sparse observations

✍ Scribed by Andrea, Montanari

• Publisher: John Wiley and Sons
• Year: 2008
• Tongue: English
• Weight: 238 KB
• Volume: 19
• Category: Article
• ISSN: 1124-318X
• DOI: 10.1002/ett.1289

✦ Synopsis

Abstract

Let X~1~, … , X~n~, be a collection of iid discrete random variables, and Y~1~, … , Y~m~, a set of noisy observations of such variables. Assume each observation Y~a~, to be a random function of a random subset of the X~i~,s, and consider the conditional distribution of X~i~, given the observations, namely µ~i~,(x~i~,) ≡ ${\cal P}${X~i~, = x~i~,|Y} (a posteriori probability).

We establish a general decoupling principle among the X~i~,s, as well as a relation between the distribution of µ~i~, and the fixed points of the associated density evolution operator. These results hold asymptotically in the large system limit, provided the average number of variables an observation depends on is bounded. We discuss the relevance of our result to a number of applications, ranging from sparse graph codes and multi‐user detection, to group testing. Copyright © 2008 John Wiley & Sons, Ltd.