Richard Zhang, Somayeh Sojoudi, and Javad Lavaei. Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery. Journal of Machine Learning Research, 2019. https://jmlr.org/papers/v20/19-020.html.
Nonconvex matrix recovery is known to contain no spurious local minima under a restricted isometry property (RIP) with a sufficiently small RIP constant δδ. If δδ is too large, however, then counterexamples containing spurious local minima are known to exist. In this paper, we introduce a proof technique that is capable of establishing sharp thresholds on δδ to guarantee the inexistence of spurious local minima. Using the technique, we prove that in the case of a rank-1 ground truth, an RIP constant of δ<1/2δ<1/2 is both necessary and sufficient for exact recovery from any arbitrary initial point (such as a random point). We also prove a local recovery result: given an initial point x0x0 satisfying f(x0)≤(1−δ)2f(0)f(x0)≤(1−δ)2f(0), any descent algorithm that converges to second-order optimality guarantees exact recovery.