A study of lagrangean decompositions and dual ascent solvers for graph matching Conference Paper

Author(s): Swoboda, Paul; Rother, Carsten; Abu Alhaija, Carsten; Kainmueller, Dagmar; Savchynskyy, Bogdan
Title: A study of lagrangean decompositions and dual ascent solvers for graph matching
Affiliation IST Austria
Abstract: We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore this direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art anytime solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each.
Conference Title: CVPR: Computer Vision and Pattern Recognition
Conference Dates: July 22 - 25, 2017
Conference Location: Honolulu, Hawaii, USA
Publisher: IEEE  
Date Published: 2017-01-01
Start Page: 1607
End Page: 1616
DOI: 10.1109/CVPR.2017.747
Notes: The authors would like to thank Vladimir Kolmogorov for helpful discussions. The work is partially funded by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160 and under the European Unions Horizon 2020 research and innovation programme (grant agreement No 647769). The last author was supported by the DFG Grant ”ERBI” SA 2640/1-1.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work