Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery

The function f is nonconvex, so a "greedy" local search algorithm can become stuck at a spurious local minimum, especially if a random initial point is used. Despite this apparent risk of failure, the nonconvex approach remains both widely popular as well as highly effective in practice. Recently,Bhojanapalli et al. [2016b] provided a rigorous theoretical justification for the empirical success of local search on problem (2). Specifically, they showed that the problem contains no spurious local minima under the assumption that A satisfies the restricted isometry property(RIP) of Recht et al. [2010] with a sufficiently small constant. The nonconvex problem is easily solved using local search algorithms because every local minimum is also a global minimum.