Almost Euclidean subspaces of ℓN1 via expander codes

ABSTRACT

We give an explicit (in particular, deterministic polynomial time) construction of subspaces X ⊆ ℝ^N of dimension (1 - o(1))N such that for every x ∈ X, {display equation}.

If we are allowed to use N^{1/log log N} ≤ N°⁽¹⁾ random bits and dim(X) ≥ (1 - η)N for any fixed constant η, the lower bound can be further improved to (log N)^-°(1) √N||x||₂. Our construction makes use of unbalanced bipartite graphs to impose local linear constraints on vectors in the subspace, and our analysis relies on expansion properties of the graph. This is inspired by similar constructions of error-correcting codes.

REFERENCES

• 1: N. Alon and F. R. K. Chung. Explicit construction of linear sized tolerant networks. In Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), volume 72, pages 15--19, 1988.
• 2: S. Artstein-Avidan and V. D. Milman. Logarithmic reduction of the level of randomness in some probabilistic geometric constructions. J. Funct. Anal., 235(1):297--329, 2006.
• 3: Boaz Barak , Russell Impagliazzo , Avi Wigderson, Extracting Randomness Using Few Independent Sources, SIAM Journal on Computing, v.36 n.4, p.1095-1118, December 2006 [doi>10.1137/S0097539705447141]
• 4: Boaz Barak , Guy Kindler , Ronen Shaltiel , Benny Sudakov , Avi Wigderson, Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060592]
• 5: P. J. Cameron and J. J. Seidel. Quadratic forms over GF(2). Indag. Math., 35:1--8, 1973.
• 6: Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510003]
• 7: Ronald A. DeVore, Deterministic constructions of compressed sensing matrices, Journal of Complexity, v.23 n.4-6, p.918-925, August, 2007 [doi>10.1016/j.jco.2007.04.002]
• 8: D. L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52:1289--1306, 2006.
• 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: P. Erdös. A theorem of Sylvester and Schur. J. London Math. Soc., 9:282--288, 1934.
• 11: T. Figiel, J. Lindenstrauss, and V. D. Milman. The dimension of almost spherical sections of convex bodies. Acta Math., 139(1--2):53--94, 1977.
• 12: R. G. Gallager. Low-Density Parity-Check Codes. MIT Press, 1963.
• 13: A. Garnaev and E. D. Gluskin. The widths of Euclidean balls. Doklady An. SSSR., 277:1048--1052, 1984.
• 14: Venkatesan Guruswami , Christopher Umans , Salil Vadhan, Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.96-108, June 13-March 16, 2007 [doi>10.1109/CCC.2007.38]
• 15: S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.), 43(4):439--561, 2006.
• 16: Piotr Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation, Journal of the ACM (JACM), v.53 n.3, p.307-323, May 2006 [doi>10.1145/1147954.1147955]
• 17: Piotr Indyk, Explicit constructions for compressed sensing of sparse signals, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.30-33, January 20-22, 2008, San Francisco, California
• 18: Piotr Indyk, Uncertainty principles, extractors, and explicit embeddings of l2 into l1, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250881]
• 19: W. B. Johnson and G. Schechtman. Finite dimensional subspaces of L_p. In Handbook of the geometry of Banach spaces, Vol. I, pages 837--870. North-Holland, Amsterdam, 2001.
• 20: B. S. Kashin. The widths of certain finite-dimensional sets and classes of smooth functions. Izv. Akad. Nauk SSSR Ser. Mat., 41(2):334--351, 478, 1977.
• 21: B. S. Kashin and V. N. Temlyakov. A remark on compressed sensing. Available at http://www.dsp.ece.rice.edu/cs/KT2007.pdf, 2007.
• 22: A. M. Kerdock. A class of low-rate nonlinear binary codes. Inform. Control, 20:182--187, 1972.
• 23: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 24: S. Lovett and S. Sodin. Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits. Electronic Colloquium on Computational Complexity, Report TR07--012, 2007.
• 25: A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261--277, 1988.
• 26: F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, 1977.
• 27: V. Milman. Topics in asymptotic geometric analysis. Geom. Funct. Anal., (Special Volume, Part II):792--815, 2000. GAFA 2000 (Tel Aviv, 1999).
• 28: Jaikumar Radhakrishnan , Amnon Ta-Shma, Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators, SIAM Journal on Discrete Mathematics, v.13 n.1, p.2-24, Jan. 2000 [doi>10.1137/S0895480197329508]
• 29: W. Rudin. Trigonometric series with gaps. J. Math. Mech., 9:203--227, 1960.
• 30: G. Schechtman. Random embeddings of Euclidean spaces in sequence spaces. Israel J. Math., 40(2):187--192, 1981.
• 31: C. Schütt. Entropy numbers of diagonal operators between symmetric Banach spaces. J. Approx. Theory, 40(2):121--128, 1984.
• 32: M. Sipser and D. A. Spielman. Expander codes. IEEE Trans. Inform. Theory, 42(6, part 1):1710--1722, 1996. Codes and complexity.
• 33: S. Szarek. Convexity, complexity, and high dimensions. In International Congress of Mathematicians. Vol. II, pages 1599--1621. Eur. Math. Soc., Zürich, 2006.
• 34: R. M. Tanner. A recursive approach to low complexity codes. IEEE Transactions on Information Theory, 27(5):533--547, 1981.
• 35: T. Tao and V. Vu. Additive combinatorics, volume 105 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2006.
• 36: G. Zémor. On expander codes. IEEE Transactions on Information Theory, 47(2):835--837, 2001.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields; Computations on polynomials
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
      G.2.3 Applications

General Terms:
Algorithms, Design, Theory