ShapeFit: Exact location recovery from corrupted pairwise directions
share
Let t_1,...,t_n ∈R^d and consider the location recovery problem: given a subset of pairwise direction observations {(t_i - t_j) / t_i - t_j_2}_i<j ∈ [n] × [n], where a constant fraction of these observations are arbitrarily corrupted, find {t_i}_i=1^n 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 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.
READ FULL TEXT