A Channel Coding Perspective of Recommendation Systems

Details A Channel Coding Perspective of Recommendation Systems A Channel Coding Perspective of Recommendation Systems

2009-01-13

arxiv.org/abs/0901.1753v1

Computer Science

Information Theory

5 pages, submitted to ISIT 2009

Scientific paper

Motivated by recommendation systems, we consider the problem of estimating block constant binary matrices (of size $m \times 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 \tends \infty$. 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$.

Affiliated with

Also associated with

No associations

Rating

A Channel Coding Perspective of Recommendation Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Channel Coding Perspective of Recommendation Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Channel Coding Perspective of Recommendation Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-71847