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×n-dimensional variable to
an n2×n2
-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