Computation of cross-moments using message passing over factor graphs

Abstract

This paper considers the problem of cross-moments computation for functions which decompose according to cycle-free factor graphs. Two algorithms are derived, both based on message passing computation of a corresponding moment-generating function (MGF). The first one is realized as message passing algorithm over a polynomial semiring and represents a computation of the MGF Taylor coefficients, while the second one represents message passing algorithm over a binomial semiring and a computation of the MGF partial derivatives. We found that some previously developed algorithms can be seen as special cases of our algorithms and we consider the time and memory complexities.