Reviews: Smoothed analysis of the low-rank approach for smooth semidefinite programs

This paper concerns the Burer-Monteiro (i.e. A(X) b, X \succeq 0. The BM heuristic relies on the fact when the constraint set is compact, the above SDP has a global solution with rank up to square root of the **number of the linear constraints** (denoted as m). This allows one to perform substitution X YY * and then perform a heuristic numerical search in the low-dimensional subspace of Y. In general, there is no guarantee such heuristic search would find the global solution, i.e. Recent advances (Bounal et al. 2016b, 2018) show that for almost all matrix C, when A(YY *) defines a smooth manifold, all second-order stationary points (SOSP) of the resulting nonconvex program are global optimal, provided the rank of Y scales as sqrt(m).