Fast Exact Matrix Completion: A Unifying Optimization Framework
share
We consider the problem of matrix completion of rank k on an n× m matrix. We show that both the general case and the case with side information can be formulated as a combinatorical problem of selecting k vectors from p column features. We demonstrate that it is equivalent to a separable optimization problem that is amenable to stochastic gradient descent. We design fastImpute, based on projected stochastic gradient descent, to enable efficient scaling of the algorithm of sizes of 10^5 × 10^5. We report experiments on both synthetic and real-world datasets that show fastImpute is competitive in both the accuracy of the matrix recovered and the time needed across all cases. Furthermore, when a high number of entries are missing, fastImpute is over 75% lower in MAPE and 10x faster than current state-of-the-art matrix completion methods in both the case with side information and without.
READ FULL TEXT