  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.
