Exact Simultaneous Recovery of Locations and Structure from Known Orientations and Corrupted Point Correspondences

Let t[subscript 1],…,t[subscript nl] ∈Rd and p[subscript 1],…,p[subscript n[subscript s]] ∈ R[superscript d] and consider the bipartite location recovery problem: given a subset of pairwise direction observations {(t[subscript i]−p[subscript j])/∥t[subscript i]−p[subscript j]∥2}[subscript i,j∈[nℓ]×[ns]], where a constant fraction of these observations are arbitrarily corrupted, find {t[subscript i]}[subscript i∈[nℓ]] and {pj}[subscript j∈[ns]] up to a global translation and scale. This task arises in the Structure from Motion problem from computer vision, which consists of recovering the three-dimensional structure of a scene from photographs at unknown vantage points. 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[subscript l]+n[subscript s]) real variables. We prove that this program recovers a set of n[subscript l]+n[subscript s] i.i.d. Gaussian locations exactly and with high probability if the observations are given by a bipartite Erdős–Rényi graph, d is large enough, and provided that at most a constant fraction of observations involving any particular location are adversarially corrupted. This recovery theorem is based on a set of deterministic conditions that we prove are sufficient for exact recovery. Finally, we propose a modified pipeline for the Structure for Motion problem, based on this bipartite location recovery problem. Keywords: Structure from Motion, Corruption robust recovery, Convex programmingUnited States. Office of Naval ResearchNational Science Foundation (U.S.) (Grant DMS-1362326