Completing a data matrix X has become an ubiquitous problem in modern data science, with motivations in recommender systems, computer vision, and networks inference, to name a few. One typical assumption is that X is low-rank. A more general model assumes that each column of X corresponds to one of several low-rank matrices. This paper generalizes these models to what we call mixture matrix completion (MMC): the case where each entry of X corresponds to one of several low-rank matrices. MMC is a more accurate model for recommender systems, and brings more flexibility to other completion and clustering problems.

This paper presents mixture matrix completion (MMC) as a novel machine learning tool for learning from low-rank and incomplete data. MMC is a problem that is similar to the problem of subspace clustering with missing data, but is more difficult. Specifically, in MMC the data is assumed to lie in a union of (unknown) low-dimensional subspaces, but the data is not fully observed: only a few entries of each data point are observed, and (unlike subspace clustering with missing data) there is no information as to which entries correspond to the same point. Therefore, one would need to estimate the assignment of entries to data points, the assignment of data points to subspaces, the missing entries, and the subspaces altogether. The major contribution of this paper is the introduction of the MMC problem, a theoretical analysis for when the problem of MMC is well-defined, and an alternating estimation algorithm for solving the MMC problem.

Completing a data matrix X has become an ubiquitous problem in modern data science, with motivations in recommender systems, computer vision, and networks inference, to name a few. One typical assumption is that X is low-rank. A more general model assumes that each column of X corresponds to one of several low-rank matrices. This paper generalizes these models to what we call mixture matrix completion (MMC): the case where each entry of X corresponds to one of several low-rank matrices. MMC is a more accurate model for recommender systems, and brings more flexibility to other completion and clustering problems.