Stochastic Variance Reduced Gradient for Affine Rank Minimization Problem

In this paper, we develop an efficient stochastic variance reduced gradient descent algorithm to solve the affine rank minimization problem consisting of finding a matrix of minimum rank from linear measurements. The proposed algorithm as a stochastic gradient descent strategy enjoys a more favorable complexity than that using full gradients. It also reduces the variance of the stochastic gradient at each iteration and accelerates the rate of convergence. We prove that the proposed algorithm converges linearly in expectation to the solution under a restricted isometry condition. Numerical experimental results demonstrate that the proposed algorithm has a clear advantageous balance of efficiency, adaptivity, and accuracy compared with other state-of-the-art algorithms.