# Efficiently Factorizing Boolean Matrices using Proximal Gradient Descent

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 45 references that are in the map.
- First posted on arXiv 14 Jul 2023.

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

- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/1702.02505/) (2017)
- [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)
- [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)
- [Fast And Efficient Boolean Matrix Factorization By Geometric Segmentation](https://mlsanity.com/paper/1909.03991/) (2019)
- [Biclustering and Boolean Matrix Factorization in Data Streams](https://mlsanity.com/paper/2012.03138/) (2020)
- [Boolean matrix factorization meets consecutive ones property](https://mlsanity.com/paper/1901.05797/) (2019)
- [An interpretable latent variable model for attribute applicability in the Amazon catalogue](https://mlsanity.com/paper/1712.00126/) (2017)
- [The Trustworthy Pal: Controlling the False Discovery Rate in Boolean Matrix Factorization](https://mlsanity.com/paper/1907.00697/) (2019)

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

- [Finding Interpretable Class-Specific Patterns through Efficient Neural Search](https://mlsanity.com/paper/2312.04311/) (2023)
- [Federated Binary Matrix Factorization using Proximal Optimization](https://mlsanity.com/paper/2407.01776/) (2024)
- [Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics](https://mlsanity.com/paper/2512.03807/) (2025)

## Abstract (arXiv)

Addressing the interpretability problem of NMF on Boolean data, Boolean Matrix Factorization (BMF) uses Boolean algebra to decompose the input into low-rank Boolean factor matrices. These matrices are highly interpretable and very useful in practice, but they come at the high computational cost of solving an NP-hard combinatorial optimization problem. To reduce the computational burden, we propose to relax BMF continuously using a novel elastic-binary regularizer, from which we derive a proximal gradient algorithm. Through an extensive set of experiments, we demonstrate that our method works well in practice: On synthetic data, we show that it converges quickly, recovers the ground truth precisely, and estimates the simulated rank exactly. On real-world data, we improve upon the state of the art in recall, loss, and runtime, and a case study from the medical domain confirms that our results are easily interpretable and semantically meaningful.