Consistent Collective Matrix Completion under Joint Low Rank Structure

Suriya Gunasekar, Makoto Yamada, Dawei Yin, Yi Chang

Abstract

Collective matrix completion (CMC) involves jointly recovering a collection of matrices with shared structure from partial observations. This paper introduces a rigorous framework for CMC, imposing a joint low-rank structure where latent spaces are shared across the collection. We provide the first non-trivial theoretical guarantees for consistency, showing that a tractable convex estimator can achieve exact recovery with optimal sample complexity.

Introduction: Beyond Isolated Tables

Standard matrix completion, popularized by the Netflix Prize, focuses on predicting missing entries in a single table, such as users versus movies. However, modern data ecosystems are rarely isolated. An e-commerce platform might manage multiple related matrices: user-product ratings, user-news clicks, and user-demographic features.

While these matrices are distinct, they are intrinsically linked by shared entities (e.g., the same users appearing in multiple datasets). Collective Matrix Completion (CMC) exploits these cross-dataset correlations to improve prediction accuracy, particularly in "cold start" scenarios where data for specific entities is extremely sparse. Despite its practical success, CMC previously lacked a rigorous theoretical foundation regarding consistency and sample complexity.

Methods: A Formal Algebra for Collective Matrices

The authors establish a formal mathematical framework to represent and manipulate these multi-view datasets.

Collective-Matrix Algebra

The core of the approach is representing a collection of matrices as a single structure. They define a "Collective-Matrix Atomic Norm," which serves as a convex surrogate for the rank of the entire collection. This allows the problem to be framed as a convex optimization task.

Figure 1: (a) Entity-relationship graph G. (b) Collection of matrices X. (c) Structured representation X. (d) Resulting block matrix B(X).

The Estimator and Algorithm

The proposed estimator uses Atomic Norm Minimization to find the simplest (lowest rank) set of matrices that fits the observed data. To handle large-scale data, the authors adapted Hazan’s approximate Semidefinite Programming (SDP) solver. This "Hazans-CMC" algorithm offers better scalability than traditional Singular Value Thresholding (SVT) methods, which often become computationally prohibitive as the number of entities grows.

Theoretical Guarantees: Optimal Sample Complexity

A key contribution of this work is the derivation of sample complexity requirements. The authors prove that for an entity type $k$, the number of samples needed scales as $O(n_k R \log N)$, where $n_k$ is the number of entities and $R$ is the rank. This bound is optimal up to logarithmic factors.

A significant technical insight is the Bipartite Graph Constraint. The authors found that for their mathematical "gauge" to behave as a proper norm, the entity-relationship graph (as shown in Figure 1a) must be bipartite—meaning it contains no odd-length cycles. This ensures that the shared latent factors can be consistently identified across the network.

Empirical Validation

The theoretical claims were verified using synthetic datasets with varying numbers of entities ($n=100$ to $500$) and sparsity levels. The experiments demonstrated a clear "phase transition" in recovery: when the error (RMSE) was plotted against the theoretical sample complexity, the curves for different matrix sizes aligned perfectly. This confirms that the $O(n_k R \log N)$ formula accurately predicts the threshold for successful recovery.

Conclusion and Future Directions

This paper provides the first consistency guarantees for collective matrix completion, bridging the gap between empirical success and theoretical understanding. While the current proof relies on a bipartite graph assumption and focuses on noise-free data, it sets the stage for future work. Potential extensions include relaxing the bipartite constraint, improving robustness to high-noise regimes, and adapting the model for directed or time-evolving relationships in complex social networks.

Summary updated

Abstract

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.
BibTeX
@inproceedings{gunasekar2015consistent,
  author = {Suriya Gunasekar and Makoto Yamada and Dawei Yin and Yi Chang},
  title = {{Consistent Collective Matrix Completion under Joint Low Rank Structure}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
  url = {https://openreview.net/forum?id=TkAxMu0X6cR},
}
Figure