Matrix factorization is a popular approach for large-scale matrix completion and constitutes a basic component of many solutions for Netflix Prize competition. In this approach, the unknown low-rank matrix is expressed as the product of two much smaller matrices so that the low-rank property is automatically fulfilled. The resulting optimization problem, even with huge size, can be solved (to stationary points) very efficiently through standard optimization algorithms such as alternating minimization and stochastic gradient descent (SGD). However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of whether these algorithms will generate a good solution. In this paper, we establish a theoretical guarantee for the factorization based formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of the factorization based formulation, thus recovering the true low-rank matrix. To the best of our knowledge, our result is the first one that provides recovery guarantee for many standard algorithms such as gradient descent, SGD and block coordinate gradient descent. Our result also applies to alternating minimization, and a notable difference from previous studies on alternating minimization is that we do not need the resampling scheme (i.e. using independent samples in each iteration).

矩阵分解是一种常用的大规模矩阵补全方法，本文提出了一种理论保证，即在正则化条件下，优化算法可以收敛于矩阵分解的全局最优解，并恢复真实的低秩矩阵，其中的非对称矩阵分解的扰动分析是一项技术贡献。

非凸因式分解实现保证矩阵补全