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, with high probability, the proposed estimator exactly recovers the true matrices whenever sample complexity requirements are met. The sample complexity requirements 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 and real life experiments.
Introduction
Standard matrix completion—predicting missing entries in a single table—is a cornerstone of modern recommendation systems. However, real-world data is often distributed across a "collection" of matrices. For instance, an e-commerce platform might manage User-Item purchase data, User-Category interests, and Item-Feature matrices simultaneously.
These matrices are deeply correlated because they share entities (e.g., the same users or items). The challenge addressed in this work is how to mathematically leverage these correlations to fill in missing values more accurately, especially when data is extremely sparse. While previous collective models existed, this paper provides the first formal understanding of the "sample complexity"—the minimum data required to guarantee recovery—and demonstrates that tractable, convex algorithms can find the optimal solution.
Methods: Joint Low Rank Structure and Algebraic Framework
The authors introduce a framework based on a Joint Low Rank Structure. They assume every entity type (e.g., "Users") has a single, shared latent factor representation. Any specific matrix in the collection is modeled as the product of the latent factors of the two entity types it connects.
To formalize this, they develop a rigorous algebra for representing multi-matrix structures. As illustrated in the framework below, an entity-relationship graph is translated into a collection of matrices, which are then embedded into a large, sparse symmetric block matrix $\mathcal{B}(\mathcal{X})$.
Key technical contributions include:
- Collective-Matrix Atomic Norm: A new convex surrogate for the "rank" of a collection of matrices, turning an NP-hard problem into a tractable convex optimization.
- Scalable Algorithm: The authors adapt Hazan’s Algorithm, a greedy approach that provides approximate solutions much faster than standard solvers by avoiding expensive full-scale Singular Value Decompositions (SVDs).
Theoretical Guarantees and Sample Complexity
Theorem 1 in the paper establishes that the proposed convex estimator exactly recovers the true matrices with high probability, provided the sample complexity meets the requirement $O(n_k R \log N)$, where $n_k$ is the number of entities and $R$ is the rank. This requirement is theoretically optimal because it scales with the degrees of freedom needed to fix the parameters of the latent factors. A critical finding is that this theory currently relies on the entity-relationship graph being bipartite (containing no odd-length cycles) to ensure the atomic norm behaves consistently.
Key Results
Simulated Verification
Experiments on simulated data confirm the theoretical phase transitions of recovery. As shown in the figure below, as soon as the number of samples crosses the threshold predicted by the theory, the Root Mean Square Error (RMSE) drops sharply to near zero across various problem sizes ($n$).
Real-World Cold-Start Performance
The model was evaluated on a commercial news recommendation dataset to test its ability to predict preferences for users with only a single recorded click (the "News-Cold-Start" benchmark). The Collective Matrix Factorization (CMF-Hazans) achieved a Mean Absolute Error (MAE) of 0.2741, significantly outperforming Standard Matrix Factorization (SMF) at 0.2905. This confirms that "borrowing" information from auxiliary matrices (like User-Category) helps predict sparse interactions for new users.
Conclusion
This paper provides the first rigorous theoretical foundation for Collective Matrix Completion. By leveraging shared latent structures, the proposed estimator achieves optimal sample complexity. Future work will focus on extending these guarantees to general graph topologies with cycles and improving robustness to noisy, real-world observations.
Summary updated