# Categorical Matrix Completion

arXiv: https://arxiv.org/abs/1507.00421 · HTML: https://mlsanity.com/paper/1507.00421/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2015.

## Built on by (most cited first, 6 of 6)

- [Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recovery](https://mlsanity.com/paper/2212.14562/) (2022)
- [Quantized Radio Map Estimation Using Tensor and Deep Generative Models](https://mlsanity.com/paper/2303.01770/) (2023)
- [Matrix Completion from One-Bit Dither Samples](https://mlsanity.com/paper/2310.03224/) (2023)
- [Downlink MIMO Channel Estimation from Bits: Recoverability and Algorithm](https://mlsanity.com/paper/2411.16043/) (2024)
- [Latent Structural Categorical Matrix Completion with Application to Quasispecies Analysis](https://mlsanity.com/paper/2606.08188/) (2026)
- [Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure](https://mlsanity.com/paper/2608.21607/) (2026)

## Abstract (arXiv)

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 O(K3/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.