Almost-Euclidean subspaces of $\ell_1^N$ via tensor products: a simple approach to randomness reduction

Details Almost-Euclidean subspaces of $\ell_1^N$ via tensor products: a simple approach to randomness reduction Almost-Euclidean subspaces of $\ell_1^N$ via tensor products: a simple approach to randomness reduction

2009-12-30

arxiv.org/abs/1001.0041v2

RANDOM 2010, LNCS 6302, Springer 2010, 632-641

Mathematics

Metric Geometry

11 pages; title change, abstract and references added, other minor changes

Scientific paper

10.1007/978-3-642-15369-3_47

It has been known since 1970's that the N-dimensional $\ell_1$-space contains nearly Euclidean subspaces whose dimension is $\Omega(N)$. However, proofs of existence of such subspaces were probabilistic, hence non-constructive, which made the results not-quite-suitable for subsequently discovered applications to high-dimensional nearest neighbor search, error-correcting codes over the reals, compressive sensing and other computational problems. In this paper we present a "low-tech" scheme which, for any $a > 0$, allows to exhibit nearly Euclidean $\Omega(N)$-dimensional subspaces of $\ell_1^N$ while using only $N^a$ random bits. Our results extend and complement (particularly) recent work by Guruswami-Lee-Wigderson. Characteristic features of our approach include (1) simplicity (we use only tensor products) and (2) yielding "almost Euclidean" subspaces with arbitrarily small distortions.

Affiliated with

Also associated with

No associations

Rating

Almost-Euclidean subspaces of $\ell_1^N$ via tensor products: a simple approach to randomness reduction 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 tensor products: a simple approach to randomness reduction, 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 tensor products: a simple approach to randomness reduction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-103842