10
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
7
  • $\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$ May 10, 2013 at 3:38
  • 2
    $\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, 2013 at 5:02
  • 1
    $\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, 2013 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$ May 10, 2013 at 5:06
  • 4
    $\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$ May 10, 2013 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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