Variable Elimination in the Fourier Domain
  The ability to represent complex high dimensional probability distributions
in a compact form is one of the key insights in the field of graphical models.
Factored representations are ubiquitous in machine learning and lead to major
computational advantages. We explore a different type of compact representation
based on discrete Fourier representations, complementing the classical approach
based on conditional independencies. We show that a large class of
probabilistic graphical models have a compact Fourier representation. This
theoretical result opens up an entirely new way of approximating a probability
distribution. We demonstrate the significance of this approach by applying it
to the variable elimination algorithm. Compared with the traditional bucket
representation and other approximate inference algorithms, we obtain
significant improvements.
