Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery
  Problems with Corrupted Measurements
  In this paper, we study a general low-rank matrix recovery problem with
linear measurements corrupted by some noise. The objective is to understand
under what conditions on the restricted isometry property (RIP) of the problem
local search methods can find the ground truth with a small error. By analyzing
the landscape of the non-convex problem, we first propose a global guarantee on
the maximum distance between an arbitrary local minimizer and the ground truth
under the assumption that the RIP constant is smaller than $1/2$. We show that
this distance shrinks to zero as the intensity of the noise reduces. Our new
guarantee is sharp in terms of the RIP constant and is much stronger than the
existing results. We then present a local guarantee for problems with an
arbitrary RIP constant, which states that any local minimizer is either
considerably close to the ground truth or far away from it. Next, we prove the
strict saddle property, which guarantees the global convergence of the
perturbed gradient descent method in polynomial time. The developed results
demonstrate how the noise intensity and the RIP constant of the problem affect
the landscape of the problem.
