Skip to yearly menu bar Skip to main content

Workshop: Nearest Neighbors for Modern Applications with Massive Data: An Age-old Solution with New Challenges

Iterative Collaborative Filtering for Sparse Matrix Estimation

Christina Lee


The sparse matrix estimation problem consists of estimating the distribution of an n-by-n matrix Y , from a sparsely observed single instance of this matrix where the entries of Y are independent random variables. This captures a wide array of problems; special instances include matrix completion in the context of recommendation systems, graphon estimation, and community detection in (mixed membership) stochastic block models. Inspired by classical collaborative filtering for recommendation systems, we propose a novel iterative, collaborative filtering style algorithm for matrix estimation in this generic setting. Under model assumptions of uniform sampling, bounded entries, and finite spectrum, we provide bounds on the the mean squared error (MSE) of our estimator and show improved sample complexity.

Live content is unavailable. Log in and register to view live content