Belief Propagation for Continuous State Spaces: Stochastic
  Message-Passing with Quantitative Guarantees
  The sum-product or belief propagation (BP) algorithm is a widely used
message-passing technique for computing approximate marginals in graphical
models. We introduce a new technique, called stochastic orthogonal series
message-passing (SOSMP), for computing the BP fixed point in models with
continuous random variables. It is based on a deterministic approximation of
the messages via orthogonal series expansion, and a stochastic approximation
via Monte Carlo estimates of the integral updates of the basis coefficients. We
prove that the SOSMP iterates converge to a \delta-neighborhood of the unique
BP fixed point for any tree-structured graph, and for any graphs with cycles in
which the BP updates satisfy a contractivity condition. In addition, we
demonstrate how to choose the number of basis coefficients as a function of the
desired approximation accuracy \delta and smoothness of the compatibility
functions. We illustrate our theory with both simulated examples and in
application to optical flow estimation.
