Uncertainty principles, extractors, and explicit embeddings of l2 into l1

ABSTRACT

We give an explicit construction of a constant distortion embedding F of l₂ⁿ into l₁^m, with m=n^1+o(1).As a bonus, our embedding also has good computational properties: for any input x, Fx can be computed in n^1+o(1) time.The previously known mappings required Ω(n²) evaluation time.

REFERENCES

• 1: Dimitris Achlioptas, Database-friendly random projections, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.274-281, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375608]
• 2: Nir Ailon , Bernard Chazelle, Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132597]
• 3: S. Artstein-Avidan and V.D. Milman. Logarithmic reduction of the level of randomness in some probabilistic geometric constructions. Journal of Functional Analysis, 235:297--329, 2006.
• 4: A.R. Calderbank, P.J. Cameron, W.M. Kantor, and J.J. Seidel. Z4-Kerdock codes, orthogonal spreads and extremal euclidean line-sets. Proceedings of the London Mathematical Society, 2000.
• 5: P.J. Cameron and J.J. Seidel. Quadratic forms over GF(2). Indag. Math, 1973.
• 6: E. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52:489 -- 509, 2006.
• 7: D. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289 -- 1306, 2006.
• 8: D. Donoho and X. Huo. Uncertainty principles and ideal atomic decomposition. Transactions on Information Theory, 47:2845--2862, 2001.
• 9: David L. Donoho , Philip B. Stark, Uncertainty principles and signal recovery, SIAM Journal on Applied Mathematics, v.49 n.3, p.906-931, June 1989 [doi>10.1137/0149053]
• 10: A. Dvoretzky. A theorem on convex bodies and applications to banach spaces. Proceedings of the National Academy of Sciences USA, 45:223--226, 1959.
• 11: T. Figiel, J. Lindenstrauss, and V.D. Milman. The dimension of almost spherical sections of convex bodies. Acta Mathematica, 139:53--94, 1977.
• 12: R. Gribonval and M. Nielsen. Sparse representations in unions of bases. IEEE Transactions on Information Theory, 2003.
• 13: V. Guruswami, C. Umans, and S. Vadhan. Extractors and condensers from univariate polynomials. IEEE Conference on Communication Complexity, 2007.
• 14: R.W. Heath, T. Strohmer, and A.J. Paulraj. On quasi-orthogonal signatures for CDMA systems. IEEE Transactions on Information Theory, 52:1217--1226, 2006.
• 15: Piotr Indyk, Dimensionality reduction techniques for proximity problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.371-378, January 09-11, 2000, San Francisco, California, United States
• 16: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 17: W.B. Johnson and G. Schechtman. Finite dimensional subspaces of l_p. In W.B. Johnson and JLindenstrauss, editors, Handbook of the Geometry of Banach Spaces, pages 837--870. Elsevier, 2001.
• 18: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Proceedings of 35th Annual IEEE Symposium on Foundations of Computer Science, pages 577--591, 1994.
• 19: Yu. Liubarskii and R. Vershynin. Uncertainty principles and vector quantization. Manuscript, 2006.
• 20: S. Lovett and S. Sodin. Almost euclidean sections of the n-dimensional cross-polytope using o(n) random bits. ECCC Report TR07-012, 2007.
• 21: J. Matousek. Collection of open problems on low-distortion embeddings of finite metric spaces. Available at http://kam.mff.cuni.cz/~matousek/metrop.ps.gz, 2004.
• 22: V. Milman. Topics in asymptotic geometric analysis. GAFA - Geometric and Functional Analysis, pages 792--815, 2000.
• 23: V.D. Milman. A new proof of the theorem of A. Dvoretzky on sections of convex bodies. Funct. Anal. Appl, 1971.
• 24: Ran Raz , Omer Reingold , Salil Vadhan, Extracting all the randomness and reducing the error in Trevisan's extractors, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.149-158, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301292]
• 25: Oded Regev , Ricky Rosen, Lattice problems and norm embeddings, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132581]
• 26: W. Rudin. Trigonometric series with gaps. J. Math. Mech., 9:203--227, 1960.
• 27: G. Schechtman. Random embeddings of euclidean spaces in sequence spaces. Israel J. Math., 40:187--192, 1981.
• 28: R. Shaltiel. Recent developments in extractors. In Current trends in theoretical computer science. The Challenge of the New Century. Vol 1: Algorithms and Complexity, 2004.
• 29: S. Szarek. Convexity, complexity and high dimensions. Proceedings of the International Congress of Mathematicians (manuscript available from the author's home page), 2006.
• 30: J. Tropp. Topics in sparse approximation. Ph.D. dissertation, Computational and Applied Mathematics, UT-Austin, 2004.
• 31: A. Wigderson and D. Zuckerman. Expanders that beat the eigenvalue bound: Explicit constructions and applications. Combinatorica, 1999.
• 32: W.K. Wooters and BD. Fields. Optimal state-determination by mutually unbiased measurements. Annals of Physics, 191:363--381, 1989.
• 33: David Zuckerman, Randomness-optimal oblivious sampling, Random Structures & Algorithms, v.11 n.4, p.345-367, Dec. 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms, Theory

Keywords:
extractors, norm embeddings, uncertainty principles