Linear-size ${\ell }_1$ sparsifiers

Abstract

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}{{\epsilon }^2})$ nonzero entries so that \[ (1-\varepsilon) \|Ax\|_1 \leq \|DAx\|_1 \leq (1+\varepsilon)\|Ax\|_1 \quad \forall x \in \mathbb{R}^n. \] In particular, for any zonotope $Z\subseteq {\mathbb{R}}^n$ there exists a zonotope $Z^{\prime }\subseteq {\mathbb{R}}^n$ generated by at most $O(\frac{n}{{\epsilon }^2})$ segments so that $(1-\epsilon )Z\subseteq Z^{\prime }\subseteq (1+\epsilon )Z$. Previously, the best known bound was $O(\frac{n}{{\epsilon }^2}\log n)$ due to Talagrand (1990).

26 pages