Id: arxiv/2606.28147 Url: https://arxiv.org/abs/2606.28147 Tags: math.MG, cs.CG, cs.DM Score: 0 Title: Linear-size $\ell_1$ sparsifiers Domain: math.MG Source: arxiv Authors: Victor Reis, Thomas Rothvoss Reviews: 0 Subject: math.MG Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-26 Page: https://delphi.science/r/arxiv/2606.28147 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(\frac{n}{\varepsilon^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' \subseteq \mathbb{R}^{n}$ generated by at most $O(\frac{n}{\varepsilon^2})$ segments so that $(1-\varepsilon) Z \subseteq Z' \subseteq (1+\varepsilon) Z$. Previously, the best…