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.

  • $\begingroup$ 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? $\endgroup$ – Dustin G. Mixon May 10 '13 at 3:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Will Sawin May 10 '13 at 5:02
  • $\begingroup$ 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? $\endgroup$ – Will Sawin May 10 '13 at 5:04
  • $\begingroup$ 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? $\endgroup$ – Dustin G. Mixon May 10 '13 at 5:06
  • 3
    $\begingroup$ 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... $\endgroup$ – Bill Johnson May 10 '13 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.