Iterative Collaborative Filtering for Sparse Matrix Estimation

• 成果类型: Article
• 署名作者: Borgs, Christian; Chayes, Jennifer T.; Shah, Devavrat; Yu, Christina Lee
• 署名单位: University of California System; University of California Berkeley; University of California System; University of California Berkeley; University of California System; University of California Berkeley; Cornell University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.2193
• 发表日期: 2022
• 页码: 3143-3175
• 关键词: matrix estimation; matrix completion; Latent Variable Models; similarity based collaborative filtering; Recommendation systems; entrywise bounds

摘要

We consider sparse matrix estimation where the goal is to estimate an n-by-n matrix from noisy observations of a small subset of its entries. We analyze the estimation error of the popularly used collaborative filtering algorithm for the sparse regime. Specifically, we propose a novel iterative variant of the algorithm, adapted to handle the setting of sparse observations. We establish that as long as the number of entries observed at random scale logarithmically larger than linear in n, the estimation error with respect to the entry-wisemax normdecays to zero as n goes to infinity, assuming the underlying matrix of interest has constant rank r. Our result is robust to model misspecification in that if the underlying matrix is approximately rank r, then the estimation error decays to the approximation error with respect to the max-norm. In the process, we establish the algorithm's ability to handle arbitrary bounded noise in the observations.