On the local stability of semidefinite relaxations

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