| Recommendation systems, like those employed by Netflix and Amazon, suggest relevant content to potential buyers. Given the lack of good statistical models and the massive datasets, the dominant research focus has been on proposing algorithms and testing their scalability and performance on specific data sets. Recently, however, there is emerging interest in provably good techniques and this talk is about the performance limits of collaborative filtering, which makes recommendations only using the available buyer-item ratings (and not on any content). Several authors have taken a compressed sensing view of this problem, and derived bounds on the least number of samples required for matrix completion. We present a different perspective on the problem that accommodates noisy user behavior and leads to sharper results. Specifically, we introduce a new model for the rating matrix and observations, we prove sharp threshold results for the model indicating when "exact recommendations" are feasible with polynomial time complexity, and we study distortion per recommendation for a local popularity based algorithm. |