# Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 51 references that are in the map.
- First posted on arXiv 3 Dec 2025.

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

- [Generalized Low Rank Models](https://mlsanity.com/paper/1410.0342/) (2014)
- [Recent Developments in Boolean Matrix Factorization](https://mlsanity.com/paper/2012.03127/) (2020)
- [Boolean Matrix Factorization and Noisy Completion via Message Passing](https://mlsanity.com/paper/1509.08535/) (2015)
- [Parameterized Low-Rank Binary Matrix Approximation](https://mlsanity.com/paper/1803.06102/) (2018)
- [Approximation Schemes for Low-Rank Binary Matrix Approximation Problems](https://mlsanity.com/paper/1807.07156/) (2018)
- [C-SALT: Mining Class-Specific ALTerations in Boolean Matrix Factorization](https://mlsanity.com/paper/1906.09907/) (2019)
- [Bayesian Boolean Matrix Factorisation](https://mlsanity.com/paper/1702.06166/) (2017)
- [The PRIMPing Routine -- Tiling through Proximal Alternating Linearized Minimization](https://mlsanity.com/paper/1906.09722/) (2019)
- [Hierarchical compositional feature learning](https://mlsanity.com/paper/1611.02252/) (2016)
- [Boolean Matrix Factorization via Nonnegative Auxiliary Optimization](https://mlsanity.com/paper/2106.04708/) (2021)
- [Efficiently Factorizing Boolean Matrices using Proximal Gradient Descent](https://mlsanity.com/paper/2307.07615/) (2023)
- [Noisy and Incomplete Boolean Matrix Factorizationvia Expectation Maximization](https://mlsanity.com/paper/1905.12766/) (2019)
- [Algorithms for Boolean Matrix Factorization using Integer Programming](https://mlsanity.com/paper/2305.10185/) (2023)

## Abstract (arXiv)

Boolean matrix factorization (BMF) approximates a given binary input matrix as the product of two smaller binary factors. Unlike binary matrix factorization based on standard arithmetic, BMF employs the Boolean OR and AND operations for the matrix product, which improves interpretability and reduces the approximation error. It is also used in role mining and computer vision. In this paper, we first propose algorithms for BMF that perform alternating optimization (AO) of the factor matrices, where each subproblem is solved via integer programming (IP). We then design different approaches to further enhance AO-based algorithms by selecting an optimal subset of rank-one factors from multiple runs. To address the scalability limits of IP-based methods, we introduce new greedy and local-search heuristics. We also construct a new C++ data structure for Boolean vectors and matrices that is significantly faster than existing ones and is of independent interest, allowing our heuristics to scale to large datasets. We illustrate the performance of all our proposed methods and compare them with the state of the art on various real datasets, both with and without missing data, including applications in topic modeling and imaging.