Abstract
In this paper, we study a nonconvex continuous relaxation of MAP inference in discrete Markov random fields
(MRFs). We show that for arbitrary MRFs, this relaxation
is tight, and a discrete stationary point of it can be easily reached by a simple block coordinate descent algorithm.
In addition, we study the resolution of this relaxation using popular gradient methods, and further propose a more
effective solution using a multilinear decomposition framework based on the alternating direction method of multipliers (ADMM). Experiments on many real-world problems
demonstrate that the proposed ADMM significantly outperforms other nonconvex relaxation based methods, and compares favorably with state of the art MRF optimization algorithms in different settings