# ShapeFit: Exact location recovery from corrupted pairwise directions

# ShapeFit: Exact location recovery from corrupted pairwise directions

We consider the problem of recovering a set of locations given observations of the direction between pairs of these locations. This recovery task arises from the Structure from Motion problem, in which a three-dimensional structure is sought from a collection of two-dimensional images. In this context, the locations of cameras and structure points are to be found from epipolar geometry and point correspondences among images. These correspondences are often incorrect because of lighting, shadows, and the effects of perspective. Hence, the resulting observations of relative directions contain significant corruptions. Over the past few years, researchers have introduced several algorithms for outlier-tolerant location recovery. For example, Wilson and Snavely introduced the 1dSfM method, and Ozyesil and Singer introduced an second-order cone program (SOCP) based solution known as LUD. Both of these methods are empirically tolerant to outliers, though they currently lack rigorous guarantees of corruption tolerance. To solve the location recovery problem in the presence of corrupted relative directions, we introduce a SOCP called ShapeFit. Empirically, ShapeFit can succeed on synthetic data with over 50% corruption. Rigorously, we prove that ShapeFit can recover a set of locations exactly when a fraction of the measurements are adversarially corrupted and when the data model is random. This and subsequent work was done in collaboration with Choongbum Lee, Vladislav Voroninski, Tom Goldstein, and Stefano Soatto.