Almost Euclidean subspaces of \ell_1^N via expander codes

Details Almost Euclidean subspaces of \ell_1^N via expander codes Almost Euclidean subspaces of \ell_1^N via expander codes

2007-09-06

arxiv.org/abs/0709.0887v2

Mathematics

Metric Geometry

Scientific paper

We give an explicit (in particular, deterministic polynomial time) construction of subspaces X of R^N of dimension (1-o(1))N such that for every element x in X, |x|_1 and N^{1/2} |x|_2 are equivalent up to a factor of (log N)^{log log log N}. If we are allowed to use N^{o(1)} random bits, this factor can be improved to poly(log N). Our construction makes use of unbalanced bipartite graphs to impose local linear constraints on vectors in the subspace, and our analysis relies on expansion properties of the graph. This is inspired by similar constructions of error-correcting codes.

Affiliated with

Also associated with

No associations

Rating

Almost Euclidean subspaces of \ell_1^N via expander codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Almost Euclidean subspaces of \ell_1^N via expander codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Almost Euclidean subspaces of \ell_1^N via expander codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-658032