  Optimization over low rank matrices has broad applications in machine
learning. For large scale problems, an attractive heuristic is to factorize the
low rank matrix to a product of two much smaller matrices. In this paper, we
study the nonconvex problem $\min_{U\in\mathcal{R}^{n\times r}} g(U)=f(UU^T)$
under the assumptions that $f(X)$ is restricted $\mu$-strongly convex and
$L$-smooth on the set $\{X:X\succeq 0,rank(X)\leq r\}$. We propose an
accelerated gradient method with alternating constraint that operates directly
on the $U$ factors and show that the method has local linear convergence rate
with the optimal dependence on the condition number of $\sqrt{L/\mu}$.
Globally, our method converges to the critical point with zero gradient from
any initializer. Our method also applies to the problem with the asymmetric
factorization of $X=\widetilde U\widetilde V^T$ and the same convergence result
can be obtained. Extensive experimental results verify the advantage of our
method.
