Linear-size ${\mathrm{\ell }}_1$ sparsifiers

We prove that for any matrix $A\in {\mathbb{R}}^{m\times n}$ and any $\epsilon \in (0,1\mathrm{/}2]$ there is a diagonal matrix $D\in {\mathbb{R}}_{\ge 0}^{m\times m}$ with at most $O(\frac{n}{{\epsilon }^2}\log (\frac{1}{\epsilon }))$ nonzero entries so that $$(1-\epsilon )\mathrm{\parallel }Ax{\mathrm{\parallel }}_1\le \mathrm{\parallel }DAx{\mathrm{\parallel }}_1\le (1+\epsilon )\mathrm{\parallel }Ax{\mathrm{\parallel }}_1\mathrm{\forall }x\in {\mathbb{R}}^n\mathrm{.}$$In particular, for any zonotope $Z\subseteq {\mathbb{R}}^n$ there exists a zonotope $Z^{\mathrm{\prime }}\subseteq {\mathbb{R}}^n$ generated by at most $O(\frac{n}{{\epsilon }^2}\log (\frac{1}{\epsilon }))$ segments so that $(1-\epsilon )Z\subseteq Z^{\mathrm{\prime }}\subseteq (1+\epsilon )Z$. Previously, the best known bound was $O(\frac{n}{{\epsilon }^2}\log n)$ due to Talagrand (1990).