Codes and Expansions (CodEx) Seminar

David Rosen (Northeastern University)
Certifiably Correct Machine Perception

Many fundamental machine perception tasks require the solution of a high-dimensional nonconvex estimation problem; this class includes (for example) the fundamental problems of simultaneous localization and mapping (in robotics), 3D reconstruction (in computer vision), and sensor network localization (in distributed sensing). Such problems are known to be computationally hard in general, with many local minima that can entrap the smooth local optimization methods commonly applied to solve them. The result is that standard machine perception algorithms (based upon local optimization) can be surprisingly brittle, often returning egregiously wrong answers even when the problem to which they are applied is well-posed.

In this talk, we present a novel class of certifiably correct estimation algorithms that are capable of efficiently recovering provably good (often globally optimal) solutions of generally-intractable machine perception problems in many practical settings. In brief, our approach directly tackles the problem of nonconvexity by employing convex relaxations (which can be efficiently solved to global optimality) whose minimizers provide provably good approximate solutions to the original estimation problem under moderate measurement noise. We illustrate the design of this class of methods using the fundamental problem of pose-graph optimization (the mathematical abstraction of robotic mapping) as a running example, culminating in the presentation of SE-Sync, the first practical method that is provably capable of recovering exact (globally optimal) solutions. We conclude with a discussion of open questions and future research directions