# Symmetrized Robust Procrustes: Constant-Factor Approximation and Exact Recovery

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 29 references that are in the map.
- First posted on arXiv 18 Jul 2022.

## Builds on (most cited first, 11 of 11)

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Word Translation Without Parallel Data](https://mlsanity.com/paper/1710.04087/) (2017)
- [TEASER: Fast and Certifiable Point Cloud Registration](https://mlsanity.com/paper/2001.07715/) (2020)
- [A robust self-learning method for fully unsupervised cross-lingual mappings of word embeddings](https://mlsanity.com/paper/1805.06297/) (2018)
- [Improving zero-shot learning by mitigating the hubness problem](https://mlsanity.com/paper/1412.6568/) (2014)
- [Non-Adversarial Unsupervised Word Translation](https://mlsanity.com/paper/1801.06126/) (2018)
- [Exact Recovery with Symmetries for Procrustes Matching](https://mlsanity.com/paper/1606.01548/) (2016)
- [Analysis of Robust Functions for Registration Algorithms](https://mlsanity.com/paper/1810.01474/) (2018)
- [Linearly Converging Quasi Branch and Bound Algorithms for Global Rigid Registration](https://mlsanity.com/paper/1904.02204/) (2019)
- [Aligning Vector-spaces with Noisy Supervised Lexicons](https://mlsanity.com/paper/1903.10238/) (2019)

## Abstract (arXiv)

The classical textitProcrustes problem is to find a rigid motion (orthogonal transformation and translation) that best aligns two given point-sets in the least-squares sense. The textitRobust Procrustes problem is an important variant, in which a power-1 objective is used instead of least squares to improve robustness to outliers. While the optimal solution of the least-squares problem can be easily computed in closed form, dating back to Sch"onemann (1966), no such solution is known for the power-1 problem. In this paper we propose a novel convex relaxation for the Robust Procrustes problem. Our relaxation enjoys several theoretical and practical advantages: Theoretically, we prove that our method provides a √2-factor approximation to the Robust Procrustes problem, and that, under appropriate assumptions, it exactly recovers the true rigid motion from point correspondences contaminated by outliers. In practice, we find in numerical experiments on both synthetic and real robust Procrustes problems, that our method performs similarly to the standard Iteratively Reweighted Least Squares (IRLS). However the convexity of our algorithm allows incorporating additional convex penalties, which are not readily amenable to IRLS. This turns out to be a substantial advantage, leading to improved results in high-dimensional problems, including non-rigid shape alignment and semi-supervised interlingual word translation.