M. Pawan Kumar 
HOME

AN ANALYSIS OF CONVEX RELAXATIONS FOR MAP ESTIMATION OF DISCRETE MRFs M. Pawan Kumar, V. Kolmogorov and P. Torr In Journal of Machine Learning Research (JMLR), 2009 The problem of obtaining the maximum a posteriori estimate of a general discrete Markov random field (i.e., a Markov random field defined using a discrete set of labels) is known to be NPhard. However, due to its central importance in many applications, several approximation algorithms have been proposed in the literature. In this paper, we present an analysis of three such algorithms based on convex relaxations: (i)LPS: the linear programming (LP) relaxation proposed by Schlesinger for a special case and independently by Chekuri et al., Koster et al., and Wainwright et al. for the general case; (ii) QPRL: the quadratic programming (QP) relaxation of Ravikumar and Lafferty; and (iii) SOCPMS: the second order cone programming (SOCP) relaxation first proposed by Muramatsu and Suzuki for two label problems and later extended by Kumar et al. for a general label set. We show that the SOCPMS and the QPRL relaxations are equivalent. Furthermore, we prove that despite the flexibility in the form of the constraints/objective function offered by QP and SOCP, the LPS relaxation strictly dominates (i.e., provides a better approximation than) QPRL and SOCPMS. We generalize these results by defining a large class of SOCP (and equivalent QP) relaxations which is dominated by the LPS relaxation. Based on these results we propose some novel SOCP relaxations which define constraints using random variables that form cycles or cliques in the graphical model representation of the random field. Using some examples we show that the new SOCP relaxations strictly dominate the previous approaches. [Paper] [Project Page] 