[VGS-IT] Linear Programming Relaxation Approach to Discrete Energy Minimization
FIT VUT v Brně 12.4.2016
The talk will be given on Tuesday, April 12 at 2pm in room A113.
Title: Linear Programming Relaxation Approach to Discrete Energy Minimization
Abstract: Discrete energy minimization consists in minimizing a function of many discrete variables that is a sum of functions, each depending on a small subset of the variables. This is also known as MAP inference in graphical models (Markov random fields) or weighted constraint satisfaction. Many successful approaches to this useful but NP-complete problem are based on its natural LP relaxation. I will discuss this LP relaxation in detail, along with algorithms able to solve it for very large instances, which appear e.g. in computer vision. In particular, I will discuss in detail a convex message passing algorihtm, generalized min-sum diffusion.
Tomáš Werner works as a researcher at the Center for Machine Perception, Faculty of Electrical Engineering, Czech Technical University, where he also obtained his PhD degree. In 2001-2002 he worked as a post-doc at the Visual Geometry Group, Oxford University, U.K. In the past, his main interest was multiple view geometry and three-dimensional reconstruction in computer vision. Today, his interest is in machine learning and optimization, in particular graphical models. He is a (co-)author of more than 70 publications, with 350 citations in WoS.
All are cordially invited.