Johnson and Lindenstrauss lemma for hamming space

Question

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.

Answer 1

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$.

Answer 2

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

Answer 3

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$).