On the simplicity and conditioning of low rank semidefinite programs
  Low rank matrix recovery problems appear widely in statistics, combinatorics,
and imaging. One celebrated method for solving these problems is to formulate
and solve a semidefinite program (SDP). It is often known that the exact
solution to the SDP with perfect data recovers the solution to the original low
rank matrix recovery problem. It is more challenging to show that an
approximate solution to the SDP formulated with noisy problem data acceptably
solves the original problem; arguments are usually ad hoc for each problem
setting, and can be complex.
  In this note, we identify a set of conditions that we call simplicity that
limit the error due to noisy problem data or incomplete convergence. In this
sense, simple SDPs are robust: simple SDPs can be (approximately) solved
efficiently at scale; and the resulting approximate solutions, even with noisy
data, can be trusted. Moreover, we show that simplicity holds generically, and
also for many structured low rank matrix recovery problems, including the
stochastic block model, $\mathbb{Z}_2$ synchronization, and matrix completion.
Formally, we call an SDP simple if it has a surjective constraint map, admits a
unique primal and dual solution pair, and satisfies strong duality and strict
complementarity.
  However, simplicity is not a panacea: we show the Burer-Monteiro formulation
of the SDP may have spurious second-order critical points, even for a simple
SDP with a rank 1 solution.
