  Low rank matrix approximation is an important tool in machine learning. Given
a data matrix, low rank approximation helps to find factors, patterns and
provides concise representations for the data. Research on low rank
approximation usually focus on real matrices. However, in many applications
data are binary (categorical) rather than continuous. This leads to the problem
of low rank approximation of binary matrix. Here we are given a $d \times n$
binary matrix $A$ and a small integer $k$. The goal is to find two binary
matrices $U$ and $V$ of sizes $d \times k$ and $k \times n$ respectively, so
that the Frobenius norm of $A - U V$ is minimized. There are two models of this
problem, depending on the definition of the dot product of binary vectors: The
$\mathrm{GF}(2)$ model and the Boolean semiring model. Unlike low rank
approximation of real matrix which can be efficiently solved by Singular Value
Decomposition, approximation of binary matrix is $NP$-hard even for $k=1$.
  In this paper, we consider the problem of Column Subset Selection (CSS), in
which one low rank matrix must be formed by $k$ columns of the data matrix. We
characterize the approximation ratio of CSS for binary matrices. For $GF(2)$
model, we show the approximation ratio of CSS is bounded by
$\frac{k}{2}+1+\frac{k}{2(2^k-1)}$ and this bound is asymptotically tight. For
Boolean model, it turns out that CSS is no longer sufficient to obtain a bound.
We then develop a Generalized CSS (GCSS) procedure in which the columns of one
low rank matrix are generated from Boolean formulas operating bitwise on
columns of the data matrix. We show the approximation ratio of GCSS is bounded
by $2^{k-1}+1$, and the exponential dependency on $k$ is inherent.
