A channel coding perspective of recommendation systems

Motivated by recommendation systems, we consider the problem of estimating block constant binary matrices (of size m × n) from sparse and noisy observations. The observations are obtained from the underlying block constant matrix after unknown row and column permutations, erasures, and errors. We de...

Full description

Saved in:
Bibliographic Details
Main Authors: Aditya, S.T., Dabeer, O., Dey, B.K.
Format: Conference Proceeding
Language:English
Subjects:
Channel coding
Clustering algorithms
Computer science
Error probability
Memoryless systems
Motion pictures
Polynomials
Recommender systems
Sparse matrices
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Motivated by recommendation systems, we consider the problem of estimating block constant binary matrices (of size m × n) from sparse and noisy observations. The observations are obtained from the underlying block constant matrix after unknown row and column permutations, erasures, and errors. We derive upper and lower bounds on the achievable probability of error. For fixed erasure and error probability, we show that there exists a constant C 1 such that if the cluster sizes are less than C 1 ln(mn), then for any algorithm the probability of error approaches one as m, n ¿ ¿. On the other hand, we show that a simple polynomial time algorithm gives probability of error diminishing to zero provided the cluster sizes are greater than C 2 ln(mn) for a suitable constant C 2 .
ISSN:2157-8095
2157-8117
DOI:10.1109/ISIT.2009.5205549