<p>Let the  matrix consist of <span class="math-container">$n$</span> points in <span class="math-container">$d$</span>-dimensional space.  We first generate a projection matrix <span class="math-container">$d\times K$</span> 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 <span class="math-container">$\ell_1$</span> norm corresponding to each feature and compute their geometric mean, which gives an estimate of pairwise <span class="math-container">$\ell_1$</span> norm. This is addressed in the following seminal work due to Ping Li - SODA, 2008 paper.</p>
<p><a href="http://statistics.rutgers.edu/home/pingli/papers/SODA08_stable.pdf" rel="nofollow noreferrer">http://statistics.rutgers.edu/home/pingli/papers/SODA08_stable.pdf</a></p>

CC BY-SA 4.0
2021-11-04T18:32:10.017Z
2021-11-04T18:32:10.017Z
Ram
<p>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$.</p>

CC BY-SA 3.0
2016-04-05T08:40:53.150Z
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.
Yuval Filmus
CC BY-SA 3.0
2016-04-04T08:38:10.163Z
2016-04-04T08:38:10.163Z
Yuval Filmus
<p>While other answers are correct, I want to mention one result from <a href="http://web.cs.ucla.edu/%7Erafail/PUBLIC/49.pdf" rel="nofollow noreferrer">Polynomial Time Approximation Schemes for Geometric k-Clustering</a>, 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.</p>
<p>Let <span class="math-container">$\mathcal{M} = (P,d)$</span> and <span class="math-container">$\mathcal{M}^\prime = (P^\prime,d^\prime)$</span> be two metric spaces and <span class="math-container">$X,Y\subseteq P$</span>. A mapping <span class="math-container">$\phi : P \rightarrow P^\prime$</span> is <span class="math-container">$(\delta,\epsilon,l)$</span>-distored on <span class="math-container">$(X,Y)$</span> if there exists a <span class="math-container">$l^\prime &gt; 0$</span> such that for every <span class="math-container">$x\in X$</span> and <span class="math-container">$y\in Y$</span>:</p>
<blockquote>
<p>if <span class="math-container">$d(x,y) &lt; \epsilon l$</span>, then <span class="math-container">$d^\prime(\phi(x),\phi(y)) &lt; (1+\delta)\epsilon l^\prime$</span>.</p>
</blockquote>
<blockquote>
<p>if <span class="math-container">$d(x,y) &gt; l/\sqrt\epsilon$</span>, then <span class="math-container">$d^\prime(\phi(x),\phi(y)) &gt; (1-\delta)l^\prime/\sqrt\epsilon$</span></p>
</blockquote>
<blockquote>
<p>if <span class="math-container">$\epsilon l \leq d(x,y) \leq l/\sqrt\epsilon$</span>, then <span class="math-container">$(1-\delta)l^\prime/l \leq d^\prime(\phi(x),\phi(y)) \leq (1+\delta)l^\prime/l$</span>.</p>
</blockquote>
<p>Then Lemma 2 of the aforementioned paper shows that there is a randomized mapping <span class="math-container">$A : \mathbb{H}^d \rightarrow \mathbb{H}^{d^\prime}$</span> where <span class="math-container">$d^\prime = O(\log n/\epsilon)$</span> which is <span class="math-container">$(\sqrt\epsilon,\epsilon,l)$</span>-distored on <span class="math-container">$(X,X)$</span>. (Here <span class="math-container">$n = \vert X\vert$</span> and <span class="math-container">$1\leq l\leq d$</span>).</p>

CC BY-SA 4.0
2021-12-01T05:27:19.810Z
2021-12-01T05:27:19.810Z
Sudipta Roy
<p>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).$</p>

<p>I am looking for reference for a similar result for Hamming space- <em>i.e.</em>  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. </p>

<randomized-algorithms><high-dimensional-geometry>
Johnson and Lindenstrauss lemma for hamming space
Ram
# Johnson and Lindenstrauss lemma for hamming space

(Asked by: username_0 on 2016-04-04)

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.

**Tags:** randomized-algorithms, high-dimensional-geometry

---

## 3 answers

### Answer by username_0 on 2021-11-04. Score: 1 | Accepted answer

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 by username_1 on 2016-04-04. Score: 12

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

> **Comments:**
> **username_1**: 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.  

---

### Answer by username_2 on 2021-12-01. Score: 1

While other answers are correct, I want to mention one result from [Polynomial Time Approximation Schemes for Geometric k-Clustering](http://web.cs.ucla.edu/%7Erafail/PUBLIC/49.pdf), 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$).


---

