# 1-Bit Matrix Completion under Exact Low-Rank Constraint

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2015.

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

- [A Majorization-Minimization Gauss-Newton Method for 1-Bit Matrix Completion](https://mlsanity.com/paper/2304.13940/) (2023)
- [Impossibility of latent inner product recovery via rate distortion](https://mlsanity.com/paper/2407.11932/) (2024)
- [One-Bit Matrix Completion with Differential Privacy](https://mlsanity.com/paper/2110.00719/) (2021)
- [Matrix Completion from One-Bit Dither Samples](https://mlsanity.com/paper/2310.03224/) (2023)
- [An Interpretable and Scalable Framework for Evaluating Large Language Models](https://mlsanity.com/paper/2605.07046/) (2026)
- [Empirical Bayes 1-bit matrix completion](https://mlsanity.com/paper/2605.09509/) (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 noisy 1-bit matrix completion under an exact rank constraint on the true underlying matrix M^*. Instead of observing a subset of the noisy continuous-valued entries of a matrix M^*, we observe a subset of noisy 1-bit (or binary) measurements generated according to a probabilistic model. We consider constrained maximum likelihood estimation of M^*, under a constraint on the entry-wise infinity-norm of M^* and an exact rank constraint. This is in contrast to previous work which has used convex relaxations for the rank. We provide an upper bound on the matrix estimation error under this model. Compared to the existing results, our bound has faster convergence rate with matrix dimensions when the fraction of revealed 1-bit observations is fixed, independent of the matrix dimensions. We also propose an iterative algorithm for solving our nonconvex optimization with a certificate of global optimality of the limiting point. This algorithm is based on low rank factorization of M^*. We validate the method on synthetic and real data with improved performance over existing methods.