  The Procrustes matching (PM) problem is the problem of finding the optimal
rigid motion and labeling of two point sets so that they are as close as
possible. Both rigid and non-rigid shape matching problems can be formulated as
PM problems. Recently [Maron et al.] presented a novel convex semi-definite
programming relaxation (PM-SDP) for PM which achieves state of the art results
on common shape matching benchmarks.
  In this paper we analyze the successfulness of PM-SDP in solving PM problems
without noise (Exact PM problems). We begin by showing Exact PM to be
computationally equivalent to the graph isomorphism problem. We demonstrate
some natural theoretical properties of the relaxation, and use these properties
together with the moment interpretation of [Lasserre] to show that for exact PM
problems and for (generic) input shapes which are asymmetric or bilaterally
symmetric, the relaxation returns a correct solution of PM.
  For symmetric shapes, PM has multiple solutions. The non-convex set of
optimal solutions of PM is strictly contained in the convex set of optimal
solutions of PM-SDP, so that `most' solutions of PM-SDP will not be solutions
of PM. We deal with this by showing the solution set of PM to be the extreme
points of the solution set of PM-SDP, and suggesting a random algorithm which
returns a solution of PM with probability one, and returns all solutions of PM
with equal probability. We also show these results can be extended to the
almost-exact case.
  To the best of our knowledge, our work is the first to achieve exact recovery
in the presence of multiple solutions.
