Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurements

Abstract

We study low-rank matrix recovery with noisy linear measurements and ask when local search can find the ground truth with small error. We derive sharp guarantees for local minimizers under a restricted-isometry assumption, show how the guarantee improves as noise decreases, and prove a strict-saddle property that supports polynomial-time convergence of perturbed gradient descent.