Iterative Collaborative Filtering for Sparse Matrix Estimation

Christian Borgs (), Jennifer T. Chayes (), Devavrat Shah () and Christina Lee Yu ()
Additional contact information
Christian Borgs: Electrical Engineering and Computer Science, University of California Berkeley, Berkeley, California 94704
Jennifer T. Chayes: Electrical Engineering and Computer Science, University of California Berkeley, Berkeley, California 94704
Devavrat Shah: Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Christina Lee Yu: Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853

Operations Research, 2022, vol. 70, issue 6, 3143-3175

Abstract: 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-wise max norm decays 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.

Keywords: Machine Learning and Data Science; matrix estimation; matrix completion; latent variable models; similarity based collaborative filtering; recommendation systems; entrywise bounds (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2193 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:6:p:3143-3175

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().