An Elementary Proof of a Theorem of Johnson and Lindenstrauss

Sanjoy Dasgupta, Anupam Gupta

Research output: Contribution to journalArticlepeer-review


A result of Johnson and Lindenstrauss [13] shows that a set of n points in high dimensional Euclidean space can be mapped into an O(log n/ε 2)-dimensional Euclidean space such that the distance between any two points changes by only a factor of (1 ± ε). In this note, we prove this theorem using elementary probabilistic techniques.

Original languageEnglish (US)
Pages (from-to)60-65
Number of pages6
JournalRandom Structures and Algorithms
Issue number1
StatePublished - Jan 2003

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'An Elementary Proof of a Theorem of Johnson and Lindenstrauss'. Together they form a unique fingerprint.

Cite this