# Boolean Matrix Factorization with SAT and MaxSAT

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 32 references that are in the map.
- First posted on arXiv 18 Jun 2021.

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

- [Recent Developments in Boolean Matrix Factorization](https://mlsanity.com/paper/2012.03127/) (2020)
- [Fast And Efficient Boolean Matrix Factorization By Geometric Segmentation](https://mlsanity.com/paper/1909.03991/) (2019)
- [topFiberM: Scalable and Efficient Boolean Matrix Factorization](https://mlsanity.com/paper/1903.10326/) (2019)

## Abstract (arXiv)

The Boolean matrix factorization problem consists in approximating a matrix by the Boolean product of two smaller Boolean matrices. To obtain optimal solutions when the matrices to be factorized are small, we propose SAT and MaxSAT encoding; however, when the matrices to be factorized are large, we propose a heuristic based on the search for maximal biclique edge cover. We experimentally demonstrate that our approaches allow a better factorization than existing approaches while keeping reasonable computation times. Our methods also allow the handling of incomplete matrices with missing entries.