Consider a semidefinite program (SDP) involving an $n\times n$ positive semidefinite matrix $X$. The Burer-Monteiro method consists in solving a nonconvex program in $Y$, where $Y$ is an $n\times p$ matrix such that $X = Y Y^T$. Despite nonconvexity, Boumal et al. showed that the method provably solves generic equality-constrained SDP’s when $p > \sqrt{2m}$, where $m$ is the number of constraints. We extend this result to arbitrary SDP’s, possibly involving inequalities or multiple semidefinite constraints. We illustrate applications to sensor network localization and to matrix sensing.
Citation
arXiv:1904.07147