Efficient inference of continuous Markov random fields with polynomial potentials

Research output: Contribution to journalConference articlepeer-review


In this paper, we prove that every multivariate polynomial with even degree can be decomposed into a sum of convex and concave polynomials. Motivated by this property, we exploit the concave-convex procedure to perform inference on continuous Markov random fields with polynomial potentials. In particular, we show that the concave-convex decomposition of polynomials can be expressed as a sum-of-squares optimization, which can be efficiently solved via semidefinite programing. We demonstrate the effectiveness of our approach in the context of 3D reconstruction, shape from shading and image denoising, and show that our method significantly outperforms existing techniques in terms of efficiency as well as quality of the retrieved solution.

Original languageEnglish (US)
Pages (from-to)936-944
Number of pages9
JournalAdvances in Neural Information Processing Systems
Issue numberJanuary
StatePublished - 2014
Externally publishedYes
Event28th Annual Conference on Neural Information Processing Systems 2014, NIPS 2014 - Montreal, Canada
Duration: Dec 8 2014Dec 13 2014

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'Efficient inference of continuous Markov random fields with polynomial potentials'. Together they form a unique fingerprint.

Cite this