Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
This provides a theoretical guarantee for matrix completion algorithms, though it appears incremental as it extends existing Burer-Monteiro factorization analysis to rectangular matrices.
The paper tackles the rectangular matrix completion problem by optimizing a nonconvex objective using gradient descent on a lifted positive semidefinite matrix, achieving linear convergence to the global optimum with high probability given O(μr²κ²n max(μ, log n)) random observations of an incoherent matrix.
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 \max(μ, \log n))$ random observations of a $n_1 \times n_2$ $μ$-incoherent matrix of rank $r$ and condition number $κ$, where $n = \max(n_1, n_2)$, the algorithm linearly converges to the global optimum with high probability.