A Channel Coding Perspective of Collaborative Filtering

DOI10.1109/TIT.2011.2111190MaRDI QIDQ5280995zbMATH OpenOpenAlexFDO

Authors S. T. Aditya, Onkar Dabeer, Bikash Kumar Dey

Publication date 27 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0908.2494

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Source coding (94A29) Channel models (including quantum) in information and communication theory (94A40)

Abstract: 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 $mimesn$), 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.

Cited in

(1)

• An efficient method for convex constrained rank minimization problems based on DC programming

This page was built for publication: A Channel Coding Perspective of Collaborative Filtering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5280995)