Fast exact matrix completion: A unified optimization framework for matrix completion
© 2020 Dimitris Bertsimas and Michael Lingzhi Li. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v21/19-471.html. We formulate the problem of matrix completion with and without side information as a non-convex opt...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/133756 |
| _version_ | 1826200752348987392 |
|---|---|
| author | Bertsimas, D Li, ML |
| author2 | Massachusetts Institute of Technology. Department of Economics |
| author_facet | Massachusetts Institute of Technology. Department of Economics Bertsimas, D Li, ML |
| author_sort | Bertsimas, D |
| collection | MIT |
| description | © 2020 Dimitris Bertsimas and Michael Lingzhi Li. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v21/19-471.html. 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. |
| first_indexed | 2024-09-23T11:41:12Z |
| format | Article |
| id | mit-1721.1/133756 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:41:12Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1337562023-09-27T20:38:10Z Fast exact matrix completion: A unified optimization framework for matrix completion Bertsimas, D Li, ML Massachusetts Institute of Technology. Department of Economics © 2020 Dimitris Bertsimas and Michael Lingzhi Li. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v21/19-471.html. 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. 2021-10-27T19:56:29Z 2021-10-27T19:56:29Z 2020-11-01 2021-02-05T19:18:15Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/133756 en https://jmlr.org/papers/v21/19-471.html Journal of Machine Learning Research Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf Journal of Machine Learning Research |
| spellingShingle | Bertsimas, D Li, ML Fast exact matrix completion: A unified optimization framework for matrix completion |
| title | Fast exact matrix completion: A unified optimization framework for matrix completion |
| title_full | Fast exact matrix completion: A unified optimization framework for matrix completion |
| title_fullStr | Fast exact matrix completion: A unified optimization framework for matrix completion |
| title_full_unstemmed | Fast exact matrix completion: A unified optimization framework for matrix completion |
| title_short | Fast exact matrix completion: A unified optimization framework for matrix completion |
| title_sort | fast exact matrix completion a unified optimization framework for matrix completion |
| url | https://hdl.handle.net/1721.1/133756 |
| work_keys_str_mv | AT bertsimasd fastexactmatrixcompletionaunifiedoptimizationframeworkformatrixcompletion AT liml fastexactmatrixcompletionaunifiedoptimizationframeworkformatrixcompletion |