Duality and the Continuous Graphical Model

Alexander Fix¹ and Sameer Agarwal²

¹Cornell University, USA

²Google Inc., USA

Abstract. Inspired by the Linear Programming based algorithms for discrete MRFs, we show how a corresponding infinite-dimensional dual for continuous-state MRFs can be approximated by a hierarchy of tractable relaxations. This hierarchy of dual programs includes as a special case the methods of Peng et al. [17] and Zach & Kohli [33]. We give approximation bounds for the tightness of our construction, study their relationship to discrete MRFs and give a generic optimization algorithm based on Nesterov’s dual-smoothing method [16].

LNCS 8691, p. 266 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer International Publishing Switzerland 2014