Event Type:

Applied Mathematics and Computation Seminar

Date/Time:

Friday, November 20, 2015 - 12:00 to 13:00

Location:

GLK 113

Event Link:

Guest Speaker:

Institution:

Rice University

Abstract:

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 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 work is

joint with Choongbum Lee and Vladislav Voroninski.