# Boolean Matrix Factorization via Nonnegative Auxiliary Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 7 Oct 2026).
- Builds on 9 of its 45 references that are in the map.
- First posted on arXiv 8 Jun 2021.

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

- [Boolean Matrix Factorization and Noisy Completion via Message Passing](https://mlsanity.com/paper/1509.08535/) (2015)
- [Optimal Bipartite Network Clustering](https://mlsanity.com/paper/1803.06031/) (2018)
- [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)
- [Bayesian Boolean Matrix Factorisation](https://mlsanity.com/paper/1702.06166/) (2017)
- [From-Below Approximations in Boolean Matrix Factorization: Geometry and New Algorithm](https://mlsanity.com/paper/1306.4905/) (2013)
- [Jointly Clustering Rows and Columns of Binary Matrices: Algorithms and Trade-offs](https://mlsanity.com/paper/1310.0512/) (2013)
- [Biclustering and Boolean Matrix Factorization in Data Streams](https://mlsanity.com/paper/2012.03138/) (2020)
- [Noisy and Incomplete Boolean Matrix Factorizationvia Expectation Maximization](https://mlsanity.com/paper/1905.12766/) (2019)

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

- [Algorithms for Boolean Matrix Factorization using Integer Programming](https://mlsanity.com/paper/2305.10185/) (2023)
- [Matrix Factorization for Inferring Associations and Missing Links](https://mlsanity.com/paper/2503.04680/) (2025)
- [Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics](https://mlsanity.com/paper/2512.03807/) (2025)

## Abstract (arXiv)

A novel approach to Boolean matrix factorization (BMF) is presented. Instead of solving the BMF problem directly, this approach solves a nonnegative optimization problem with the constraint over an auxiliary matrix whose Boolean structure is identical to the initial Boolean data. Then the solution of the nonnegative auxiliary optimization problem is thresholded to provide a solution for the BMF problem. We provide the proofs for the equivalencies of the two solution spaces under the existence of an exact solution. Moreover, the nonincreasing property of the algorithm is also proven. Experiments on synthetic and real datasets are conducted to show the effectiveness and complexity of the algorithm compared to other current methods.