{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-26","reactions":{}}