# Optimal $\ell^1$ sketching, including the coefficient

Let us define the sketch as mapping $$\varphi:R^D\to R^d$$, such that for arbitrary $$x\in\mathbb{R}^D$$, its $$\ell^1$$ norm is preserved up to $$\epsilon$$ error, with $$1-\delta$$ success probability: $$\mathbb{P}\left(1-\epsilon\le \frac{\|\varphi(x)\|_1}{\|x\|_1}< 1+\epsilon\right) > 1-\delta \qquad \forall x\in\mathbb{R}^D,x\neq 0$$ Clearly, the design of $$\varphi$$ must be agnostic to $$x$$, or otherwise the problem becomes trivial. I believe $$d=\mathcal{O}(\epsilon^{-2}\log(1/\delta))$$ can be achieved by defining $$\varphi(x)=M x,$$ where $$M\in\mathbb{R}^{d\times D}$$ is a random matrix with elements drawn from the Cauchy distribution, and use a median estimator to approximate its norm. My question is two folds:

1. can we generate $$\varphi$$ such that the norm can be assessed using $$\ell^1$$ norm, rather than the median (or some other simple geometry, like $$\ell^2$$ or on Hamming cube)
2. for a given $$\delta,\epsilon$$, what is the lowest possible $$d$$, including the optimal constants and not just the asymptotic optimal relationship? I am also interested the answer to the same question for $$\ell^2$$ embedding/sketching
• See, e.g., dl.acm.org/doi/10.1145/1089023.1089026 (also, I think you have an extra $\|x\|_1$ in the equation, should it be simply $\|\varphi(x)\|_1$ in the middle?) Jan 12 at 22:48