# On the local stability of semidefinite relaxations

arXiv: https://arxiv.org/abs/1710.04287 · HTML: https://mlsanity.com/paper/1710.04287/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Oct 2017.

## Built on by (most cited first, 12 of 12)

- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [Convex Relaxation for Robust Vanishing Point Estimation in Manhattan World](https://mlsanity.com/paper/2505.04788/) (2025)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [GlobalPointer: Large-Scale Plane Adjustment with Bi-Convex Relaxation](https://mlsanity.com/paper/2407.13537/) (2024)
- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [Snapshot of Algebraic Vision](https://mlsanity.com/paper/2210.11443/) (2022)
- [On the Tightness of Semidefinite Relaxations for Rotation Estimation](https://mlsanity.com/paper/2101.02099/) (2021)
- [An Overview of the Burer-Monteiro Method for Certifiable Robot Perception](https://mlsanity.com/paper/2410.00117/) (2024)
- [From Correspondences to Pose: Non-minimal Certifiably Optimal Relative Pose without Disambiguation](https://mlsanity.com/paper/2312.05995/) (2023)
- [Semidefinite Relaxations for Robust Multiview Triangulation](https://mlsanity.com/paper/2301.11431/) (2023)
- [Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search](https://mlsanity.com/paper/2207.08350/) (2022)
- [Certifiable Factor Graph Optimization](https://mlsanity.com/paper/2603.01267/) (2026)

## Abstract (arXiv)

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.