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.
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