  Projected gradient descent and its Riemannian variant belong to a typical
class of methods for low-rank matrix estimation. This paper proposes a new
Nesterov's Accelerated Riemannian Gradient algorithm by efficient orthographic
retraction and tangent space projection. The subspace relationship between
iterative and extrapolated sequences on the low-rank matrix manifold provides a
computational convenience. With perturbation analysis of truncated singular
value decomposition and two retractions, we systematically analyze the local
convergence of gradient algorithms and Nesterov's variants in the Euclidean and
Riemannian settings. Theoretically, we estimate the exact rate of local linear
convergence under different parameters using the spectral radius in a closed
form and give the optimal convergence rate and the corresponding momentum
parameter. When the parameter is unknown, the adaptive restart scheme can avoid
the oscillation problem caused by high momentum, thus approaching the optimal
convergence rate. Extensive numerical experiments confirm the estimations of
convergence rate and demonstrate that the proposed algorithm is competitive
with first-order methods for matrix completion and matrix sensing.
