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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.