Abstract
Matrix completion is a cornerstone of modern recommendation systems, typically operating under the assumption that missing entries are real-valued. However, many real-world applications involve categorical data, such as discrete movie ratings or clinical diagnoses. This paper extends matrix completion theory to the categorical domain. We propose a nuclear-norm regularized maximum likelihood estimator (MLE) and demonstrate that its recovery error is theoretically optimal up to a factor related to the number of categories $K$. Empirical results on the MovieLens dataset show that our categorical approach outperforms traditional real-valued methods, particularly in accurately predicting high-value ratings.
Introduction
The "Netflix Prize" popularized matrix completion as a method for predicting missing entries in a large, sparse matrix by assuming a low-rank structure. While standard techniques treat these entries as continuous real numbers, most practical data is discrete. Movie ratings (1-5 stars) or medical outcomes (positive, negative, uncertain) are categorical.
Treating these categories as real numbers and applying standard completion followed by rounding is a common heuristic, but it lacks a rigorous probabilistic foundation. This paper addresses the gap by developing a framework for completing matrices where entries belong to an arbitrary number of categories $K$, moving beyond the well-studied "one-bit" (binary) case.
Methodology
The core of the proposed approach is the assumption of an underlying, unobserved low-rank matrix $X \in \mathbb{R}^{m \times n}$. The observed categorical entries $Y_{ij} \in \{1, \dots, K\}$ are generated by passing the latent entries of $X$ through a set of link functions $f_k$. These functions represent the probability that an entry belongs to category $k$, such that $\sum_{k=1}^K f_k(x) = 1$.
As shown in Figure 1, the link functions (often modeled as multinomial logistic functions) provide a smooth transition between categories. The recovery process involves:
- Nuclear Norm Regularization: To enforce the low-rank constraint, we minimize the sum of the singular values of the candidate matrix.
- Maximum Likelihood Estimation (MLE): We maximize the log-likelihood of the observed data $Y$ given the latent matrix $X$, subject to constraints on the nuclear norm and the maximum absolute value of the entries (the infinity norm).
A key theoretical insight is that recovery performance depends heavily on the "smoothness" of these link functions. Sharp boundaries or lack of overlap between functions can make it difficult to uniquely identify the correct category from noisy observations.
Empirical Evaluation
We evaluated the categorical MLE approach using the MovieLens dataset, consisting of a 942-by-1683 matrix of movie ratings (integers 1 to 5). We compared our method against a conventional real-valued matrix completion model that predicts continuous values and rounds them to the nearest integer.
The results in Figure 2 demonstrate that the categorical method achieves a lower overall error (0.708) compared to the conventional method (0.783). Notably, the categorical model shows superior performance in the high-rating categories (4 and 5). This is likely because the MovieLens dataset contains more training data for these ratings, allowing the multinomial logistic model to calibrate more effectively for these specific outcomes. Conversely, the conventional method performed better on the lowest ratings, suggesting that simple rounding may be more effective when data is sparse or the link functions are less well-defined.
Conclusion
This work provides a mathematically rigorous framework for categorical matrix completion. By respecting the discrete, probabilistic nature of categorical labels rather than treating them as continuous values, the proposed MLE approach achieves better predictive accuracy and theoretical optimality. Future research may explore extending this framework to low-rank tensor structures for multi-dimensional data or developing more computationally efficient optimization algorithms to scale the method for industrial-sized datasets.
Summary updated