ShapeFit: Exact location recovery from corrupted pairwise directions

Let t1,ldots,tn ∈ ℝd and consider the location recovery problem: given a subset of pairwise direction observations (ti - tj) / |ti - tj|2i<j ∈ [n] × [n], where a constant fraction of these observations are arbitrarily corrupted, find tii=1n up to a global translation and scale. We propose a novel algorithm for the location recovery problem, which consists of a simple convex program over dn real variables. We prove that this program recovers a set of n i.i.d. Gaussian locations exactly and with high probability if the observations are given by an erdosrenyi graph, d is large enough, and provided that at most a constant fraction of observations involving any particular location are adversarially corrupted. We also prove that the program exactly recovers Gaussian locations for d=3 if the fraction of corrupted observations at each location is, up to poly-logarithmic factors, at most a constant. Both of these recovery theorems are based on a set of deterministic conditions that we prove are sufficient for exact recovery.