{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T14:56:08Z","timestamp":1743000968515,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030676575"},{"type":"electronic","value":"9783030676582"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-67658-2_43","type":"book-chapter","created":{"date-parts":[[2021,2,24]],"date-time":"2021-02-24T12:03:33Z","timestamp":1614168213000},"page":"746-761","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["NoisyCUR: An Algorithm for Two-Cost Budgeted Matrix Completion"],"prefix":"10.1007","author":[{"given":"Dong","family":"Hu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Gittens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Malik","family":"Magdon-Ismail","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,25]]},"reference":[{"key":"43_CR1","unstructured":"Avron, H., Clarkson, K.L., Woodruff, D.P.: Sharper bounds for regularized data fitting. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2017), vol. 81, pp. 27:1\u201327:22. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"102","key":"43_CR2","first-page":"1","volume":"20","author":"MF Balcan","year":"2019","unstructured":"Balcan, M.F., Liang, Z., Song, Y., Woodruff, D.P., Zhang, H.: Non-convex matrix completion and related problems via strong duality. J. Mach. Learn. Res. 20(102), 1\u201356 (2019)","journal-title":"J. Mach. Learn. Res."},{"key":"43_CR3","unstructured":"Balcan, M.F., Zhang, H.: Noise-tolerant life-long matrix completion via adaptive sampling. In: Advances in Neural Information Processing Systems 29, pp. 2955\u20132963. Curran Associates, Inc. (2016)"},{"issue":"5","key":"43_CR4","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1109\/TIT.2010.2044061","volume":"56","author":"EJ Cand\u00e9s","year":"2010","unstructured":"Cand\u00e9s, E.J., Tao, T.: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inf. Theory 56(5), 2053\u20132080 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"6","key":"43_CR5","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1109\/JPROC.2009.2035722","volume":"98","author":"EJ Candes","year":"2010","unstructured":"Candes, E.J., Plan, Y.: Matrix completion with noise. Proc. IEEE 98(6), 925\u2013936 (2010)","journal-title":"Proc. IEEE"},{"key":"43_CR6","unstructured":"Chen, Y., Bhojanapalli, S., Sanghavi, S., Ward, R.: Coherent matrix completion. In: Proceedings of the 31st International Conference on Machine Learning (ICML), pp. 674\u2013682 (2014)"},{"key":"43_CR7","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chi, Y., Fan, J., Ma, C., Yan, Y.: Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization. arXiv preprint, arXiv:1902.07698 (2019)","DOI":"10.1137\/19M1290000"},{"key":"43_CR8","doi-asserted-by":"crossref","unstructured":"Cho, K., Reyhani, N.: An iterative algorithm for singular value decomposition on noisy incomplete matrices. In: The 2012 International Joint Conference on Neural Networks (IJCNN), pp. 1\u20136 (2012)","DOI":"10.1109\/IJCNN.2012.6252789"},{"issue":"2","key":"43_CR9","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1023\/A:1011419012209","volume":"6","author":"K Goldberg","year":"2001","unstructured":"Goldberg, K., Roeder, T., Gupta, D., Perkins, C.: An iterative algorithm for singular value decomposition on noisy incomplete matrices. Inf. Retrieval 6(2), 133\u2013151 (2001)","journal-title":"Inf. Retrieval"},{"key":"43_CR10","doi-asserted-by":"crossref","unstructured":"Harper, F.M., Konstan, J.A.: The movielens datasets: history and context. ACM Trans. Interact. Intell. Syst. (TiiS) 5, 1\u201319 (2015)","DOI":"10.1145\/2827872"},{"issue":"1","key":"43_CR11","first-page":"3367","volume":"16","author":"T Hastie","year":"2015","unstructured":"Hastie, T., Mazumder, R., Lee, J.D., Zadeh, R.: Matrix completion and low-rank SVD via fast alternating least squares. J. Mach. Learn. Res. 16(1), 3367\u20133402 (2015)","journal-title":"J. Mach. Learn. Res."},{"key":"43_CR12","doi-asserted-by":"crossref","unstructured":"Keshavan, R., Montanari, A., Oh, S.: Matrix completion from noisy entries. In: Advances in Neural Information Processing Systems, pp. 952\u2013960 (2009)","DOI":"10.1109\/ISIT.2009.5205567"},{"key":"43_CR13","unstructured":"Krishnamurthy, A., Singh, A.: Low-rank matrix and tensor completion via adaptive sampling. In: Advances in Neural Information Processing Systems 26, pp. 836\u2013844. Curran Associates, Inc. (2013)"},{"key":"43_CR14","unstructured":"Krishnamurthy, A., Singh, A.R.: On the power of adaptivity in matrix completion and approximation. arXiv preprint arXiv:1407.3619 (2014)"},{"issue":"1","key":"43_CR15","first-page":"861","volume":"16","author":"P Ma","year":"2015","unstructured":"Ma, P., Mahoney, M.W., Yu, B.: A statistical perspective on algorithmic leveraging. J. Mach. Learn. Res. 16(1), 861\u2013911 (2015)","journal-title":"J. Mach. Learn. Res."},{"key":"43_CR16","unstructured":"Recht, B.: A simpler approach to matrix completion. J. Mach. Learn. Res. 12(12), 3413\u20133430 (2011)"},{"key":"43_CR17","doi-asserted-by":"crossref","unstructured":"Wainwright, M.J.: High-Dimensional Statistics: A Non-asymptotic Viewpoint. Cambridge University Press, Cambridge (2019)","DOI":"10.1017\/9781108627771"},{"issue":"218","key":"43_CR18","first-page":"1","volume":"18","author":"S Wang","year":"2018","unstructured":"Wang, S., Gittens, A., Mahoney, M.W.: Sketched ridge regression: optimization perspective, statistical perspective, and model averaging. J. Mach. Learn. Res. 18(218), 1\u201350 (2018)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"43_CR19","first-page":"7329","volume":"17","author":"S Wang","year":"2016","unstructured":"Wang, S., Zhang, Z., Zhang, T.: Towards more efficient SPSD matrix approximation and CUR matrix decomposition. J. Mach. Learn. Res. 17(1), 7329\u20137377 (2016)","journal-title":"J. Mach. Learn. Res."},{"key":"43_CR20","unstructured":"Woodruff, D.P.: Sketching as a tool for numerical linear algebra. Found. Trends\u00ae Theor. Comput. Sci. 10(1\u20132), 1\u2013157 (2014)"},{"key":"43_CR21","unstructured":"Xu, M., Jin, R., Zhou, Z.H.: CUR algorithm for partially observed matrices. In: Proceedings of the 32nd International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 37, pp. 1412\u20131421. PMLR (2015)"}],"container-title":["Lecture Notes in Computer Science","Machine Learning and Knowledge Discovery in Databases"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-67658-2_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T23:09:33Z","timestamp":1740352173000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-67658-2_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030676575","9783030676582"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-67658-2_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"25 February 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ECML PKDD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Joint European Conference on Machine Learning and Knowledge Discovery in Databases","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ghent","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Belgium","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 September 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ecml2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ecmlpkdd2020.net\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"945","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"195","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4,5","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4,4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference took place virtually due to the COVID-19 pandemic","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}