ShapeFit: Exact location recovery from corrupted pairwise directions
- Series
- Stochastics Seminar
- Time
- Thursday, December 3, 2015 - 15:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Paul Hand – Rice University – hand@rice.edu
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. To solve the location recovery problem in the
presence of corrupted relative directions, we introduce a tractable
convex program called ShapeFit. Empirically, ShapeFit can succeed on
synthetic data with over 40% 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, and Tom Goldstein.