# Johnson and Lindenstrauss lemma for hamming space

A result of Johnson and Lindenstrauss shows that a set of $n$ points in high dimensional Euclidean space can be mapped into an $O(\frac{\log n}{\epsilon^2})$- dimensional Euclidean space such that the distance between any two points changes by only a factor of $(1\pm \epsilon).$

I am looking for reference for a similar result for Hamming space- i.e. a set of $n$ binary vectors can be mapped into a very low dimensional space such that the hamming distance between any pair of vectors is approximately preserved.

Consider the $n$ vectors $e_1,\ldots,e_n$ of weight $1$, and the zero vector $e_0$. The Hamming distance between $e_0$ to any $e_i$ is $1$. Let $\varphi$ be a map into a Hamming cube of dimension $m$, and suppose that it preserves distances up to a factor of $C$. In particular, the $n$ points $\varphi(e_1),\ldots,\varphi(e_n)$ are within distance $C$ of $\varphi(e_0)$. On the other hand, the number of points at distance at most $C$ from $\varphi(e_0)$ is $O(m^C)$. We conclude that $m = \Omega(n^{1/C})$ is polynomial in $n$ rather than logarithmic in $n$.

• At this point, I think you should be able to read the paper yourself and compare your perception of it to the problem highlighted in my answer. If you need someone to talk to about your research, I suggest finding someone local. This site is not the correct forum for such discussions. Apr 5, 2016 at 8:40

Let the matrix consist of $$n$$ points in $$d$$-dimensional space. We first generate a projection matrix $$d\times K$$ whose each entry is sampled from the Cauchy distribution. Then the sketch matrix is computed via projecting the input matrix on the projection matrix. For a pair of points, we compute their sketch vector using the same projection matrix. Then we compute the $$\ell_1$$ norm corresponding to each feature and compute their geometric mean, which gives an estimate of pairwise $$\ell_1$$ norm. This is addressed in the following seminal work due to Ping Li - SODA, 2008 paper.

http://statistics.rutgers.edu/home/pingli/papers/SODA08_stable.pdf

While other answers are correct, I want to mention one result from Polynomial Time Approximation Schemes for Geometric k-Clustering, which is weaker, which roughly says that there exists a (randomized) mapping which does not increase the distance between two points which are already close enough and it does not decrease the distance between two point which are far enough.

Let $$\mathcal{M} = (P,d)$$ and $$\mathcal{M}^\prime = (P^\prime,d^\prime)$$ be two metric spaces and $$X,Y\subseteq P$$. A mapping $$\phi : P \rightarrow P^\prime$$ is $$(\delta,\epsilon,l)$$-distored on $$(X,Y)$$ if there exists a $$l^\prime > 0$$ such that for every $$x\in X$$ and $$y\in Y$$:

if $$d(x,y) < \epsilon l$$, then $$d^\prime(\phi(x),\phi(y)) < (1+\delta)\epsilon l^\prime$$.

if $$d(x,y) > l/\sqrt\epsilon$$, then $$d^\prime(\phi(x),\phi(y)) > (1-\delta)l^\prime/\sqrt\epsilon$$

if $$\epsilon l \leq d(x,y) \leq l/\sqrt\epsilon$$, then $$(1-\delta)l^\prime/l \leq d^\prime(\phi(x),\phi(y)) \leq (1+\delta)l^\prime/l$$.

Then Lemma 2 of the aforementioned paper shows that there is a randomized mapping $$A : \mathbb{H}^d \rightarrow \mathbb{H}^{d^\prime}$$ where $$d^\prime = O(\log n/\epsilon)$$ which is $$(\sqrt\epsilon,\epsilon,l)$$-distored on $$(X,X)$$. (Here $$n = \vert X\vert$$ and $$1\leq l\leq d$$).