  We consider the problem of completing a matrix with categorical-valued
entries from partial observations. This is achieved by extending the
formulation and theory of one-bit matrix completion. We recover a low-rank
matrix $X$ by maximizing the likelihood ratio with a constraint on the nuclear
norm of $X$, and the observations are mapped from entries of $X$ through
multiple link functions. We establish theoretical upper and lower bounds on the
recovery error, which meet up to a constant factor $\mathcal{O}(K^{3/2})$ where
$K$ is the fixed number of categories. The upper bound in our case depends on
the number of categories implicitly through a maximization of terms that
involve the smoothness of the link functions. In contrast to one-bit matrix
completion, our bounds for categorical matrix completion are optimal up to a
factor on the order of the square root of the number of categories, which is
consistent with an intuition that the problem becomes harder when the number of
categories increases. By comparing the performance of our method with the
conventional matrix completion method on the MovieLens dataset, we demonstrate
the advantage of our method.
