  Convex (specifically semidefinite) relaxation provides a powerful approach to
constructing robust machine perception systems, enabling the recovery of
certifiably globally optimal solutions of challenging estimation problems in
many practical settings. However, solving the large-scale semidefinite
relaxations underpinning this approach remains a formidable computational
challenge. A dominant cost in many state-of-the-art (Burer-Monteiro
factorization-based) certifiable estimation methods is solution verification
(testing the global optimality of a given candidate solution), which entails
computing a minimum eigenpair of a certain symmetric certificate matrix. In
this letter, we show how to significantly accelerate this verification step,
and thereby the overall speed of certifiable estimation methods. First, we show
that the certificate matrices arising in the Burer-Monteiro approach
generically possess spectra that make the verification problem expensive to
solve using standard iterative eigenvalue methods. We then show how to address
this challenge using preconditioned eigensolvers; specifically, we design a
specialized solution verification algorithm based upon the locally optimal
block preconditioned conjugate gradient (LOBPCG) method together with a simple
yet highly effective algebraic preconditioner. Experimental evaluation on a
variety of simulated and real-world examples shows that our proposed
verification scheme is very effective in practice, accelerating solution
verification by up to 280x, and the overall Burer-Monteiro method by up to 16x,
versus the standard Lanczos method when applied to relaxations derived from
large-scale SLAM benchmarks.
