On the local stability of semidefinite relaxations

Published in preprint, 2017

Recommended citation: Diego Cifuentes, Sameer Agarwal, Pablo Parrilo, Rekha Thomas (2017). "On the local stability of semidefinite relaxations." arXiv:1710.04287. https://arxiv.org/abs/1710.04287

Consider the problem of finding the nearest point to an algebraic variety. This class encompasses several important estimation problems, including low rank tensor approximation, the triangulation problem from computer vision, sensor network localization, rotation synchronization. These problems are typically nonconvex, and SDP relaxations provide a tractable alternative. In this paper we show that, under some regularity assumptions, these relaxations solve the problem exactly in the low noise regime, i.e., when the point is sufficiently close to the variety. More generally, our framework captures a parametric family of polynomial optimization problems over algebraic sets. We characterize sufficient conditions for stability of the relaxation, and provide quantitative bounds on the region of stability.

Download paper here

See also:

  • My slides from SIAM Conference on Applied Algebraic Geometry’ 17