  Boolean Matrix Factorization (BMF) aims to find an approximation of a given
binary matrix as the Boolean product of two low-rank binary matrices. Binary
data is ubiquitous in many fields, and representing data by binary matrices is
common in medicine, natural language processing, bioinformatics, computer
graphics, among many others. Unfortunately, BMF is computationally hard and
heuristic algorithms are used to compute Boolean factorizations. Very recently,
the theoretical breakthrough was obtained independently by two research groups.
Ban et al. (SODA 2019) and Fomin et al. (Trans. Algorithms 2020) show that BMF
admits an efficient polynomial-time approximation scheme (EPTAS). However,
despite the theoretical importance, the high double-exponential dependence of
the running times from the rank makes these algorithms unimplementable in
practice. The primary research question motivating our work is whether the
theoretical advances on BMF could lead to practical algorithms.
  The main conceptional contribution of our work is the following. While EPTAS
for BMF is a purely theoretical advance, the general approach behind these
algorithms could serve as the basis in designing better heuristics. We also use
this strategy to develop new algorithms for related $\mathbb{F}_p$-Matrix
Factorization. Here, given a matrix $A$ over a finite field GF($p$) where $p$
is a prime, and an integer $r$, our objective is to find a matrix $B$ over the
same field with GF($p$)-rank at most $r$ minimizing some norm of $A-B$. Our
empirical research on synthetic and real-world data demonstrates the advantage
of the new algorithms over previous works on BMF and $\mathbb{F}_p$-Matrix
Factorization.
