ML Anthology

DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems

Florian Bernard, Christian Theobalt, Michael Moeller
CVPR 2018
doi:10.1109/CVPR.2018.00453 /cvpr/2018/bernard2018cvpr-ds/

Abstract

In this work we study convex relaxations of quadratic optimisation problems over permutation matrices. While existing semidefinite programming approaches can achieve remarkably tight relaxations, they have the strong disadvantage that they lift the original n^2-dimensional variable to an n^4-dimensional variable, which limits their practical applicability. In contrast, here we present a lifting-free convex relaxation that is provably at least as tight as existing (lifting-free) convex relaxations. We demonstrate experimentally that our approach is superior to existing convex and non-convex methods for various problems, including image arrangement and multi-graph matching.

PDF CVPR Semantic Scholar

Cite

Text

Bernard et al. "DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2018. doi:10.1109/CVPR.2018.00453

Markdown

[Bernard et al. "DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2018.](https://mlanthology.org/cvpr/2018/bernard2018cvpr-ds/) doi:10.1109/CVPR.2018.00453

BibTeX

@inproceedings{bernard2018cvpr-ds,
  title     = {{DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems}},
  author    = {Bernard, Florian and Theobalt, Christian and Moeller, Michael},
  booktitle = {Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year      = {2018},
  doi       = {10.1109/CVPR.2018.00453},
  url       = {https://mlanthology.org/cvpr/2018/bernard2018cvpr-ds/}
}