content_image/379535.jpg content_image/379547.jpg content_image/379544.jpg content_image/379539.jpg content_image/379540.jpg content_image/379541.jpg content_image/379545.jpg content_image/379533.jpg content_image/379534.jpg content_image/379536.jpg content_image/379546.jpg content_image/379543.jpg content_image/379542.jpg content_image/379538.jpg content_image/379537.jpg
Numbers and the Central Limit Theorem. We omit the proofs as the results can be proven with minor modifications to standard arguments using characteristic functions [38]. 

Lemma 2 (Modified Law of Large Numbers): For each n and d , let x d n,i ∈ $_{R}$, i = 1 , . . . , d be a set of independent (though not necessarily identically distributed) random vari- ables satisfying 

where the convergence is in distribution and p$_{X}$ ( x ) is the distribution for the limiting random variable x and i = i ( n, d ) ∈ { 1 , . . . , d } is any deterministic sequence. Assume x has bounded second moments. Let b d n,i be a set of non- negative deterministic constants such that 

Then, the limit 

holds in distribution. 

Lemma 3 (Modified Central Limit Theorem): Let x d n,i be as in Lemma 2 such that, for any deterministic sequence of indices i = i ( n, d ) ∈ { 1 , . . . , d } , we have the limit 

Also, suppose that a d n,i is a deterministic sequence of scalars such that that 

Then, 

<img src='content_image/379535.jpg'>

where the limit is in distribution. 

As stated earlier, part (c) of Theorem 1 is not new and can be found in [13], [14]. Their proof is restated here only for completeness. Using similar arguments as [39], their proof considers a “genie” or “oracle-aided” algorithm that has, as side information, knowledge of certain subsets of the components x$_{j}$ . 

The genie algorithm is defined as follows: In step 1 of the relaxed BP algorithm in Section IV-B, we simply replace the initialization (17) at t = 1 with 

<img src='content_image/379547.jpg'>

<img src='content_image/379544.jpg'>

<img src='content_image/379539.jpg'>

<img src='content_image/379540.jpg'>

<img src='content_image/379541.jpg'>

<img src='content_image/379545.jpg'>

## APPENDIX B 

## GENIE ALGORITHM 

<img src='content_image/379533.jpg'>

<img src='content_image/379534.jpg'>

where x$_{j}$ is the true value of the component. Otherwise, all the steps of the algorithm are the same as the regular relaxed BP algorithm. 

We will see that while the error in the regular BP algorithm improves with each iteration, the genie algorithm starts with zero error and then increases. The performance of the true op- timal estimator is “sandwiched” somewhere between the genie and regular relaxed BP algorithms, and thus consideration of the regular and relaxed algorithms provide upper and lower bounds on the optimal performance. 

Fix µ > 0 and for r = 0 , 1 , 2 , . . . , define the functions 

Then, the conditional mean F$_{in}$ ( q, µ ) and variance E$_{in}$ ( q, µ ) are given by 

Now, taking the derivative of the Gaussian distribution φ ( · ; µ ) in (5), it is easily verified that 

Bringing this derivative inside the integral (48) then shows that 

Applying (50) to (49) we obtain 

<img src='content_image/379536.jpg'>

## COMPUTATION SUBGRAPHS AND LOCAL TREE-LIKE PROPERTIES 

An essential assumption of the large sparse limit analysis is that the Tanner graph is locally tree-like . To describe this property more precisely, we review some standard definitions and results that can be found in any description of BP such as [40]. Consider the Tanner graph G for the linear mixing problem defined in Section III. For t = 0 , 1 , 2 , . . . , recursively define a sequence of computation subgraphs , G$_{j}$ ( t ) , G$_{i}$ ( t ) , G$_{i}$$_{←}$$_{j}$ ( t ) and G$_{i}$$_{→}$$_{j}$ ( t ) , as follows: 

1) Initialize: Set t = 1 , and for all ( i, j ) ∈ E let G$_{i}$$_{←}$$_{j}$ ( t ) and G$_{j}$ ( t ) be the empty subgraphs. 

2) Output update: For all ( i, j ) ∈ E , let G$_{i}$$_{→}$$_{j}$ ( t ) be the subgraph containing, for all r ∈ N$_{out}$ ( i ) ̸ = j : 

(a) the edges ( i, r ) ; and 

<img src='content_image/379546.jpg'>

<img src='content_image/379543.jpg'>

<img src='content_image/379542.jpg'>

<img src='content_image/379538.jpg'>

<img src='content_image/379537.jpg'>

## APPENDIX C 

## PROOF OF LEMMA 1 

## APPENDIX D 

