Global MAP-Optimality by Shrinking the Combinatorial Search Area with Convex Relaxation

Add to your list(s) Download to your calendar using vCal

• Bogdan Savchynskyy, University of Heidelberg
• Wednesday 21 May 2014, 15:00-16:00
• MR 5, Centre for Mathematical Sciences.

If you have a question about this talk, please contact Dr Jan Lellmann.

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 significant progress in the past decade, they are still typically unable to cope with large-scale datasets. On the other hand, large scale datasets are often defined on sparse graphs and convex relaxation methods, such as linear programming relaxations then 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 much larger problems. We demonstrate the efficacy of our approach on a computer vision energy minimization benchmark.

This talk is part of the Cambridge Image Analysis Seminars series.

This talk is included in these lists:

• Cambridge Image Analysis Seminars
• MR 5, Centre for Mathematical Sciences

Note that ex-directory lists are not shown.