Continuous Relaxation of MAP Inference: A Nonconvex Perspective

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 multi-pliers (ADMM). Experiments on many real-world problems demonstrate that the proposed ADMM significantly outper-forms other nonconvex relaxation based methods, and compares favorably with state of the art MRF optimization algorithms in different settings.
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01716514
Contributor : D. Khuê Lê-Huu <>
Submitted on : Monday, February 26, 2018 - 4:44:57 PM
Last modification on : Thursday, February 7, 2019 - 4:35:01 PM
Long-term archiving on : Monday, May 28, 2018 - 8:33:29 PM

File

norelax_cvpr2018.pdf
Files produced by the author(s)

Identifiers

Citation

D. Khuê Lê-Huu, Nikos Paragios. Continuous Relaxation of MAP Inference: A Nonconvex Perspective. CVPR 2018 - IEEE Conference on Computer Vision and Pattern Recognition, Jun 2018, Salt Lake City, United States. pp.1-19, ⟨10.1109/CVPR.2018.00580⟩. ⟨hal-01716514v2⟩

Share

Metrics

Record views

330

Files downloads

215