We propose a generic framework based on a new stochastic variance-reduced
gradient descent algorithm for accelerating nonconvex low-rank matrix recovery.
Starting from an appropriate initial estimator, our proposed algorithm performs
projected gradient descent based on a novel semi-stochastic gradient
specifically designed for low-rank matrix recovery. Based upon the mild
restricted strong convexity and smoothness conditions, we derive a projected
notion of the restricted Lipschitz continuous gradient property, and prove that
our algorithm enjoys linear convergence rate to the unknown low-rank matrix
with an improved computational complexity. Moreover, our algorithm can be
employed to both noiseless and noisy observations, where the optimal sample
complexity and the minimax optimal statistical rate can be attained
respectively. We further illustrate the superiority of our generic framework
through several specific examples, both theoretically and experimentally.