Wavelet Belief Propagation for Large Scale Inference Problems
Abstract
Loopy belief propagation (LBP) is a powerful tool
for approximate inference in Markov random fields
(MRFs). However, for problems with large state
spaces, the runtime costs are often prohibitively high.
In this paper, we present a new LBP algorithm that
represents all beliefs, marginals, and messages in a
wavelet representation, which can encode the probabilistic information much more compactly. Unlike previous
work, our algorithm operates solely in the wavelet domain. This yields an output-sensitive algorithm where
the running time depends mostly on the information
content rather than discretization resolution. We apply
the new technique to typical problems with large state
spaces such as image matching and wide-baseline optical flow where we observe a signicantly improved scaling
behavior with discretization resolution. For large
problems, the new technique is signicantly faster than
even an optimized spatial domain implementation.
Keywords:
belief propagation, wavelet, inference, compression, optimization
Paper [preprint version] (~2MB)
- 11496 mal angeklickt
Bibliography
R. Lasowski, A. Tevs, M. Wand, H.-P. Seidel "Wavelet Belief Propagation for Large Scale Inference Problems" , CVPR, 2011 [bibtex]