A New Look at the Generalized Distributive Law

Wednesday, August 8, 2001 - 11:00am - 12:00pm
Keller 3-180
Vankat Anantharam (University of California, Berkeley)
(Joint work with Payam Pakzad).

The Generalized Distributive Law provides an algorithm for solving the problem of marginalizing a function of several variables over certain subsets of those variables. It has been recognized as underlying a number of important algorithms that are widely used in physical layer communications, such as the BCJR algorithm, the Viterbi algorithm, certain fast transforms, etc.. Convergence of the algorithm to the correct answer is known if a certain junction tree condition holds, and it is generally necessary to force this condition by grouping variables, which results in a provably convergent algorithm of higher complexity. However, it is also the practice in several important applications to avoid such grouping of variables, thus using lower complexity versions of this algorithm even though no one knows the conditions for convergence to the correct answer. This is the case, for instance, in some popular decoding algorithms for turbo codes and low density parity check codes.

We decided to take a fresh look at the problem that the GDL attempts to solve by reformulating the marginalization problem in a broader context. In the process we have developed a parallel theory to the existing one which includes the current one as a special case. It is of particular interest that our theory offers a novel way to force (an analog of) the junction tree condition and appears to be able to do so without taking such a big complexity hit. Thus our theory leads to new algorithms which are provably convergent. Also, in some of the examples we have examined, such algorithms seem to offer significant improvements over the provably convergent algorithms that would be derived using the current theory.

Developing more convincing examples (if such exist !) is ongoing work. In this talk our theory will be presented together with such examples as we currently have.