# Exact Recovery with Symmetries for Procrustes Matching

arXiv: https://arxiv.org/abs/1606.01548 · HTML: https://mlsanity.com/paper/1606.01548/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2016.

## Built on by (most cited first, 10 of 10)

- [Low Dimensional Invariant Embeddings for Universal Geometric Learning](https://mlsanity.com/paper/2205.02956/) (2022)
- [Equivariant Deep Weight Space Alignment](https://mlsanity.com/paper/2310.13397/) (2023)
- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [A Simple and Universal Rotation Equivariant Point-cloud Network](https://mlsanity.com/paper/2203.01216/) (2022)
- [Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries](https://mlsanity.com/paper/2106.15493/) (2021)
- [Toward bilipshiz geometric models](https://mlsanity.com/paper/2511.11735/) (2025)
- [Symmetrized Robust Procrustes: Constant-Factor Approximation and Exact Recovery](https://mlsanity.com/paper/2207.08592/) (2022)
- [A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials](https://mlsanity.com/paper/2504.03097/) (2025)

## Abstract (arXiv)

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.