Publications
Publications
- 2020
- Journal of Machine Learning Research
Fast Exact Matrix Completion: A Unified Optimization Framework for Matrix Completion
By: Dimitris Bertsimas and Michael Lingzhi Li
Abstract
We formulate the problem of matrix completion with and without side information as a non-convex optimization problem. We design fastImpute based on non-convex gradient descent and show it converges to a global minimum that is guaranteed to recover closely the underlying matrix while it scales to matrices of sizes beyond 105 × 105. 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 15 times faster than current state-of-the-art matrix completion methods in both the case with side information and without.
Keywords
Citation
Bertsimas, Dimitris, and Michael Lingzhi Li. "Fast Exact Matrix Completion: A Unified Optimization Framework for Matrix Completion." Journal of Machine Learning Research 21, no. 1 (2020).