This is an announcement for the paper "A simple construction of almost-Euclidean subspaces of $\ell_1^N$ via tensor products" by Piotr Indyk and Stanislaw Szarek.

Abstract: 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 arbitrarily small distortions, or "almost Euclidean" subspaces.

Archive classification: math.MG math.FA

Mathematics Subject Classification: 46B25, 52A21, 68P30

Remarks: 10 pages

The source file(s), tensoring3e.tex: 37038 bytes, is(are) stored in gzipped form as 1001.0041.gz with size 13kb. The corresponding postcript file has gzipped size 99kb.

Submitted from: szarek@cwru.edu

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/1001.0041

or

http://arXiv.org/abs/1001.0041

or by email in unzipped form by transmitting an empty message with subject line

uget 1001.0041

or in gzipped form by using subject line

get 1001.0041

to: math@arXiv.org.