Estimating random variables from random sparse observations
Montanari Andrea · European Transactions on Telecommunications · 2008
Abstract Let X1, … , Xn, be a collection of iid discrete random variables, and Y1, … , Ym, a set of noisy observations of such variables. Assume each observation Ya, to be a random function of a random subset of the Xi,s, and consider the conditional distribution of Xi, given the observations, namely µi,(xi,) ≡ ${\cal P}$ {Xi, = xi,|Y} (a posteriori probability). We establish a general decoupling principle among the Xi,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.