Fast Exact Matrix Completion: A Unified Optimization Framework for Matrix Completion
This provides a faster and more accurate solution for matrix completion tasks, which is incremental but offers strong practical improvements for applications like recommendation systems or data imputation.
The paper tackles matrix completion with and without side information by proposing fastImpute, a non-convex optimization method that recovers matrices accurately and scales to sizes over 10^5 × 10^5, achieving over 75% lower MAPE and 15 times faster performance than state-of-the-art methods when many entries are missing.
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 $10^5 \times 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 $15$ times faster than current state-of-the-art matrix completion methods in both the case with side information and without.