hide
Free keywords:
Mathematics, Optimization and Control, math.OC,Computer Science, Computer Vision and Pattern Recognition, cs.CV,Statistics, Machine Learning, stat.ML
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 {\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.