# Adaptive Multinomial Matrix Completion

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Aug 2014.

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

- [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)
- [Concentration properties of fractional posterior in 1-bit matrix completion](https://mlsanity.com/paper/2404.08969/) (2024)
- [Matrix Completion with Model-free Weighting](https://mlsanity.com/paper/2106.05850/) (2021)
- [Quantized Low-Rank Multivariate Regression with Random Dithering](https://mlsanity.com/paper/2302.11197/) (2023)
- [A Generalized Latent Factor Model Approach to Mixed-data Matrix Completion with Entrywise Consistency](https://mlsanity.com/paper/2211.09272/) (2022)
- [Misclassification excess risk bounds for 1-bit matrix completion](https://mlsanity.com/paper/2312.12945/) (2023)
- [Exponential-Family Tensor Completion via Nonconvex Dual Total-Variation Regularization](https://mlsanity.com/paper/2606.30958/) (2026)

## Abstract (arXiv)

The task of estimating a matrix given a sample of observed entries is known as the matrix completion problem. Most works on matrix completion have focused on recovering an unknown real-valued low-rank matrix from a random sample of its entries. Here, we investigate the case of highly quantized observations when the measurements can take only a small number of values. These quantized outputs are generated according to a probability distribution parametrized by the unknown matrix of interest. This model corresponds, for example, to ratings in recommender systems or labels in multi-class classification. We consider a general, non-uniform, sampling scheme and give theoretical guarantees on the performance of a constrained, nuclear norm penalized maximum likelihood estimator. One important advantage of this estimator is that it does not require knowledge of the rank or an upper bound on the nuclear norm of the unknown matrix and, thus, it is adaptive. We provide lower bounds showing that our estimator is minimax optimal. An efficient algorithm based on lifted coordinate gradient descent is proposed to compute the estimator. A limited Monte-Carlo experiment, using both simulated and real data is provided to support our claims.