Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/106855
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Efficient semidefinite branch-and-cut for MAP-MRF inference |
Author: | Wang, P. Shen, C. van den Hengel, A. Torr, P. |
Citation: | International Journal of Computer Vision, 2016; 117(3):269-289 |
Publisher: | Springer US |
Issue Date: | 2016 |
ISSN: | 0920-5691 1573-1405 |
Statement of Responsibility: | Peng Wang, Chunhua Shen, Anton van den Hengel, Philip H. S. Torr |
Abstract: | We propose a branch-and-cut (B&C) method for solving general MAP-MRF inference problems. The core of our method is a very efficient bounding procedure, which combines scalable semidefinite programming (SDP) and a cutting-plane method for seeking violated constraints. In order to further speed up the computation, several strategies have been exploited, including model reduction, warm start and removal of inactive constraints. We analyze the performance of the proposed method under different settings, and demonstrate that our method either outperforms or performs on par with state-of-the-art approaches. Especially when the connectivities are dense or when the relative magnitudes of the unary costs are low, we achieve the best reported results. Experiments show that the proposed algorithm achieves better approximation than the state-of-the-art methods within a variety of time budgets on challenging non-submodular MAP-MRF inference problems. |
Keywords: | MAP inference; Markov random field; semidefinite programming; branch and cut |
Description: | Published online: 24 October 2015 |
Rights: | © Springer Science+Business Media New York 2015 |
DOI: | 10.1007/s11263-015-0865-2 |
Published version: | http://dx.doi.org/10.1007/s11263-015-0865-2 |
Appears in Collections: | Aurora harvest 3 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_106855.pdf Restricted Access | Restricted Access | 1.21 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.