The sparse ℓ1 representation conjecture for zonotopes

Let $A\in\mathbb{R}^{m\times d}$ with $m\geq d$ and $0<\varepsilon\leq\frac12$. Sparse $\ell_1$ representation conjecture. There exists a universal constant $C>0$ and a matrix $\widetilde A\in\mathbb{R}^{Cd/\varepsilon^2\times d}$ such that, for every $x\in\mathbb{R}^d$,

$$\|\widetilde A x\|_1\leq\|Ax\|_1\leq(1+\varepsilon)\|\widetilde A x\|_1.$$

Equivalently, this is the polar formulation of sparse approximation of zonotopes. The source presents it as an open conjecture; the analogous $\ell_2$ statement follows from linear-size spectral sparsification.