A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation

Understand

We propose a unified framework for estimating low-rank matrices through nonconvex optimization based on gradient descent algorithm.

• Our framework is quite general and can be applied to both noisy and noiseless observations.
• In the general case with noisy observations, we show that our algorithm is guaranteed to linearly converge to the unknown low-rank matrix up to minimax optimal statistical error, provided an appropriate initial estimator.
• While in the generic noiseless setting, our algorithm converges to the unknown low-rank matrix at a linear rate and enables exact recovery with optimal sample complexity.