Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements

摘要: We study the problem of estimating low-rank matrices from linear measurements (a.k.a., matrix sensing) through nonconvex optimization. propose an efficient stochastic variance reduced gradient descent algorithm to solve a optimization sensing. Our is applicable both noisy and noiseless settings. In case with observations, we prove that our converges unknown at rate up minimax optimal statistical error. And in setting, guaranteed linearly converge achieves exact recovery sample complexity. Most notably, overall computational complexity proposed algorithm, which defined as iteration times per time complexity, lower than state-of-the-art algorithms based on descent. Experiments synthetic data corroborate superiority over algorithms.