Almost-Euclidean subspaces of ${\ell }_1^N$ via tensor products: a simple approach to randomness reduction

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 "almost Euclidean" subspaces with arbitrarily small distortions.

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

References in corpus (2)

• Uncertainty Principles and Vector Quantization
• Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits

Cited by in corpus (3)

• From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking
• Metric and classical fidelity uncertainty relations for random unitary matrices
• Online codes for analog signals