Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent

Abstract

We address the rectangular matrix completion problem by lifting the unknown matrix to a positive semidefinite matrix in higher dimension, and optimizing a nonconvex objective over the semidefinite factor using a simple gradient descent scheme. With O( r^2 ^2 n (, n)) random observations of a n_1 n_2 -incoherent matrix of rank r and condition number , where n = (n_1, n_2), the algorithm linearly converges to the global optimum with high probability.

Tasks

Reproductions