Algorithm Notes

Based on a little formal analysis, we know:

• As long as the constraint network N is 2-consistent, the candidate lists are non-empty and the normalization factors are non-zero.
• Computationally equivalent to ``turbodecoding''.
• The sequence $\{q_d(x,v)\}$ does not always converge. However, it converges in all of our artificial experiments.
• In the case in which N is a tree of maximum depth k, $U_d(x) = U_\infty(x) = N$ for all $d \geq k$. Thus, $q_\infty(x,v) = q(x,v)$,the true posterior probability.
• The running time of the calculation of q_d is polynomial.