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

Dasgupta, Sanjoy; Gupta, Anupam

Random Struct. Algorithms 22, No. 1, 60-65 (2003).

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.

MSC:

51K05	General theory of distance geometry
68W20	Randomized algorithms

Keywords:

Euclidean space; distance

Citations:

Zbl 0539.46017

References:

[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