On the impossibility of dimension reduction in l1

ABSTRACT

The Johnson--Lindenstrauss lemma shows that any n points in Euclidean space (i.e., ℝⁿ with distances measured under the ℓ2 norm) may be mapped down to O((log n)/ε²) dimensions such that no pairwise distance is distorted by more than a (1 + ε) factor. Determining whether such dimension reduction is possible in ℓ1 has been an intriguing open question. We show strong lower bounds for general dimension reduction in ℓ1. We give an explicit family of n points in ℓ1 such that any embedding with constant distortion D requires n^Ω(1/D2) dimensions. This proves that there is no analog of the Johnson--Lindenstrauss lemma for ℓ1; in fact, embedding with any constant distortion requires n^Ω(1) dimensions. Further, embedding the points into ℓ1 with (1+ε) distortion requires n^{½−O(ε log(1/ε))} dimensions. Our proof establishes this lower bound for shortest path metrics of series-parallel graphs. We make extensive use of linear programming and duality in devising our bounds. We expect that the tools and techniques we develop will be useful for future investigations of embeddings into ℓ1.

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: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545 ]
• 3: Arora Sanjeev , Ravi Kannan, Learning mixtures of arbitrary gaussians, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.247-257, July 2001, Hersonissos, Greece [doi>10.1145/380752.380808]
• 4: Rosa I. Arriaga , Santosh Vempala, An Algorithmic Theory of Learning: Robust Concepts and Random Projection, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.616, October 17-18, 1999
• 5: Ball, K. 1990. Isometric embedding in lp-spaces. Europ. J. Combinat. 11, 305--311.
• 6: Bourgain, J. 1985. On Lipschitz embedding of finite metric spaces into Hilbert space. Isr. J. Math. 52, 46--52.
• 7: 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
• 8: Sanjoy Dasgupta, Learning Mixtures of Gaussians, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.634, October 17-18, 1999
• 9: Dasgupta, S., and Gupta, A. 1999. An elementary proof of the Johnson--Lindenstrauss lemma. Tech. Rep. TR-99-06, International Computer Science Institute, UC Berkeley.
• 10: de Reyna, J. A., and Rodriguez-Piazza, L. 1992. Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces. Isr. J. Math. 79, 103--111.
• 11: Deza, M., and Laurent, M. 1997. Geometry of Cuts and Metrics. Springer-Verlag, New York.
• 12: P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
• 13: Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Cuts, Trees and ℓ₁-Embeddings of Graphs*, Combinatorica, v.24 n.2, p.233-269, April 2004 [doi>10.1007/s00493-004-0015-x]
• 14: 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
• 15: 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
• 16: 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
• 17: 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]
• 18: Johnson, W., and Lindenstrauss, J. 1984. Extensions of Lipschitz mapping into Hilbert space. Contemp. Math. 26, 189--206.
• 19: 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]
• 20: Lee, J., and Naor, A. 2004. Embedding the diamond graph in lp and dimension reduction in l1. Geomet. Funct. Anal. 14, 4 (Aug.), 745--474.
• 21: Linial, N. 2002. Finite metric spaces---combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians III. 573--586.
• 22: Linial, N., London, E., and Rabinovich, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 215--245.
• 23: Matoušek, J. 1996. On the distortion required for embedding finite metric spaces into normed spaces. Isr. J. Math. 93, 333--344.
• 24: Matoušek, J. 2002. Chapter 15: Embedding finite metric spaces into euclidean spaces. Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer-Verlag.
• 25: Ilan Newman , Yuri Rabinovich, A lower bound on the distortion of embedding planar metrics into Euclidean space, Proceedings of the eighteenth annual symposium on Computational geometry, p.94-96, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513412]
• 26: R. Ostrovsky , Y. Rabani, Polynomial time approximation schemes for geometric k-clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.349, November 12-14, 2000
• 27: Satish Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the fifteenth annual symposium on Computational geometry, p.300-306, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304983]
• 28: Schechtman, G. 1987. More on embedding subspaces of Lp in ℓnr. Composi. Math. 61, 2, 159--169.
• 29: Talagrand, M. 1990. Embedding subspaces of L1 into ℓn1. Proceedings of the American Mathetmatical Society, vol. 108, 2, 363--369.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      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

General Terms:
Algorithms, Theory

Keywords:
Metric spaces, dimension reduction, embedding