  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.
