# On the simplicity and conditioning of low rank semidefinite programs

arXiv: https://arxiv.org/abs/2002.10673 · HTML: https://mlsanity.com/paper/2002.10673/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2020.

## Built on by (most cited first, 5 of 5)

- [Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching](https://mlsanity.com/paper/2312.11801/) (2023)
- [Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle](https://mlsanity.com/paper/2210.13968/) (2022)
- [Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the Tensor Nuclear Norm Under Strict Complementarity](https://mlsanity.com/paper/2308.01677/) (2023)
- [Low-Rank Extragradient Methods for Scalable Semidefinite Optimization](https://mlsanity.com/paper/2402.09081/) (2024)
- [SATORIS-N: Spectral Analysis based Traffic Observation Recovery via Informed Subspaces and Nuclear-norm minimization](https://mlsanity.com/paper/2602.03138/) (2026)

## Abstract (arXiv)

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, mathbbZ2 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.