A Channel Coding Perspective of Collaborative Filtering

Details A Channel Coding Perspective of Collaborative Filtering A Channel Coding Perspective of Collaborative Filtering

2009-08-18

arxiv.org/abs/0908.2494v1

Computer Science

Information Theory

32 pages, 1 figure, Submitted to IEEE Transactions on Information Theory

Scientific paper

We consider the problem of collaborative filtering from a channel coding perspective. We model the underlying rating matrix as a finite alphabet matrix with block constant structure. The observations are obtained from this underlying matrix through a discrete memoryless channel with a noisy part representing noisy user behavior and an erasure part representing missing data. Moreover, the clusters over which the underlying matrix is constant are {\it unknown}. We establish a sharp threshold result for this model: if the largest cluster size is smaller than $C_1 \log(mn)$ (where the rating matrix is of size $m \times n$), then the underlying matrix cannot be recovered with any estimator, but if the smallest cluster size is larger than $C_2 \log(mn)$, then we show a polynomial time estimator with diminishing probability of error. In the case of uniform cluster size, not only the order of the threshold, but also the constant is identified.

Affiliated with

Also associated with

No associations

Rating

A Channel Coding Perspective of Collaborative Filtering 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 Collaborative Filtering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Channel Coding Perspective of Collaborative Filtering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-8233