A Fast Certifier for Large-Scale Degenerate SDPs in Outlier-Robust Machine Perception

Wednesday, March 24, 2021 - 4:00pm to 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Heng Yang



Zoom meeting id

941 9313 3201

Join Zoom meeting



The Moment/Sums-of-Squares hierarchy of semidefinite relaxations at order two has been shown as a powerful tool for solving non-convex and combinatorial outlier-robust machine perception problems to certifiable global optimality. Unfortunately, the resulting semidefinite programs (SDPs) are not only large but also highly degenerate. For example, in an SDP with matrix size n=804, and a number of equality constraints m=122,601, the primal solution X has rank r=1, making it pessimistically difficult for all existing SDP solvers. In this talk, I focus on the certification problem — given a primal feasible X, assert if X is optimal — and present an efficient two-phase certifier. In phase-one, we use an (accelerated) Douglas-Rachford Splitting method to find a dual solution that attains medium-accuracy dual infeasibility. In phase-two, we incorporate second-order information and employ an inexact semi-smooth newton method to attain high accuracy. For medium-scale problems, we show that the inexact newton step can be computed using a direct solver on a linear system that is much smaller than m (in fact on the order of r*n) by invoking the matrix inverse lemma on the original newton system. For large-scale problems, we solve the original newton system using an iterative solver with an effective diagonal preconditioner. We demonstrate solving certification problems to high accuracy in seconds. Joint and ongoing work with Luca Carlone, Ling Liang (NUS), and Kim-Chuan Toh (NUS).

Link to paper: https://arxiv.org/abs/2006.06769



Heng Yang is a Ph.D. student at LIDS, advised by Prof. Luca Carlone. He is broadly interested in robotics, computer vision, and optimization, and learning. In particular, his research, certifiably robust perception, focuses on developing machine perception algorithms for safety-critical applications that are not only robust against large amounts of outliers but also can be certified to be optimal. He received a B.E. from Tsinghua University in China, and an S.M. from MIT, both in Mechanical Engineering. He is a recipient of the Best Paper Award in Robot Vision at the 2020 International Conference on Robotics and Automation (ICRA).