# Probabilistic low-rank matrix completion on finite alphabets

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Dec 2014.

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

- [High Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantization](https://mlsanity.com/paper/2202.13157/) (2022)
- [Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recovery](https://mlsanity.com/paper/2212.14562/) (2022)
- [Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss](https://mlsanity.com/paper/2202.02063/) (2022)
- [Matrix Completion with Model-free Weighting](https://mlsanity.com/paper/2106.05850/) (2021)
- [Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure](https://mlsanity.com/paper/2608.21607/) (2026)

## Abstract (arXiv)

The task of reconstructing a matrix given a sample of observedentries is known as the matrix completion problem. It arises ina wide range of problems, including recommender systems, collaborativefiltering, dimensionality reduction, image processing, quantum physics or multi-class classificationto name a few. Most works have focused on recovering an unknown real-valued low-rankmatrix from randomly sub-sampling its entries.Here, we investigate the case where the observations take a finite number of values, corresponding for examples to ratings in recommender systems or labels in multi-class classification.We also consider a general sampling scheme (not necessarily uniform) over the matrix entries.The performance of a nuclear-norm penalized estimator is analyzed theoretically.More precisely, we derive bounds for the Kullback-Leibler divergence between the true and estimated distributions.In practice, we have also proposed an efficient algorithm based on lifted coordinate gradient descent in order to tacklepotentially high dimensional settings.