Recent Developments in Boolean Matrix Factorization

Boolean matrix factorization (BMF) is a variant of the standard matrix factorization problem in the Boolean semiring: given a binary matrix, the task is to find two smaller binary matrices so that their product, taken over the Boolean semiring, is as close to the original matrix as possible. Because the matrix product is not done over a field but over a semiring, many standard matrix factorization techniques fail to work. Indeed, finding the best Boolean factorization is computationally hard. The computational hardness of the problem has not prevented people from studying it. In psychometrics, some of the first algorithms appeared in the 1980's (see Bělohlávek and Trnecka (2018)). Even before that, mathematicians studying combinatorics had studied the "Boolean linear algebra" (Kim, 1982; Monson et al., 1995).