  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.
