Almost-Euclidean Subspaces of ℓ1N via Tensor Products: A Simple Approach to Randomness Reduction
Proceedings of the 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011.
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72179 https://orcid.org/0000-0002-7983-9524 |
| _version_ | 1811083413425225728 |
|---|---|
| author | Indyk, Piotr Szarek, Stanislaw |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Indyk, Piotr Szarek, Stanislaw |
| author_sort | Indyk, Piotr |
| collection | MIT |
| description | Proceedings of the 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. |
| first_indexed | 2024-09-23T12:32:40Z |
| format | Article |
| id | mit-1721.1/72179 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:32:40Z |
| publishDate | 2012 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/721792022-09-28T08:25:49Z Almost-Euclidean Subspaces of ℓ1N via Tensor Products: A Simple Approach to Randomness Reduction Indyk, Piotr Szarek, Stanislaw Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Indyk, Piotr Indyk, Piotr Proceedings of the 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. It has been known since 1970’s that the N-dimensional ℓ[subscript 1]-space contains almost 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 almost Euclidean Ω(N)-dimensional subspaces of ℓ[subscript 1][superscript N] while using only N γ 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. National Science Foundation (U.S.). (Grant number CCF-0728645) 2012-08-17T12:46:05Z 2012-08-17T12:46:05Z 2010-08 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-22934-3 http://hdl.handle.net/1721.1/72179 Indyk, Piotr, and Stanislaw Szarek. “Almost-Euclidean Subspaces of ℓ1N via Tensor Products: A Simple Approach to Randomness Reduction.” Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Ed. Maria Serna et al. (Lecture Notes in Computer Science Vol. 6302). Berlin, Heidelberg, 2010. 632–641. https://orcid.org/0000-0002-7983-9524 en_US http://dx.doi.org/10.1007/978-3-642-15369-3_47 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer-Verlag arXiv |
| spellingShingle | Indyk, Piotr Szarek, Stanislaw Almost-Euclidean Subspaces of ℓ1N via Tensor Products: A Simple Approach to Randomness Reduction |
| title | Almost-Euclidean Subspaces of ℓ1N via Tensor Products: A Simple Approach to Randomness Reduction |
| title_full | Almost-Euclidean Subspaces of ℓ1N via Tensor Products: A Simple Approach to Randomness Reduction |
| title_fullStr | Almost-Euclidean Subspaces of ℓ1N via Tensor Products: A Simple Approach to Randomness Reduction |
| title_full_unstemmed | Almost-Euclidean Subspaces of ℓ1N via Tensor Products: A Simple Approach to Randomness Reduction |
| title_short | Almost-Euclidean Subspaces of ℓ1N via Tensor Products: A Simple Approach to Randomness Reduction |
| title_sort | almost euclidean subspaces of l1n via tensor products a simple approach to randomness reduction |
| url | http://hdl.handle.net/1721.1/72179 https://orcid.org/0000-0002-7983-9524 |
| work_keys_str_mv | AT indykpiotr almosteuclideansubspacesofl1nviatensorproductsasimpleapproachtorandomnessreduction AT szarekstanislaw almosteuclideansubspacesofl1nviatensorproductsasimpleapproachtorandomnessreduction |