Low-rank binary matrix approximation in column-sum norm

Abstract

We consider ${\ell }_1$-Rank-$r$ Approximation over GF(2), where for a binary $m\times n$ matrix $\mathbf{A}$ and a positive integer $r$, one seeks a binary matrix $\mathbf{B}$ of rank at most $r$, minimizing the column-sum norm $||\mathbf{A}-\mathbf{B}|{|}_1$. We show that for every $\epsilon \in (0,1)$, there is a randomized $(1+\epsilon )$-approximation algorithm for ${\ell }_1$-Rank-$r$ Approximation over GF(2) of running time $m^{O(1)}{n}^{O(2^{4r}\cdot {\epsilon }^{-4})}$. This is the first polynomial time approximation scheme (PTAS) for this problem.