RELAXED BELIEF PROPAGATION 6 for some β ≥ 0 . of the proofs. In particular, the input and output degrees are deterministically bounded as opposed to be bounded on aver- age – which simplifies some of the convergence arguments. The components s$_{j}$ in (28) are called the scale factors and are assumed to be i.i.d. with some probability distribution p$_{S}$ ( s$_{j}$ ) that does not depend on n or d . We assume s$_{j}$ > 0 almost surely. The diagonal scale factor matrix S is used to scale the powers of the components of x . Specifically, multi- plication by S 1 / 2 scales the variance of the j th component of x by a factor s$_{j}$ . In this way, the scale factors can be used to capture variations in the power of the components of x that are known a priori at the estimator. Variations in the power of x that are not known to the estimator should be captured in the distribution of x . In the large sparse limit analysis, we first let n → ∞ with m growing linearly with n and keeping d fixed. This enables the local-tree like properties. We then let d → ∞ , which will enable the use of a Central Limit Theorem approximation. This order of limits is critical. Unfortunately, to analyze dense matrices, one would like an analysis where d can grow with n . Indeed, if the matrix is completely dense, we would like d = m ( n ) . Unfortunately, the large sparse limit analysis that we rely on here requires that we consider the two limits separately; it thus represents an approximation to the actual problem. Nevertheless, we will see in simulations that large sparse limit analysis appears to predict the behavior with dense matrices as well. The matrix A is deterministic, and we evaluate the perfor- mance of the relaxed BP algorithm on a deterministic sequence of input and output indices i = i ( n, d ) and j = j ( n, d ) . The sequence of matrices A and indices i and j are assumed to satisfy the following conditions: More sophisticated analysis techniques developed recently in [22] enable the study of dense matrices without the order of limits above. One possible avenue of future research would be to see if that analysis can be applied to the relaxed BP algorithm with general (non-AWGN) output channels as well. Assumption 1: Let A = A ( n, d ) be a sequence of deter- ministic matrices in the factorization of Φ = Φ( n, d ) in (28). Let i = i ( n, d ) and j = j ( n, d ) be a deterministic sequence of indices. Let t > 0 be some fixed iteration number of the relaxed BP algorithm. Assume that A , i and j satisfy the following: Under the large sparse limit model, define the random vectors where the dependence on n and d on the right-hand side of the equations is implicit. Our goal is to describe the large sparse limit behavior of these random vectors. A key result of [14] is that the large sparse limit behavior of BP is described by a set of simple state evolution (SE) equations, which can be described as follows: Given E$_{in}$ ( q, µ ) in Section IV-A, define For all input nodes r in the subgraph G$_{j}$ ( t ) , we have the limits where the expectation is taken over the scalar random variables s ∼ p$_{S}$ ( s ) and q given by (14) with x ∼ p$_{X}$ ( x ) . We will call E$_{in}$ ( µ ) the input node MSE function . In addition to the works [13], [14], this function appeared in Guo and Verd´u’s replica analysis of MSE estimation [16] and related works [28], [29]. Variants also appear in the analysis of the AMP algorithm [11], [22]. At the output node, let As in [12]–[14], the key assumption is that the Tanner graph G associated with the transform matrix Φ is locally tree-like around the components of interest i and j . The assumption is common in the study of BP algorithms as it makes the messages independent. This local tree-like property is only possible with the graph being sparse. This sparsity assumption is brought out explicitly by bounding the input and output degrees of the Tanner graph. Assumption 1 uses a deterministic model for the A as opposed to the random matrix model with i.i.d. components studied in [12]–[14]. The deterministic model simplifies some where µ x init is variance of x$_{j}$ according to the prior p$_{X}$ ( x$_{j}$ ) , and the expectation is over s ∼ p$_{S}$ ( s ) . Then, for µ ≤ µ z $_{init}$, Guo and Wang [14] define the output node MSE function as E$_{out}$ ( µ ) = 1 E [ D$_{2}$ ( y,$_{̂}$ z, µ )] , (34) µ z init = β E ( s ) µ x $_{init}$, (33) E$_{in}$ ( µ, s ) = E [ E$_{in}$ ( q, µ/s ) | s ] (32a) E$_{in}$ ( µ ) = E [ s E$_{in}$ ( q, µ/s )] , (32b) lim d →∞ lim n →∞ 1 d ∑ ℓ ∈ N$_{in}$ ( r ) | a$_{ℓr}$ | 2 = 1 , (30c) lim d →∞ lim n →∞ 1 d 3 / 2 ∑ ℓ ∈ N$_{in}$ ( r ) | a$_{ℓr}$ | 3 = 0 . (30d) lim d →∞ lim n →∞ 1 d 3 / 2 ∑ r ∈ N$_{out}$ ( ℓ ) | a$_{ℓr}$ | 3 = 0 . (30b) lim d →∞ lim n →∞ 1 d ∑ r ∈ N$_{out}$ ( ℓ ) | a$_{ℓr}$ | 2 = β, (30a) (d) For all output nodes ℓ in the subgraph G$_{i}$ ( t ) , we have the limits (c) All the nodes in the subgraphs G$_{i}$ ( t ) and G$_{j}$ ( t ) have degrees bounded above by d . (b) The computation subgraphs G$_{i}$ ( t ) and G$_{j}$ ( t ) of the Tanner graph taken a depth of 2 t hops from the output node i and input node j are trees. Precise definitions of these computation subgraphs are given in Appendix D. (a) For every n and d , ( i, j ) is an edge in the Tanner graph G associated with Φ . B. Large Sparse Limit Convergence θ x i ← $_{j}$( n, d, t ) = ( x$_{j}$, s$_{j}$,$_{̂}$ x$_{i}$$_{←}$$_{j}$ ( t ) , µ x i ← $_{j}$( t )) (31a) θ x $_{j}$( n, d, t ) = ( x$_{j}$, s$_{j}$,$_{̂}$ x$_{j}$ ( t ) , µ x $_{j}$( t )) (31b) θ z i → $_{j}$( n, d, t ) = ( z$_{i}$$_{→}$$_{j}$,$_{̂}$ z$_{i}$$_{→}$$_{j}$ ( t ) , µ z i → $_{j}$( t )) (31c) θ z $_{i}$( n, d, t ) = ( z$_{i}$,$_{̂}$ z$_{i}$ ( t ) , µ z $_{i}$( t )) , (31d)