We discuss semidefinite relaxations of two popular shape matching paradigms: Quadratic Matching (QAM) and Procrustes Matching (PM).
For quadratic matching we show that the problem can be lifted to a higher dimensional space where standard relaxations to QAM can be seen as intersections of some spectrahedron and a polyhedron. This unified point of view allows constructing a state of the art semidefinite QAM relaxation provably better than standard relaxations including doubly stochastic and spectral relaxations.
Although this leads to a tight relaxation, scalability is a bottleneck. We show that a similar, equivalent lower-dimensional lift exist for the more particular problem of Procrustes Matching. This allows a more efficient semidefinite relaxation for the PM problem and the intimately related Functional Maps problem. Furthermore, we show that the suggested relaxation has an exact recovery property even in the case the shapes have bilateral symmetries.
Copyright. All Rights Reserved.