2023/11/01 by Vincent Cohen-Addad, Chenglin Fan, Cohen-Addad, Vincent +11
Computer Science · #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2311.00892
openalex publication_date 2023/11/01 · openalex created_date 2023/11/04 · openalex updated_date 2026/07/28
We consider the Low Rank Approximation problem, where the input consists of a matrix A ∈ ℝnR × nC 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 ℝk. In this view, we have a constraint between each row and column, which results in a \em 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 ℝ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 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).