Mixture Matrix Completion

Daniel L. Pimentel-Alarcón

Abstract

Traditional matrix completion techniques often assume that data resides within a single low-rank subspace or that entire columns belong to distinct categories. However, real-world data frequently exhibits entry-wise mixtures, such as shared user accounts in recommender systems. This paper introduces Mixture Matrix Completion (MMC), a framework where individual entries can belong to different low-rank structures. We establish theoretical sample complexity bounds and propose the Alternating Mixture Matrix Completion (AMMC) algorithm. Experimental results on synthetic data, facial imagery, and video segmentation demonstrate that MMC significantly outperforms existing models in handling complex, overlapping data structures.

Introduction

In data science, the challenge of "filling in the blanks"—reconstructing a complete matrix from sparse, noisy observations—is foundational to applications ranging from Netflix recommendations to computer vision. Traditional Low-Rank Matrix Completion (LRMC) assumes all data points live in a single, low-dimensional subspace. While High-Rank Matrix Completion (HRMC) improved upon this by allowing each column to belong to one of several subspaces, it fails when a single column is itself a mixture of different categories.

Consider a shared streaming account: a single column of ratings may contain a parent’s preference for documentaries and a child’s interest in cartoons. MMC addresses this "entry-wise" mixture, providing a more granular and realistic framework for modern data modeling.

Comparison of matrix completion paradigms: LRMC (single subspace), HRMC (column-wise subspaces), and MMC (entry-wise mixture).

Methodology

Theoretical Foundations

The paper proves that MMC is a well-posed mathematical problem. A key contribution is the derivation of sample complexity, showing that recovery is possible with $O(K \max\{r, \log d\})$ observations per column. Remarkably, this complexity is essentially the same as that of HRMC, suggesting that the added flexibility of entry-wise mixing comes with virtually no theoretical "information-theoretic" penalty.

The AMMC Algorithm

To solve MMC in practice, we propose the Alternating Mixture Matrix Completion (AMMC) algorithm. This iterative approach consists of two primary steps:

  1. Cluster: For each column, the algorithm employs an "erasure strategy." It begins with all observed entries and iteratively prunes those that deviate most from a candidate subspace until a consistent subset is identified.
  2. Complete: Once entries are assigned to their respective sub-matrices, standard LRMC techniques (such as LMaFit) are used to fill missing values and refine subspace estimates.

Experimental Results

Face Unmixing and Inpainting

Using the Yale B Face Dataset, we tested AMMC’s ability to "unmix" faces where pixels from different individuals were blended. AMMC achieved a pixel classification error of 2.98% and a reconstruction error of 4.1%. For context, an ideal rank-10 approximation of the full, unmixed data yields an error of 1.8%, highlighting the algorithm's high fidelity.

Video Background Segmentation

On the Wallflower and I2R datasets, MMC was applied to distinguish static backgrounds from structured foreground objects. MMC achieved 87.67% accuracy, significantly outperforming state-of-the-art Robust PCA (74.88%), particularly in scenarios featuring large, coherent foreground objects that typically confuse standard models.

Discussion and Limitations

While MMC offers superior flexibility, it is computationally intensive. The AMMC algorithm is currently orders of magnitude slower than Robust PCA due to its iterative erasure and alternating steps. Additionally, like many non-convex optimization problems, the algorithm can be sensitive to initialization and may converge to local minima if data is excessively sparse. Future work will focus on closing the gap between the theoretical recovery limit (~50% sampling) and current practical performance (~60% sampling), as well as optimizing computational efficiency.

Summary updated

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