content_image/384169.jpg content_image/384166.jpg content_image/384172.jpg content_image/384174.jpg content_image/384173.jpg content_image/384175.jpg content_image/384162.jpg content_image/384163.jpg content_image/384164.jpg content_image/384165.jpg content_image/384167.jpg content_image/384168.jpg content_image/384170.jpg content_image/384171.jpg
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 Φ . 

## A. Scalar Estimation Functions 

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 

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

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 

for r > 0 . Again, this function can in general be evaluated numerically. 

## B. Algorithm 

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: 

1) Initialization: Set t = 1 , and for every input node index j and every ( i, j ) ∈ E , initialize 

where ̂ x$_{init}$ and µ x init are the mean and variance of the prior p$_{X}$ ( x ) . 

## IV. RELAXED BELIEF PROPAGATION 

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

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

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

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

## C. Heuristic Justification 

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 

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 } . 

3) Output node, non-linear step: For every ( i, j ) ∈ E compute 

where D$_{r}$ ( y, ̂ z, µ ) are the derivatives of the negative log likelihood function in (16). 

4) Input node, linear step: For every ( i, j ) ∈ E compute 

Also, compute ̂ q$_{j}$ ( t ) and µ q $_{j}$( t ) similarly, but with the summation over all ℓ ∈ { 1 , . . . , m } . 

5) Input node, non-linear step: For every ( i, j ) ∈ E compute 

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. 

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

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

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

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

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

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

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

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

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

