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

Understand

We study the problem of estimating low-rank matrices from linear measurements (a.k.a., matrix sensing) through nonconvex optimization.

• We propose an efficient stochastic variance reduced gradient descent algorithm to solve a nonconvex optimization problem of matrix sensing.
• Our algorithm is applicable to both noisy and noiseless settings.
• In the case with noisy observations, we prove that our algorithm converges to the unknown low-rank matrix at a linear rate up to the minimax optimal statistical error.