Timeline for A Johnson-Lindenstrauss lemma for finite fields?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jun 5, 2020 at 20:43 | history | suggested | A.2 | CC BY-SA 4.0 |
improved formatting.
|
| Jun 5, 2020 at 20:13 | review | Suggested edits | |||
| S Jun 5, 2020 at 20:43 | |||||
| May 10, 2013 at 6:13 | comment | added | Will Sawin | @Dustin: I mean just use a projection which, written in coordinates, is a sparse matrix. I don't know what a nonlinear projection is. | |
| May 10, 2013 at 5:35 | comment | added | Bill Johnson |
into $\ell_1^n$ with $n \le \delta m$ with distortion depending only on $\delta$.
|
|
| May 10, 2013 at 5:34 | comment | added | Bill Johnson |
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:06 | comment | added | Dustin G. Mixon | 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:04 | comment | added | Will Sawin | 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:02 | comment | added | Will Sawin | 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 3:38 | comment | added | Dustin G. Mixon | 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 0:23 | history | answered | JSE | CC BY-SA 3.0 |