cs.DS
Low rank binary matrix approximation in column sum norm. We consider ell 1 Rank r Approximation over GF(2), where for a binary m times n matrix bf A and a positive integer r , one seeks a binary matrix bf B of rank at most r , minimizing the column sum norm bf A bf B 1 . We show that for every varepsilon in (0, 1) , there is a randomized (1 varepsilon) approximation algorithm for ell 1 Rank r Approximation over GF(2) of running time m O(1) n O(2 4r cdot varepsilon 4 ) . This is the first polynomial time approximation scheme (PTAS) for this problem.