An elementary proof of a theorem of Johnson and Lindenstrauss. (English) Zbl 1018.51010

Summary: A result of W. B. Johnson and J. Lindenstrauss [Contemp. Math. 26, 189-206 (1984; Zbl 0539.46017)] shows that a set of \(n\) points in high dimensional Euclidean space can be mapped into an \(O(\log n/ \varepsilon^2)\)-dimensional Euclidean space such that the distance between any two points changes by only a factor of \((1\pm \varepsilon)\). In this note, we prove this theorem using elementary probabilistic techniques.


51K05 General theory of distance geometry
68W20 Randomized algorithms


Zbl 0539.46017
Full Text: DOI


[1] Problems and results in extremal combinatorics, Part I, unpublished manuscript.
[2] Database friendly random projections, Proc 20th ACM Symp Principles of Database Systems, Santa Barbara, CA, 2001, 274-281.
[3] and An algorithmic theory of learning: Robust concepts and random projection, Proc 40th Annu IEEE Symp Foundations of Computer Science, New York, NY, 1999, pp. 616-623.
[4] Chernoff, Ann Math Stat 23 pp 493– (1952)
[5] Learning mixtures of Gaussians, Proc 40th Annu IEEE Symp Foundations of Computer Science, New York, NY, 1999, pp. 634-644.
[6] and Derandomized dimensionality reduction with applications, Proc 13th Annu ACM SIAM Symp Discrete Algorithms, San Francisco, CA, 2002, pp. 705-712. · Zbl 1093.68668
[7] Frankl, J Combin Theory Ser B 44 pp 355– (1988)
[8] Frankl, Ann Inst Stat Math 42 pp 463– (1990)
[9] Hoeffding, J Am Stat Assoc 58 pp 13– (1963)
[10] and Approximate nearest neighbors: Towards removing the curse of dimensionality, Proc 30th Annu ACM Symp Theory of Computing, Dallas, TX, 1998, pp. 604-613. · Zbl 1029.68541
[11] Johnson, Contemp Math 26 pp 189– (1984)
[12] Linial, Combinatorica 15 pp 215– (1995)
[13] Algorithmic derandomization using complexity theory, Proc 34th Annu ACM Symp Theory of Computing, Montréal, Canada, 2002, pp. 619-626. · Zbl 1192.68303
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.