  We address the collective matrix completion problem of jointly recovering a
collection of matrices with shared structure from partial (and potentially
noisy) observations. To ensure well--posedness of the problem, we impose a
joint low rank structure, wherein each component matrix is low rank and the
latent space of the low rank factors corresponding to each entity is shared
across the entire collection. We first develop a rigorous algebra for
representing and manipulating collective--matrix structure, and identify
sufficient conditions for consistent estimation of collective matrices. We then
propose a tractable convex estimator for solving the collective matrix
completion problem, and provide the first non--trivial theoretical guarantees
for consistency of collective matrix completion. We show that under reasonable
assumptions stated in Section 3.1, with high probability, the proposed
estimator exactly recovers the true matrices whenever sample complexity
requirements dictated by Theorem 1 are met. The sample complexity requirement
derived in the paper are optimum up to logarithmic factors, and significantly
improve upon the requirements obtained by trivial extensions of standard matrix
completion. Finally, we propose a scalable approximate algorithm to solve the
proposed convex program, and corroborate our results through simulated
experiments.
