Convex Relaxations for Matching Symmetric Shapes

Finding an isometric-as-possible mapping between two (discretized) shapes is an important task in computer graphics and related shape analysis fields. This problem is often modeled as a quadratic assignment problem (QAP), which is an NP hard combinatorial problem. In this talk we will introduce the DS++ algorithm for (approximately) solving the QAP. We show the algorithm improves upon standard algorithms such as the DS (doubly stochastic) algorithm, both in terms of the accuracy of the relaxation, and in terms of  the projection procedure used to obtain a feasible integer solution.

Next we will analyze the successfulness of the DS++ relaxation (and even the weaker DS relaxation) for fully isometric matching problems. We will review results showing that both algorithms are successful for almost all asymmetric shapes, and present our results which show that they are successful for almost all shapes with reflective symmetry as well. We also provide example of simple symmetry groups for which the DS relaxation is never successful.