Evaluation of Scalable Semidefinite Relaxation Against Modern Inference Techniques

Abstract

In the 2013 in “A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems”, Kappes et. al”1 provided a modernization to the previous benchmark models and algorithms used by Szeliski et al. In 2014, the paper “Scalable Semidefinite Relaxation for Maximum A Posterior Estimation”2 was published by Huang et. al. Huang et. al “proposed a novel semidefinite relaxation algorithm for second-order MAP inference in pairwise undirected graphical models. For this project, we will compare the semidefinite relaxation algorithm to several of the algorithms available in OpenGM2 as of the 2014 update to “A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems”3.