On the local stability of semidefinite relaxations

• 成果类型: Article
• 署名作者: Cifuentes, Diego; Agarwal, Sameer; Parrilo, Pablo A.; Thomas, Rekha R.
• 署名单位: University System of Georgia; Georgia Institute of Technology; Alphabet Inc.; Google Incorporated; University of Washington; University of Washington Seattle; Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01696-1
• 发表日期: 2022
• 页码: 629-663
• 关键词: nonconvex quadratic optimization; RECOVERY

摘要

We consider a parametric family of quadratically constrained quadratic programs 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.