# From-Below Approximations in Boolean Matrix Factorization: Geometry and New Algorithm

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2013.

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

- [Boolean Matrix Factorization via Nonnegative Auxiliary Optimization](https://mlsanity.com/paper/2106.04708/) (2021)
- [What is the textitintrinsic dimension of your binary data? -- and how to compute it quickly](https://mlsanity.com/paper/2404.06326/) (2024)
- [Factorizing formal contexts from closures of necessity operators](https://mlsanity.com/paper/2604.09582/) (2026)

## Abstract (arXiv)

We present new results on Boolean matrix factorization and a new algorithm based on these results. The results emphasize the significance of factorizations that provide from-below approximations of the input matrix. While the previously proposed algorithms do not consider the possibly different significance of different matrix entries, our results help measure such significance and suggest where to focus when computing factors. An experimental evaluation of the new algorithm on both synthetic and real data demonstrates its good performance in terms of good coverage by the first k factors as well as a small number of factors needed for exact decomposition and indicates that the algorithm outperforms the available ones in these terms. We also propose future research topics.