Linear-size ℓ₁ Sparsifiers

Victor Reis (Microsoft Research)

Beyond Graph Laplacians

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