Abstract Let t 1 ,…, t n ∊ ℝ d for d ≥ 2 and consider the location recovery problem: given a subset of pairwise direction observations , where a constant fraction of these observations are arbitrarily corrupted, find 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 Erdős‐Rényi graph, with d 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. © 2017 Wiley Periodicals, Inc.