Sharp Global Guarantees for Nonconvex Low-Rank Matrix Recovery in the Overparameterized Regime
share
We prove that it is possible for nonconvex low-rank matrix recovery to contain no spurious local minima when the rank of the unknown ground truth r^⋆<r is strictly less than the search rank r, and yet for the claim to be false when r^⋆=r. Under the restricted isometry property (RIP), we prove, for the general overparameterized regime with r^⋆≤ r, that an RIP constant of δ<1/(1+√(r^⋆/r)) is sufficient for the inexistence of spurious local minima, and that δ<1/(1+1/√(r-r^⋆+1)) is necessary due to existence of counterexamples. Without an explicit control over r^⋆≤ r, an RIP constant of δ<1/2 is both necessary and sufficient for the exact recovery of a rank-r ground truth. But if the ground truth is known a priori to have r^⋆=1, then the sharp RIP threshold for exact recovery is improved to δ<1/(1+1/√(r)).
READ FULL TEXT