# Binary Matrix Factorisation and Completion via Integer Programming

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 40 references that are in the map.
- First posted on arXiv 25 Jun 2021.

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

- [On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation](https://mlsanity.com/paper/1509.09236/) (2015)
- [Binary Matrix Factorisation via Column Generation](https://mlsanity.com/paper/2011.04457/) (2020)
- [A divide-and-conquer algorithm for binary matrix completion](https://mlsanity.com/paper/1907.04251/) (2019)
- [Low-Rank Boolean Matrix Approximation by Integer Programming](https://mlsanity.com/paper/1803.04825/) (2018)

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

- [Algorithms for Boolean Matrix Factorization using Integer Programming](https://mlsanity.com/paper/2305.10185/) (2023)

## Abstract (arXiv)

Binary matrix factorisation is an essential tool for identifying discrete patterns in binary data. In this paper we consider the rank-k binary matrix factorisation problem (k-BMF) under Boolean arithmetic: we are given an n x m binary matrix X with possibly missing entries and need to find two binary matrices A and B of dimension n x k and k x m respectively, which minimise the distance between X and the Boolean product of A and B in the squared Frobenius distance. We present a compact and two exponential size integer programs (IPs) for k-BMF and show that the compact IP has a weak LP relaxation, while the exponential size IPs have a stronger equivalent LP relaxation. We introduce a new objective function, which differs from the traditional squared Frobenius objective in attributing a weight to zero entries of the input matrix that is proportional to the number of times the zero is erroneously covered in a rank-k factorisation. For one of the exponential size IPs we describe a computational approach based on column generation. Experimental results on synthetic and real word datasets suggest that our integer programming approach is competitive against available methods for k-BMF and provides accurate low-error factorisations.