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

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.