Graphical models provide a compelling framework for representing complex high dimensional probability distributions in a compact form. We explore a different type of compact representation based on the Hadamard-Fourier transform. We show that a large class of probabilistic models have a compact Fourier representation. This formal result opens up a new way of approximating complex probability distributions. We demonstrate the advantage of incorporating a Fourier representation into a variable elimination inference strategy. Compared to other state-of-the-art probabilistic inference techniques, we demonstrate significant computational gains in several domains.

This is joint work with Yexiang Xue, Stefano Ermon, Ronan Le Bras, and Carla P. Gomes.