Many research fields, such as personalized medicine, space research, social sciences, climate research, nonproliferation, emergency response, finances, etc. collect and generate large-scale datasets. Analysis of such datasets is difficult, since often the underlying fundamental processes (or features) remain hidden or latent (i.e., not directly observable) [1]}.
Extracting such latent features reveals valuable information and hidden causality and relations. One of the most powerful tools for extracting latent (hidden) features from data is factor analysis [2]}.
Traditionally, factor analysis approximates a data-matrix \(X \in \mathbb {R}^{n \times m}\)  by a product of two low-rank (factor) matrices, \(X \approx WH\) , where \(W \in \mathbb {R}^{n \times k}\) , \(H \in \mathbb {R}^{k \times m}\) , and \(k \ll n,m\) . Various types of factorizations can be obtained by imposing different constraints. For instance, imposing orthogonality on the factors leads to the singular value decomposition (SVD) [3]}, while the nonnegativity constraint leads to non-negative matrix factorization (NMF) [4]}. In a lot of investigations, the variables are simple dichotomies, {false, true}, that is, the data contains only binary values, \(\lbrace 0, 1\rbrace \) . For example, in relational databases, an object-attribute relation is represented by a Boolean variable, which takes value \(\lbrace 1\rbrace \) -true, if the object has this attribute, or \(\lbrace 0\rbrace \) -false, otherwise. In this case, all the values of the factors have to be 0 or 1. In this case, instead of simple arithmetic we also need to use Boolean algebra: instead of “plus” and “times” we need the logical operations of “or” with “and”, which results in a Boolean factorization [5]}. To be precise, letting \(\mathbb {B}=\lbrace 0,1\rbrace \) ,
and assuming the input data is a matrix \(X \in \mathbb {B}^{n \times m}\) , where \(\mathbb {B}=\lbrace 0,1\rbrace \) , Boolean matrix factorization (BMF) is looking for two binary matrices \(W \in \mathbb {B}^{n \times k}\) , \(H \in \mathbb {B}^{k \times m}\)  such that \(X \approx W \otimes _B H\) , where \((W \otimes _B H)_{ij}=\vee _{l=1}^k W_{il} \wedge H_{lj} \in \mathbb {B}\)  and \(\vee \)  and \(\wedge \)  are the logical "or" and "and" operations. The Boolean rank of \(X\)  is the smallest \(k\)  for which such an exact representation, \(X=W \otimes _B H\) , exists. Interestingly, in contrast to the non-negative rank, the Boolean rank can be not only bigger or equal, but also smaller than the real rank [6]}, [7]}.
