Estimating Random Variables from Random Sparse Observations

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 some a random subset of the Xi’s, and consider the conditional distribution of Xi given the observations, namely µi(xi) ≡ 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, to multi-user detection, to group testing.