标题： 矩阵补全的类别问题 显示英文标题

标题： Categorical Matrix Completion

摘要： 我们研究了从部分观测值中完成一个具有分类值条目的矩阵的问题。 这是通过扩展一比特矩阵补全的公式和理论来实现的。 我们通过在$X$的核范数约束下最大化似然比，恢复了一个低秩矩阵$X$，并且观测值是通过多个链接函数从$X$的条目映射而来的。 我们建立了恢复误差的理论上下界，它们相差一个常数因子$\mathcal{O}(K^{3/2})$，其中 $K$是固定的类别数量。 在我们的案例中，上界隐式地依赖于涉及链接函数平滑性的项的最大化，从而间接依赖于类别数量。 与一比特矩阵补全相比，我们的分类矩阵补全界的最优性达到了类别数量平方根数量级的一个因子，这与当类别数量增加时问题变得更难的直觉是一致的。 通过在 MovieLens 数据集上将我们的方法与传统矩阵补全方法的表现进行比较，我们展示了我们方法的优势。 显示英文摘要

摘要： 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.