Low-rank binary matrix approximation in column-sum norm

We consider ℓ1-Rank-r Approximation over GF(2), where for a binary m × n matrix A and a positive integer constant r, one seeks a binary matrix B of rank at most r, minimizing the column-sum norm ||A − B||1. We show that for every ε ∈ (0, 1), there is a randomized (1 + ε)-approximation algorithm for ℓ1-Rank-r Approximation over GF(2) of running time mO(1)nO(24r·ε−4). This is the first polynomial time approximation scheme (PTAS) for this problem. © 2020 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved