Linear-size $\ell_1$ sparsifiers
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.28147
curl -X POST /api/v1/records/arxiv/2606.28147/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.28147/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'