RELAXED BELIEF PROPAGATION 4 ̂ z$_{i}$$_{→}$$_{j}$ ( t ) = ∑ r = j Φ$_{ir}$$_{̂}$ x$_{i}$$_{←}$$_{r}$ ( t ) , (18a) µ z i → $_{j}$( t ) = ∑ r = j | Φ$_{ir}$ | $^{2}$µ x i ← $_{r}$( t ) . (18b) ̂ u$_{i}$$_{→}$$_{j}$ ( t ) = − D$_{1}$ ( y$_{i}$, ̂ z$_{i}$$_{→}$$_{j}$ ( t ) , µ z i → $_{j}$( t )) D$_{2}$ ( y$_{i}$, ̂ z$_{i}$$_{→}$$_{j}$ ( t ) , µ z i → $_{j}$( t )) , (19a) µ u i → $_{j}$( t ) = 1 D$_{2}$ ( y$_{i}$, ̂ z$_{i}$$_{→}$$_{j}$ ( t ) , µ z i → $_{j}$( t )) , (19b) q = x + v, v ∼ N (0 , µ ) , (14) ̂ q$_{i}$$_{←}$$_{j}$ ( t ) = µ q i ← $_{j}$( t ) ∑ ℓ = i Φ ∗ ℓj ̂ u$_{ℓ}$$_{→}$$_{j}$ ( t ) µ u ℓ → $_{j}$( t ) , (20a) µ q i ← $_{j}$( t ) =   ∑ ℓ = i | Φ$_{ℓj}$ | 2 µ u ℓ → $_{j}$( t )$^{}$  − 1 . (20b) p$_{Y}$$_{|}$$_{̂}$ $_{Z,µ}$( y |$_{̂}$ z, µ ) = ∫ p$_{Y}$$_{|}$$_{Z}$ ( y | z ) φ ( z − ̂ z ; µ ) dz, (15) ̂ x$_{i}$$_{←}$$_{j}$ ( t + 1) = F$_{in}$ ($_{̂}$ q$_{i}$$_{←}$$_{j}$ ( t ) , µ q i ← $_{j}$( t )) , (21a) µ x i ← $_{j}$( t + 1) = E$_{in}$ ($_{̂}$ q$_{i}$$_{←}$$_{j}$ ( t ) , µ q i ← $_{j}$( t )) . (21b) D$_{r}$ ( y, ̂ z, µ ) = − ∂ r ∂$_{̂}$ z r log p$_{y}$$_{|}$$_{̂}$ $_{Z,µ}$( y |$_{̂}$ z, µ ) , (16) µ x i ← $_{j}$( t ) = µ x $_{j}$( t ) = µ x $_{init}$, (17b) ̂ x$_{i}$$_{←}$$_{j}$ ( t ) = ̂ x$_{j}$ ( t ) = ̂ x$_{init}$, (17a) p u i → $_{j}$( t, u$_{i}$ ) ≈ p$_{Y}$$_{|}$$_{̂}$ $_{Z,µ}$( y$_{i}$ |$_{̂}$ z$_{i}$$_{→}$$_{j}$ ( t ) , µ z i → $_{j}$( t )) , (22) Although we will formally analyze the relaxed BP algorithm below, it is useful to first provide a heuristic understanding of the steps. The relaxed BP algorithm is a simplification of the standard BP method where only the means and variances of the probability distributions are passed. Specifically, the terms ̂ x$_{i}$$_{←}$$_{j}$ ( t ) and µ x i ← $_{j}$( t ) are approximations of the mean and variance of the distribution p x i ← $_{j}$( t, x$_{j}$ ) in (13) in the standard BP algorithm. In step 1, these are initialized based on the prior p$_{X}$ ( x$_{j}$ ) . The relaxed BP approximation does not assume that p x i ← $_{j}$( t, x$_{j}$ ) itself is Gaussian. However, relaxed BP does assume that there is a sufficient number of terms in the summation in (9) that p z i → $_{j}$( t, z$_{i}$$_{→}$$_{j}$ ) of the standard BP al- gorithm is well-approximated as Gaussian. The terms ̂ z$_{i}$$_{→}$$_{j}$ ( t ) and µ z i → $_{j}$( t ) in (18) in step 2 of the relaxed BP algorithm are the mean and variance of this Gaussian distribution. Under this Gaussian assumption, the likelihood function p u i → $_{j}$( t, u$_{i}$ ) in (11) is approximately given by where ̂ x$_{init}$ and µ x init are the mean and variance of the prior p$_{X}$ ( x ) . We can now describe the relaxed BP algorithm. The algo- rithm produces a sequence of estimates ̂ x$_{j}$ ( t ) , t = 0 , 1 , . . . for each variable x$_{j}$ as well as estimates ̂ z$_{i}$ ( t ) for each transformed variable z$_{i}$ . Several other intermediate estimates and variances are also computed. The steps are as follows: for r > 0 . Again, this function can in general be evaluated numerically. Similarly, for every j = 1 , . . . , n , compute ̂ x$_{j}$ ( t +1) and µ x $_{j}$( t +1) using ̂ q$_{j}$ ( t ) and µ q $_{j}$( t ) . Set t = t +1 and return to step 2. 5) Input node, non-linear step: For every ( i, j ) ∈ E compute 4) Input node, linear step: For every ( i, j ) ∈ E compute 3) Output node, non-linear step: For every ( i, j ) ∈ E compute 2) Output node, linear step: For every ( i, j ) ∈ E compute Also compute ̂ z$_{i}$ ( t ) and µ z $_{i}$( t ) similarly, but with the summation over all r ∈ { 1 , . . . , n } . where D$_{r}$ ( y, ̂ z, µ ) are the derivatives of the negative log likelihood function in (16). Also, compute ̂ q$_{j}$ ( t ) and µ q $_{j}$( t ) similarly, but with the summation over all ℓ ∈ { 1 , . . . , m } . C. Heuristic Justification B. Algorithm A. Scalar Estimation Functions IV. RELAXED BELIEF PROPAGATION the mixing update. Suppose the output node y$_{i}$ has in-degree d . That is, there are d indices j such that Φ$_{ij}$ is non-zero. Then, the evaluation of the distributions on z$_{i}$$_{→}$$_{j}$ and z$_{i}$ involve the integration over d − 1 and d components x$_{r}$ . Since the complexity of this computation grows exponentially in d , the BP algorithm is only tractable when the transform matrix Φ is sparse (i.e., d is small). The point of relaxed BP is to provide an approximation to BP suitable for large, dense Φ . Before describing the relaxed BP algorithm, we need to define certain functions related to scalar estimation problems at the input and output nodes. At the input nodes, we consider the problem of estimating a scalar random variable x ∼ p$_{X}$ ( x ) from some scalar observation of the form where µ > 0 is a noise-level and v is additive Gaussian noise independent of x . Let F$_{in}$ ( q, µ ) and E$_{in}$ ( q, µ ) be the conditional mean and variance of the random variable x given the scalar observation q . Although, the functions F$_{in}$ ( q, µ ) and E$_{in}$ ( q, µ ) may not have closed form expressions, they can be evaluated with one-dimensional integrals. To analyze the output nodes, suppose that z is a scalar Gaus- sian random variable z ∼ N ($_{̂}$ z, µ ) and y has the conditional distribution p$_{Y}$$_{|}$$_{Z}$ ( y | z ) . Let p$_{Y}$$_{|}$$_{̂}$ $_{Z,µ}$( y |$_{̂}$ z, µ ) be the likelihood function where φ ( z − ̂ z ; µ ) is the Gaussian p.d.f. in (5) with mean ̂ z and variance µ . The relaxed BP algorithm is based on the derivatives of log likelihood or score function 1) Initialization: Set t = 1 , and for every input node index j and every ( i, j ) ∈ E , initialize