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.

基于针对实践的 heuristics 我们提出了一种新的算法，它基于 BMF 的最新的理论进展，用于在有限域上找到 GF （p）-Matrix 分解的有效多项式时间逼近方案，并通过人工合成和现实世界数据的实证研究证明了我们算法的优越性。

从理论到实践：布尔和有限域矩阵分解

Boolean and $\mathbb{F}_p$-Matrix Factorization: From Theory to Practice

Let $\{f_i:\mathbb{F}_p^i \to \{0,1\}\}$ be a sequence of functions, where
$p$ is a fixed prime and $\mathbb{F}_p$ is the finite field of order $p$. The
limit of the sequence can be syntactically defined using the notion of
ultralimit. Inspired by the Gowers norm, we introduce a metric over limits of
function sequences, and study properties of it. One application of this metric
is that it provides a characterization of affine-invariant parameters of
functions that are constant-query estimable. Using this characterization, we
show that the property of being a function of a constant number of low-degree
polynomials and a constant number of factored polynomials (of arbitrary
degrees) is constant-query testable if it is closed under blowing-up. Examples
of this property include the property of having a constant spectral norm and
degree-structural properties with rank conditions.

利用极限概念，通过 Gowers 范数引入度量，以研究函数序列极限的属性，阐明了低次多项式及系数 - 结构性质的常数查询检测，如谱范数和秩条件。