# A Majorization-Minimization Gauss-Newton Method for 1-Bit Matrix Completion

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 42 references that are in the map.
- First posted on arXiv 27 Apr 2023.

## Builds on (most cited first, 10 of 10)

- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion](https://mlsanity.com/paper/1309.6013/) (2013)
- [Infinite Edge Partition Models for Overlapping Community Detection and Link Prediction](https://mlsanity.com/paper/1501.06218/) (2015)
- [Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality](https://mlsanity.com/paper/1811.05076/) (2018)
- [Learning tensors from partial binary measurements](https://mlsanity.com/paper/1804.00108/) (2018)
- [Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries](https://mlsanity.com/paper/2002.01849/) (2020)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [1-Bit Matrix Completion under Exact Low-Rank Constraint](https://mlsanity.com/paper/1502.06689/) (2015)
- [Bayesian Mean-parameterized Nonnegative Binary Matrix Factorization](https://mlsanity.com/paper/1812.06866/) (2018)
- [A majorization-minimization algorithm for nonnegative binary matrix factorization](https://mlsanity.com/paper/2204.09741/) (2022)

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

- [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)

## Abstract (arXiv)

In 1-bit matrix completion, the aim is to estimate an underlying low-rank matrix from a partial set of binary observations. We propose a novel method for 1-bit matrix completion called Majorization-Minimization Gauss-Newton (MMGN). Our method is based on the majorization-minimization principle, which converts the original optimization problem into a sequence of standard low-rank matrix completion problems. We solve each of these sub-problems by a factorization approach that explicitly enforces the assumed low-rank structure and then apply a Gauss-Newton method. Using simulations and a real data example, we illustrate that in comparison to existing 1-bit matrix completion methods, MMGN outputs comparable if not more accurate estimates. In addition, it is often significantly faster, and less sensitive to the spikiness of the underlying matrix. In comparison with three standard generic optimization approaches that directly minimize the original objective, MMGN also exhibits a clear computational advantage, especially when the fraction of observed entries is small.