2014/02/18 by Changho Suh, Suh, Changho
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1402.4225
5 pages, submitted to the International Symposium on Information Theory 2014
arxiv created 2014/02/18 · arxiv updated 2014/02/19
Matrix completion is a fundamental problem that comes up in a variety of applications like the Netflix problem, collaborative filtering, computer vision, and crowdsourcing. The goal of the problem is to recover a k-by-n unknown matrix from a subset of its noiseless (or noisy) entries. We define an information-theoretic notion of completion capacity C that quantifies the maximum number of entries that one observation of an entry can resolve. This number provides the minimum number m of entries required for reliable reconstruction: m=kn/C. Translating the problem into a distributed joint source-channel coding problem with encoder restriction, we characterize the completion capacity for a wide class of stochastic models of the unknown matrix and the observation process. Our achievability proof is inspired by that of the Slepian-Wolf theorem. For an arbitrary stochastic matrix, we derive an upper bound on the completion capacity.