Scalable Low-Rank Semidefinite Programming for Certifiably Correct Machine Perception

Semidefinite relaxation has recently emerged as a powerful technique for machine perception, in many cases enabling the recovery of certifiably globally optimal solutions of generally-intractable nonconvex estimation problems. However, the high computational cost of standard interior-point methods for semidefinite optimization prevents these algorithms from scaling effectively to the high-dimensional problems frequently encountered in machine perception tasks. To address this challenge, in this paper we present an efficient algorithm for solving the large-scale but low-rank semidefinite relaxations that underpin current certifiably correct machine perception methods. Our algorithm preserves the scalability of current state-of-the-art low-rank semidefinite optimizers that are custom-built for the geometry of specific machine perception problems, but generalizes to a broad class of convex programs over spectrahedral sets without the need for detailed manual analysis or design. The result is an easy-to-use, general-purpose computational tool capable of supporting the development and deployment of a broad class of novel certifiably correct machine perception methods.