A PTAS for ℓ0-Low Rank Approximation: Solving Dense CSPs over Reals

We consider the ℓ 0 -Low Rank Approximation problem, where the input consists of a matrix A ∈ R n R ×n C and an integer k, and the goal is to find a matrix B of rank at most k that minimizes ∥A -B∥ 0 , which is the number of entries where A and B differ. For any constant k and ε > 0, we present a polynomial time (1 + ε)-approximation time for this problem, which significantly improves the previous best poly(k)-approximation.

Our algorithm is obtained by viewing the problem as a Constraint Satisfaction Problem (CSP) where each row and column becomes a variable that can have a value from R k . In this view, we have a constraint between each row and column, which results in a dense CSP, a well-studied topic in approximation algorithms. While most of previous algorithms focus on finite-size (or constant-size) domains and involve an exhaustive enumeration over the entire domain, we present a new framework that bypasses such an enumeration in R k . We also use tools from the rich literature of Low Rank Approximation in different objectives (e.g., ℓ p with p ∈ (0, ∞)) or domains (e.g., finite fields/generalized Boolean). We believe that our techniques might be useful to study other real-valued CSPs and matrix optimization problems.

On the hardness side, when k is part of the input, we prove that ℓ 0 -Low Rank Approximation is NP-hard to approximate within a factor of Ω(log n). This is the first superconstant NP-hardness of approximation for any p ∈ [0, ∞] that does not rely on stronger conjectures (e.g., the Small Set Expansion Hypothesis).