The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite

ABSTRACT

Let X be a normed space that satisfies the Johnson-Lindenstrauss lemma (J--L lemma, in short) in the sense that for any integer n and any x₁,...,x_n ε X there exists a linear mapping L: X → F, where F ⊆ X is a linear subspace of dimension O(log n), such that

||x_i - x_j|| ≤ ||L(x_i) - L(x_j)|| ≤ O(1) · ||x_i - x_j||

for all i, j ε {1,..., n). We show that this implies that X is almost Euclidean in the following sense: Every n-dimensional subspace of X embeds into Hilbert space with distortion [EQUATION]. On the other hand, we show that there exists a normed space Y which satisfies the J-L lemma, but for every n there exists an n-dimensional subspace E_n ⊆ Y whose Euclidean distortion is at least 2^Ω(α(n)), where α is the inverse Ackermann function.

REFERENCES

• 1: 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]
• 2: Noga Alon , Haim Kaplan , Gabriel Nivasch , Micha Sharir , Shakhar Smorodinsky, Weak ε-nets and interval chains, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1194-1203, January 20-22, 2008, San Francisco, California
• 3: J. Arias-de Reyna and L. Rodríguez-Piazza. Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces. Israel J. Math., 79(1):103--111, 1992.
• 4: K. Ball. An elementary introduction to modern convex geometry. In Flavors of geometry, volume 31 of Math. Sci. Res. Inst. Publ., pages 1--58. Cambridge Univ. Press, Cambridge, 1997.
• 5: S. F. Bellenot. The Banach space T and the fast growing hierarchy from logic. Israel J. Math., 47(4):305--313, 1984.
• 6: Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.
• 7: J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1--2):46--52, 1985.
• 8: J. Bourgain, J. Lindenstrauss, and V. Milman. Approximation of zonoids by zonotopes. Acta Math., 162(1--2):73--141, 1989.
• 9: Bo Brinkman , Moses Charikar, On the impossibility of dimension reduction in l₁, Journal of the ACM (JACM), v.52 n.5, p.766-788, September 2005 [doi>10.1145/1089023.1089026]
• 10: P. G. Casazza, W. B. Johnson, and L. Tzafriri. On Tsirelson's space. Israel J. Math., 47(2--3):81--98, 1984.
• 11: P. G. Casazza and E. Odell. Tsirelson's space and minimal subspaces. In Texas functional analysis seminar 1982--1983 (Austin, Tex.), Longhorn Notes, pages 61--72. Univ. Texas Press, Austin, TX, 1983.
• 12: P. G. Casazza and T. J. Shura. Tsirel'son's space, volume 1363 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1989. With an appendix by J. Baker, O. Slotterbeck and R. Aron.
• 13: Moses Charikar , Amit Sahai, Dimension Reduction in the \ell _1 Norm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.551-560, November 16-19, 2002
• 14: B. S. Cirel'son. It is impossible to imbed 1_p of c₀ into an arbitrary Banach space. Funkcional. Anal. i Priložen., 8(2):57--60, 1974.
• 15: L. Danzer, B. Grünbaum, and V. Klee. Helly's theorem and its relatives. In Proc. Sympos. Pure Math., Vol. VII, pages 101--180. Amer. Math. Soc., Providence, R. I., 1963.
• 16: T. Figiel and W. B. Johnson. A uniformly convex Banach space which contains no l_p. Compositio Math., 29:179--190, 1974.
• 17: 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.
• 18: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 19: 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]
• 20: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 21: F. John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, pages 187--204. Interscience Publishers, Inc., New York, N. Y., 1948.
• 22: W. B. Johnson. A reflexive Banach space which is not sufficiently Euclidean. Studia Math., 55(2):201--205, 1976.
• 23: W. B. Johnson. Banach spaces all of whose subspaces have the approximation property. In Special topics of applied mathematics (Proc. Sem., Ges. Math. Datenverarb., Bonn, 1979), pages 15--26. North-Holland, Amsterdam, 1980.
• 24: W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemp. Math., pages 189--206. Amer. Math. Soc., Providence, RI, 1984.
• 25: W. B. Johnson, J. Lindenstrauss, and G. Schechtman. On Lipschitz embedding of finite metric spaces In low-dimensional normed spaces. In Geometrical aspects of functional analysis (1985/86), pages 177--184. Lecture Notes in Math., 1267, Springer, Berlin, 1987.
• 26: 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.
• 27: Jon M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.599-608, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258653]
• 28: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces, SIAM Journal on Computing, v.30 n.2, p.457-474, 2000 [doi>10.1137/S0097539798347177]
• 29: S. Kwapień. Isomorphic characterizations of inner product spaces by orthogonal series with vector valued coefficients. Studia Math., 44:583--595, 1972. Collection of articles honoring the completion by Antoni Zygmund of 50 years of scientific activity, VI.
• 30: James R. Lee , Manor Mendel , Assaf Naor, Metric structures in L1: dimension, snowflakes, and average distortion, European Journal of Combinatorics, v.26 n.8, p.1180-1190, November 2005 [doi>10.1016/j.ejc.2004.07.002]
• 31: J. R. Lee and A. Naor. Embedding the diamond graph in L_p and dimension reduction in L₁. Geom. Funct. Anal., 14(4):745--747, 2004.
• 32: J. Matoušek. Bi-Lipschitz embeddings into low-dimensional Euclidean spaces. Comment. Math. Univ. Carolin., 31(3):589--600, 1990.
• 33: J. Matoušek. On the distortion required for embedding finite metric spaces into normed spaces. Israel J. Math., 93:333--344, 1996.
• 34: N. J. Nielsen and N. Tomczak-Jaegermann. Banach lattices with property (H) and weak Hilbert spaces. Illinois J. Math., 36(3):345--371, 1992.
• 35: G. Pisier. Martingales with values in uniformly convex spaces. Israel J. Math., 20(3--4):326--350, 1975.
• 36: G. Pisier. Factorization of linear operators and geometry of Banach spaces, volume 60 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1986.
• 37: G. Pisier. The volume of convex bodies and Banach space geometry, volume 94 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1989.
• 38: G. Schechtman. More on embedding subspaces of L_p in lⁿ_r. Compositio Math., 61(2):159--169, 1987.
• 39: M. Talagrand. Embedding subspaces of L₁ into l^N₁. Proc. Amer. Math. Soc., 108(2):363--369, 1990.
• 40: N. Tomczak-Jaegermann. Computing 2-summing norm with few vectors. Ark. Mat., 17(2):273--277, 1979.
• 41: N. Tomczak-Jaegermann. The Banach-Mazur distance between symmetric spaces. Israel J. Math., 46(1--2):40--66, 1983.
• 42: N. Tomczak-Jaegermann. Banach-Mazur distances and finite-dimensional operator ideals, volume 38 of Pitman Monographs and Surveys in Pure and Applied Mathematics. Longman Scientific & Technical, Harlow, 1989.
• 43: S. S. Vempala. The random projection method. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 65. American Mathematical Society, Providence, RI, 2004. With a foreword by Christos H. Papadimitriou.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms