An analysis of convex relaxations for MAP estimation of discrete MRFs

Pawan Kumar, M; Kolmogorov, V; Torr, PHS

Journal article

An analysis of convex relaxations for MAP estimation of discrete MRFs

Abstract:: 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 NP-hard. 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) LP-S: the linear programming (LP) relaxation proposed by Schlesinger (1976) for a special case and independently in Chekuri et al. (2001), Koster et al. (1998), and Wainwright et al. (2005) for the general case; (ii) QP-RL: the quadratic programming (QP) relaxation of Ravikumar and Lafferty (2006); and (iii) SOCP-MS: the second order cone programming (SOCP) relaxation first proposed by Muramatsu and Suzuki (2003) for two label problems and later extended by Kumar et al. (2006) for a general label set.

We show that the SOCP-MS and the QP-RL relaxations are equivalent. Furthermore, we prove that despite the flexibility in the form of the constraints/objective function offered by QP and SOCP, the LP-S relaxation strictly dominates (i.e., provides a better approximation than) QP-RL and SOCPMS. We generalize these results by defining a large class of SOCP (and equivalent QP) relaxations which is dominated by the LP-S 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.

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Cite

Cite this record

APA Style

Pawan Kumar, M., Kolmogorov, V., & Torr, P. H. S. (2009). An analysis of convex relaxations for MAP estimation of discrete MRFs. Journal of Machine Learning Research, 10(3), 71–106.

MLA Style

Pawan Kumar, M., et al. “An Analysis of Convex Relaxations for MAP Estimation of Discrete MRFs.” Journal of Machine Learning Research, vol. 10, no. 3, Journal of Machine Learning Research, 2009, pp. 71–106.

Chicago Style

Pawan Kumar, M, V Kolmogorov, and PHS Torr. 2009. “An Analysis of Convex Relaxations for MAP Estimation of Discrete MRFs.” Journal of Machine Learning Research 10 (3): 71–106.
Share
Print