An Elementary Proof of a Theorem of Johnson and Lindenstrauss

Sanjoy Dasgupta; Anupam Gupta

doi:10.1002/rsa.10073

An Elementary Proof of a Theorem of Johnson and Lindenstrauss

Sanjoy Dasgupta, Anupam Gupta

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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/ε ²)-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 language	English (US)
Pages (from-to)	60-65
Number of pages	6
Journal	Random Structures and Algorithms
Volume	22
Issue number	1
DOIs	https://doi.org/10.1002/rsa.10073
State	Published - Jan 2003

ASJC Scopus subject areas

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

Access to Document

10.1002/rsa.10073

Cite this

@article{446f4f4a5c084ec2ac49d478e52505da,

title = "An Elementary Proof of a Theorem of Johnson and Lindenstrauss",

abstract = "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.",

author = "Sanjoy Dasgupta and Anupam Gupta",

year = "2003",

month = jan,

doi = "10.1002/rsa.10073",

language = "English (US)",

volume = "22",

pages = "60--65",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "1",

}

TY - JOUR

T1 - An Elementary Proof of a Theorem of Johnson and Lindenstrauss

AU - Dasgupta, Sanjoy

AU - Gupta, Anupam

PY - 2003/1

Y1 - 2003/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0037236821&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037236821&partnerID=8YFLogxK

U2 - 10.1002/rsa.10073

DO - 10.1002/rsa.10073

M3 - Article

AN - SCOPUS:0037236821

SN - 1042-9832

VL - 22

SP - 60

EP - 65

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 1

ER -

An Elementary Proof of a Theorem of Johnson and Lindenstrauss

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this