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

-

The problem with Hamming distance is that it's bounded above by N, so if you have a subset of F_2^N with Hamming distances in that range, you're not going to be able to embed it in 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 R^N into R^n in such a way that

d(f(x),f(y)) ~ (n/N)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? –  Dustin G. Mixon May 10 '13 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. –  Will Sawin May 10 '13 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? –  Will Sawin May 10 '13 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? –  Dustin G. Mixon May 10 '13 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... –  Bill Johnson May 10 '13 at 5:34