Loading...
Please wait, while we are loading the content...
Similar Documents
Almost-Euclidean Subspaces of 1 N via Tensor Products : A Simple Approach to Randomness Reduction
| Content Provider | Semantic Scholar |
|---|---|
| Author | Indyk, Piotr Szarek, Stanislaw J. |
| Copyright Year | 2010 |
| Abstract | It has been known since 1970’s that the N-dimensional l1space contains nearly Euclidean subspaces whose dimension is Ω(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 γ > 0, allows us to exhibit nearly Euclidean Ω(N)dimensional subspaces of l1 while using only N γ random bits. Our results extend and complement (particularly) recent work by GuruswamiLee-Wigderson. Characteristic features of our approach include (1) simplicity (we use only tensor products) and (2) yielding almost Euclidean subspaces with arbitrarily small distortions. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://dspace.mit.edu/openaccess-disseminate/1721.1/72179 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
