A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching

Paul Swoboda, Carsten Rother, Hassan Abu Alhaija, Dagmar Kainmuller, Bogdan Savchynskyy

CVPR 2017

doi:10.1109/CVPR.2017.747 /cvpr/2017/swoboda2017cvpr-study/

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.

PDF CVPR Semantic Scholar

Cite

Text

Swoboda et al. "A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching." Conference on Computer Vision and Pattern Recognition, 2017. doi:10.1109/CVPR.2017.747

Markdown

[Swoboda et al. "A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching." Conference on Computer Vision and Pattern Recognition, 2017.](https://mlanthology.org/cvpr/2017/swoboda2017cvpr-study/) doi:10.1109/CVPR.2017.747

BibTeX

@inproceedings{swoboda2017cvpr-study,
  title     = {{A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching}},
  author    = {Swoboda, Paul and Rother, Carsten and Alhaija, Hassan Abu and Kainmuller, Dagmar and Savchynskyy, Bogdan},
  booktitle = {Conference on Computer Vision and Pattern Recognition},
  year      = {2017},
  doi       = {10.1109/CVPR.2017.747},
  url       = {https://mlanthology.org/cvpr/2017/swoboda2017cvpr-study/}
}