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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Dustin G. Mixon
    Commented 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
    Commented 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
    Commented 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$
    – Dustin G. Mixon
    Commented 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$
    – Bill Johnson
    Commented May 10, 2013 at 5:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .