A PTAS for ${\ell }_0$-Low Rank Approximation: Solving Dense CSPs over Reals

Abstract

We consider the Low Rank Approximation problem, where the input consists of a matrix $A\in {\mathbb{R}}^{n_R\times n_C}$ and an integer $k$, and the goal is to find a matrix $B$ of rank at most $k$ that minimizes $\Vert A-B{\Vert }_0$, which is the number of entries where $A$ and $B$ differ. For any constant $k$ and $\epsilon >0$, we present a polynomial time $(1+\epsilon )$-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 ${\mathbb{R}}^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 ${\mathbb{R}}^k$. We also use tools from the rich literature of Low Rank Approximation in different objectives (e.g., ${\ell }_p$ with $p\in (0,\infty )$) 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 $\hat{I}\text{c◯}(\log n)$. This is the first superconstant NP-hardness of approximation for any $p\in [0,\infty ]$ that does not rely on stronger conjectures (e.g., the Small Set Expansion Hypothesis).

To appear in SODA 24