Mixture Matrix Completion

Daniel L. Pimentel-Alarcón

This paper introduces a significant generalization of matrix completion theory. While traditional methods assume a single underlying structure for an entire dataset, this work explores what happens when every single data point could belong to one of several different "realities."

TL;DR

The paper introduces Mixture Matrix Completion (MMC), a model where each individual entry in a missing data matrix can belong to one of several different low-rank structures. The authors prove that recovering these mixtures is theoretically possible with nearly the same sample complexity as simpler models and provide a practical alternating algorithm to solve it.

What Problem Does This Paper Address?

Matrix completion is the science of "filling in the blanks" in a data table (like predicting movie ratings on Netflix). Historically, researchers used two models:

  1. Low-Rank Matrix Completion (LRMC): Assumes the entire matrix follows one simple pattern.
  2. High-Rank Matrix Completion (HRMC): Assumes each column (e.g., a user) follows one of several patterns.
Comparison of LRMC, HRMC, and MMC models, along with the goal of separating a mixed observation matrix into its constituent low-rank matrices.

However, real-world data is messier. Consider a shared Netflix account: one column contains ratings from a husband, a wife, and a child. The entries in that single column belong to three different "low-rank" preference profiles. This paper addresses this entry-wise mixture, which is a much harder problem because we don't know which entry belongs to which pattern.

Methods

The authors tackle MMC through both theoretical proofs and a new algorithm:

  • Identifiability & Complexity: They provide deterministic conditions under which a mixture is "identifiable" (recoverable). Crucially, they derive the sample complexity, showing how many observed entries are needed to guarantee success.
  • AMMC Algorithm: They propose Alternating Mixture Matrix Completion. Since we don't know which entries belong to which low-rank subspace, the algorithm treats this as a clustering problem.
  • The Erasure Strategy: To find which entries belong to which subspace, the algorithm uses a clever "erasure" technique. It starts with all observed entries in a column and iteratively removes (erases) the ones that deviate most from a candidate subspace until it finds a subset that fits perfectly. It then alternates between updating the subspaces and re-clustering the entries.

Datasets

The authors evaluated their approach on three types of data:

  • Synthetic Data: Randomly generated low-rank matrices used to verify theoretical sample complexity and sensitivity to initialization.
  • Yale B Face Dataset: Used for "Face Clustering and Inpainting." They mixed pixels from different people's faces into single images to see if the algorithm could untangle them and fill in missing pixels.
  • Wallflower and I2R Datasets: Standard computer vision benchmarks for background segmentation in video (separating moving foreground objects from a static background).

Key Insights and Ideas

  • The "Information-Theoretic Free Lunch": One of the most surprising findings is that the sample complexity for MMC is $O(K \max\{r, \log d\})$. This is essentially the same as the complexity for HRMC. Intuitively, this means that while mixing makes the problem computationally harder to solve, it doesn't significantly increase the amount of data required to make recovery theoretically possible.
  • Entry-wise Flexibility: By moving from column-wise to entry-wise mixtures, the model becomes far more robust for applications like metagenomics (where a single DNA sample contains a mixture of different bacteria) or network inference (where data packets might take different routes).
  • Deterministic Conditions: Unlike many papers that rely on "uniform sampling" assumptions, this work provides deterministic conditions, making it more applicable to real-world scenarios where data isn't missing at random.

Key Results

  • Performance Parity: In synthetic tests, the AMMC algorithm performed comparably to state-of-the-art algorithms (like LMaFit and GSSC) designed for much simpler problems, even though MMC is significantly more complex.
  • Face Reconstruction: On the Yale B dataset, the algorithm achieved a pixel classification error of only 2.98% and a reconstruction error of 4.1%, effectively "unmixing" two faces combined into one.
  • Superior Segmentation: In video background segmentation, AMMC achieved 87.67% accuracy in a challenging case where the standard "Robust PCA" method only managed 74.88%. This is because MMC can model structured foreground objects as their own low-rank matrices rather than just "noise."

Limitations and Future Work

  • Computational Speed: The authors candidly note that AMMC is "orders of magnitude slower" than simpler methods like Robust PCA. The iterative erasure and alternating steps are computationally expensive.
  • Initialization Sensitivity: Like many non-convex optimization problems, the algorithm's success depends heavily on having a decent starting guess (initialization). If the starting point is too far from the truth, the algorithm can get stuck in local minima.
  • The Theoretical Gap: While the theory says recovery is possible with a sampling rate of $p \ge 0.5$, the practical algorithm currently requires $p \approx 0.6$ to work reliably. Closing this gap is a primary goal for future research.

Summary updated

Abstract

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. We make four fundamental contributions about this new model. First, we show that MMC is theoretically possible (well-posed). Second, we give its precise information-theoretic identifiability conditions. Third, we derive the sample complexity of MMC. Finally, we give a practical algorithm for MMC with performance comparable to the state-of-the-art for simpler related problems, both on synthetic and real data.
BibTeX
@inproceedings{pimentelalarcon2018mixture,
  author = {Daniel L. Pimentel-Alarcón},
  title = {{Mixture Matrix Completion}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=rk43lKb_bB},
}
Figure