DS: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems
DS: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems
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 …