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. His talk will take place on Wednesday, February 24, 2016, 1pm in room G202. THE TALK IS POSTPONED, it will take place on Tuesday, April 12, 2016, 2pm in room A113.

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.