  We study the convergence rate of gradient-based local search methods for
solving low-rank matrix recovery problems with general objectives in both
symmetric and asymmetric cases, under the assumption of the restricted isometry
property. First, we develop a new technique to verify the Polyak-Lojasiewicz
inequality in a neighborhood of the global minimizers, which leads to a local
linear convergence region for the gradient descent method. Second, based on the
local convergence result and a sharp strict saddle property proven in this
paper, we present two new conditions that guarantee the global linear
convergence of the perturbed gradient descent method. The developed local and
global convergence results provide much stronger theoretical guarantees than
the existing results. As a by-product, this work significantly improves the
existing bounds on the RIP constant required to guarantee the non-existence of
spurious solutions.
