Algorithms for Boolean Matrix Factorization using Integer Programming
Christos Kolomvakis Arnaud Vandaele Nicolas Gillis
Boolean matrix factorization (BMF) approximates a given binary input matrix
as the product of two smaller binary factors. As opposed to binary matrix
factorization which uses standard arithmetic, BMF uses the Boolean OR and
Boolean AND operations to perform matrix products, which leads to lower
reconstruction errors. BMF is an NP-hard problem. In this paper, we first
propose an alternating optimization (AO) strategy that solves the subproblem in
one factor matrix in BMF using an integer program (IP). We also provide two
ways to initialize the factors within AO. Then, we show how several solutions
of BMF can be combined optimally using another IP. This allows us to come up
with a new algorithm: it generates several solutions using AO and then combines
them in an optimal way. Experiments show that our algorithms (available on
gitlab) outperform the state of the art on medium-scale problems.