DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems
This work addresses computational efficiency for researchers and practitioners in computer vision and optimization by providing a tighter, more scalable solution without the high-dimensional lifting of prior methods.
The paper tackles the problem of quadratic optimization over permutations by introducing a lifting-free convex relaxation that is at least as tight as existing methods, demonstrating experimental superiority over convex and non-convex approaches in tasks like image arrangement and multi-graph matching.
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 {\times} n$-dimensional variable to an $n^2 {\times} n^2$-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.