Linear-size ${\ell }_1$ sparsifiers

Victor Reis, Thomas Rothvoss

We prove that for any matrix $A\in {\mathbb{R}}^{m\times n}$ and any $\epsilon >0$ there is a diagonal matrix $D\in {\mathbb{R}}_{\ge 0}^{m\times m}$ with at most $O(\frac{n}{…