Low-Rank Binary Matrix Approximation in Column-Sum Norm
Journal article, Peer reviewed
Published version
View/ Open
Date
2020Metadata
Show full item recordCollections
- Department of Informatics [917]
- Registrations from Cristin [9489]
Original version
Leibniz International Proceedings in Informatics. 2020, 176, 32:1-32:18 10.4230/LIPIcs.APPROX/RANDOM.2020.32Abstract
We consider 𝓁₁-Rank-r Approximation over {GF}(2), where for a binary m× n matrix 𝐀 and a positive integer constant r, one seeks a binary matrix 𝐁 of rank at most r, minimizing the column-sum norm ‖ 𝐀 -𝐁‖₁. We show that for every ε ∈ (0, 1), there is a {randomized} (1+ε)-approximation algorithm for 𝓁₁-Rank-r Approximation over {GF}(2) of running time m^{O(1)}n^{O(2^{4r}⋅ ε^{-4})}. This is the first polynomial time approximation scheme (PTAS) for this problem.