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

Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal +4

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…