We consider energy minimization for undirected graphical models, also
known as the MAP-inference problem for Markov random fields. Although
combinatorial methods, which return a provably optimal integral
solution of the problem, made a big progress in the past decade, they
are still typically unable to cope with largescale datasets. On the
other hand, large scale datasets are usually defined on sparse graphs
and convex relaxation methods, such as linear programming relaxations
often provide good approximations to integral solutions.
We propose a novel method of combining combinatorial and convex
programming techniques to obtain a global solution of the initial
combinatorial problem. Based on the information obtained from the
solution of the convex relaxation, our method confines application of
the combinatorial solver to a small fraction of the initial graphical
model, which allows to optimally solve big problems. We demonstrate
the power of our approach on a computer vision energy minimization
benchmark.