# A Johnson-Lindenstrauss lemma for finite fields?

Given $m$ points in $\mathbb{R}^N$, the Johnson-Lindenstrauss lemma guarantees the existence of a linear operator $\mathbb{R}^N\rightarrow\mathbb{R}^n$ that nearly preserves pairwise distances between the points. Here, we can take $n=\Omega(\log(m)/\varepsilon^2)$, where $\varepsilon$ is the level of distortion.

Is there a similar result for points in a vector space over a finite field, e.g. $\mathbb{F}_2^N$? I assume a result of this form would be in terms of Hamming distance.

## 1 Answer

The problem with Hamming distance is that it's bounded above by $$N$$, so if you have a subset of $$\mathbb{F}_2^N$$ with Hamming distances in that range, you're not going to be able to embed it in $$\mathbb{F}_2^n$$ for $$n$$ much smaller than $$N$$.

Perhaps more natural is to build in a scaling, so that you want to find an embedding $$f$$ of the subset $$S$$ of $$\mathbb{R}^N$$ into $$\mathbb{R}^n$$ in such a way that

$$d(f(x),f(y)) \approx \frac{n}{N}\cdot d(x,y)$$.

In other words, given two vectors $$x$$ and $$y$$, you want the proportion of coordinates in which they agree to be more or less left alone by the projection. Then you could try a random projection as in Johnson-Lindenstrauss -- i.e. show that (if indeed this is true) a random choice of one of the $$N \choose n$$ coordinate projections gives you low distortion in this sense, when $$n$$ is not too horrifically small.

• Agreed. Another way to address the scaling issue: Project onto an $n$-dimensional subspace of $\mathbb{F}_2^N$ and use Hamming distance in $\mathbb{F}_2^N$. I suppose a linear error-correcting code would provide a worthy subspace, but is there a randomized alternative that enjoys JL-type performance? May 10, 2013 at 3:38
• I think a truly random projection will scramble the Hamming distance too much - for instance, I don't see the need for there to be any correlation at all between the Hamming distance between two distinct points before and after the projection! Your only hope seems to be a random sparse projection. But it's not clear to me how to make one such that the expected Hamming distance after projection, as a function of the Hamming distance before, is approximately linear. It seems like the best you can do is a convex curve. May 10, 2013 at 5:02
• In general, "distance" is rarely a useful concept over finite fields, as far as I know. What are you using this for? Is distance really accurate? May 10, 2013 at 5:04
• I don't know what a sparse projection is, but why not use a nonlinear projection? I.e., find a point in the (random) subspace that is closest in Hamming distance? May 10, 2013 at 5:06
• How can scaling help? $\{1,2,\dots, N\}$ embeds isometrically into $F_2^N$, while in $F_2^n$ there are only $n$ distances. Every finite subset of $L_1$ embeds into $F_1^N$ with arbitrarily small distortion (allowing scaling, of course) if $N$ is sufficiently large, so you are asking more than having $m$ element subsets of $L_1$ embed into $\ell_1^n$ with $n$ small relative to $m$. Here there are negative results due to Brinkman-Charikar (simplified by Lee-Naor and further simplified by Schechtman and me). Only recently was it proved that $m$ element subsets of $L_1$ embed... May 10, 2013 at 5:34