Skip to main content
edited tags
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286
Source Link
GWB
  • 301
  • 1
  • 3

Embedding a binary subspace to $l_2$ in a much lower dimension

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.