(a) The random vectors in (31) converge in distribution as follows: 7 (b) The error variances satisfy the limits (c) The minimum conditional error variance of x$_{j}$ and z$_{i}$ given Φ and y satisfy the asymptotic lower bounds θ $^{z}$( t ) = ( z, ̂ z, µ $^{z}$( t )) , (41) θ $^{x}$(1) = ( x, s, ̂ x$_{init}$, µ x $_{init}$) , (40) θ $^{x}$( t ) = ( x, s, F$_{in}$ ( q, µ ) , E$_{in}$ ( q, µ )) , (39) lim d →∞ lim n $_{→∞}$E [ var ( z$_{i}$ | y , Φ)] ≥ µ z $_{lo}$( t ) , (44b) lim d →∞ lim n $_{→∞}$E [ var ( x$_{j}$ | y , Φ) | s$_{j}$ = s ] ≥ µ x $_{lo}$( t, s ) , (44a) lim d →∞ lim n $_{→∞}$E $^{[}$| z$_{i}$ − ̂ z$_{i}$ ( t ) | 2 ] = µ z $_{hi}$( t ) , (43b) lim d →∞ lim n $_{→∞}$E $^{[}$| x$_{j}$ − ̂ x$_{j}$ ( t ) | $^{2}$| s$_{j}$ = s ] = µ x $_{hi}$( t, s ) , (43a) µ $^{q}$( t ) = E$_{out}$ ( µ $^{z}$( t )) , (37a) µ $^{x}$( t + 1 , s ) = E$_{in}$ ( µ $^{q}$( t ) , s ) , (37b) µ $^{z}$( t + 1) = β E$_{in}$ ( µ $^{q}$( t )) , (37c) µ $^{z}$( t + 1) = β E$_{in}$ $^{[}$E$_{out}$ ( µ $^{z}$( t )) $^{]}$. (38) P$_{z}$ ( µ ) = ( µ z init µ z init − µ µ z init − µ µ z init − µ ) , (36) ( z, ̂ z ) ∼ N (0 , P$_{z}$ ( µ )) , (35) lim d →∞ lim n $_{→∞}$θ x i ← $_{j}$( n, d, t ) = θ $^{x}$( t ) (42a) lim d →∞ lim n $_{→∞}$θ x $_{j}$( n, d, t ) = θ $^{x}$( t ) (42b) lim d →∞ lim n $_{→∞}$θ z i ← $_{j}$( n, d, t ) = θ $^{z}$( t ) (42c) lim d →∞ lim n $_{→∞}$θ z $_{i}$( n, d, t ) = θ $^{z}$( t ) , (42d) where the random vectors θ $^{x}$( t ) and θ $^{z}$( t ) are defined as above with µ $^{q}$( t ) = µ q $_{hi}$( t ) and µ $^{z}$( t ) = µ z $_{hi}$( t ) . and the conditional distribution of y given z is given by p$_{Y}$$_{|}$$_{Z}$ ( y | z ) . Now consider the recursion where P$_{z}$ ( µ ) is the covariance matrix where D$_{2}$ ( y, ̂ z, µ ) is the derivative (16) of the score function. The expectation in (34) is taken over RANGAN where µ x $_{hi}$( t, s ) and µ z $_{hi}$( t ) are the output of the SE equations (37) with the “hi” initial condition. defined for t ≥ 1 . We can also write (37) with the single equation where µ x $_{lo}$( t, s ) and µ z $_{lo}$( t ) are the output of the SE equations (37) with the “lo” initial condition. Proof: See Appendices E and F. The performance bounds in parts (a) and (b) are largely identical to the results in [14] except that they apply to relaxed BP instead of BP. This is our main result: in the large sparse limit model, relaxed BP and standard BP have the identical asymptotic behavior. The lower bound in part (c) of the theorem is also very close to results in [14] and just repeated here for completeness. We consider two possible initial conditions for this recur- sion: one low value and one high value. The low sequence will be initialized with µ $^{z}$(1) = µ z $_{lo}$(1) = 0 , and the high sequence will be initialized with µ $^{z}$(1) = µ z $_{hi}$(1) = µ z init in (33). We will use the subscripts as in µ z $_{lo}$( t ) and µ z $_{hi}$( t ) to differentiate between the two sequences. In [14], the equations (37) (or the single equation version (38)) are called the state evolution equations for BP as they describe the evolution of the error variances. Now, for t ∈$_{Z}$ $^{+}$, let θ $^{x}$( t ) be the random vector where x ∼ p$_{X}$ ( x ) , s ∼ p$_{S}$ ( s ) , q is distributed as (14), and µ = µ $^{q}$( t − 1) /s with µ $^{q}$( t − 1) being the (deterministic) quantity in the state evolution (SE) equation (37). To initialize, let Part (a) of the theorem provides a simple scalar char- acterization for this asymptotic behavior. Specifically, using the definition of θ $^{x}$( t ) in (39), Theorem 1 shows that the componentwise behavior of the relaxed BP follows a scalar equivalent model as shown in Fig. 3: The component x$_{j}$ is first corrupted by Gaussian noise yielding a noisy component q$_{j}$ . The relaxed BP estimate ̂ x$_{j}$ ( t ) then behaves identically to the optimal scalar MMSE estimate of x$_{j}$ from the AWGN measurement q$_{j}$ . From this scalar equivalent joint distribution of the components and their estimates, one can compute any componentwise separable performance metric such as mean- squared error or probability of detection. The effective Gaussian noise levels in the scalar models are described by µ z $_{hi}$( t ) and µ q $_{hi}$( t ) from the state evolu- tion equations (37). Since the state evolution equations can be evaluated easily with numerical integration, Theorem 1 thus provides a simple, computationally-tractable method for exactly characterizing the performance of the relaxed BP algorithm. where ̂ x$_{init}$ and µ x init are the mean and variance of the prior of p$_{X}$ ( x ) . We will see below that when we use µ $^{q}$( t ) = µ q $_{hi}$( t ) , the SE output with the “high” initial condition θ $^{x}$( t ) describes the limit of the random vector θ x i ← $_{j}$( n, d, t ) in (31). When µ $^{q}$( t ) = µ q $_{lo}$( t ) , θ $^{x}$( t ) is the limit of a related quantity for a certain “genie-aided” algorithm (see Appendix B). Also, for all t ∈$_{Z}$ $^{+}$, define the random vector where µ $^{z}$( t ) is the output of the state evolution equations (37) and ( z, z ) ∼ N (0 , P$_{z}$ ( µ $^{z}$( t ))) . Theorem 1: Consider the relaxed BP algorithm under the large sparse limit model above with transform matrix Φ and indices i and j satisfying Assumption 1 for some fixed iteration number t . Then: Part (b) shows that the SE outputs µ x $_{hi}$( t, s ) and µ z $_{hi}$( t ) respectively describe the asymptotic estimation error on the components x$_{j}$ and prediction error on the outputs z$_{i}$ . Part (c) provides corresponding lower bounds on these error variances for any estimator.