Low-rank binary matrix approximation in column-sum norm

2019/04/12 by Fomin, Fedor V., Golovach, Petr A., Panolan, Fahad +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1904.06141

Abstract

We consider ℓ₁-Rank-r Approximation over GF(2), where for a binary m× 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||₁. 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.

Related

• A PTAS for ℓ_p-Low Rank Approximation
• Approximation Algorithms for ℓ₀-Low Rank Approximation
• Low Rank Approximation with Entrywise ℓ₁-Norm Error
• Approximation Schemes for Low-Rank Binary Matrix Approximation Problems
• Parameterized Low-Rank Binary Matrix Approximation