Exact simultaneous recovery of locations and structure from known orientations and corrupted point correspondences

Understand

Let $t_1,\ldots,t_{n_l} \in \mathbb{R}^d$ and $p_1,\ldots,p_{n_s} \in \mathbb{R}^d$ and consider the bipartite location recovery problem: given a subset of pairwise direction observations $\{(t_i - p_j) / \|t_i - p_j\|_2\}_{i,j \in [n_l] \times [n_s]}$, where a constant fraction of these observations are arbitrarily corrupted, find $\{t_i\}_{i \in [n_ll]}$ and $\{p_j\}_{j \in [n_s]}$ up to a global translation and scale.

• We study the recently introduced ShapeFit algorithm as a method for solving this bipartite location recovery problem.
• In this case, ShapeFit consists of a simple convex program over $d(n_l + n_s)$ real variables.
• We prove that this program recovers a set of $n_l+n_s$ i.i.d.