Recommendation systems are commonly used in e-commerce to suggest relevant content to users. Popular examples include Amazon, iTunes Genius, Google News and typically they operate on a corpus of millions of users/items. Such recommendation systems often rely on collaborative filters - algorithms that use implicit or explicit user-item ratings to make recommendations. In this talk I will:
a) discuss the current state-of-the-art in collaborative filtering
b) show connections with the problem of channel coding arising in communications and exploit this viewpoint to derive performance limits for collaborative filters
c) introduce a simple scalable algorithm based on the principle of popularity amongst friends (PAF)
d) show that PAF yields competitive performance on real life datasets such Movielens and Netflix movie ratings
e) show that PAF is near-optimal in a certain regime.