• Calendar

June 13, Tuesday
12:00 – 14:00

It is often useful to formulate problems in vision and in computational biology as energy minimization problems. For many of these problems, finding the global optimum is NP hard and researchers have focused on approximation methods. From an application standpoint, using approximations is problematic because when things fail we don't know whom to blame - the energy function or the approximate minimization.

In this talk I will describe our recent successes in finding the GLOBAL optimum for energy functions in stereo vision, side chain prediction and protein design. Our approach is based on a classical technique - linear programming (LP) relaxations, but with a novel twist - we use a variant of belief propagation to solve the LP relaxation. By using belief propagation, we can find the global optimum for large, real-world problems in a few minutes.

Joint work with Talya Meltzer and Chen Yanover