  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, 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.
