Planar Cycle Covering Graphs

摘要

We describe a new variational lower-bound on the minimum energy configuration, of a planar binary Markov Random Field (MRF). Our method is based on adding auxiliary nodes to every face of a planar embedding of the graph in order to capture the effect of unary potentials. A ground state of the re sulting approximation can be computed effi ciently by reduction to minimum-weight per fect matching. We show that optimization of variational parameters achieves the same lower-bound as dual-decomposition into the set of all cycles of the original graph. We demonstrate that our variational optimiza tion converges quickly and provides high quality solutions to hard combinatorial prob lems 10-100x faster than competing algo rithms that optimize the same bound.