2
$\begingroup$

I'm trying to find a way to embed a binary linear subspace of dimension $n$ (a linear code) to the Euclidian space while reducing the dimension significantly.

The subspace (or code) contains points on the Hamming cube with the $l_1$ norm. I tried considering the embedding which looks at the points of the subspace as points in the Euclidean space. Using the Johnson-Lindenstrauss lemma (and since there are $2^n$ points in the subspace), it's possible to reduce the dimension to $O(n/\epsilon^2)$, but this dimension is too big for what I'm looking for.

So my question is: is there a way to reduce the dimension of a n-dimensional binary linear subspace to dimension which is something like $O(\log n/\epsilon^2)$?

I thought about maybe looking at probabilisitic dimension reduction which promises the distances preserving in expectation or with high probability.

Also, other dimension reduction techniques for this types of binary linear subspaces in the $l_1$ norm, or embeddings to $l_2$ norm with low distortion for this kind of subspaces, could also be useful for what I'm looking for.

Improve this question
$\endgroup$
1
  • $\begingroup$ For bi-Lipschitz embedding it seems like too optimistic of a request. The doubling condition probably should be an obstacle for such an embedding. Also see Proposition 4 from N. Linial, E. London, and Y. Rabinovich. "The geometry of graphs and some of its algorithmic applications." $\endgroup$
    – Vladimir Zolotov
    Commented Nov 25, 2019 at 15:39

0

Reset to default

You must log in to answer this question.