Low-Rank Binary Matrix Approximation in Column-Sum Norm
Journal article, Peer reviewed
Published version
Åpne
Permanent lenke
https://hdl.handle.net/11250/2755711Utgivelsesdato
2020Metadata
Vis full innførselSamlinger
- Department of Informatics [981]
- Registrations from Cristin [10402]
Originalversjon
Leibniz International Proceedings in Informatics. 2020, 176, 32:1-32:18 10.4230/LIPIcs.APPROX/RANDOM.2020.32Sammendrag
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.