Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery
This work addresses the challenge of ensuring reliable optimization in nonconvex matrix recovery for researchers and practitioners in machine learning and signal processing, providing precise theoretical guarantees.
The paper tackles the problem of nonconvex matrix recovery by establishing sharp thresholds on the restricted isometry property (RIP) constant to guarantee no spurious local minima, proving that δ < 1/2 is necessary and sufficient for exact recovery from any initial point in rank-1 cases, and also shows local recovery results under specific conditions.
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$ 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 $x_{0}$ satisfying $f(x_{0})\le(1-δ)^{2}f(0)$, any descent algorithm that converges to second-order optimality guarantees exact recovery.