{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T14:51:11Z","timestamp":1776955871126,"version":"3.51.4"},"reference-count":29,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:p> Matrix estimation or completion has served as a canonical mathematical model for recommendation systems. More recently, it has emerged as a fundamental building block for data analysis as a first step to denoise the observations and predict missing values. Since the dawn of e-commerce, similarity-based collaborative filtering has been used as a heuristic for matrix etimation. At its core, it encodes typical human behavior: you ask your friends to recommend what you may like or dislike. Algorithmically, friends are similar \u201crows\u201d or \u201ccolumns\u201d of the underlying matrix. The traditional heuristic for computing similarities between rows has costly requirements on the density of observed entries. In \u201cIterative Collaborative Filtering for Sparse Matrix Estimation\u201d by Christian Borgs, Jennifer T. Chayes, Devavrat Shah, and Christina Lee Yu, the authors introduce an algorithm that computes similarities in sparse datasets by comparing expanded local neighborhoods in the associated data graph: in effect, you ask friends of your friends to recommend what you may like or dislike. This work provides bounds on the max entry-wise error of their estimate for low rank and approximately low rank matrices, which is stronger than the aggregate mean squared error bounds found in classical works. The algorithm is also interpretable, scalable, and amenable to distributed implementation. <\/jats:p>","DOI":"10.1287\/opre.2021.2193","type":"journal-article","created":{"date-parts":[[2021,12,6]],"date-time":"2021-12-06T20:38:47Z","timestamp":1638823127000},"page":"3143-3175","source":"Crossref","is-referenced-by-count":5,"title":["Iterative Collaborative Filtering for Sparse Matrix Estimation"],"prefix":"10.1287","volume":"70","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0001-5653-0498","authenticated-orcid":false,"given":"Christian","family":"Borgs","sequence":"first","affiliation":[{"name":"Electrical Engineering and Computer Science, University of California Berkeley, Berkeley, California 94704;"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jennifer T.","family":"Chayes","sequence":"additional","affiliation":[{"name":"Electrical Engineering and Computer Science, University of California Berkeley, Berkeley, California 94704;"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0003-0737-3259","authenticated-orcid":false,"given":"Devavrat","family":"Shah","sequence":"additional","affiliation":[{"name":"Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142;"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-2165-5220","authenticated-orcid":false,"given":"Christina Lee","family":"Yu","sequence":"additional","affiliation":[{"name":"Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B2","author":"Abbe E","year":"2015","journal-title":"Adv. Neural Inform. Processing Systems 28:676\u2013684."},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1854"},{"key":"B6","first-page":"1369","volume":"28","author":"Borgs C","year":"2015","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B11","first-page":"4715","volume-title":"Advances in Neural Information Processing Systems","author":"Borgs C","year":"2017"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.07.008"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1145\/2184319.2184343"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2009.2035722"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2044061"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1272"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1214\/18-AOS1745"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iau006"},{"issue":"28","key":"B22","first-page":"33","author":"Diaconis P","year":"2008","journal-title":"Rendiconti Matematica"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2992769"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOS1354"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386302"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.208702"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2046205"},{"key":"B29","first-page":"2057","volume":"11","author":"Keshavan RH","year":"2010","journal-title":"J. Machine Learning Res."},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1454"},{"key":"B32","volume-title":"Advances in Collaborative Filtering. Recommender Systems Handbook","author":"Koren Y","year":"2011"},{"key":"B34","first-page":"2155","volume":"29","author":"Lee CE","year":"2016","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2950299"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2003.1167344"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/060"},{"key":"B41","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1214\/10-AOS850","volume":"39","author":"Negahban S","year":"2011","journal-title":"Ann. Statist."},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-7637-6_2"},{"key":"B43","first-page":"3413","volume":"12","author":"Recht B","year":"2011","journal-title":"J. Machine Learn. Res."},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1137\/18M1183480"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1137\/17M1122025"}],"container-title":["Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/pubsonline.informs.org\/doi\/pdf\/10.1287\/opre.2021.2193","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T18:01:58Z","timestamp":1680458518000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/pubsonline.informs.org\/doi\/10.1287\/opre.2021.2193"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["10.1287\/opre.2021.2193"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1287\/opre.2021.2193","relation":{},"ISSN":["0030-364X","1526-5463"],"issn-type":[{"value":"0030-364X","type":"print"},{"value":"1526-5463","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11]]}}}