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

preprint2010arXivOpen access

Abstract

It has been known since 1970's that the N-dimensional ℓ1\ell_1-space contains nearly Euclidean subspaces whose dimension is Ω(N)Ω(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>0a > 0, allows to exhibit nearly Euclidean Ω(N)Ω(N)-dimensional subspaces of ℓ1N\ell_1^N while using only NaN^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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.