On the local stability of semidefinite relaxations

Abstract

We consider a parametric family of quadratically constrained quadratic programs (QCQP) and their associated semidefinite programming (SDP) relaxations. Given a nominal value of the parameter at which the SDP relaxation is exact, we study conditions (and quantitative bounds) under which the relaxation will continue to be exact as the parameter moves in a neighborhood around the nominal value. Our framework captures a wide array of statistical estimation problems including tensor principal component analysis, rotation synchronization, orthogonal Procrustes, camera triangulation and resectioning, essential matrix estimation, system identification, and approximate GCD. Our results can also be used to analyze the stability of SOS relaxations of general polynomial optimization problems.

23 pages, 3 figures

References in corpus (2)

• An Efficient Solution to Non-Minimal Case Essential Matrix Estimation
• Sampling algebraic varieties for sum of squares programs

Cited by in corpus (6)

• An Efficient Solution to Non-Minimal Case Essential Matrix Estimation
• Convex Iteration for Distance-Geometric Inverse Kinematics
• Safe and Smooth: Certified Continuous-Time Range-Only Localization
• One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers
• An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization
• Voronoi Cells of Varieties