An elementary proof of a theorem of Johnson and Lindenstrauss

被引：574

作者：

Dasgupta, S

Gupta, A

机构：

[1] Lucent Bell Labs, Murray Hill, NJ 07974 USA

[2] AT&T Labs Res, Florham Pk, NJ 07932 USA

来源：

RANDOM STRUCTURES & ALGORITHMS | 2003年 / 22卷 / 01期

关键词：

D O I：

10.1002/rsa.10073

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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/epsilon(2))-dimensional Euclidean space such that the distance between any two points changes by only a factor of (1 +/- epsilon). In this note, we prove this theorem using elementary probabilistic techniques. (C) 2002 Wiley Periodicals. Inc.

引用

页码：60 / 65

页数：6

共 13 条

[1]

Achlioptas D., 2001, P 20 ACM SIGMOD SIGA, P274, DOI DOI 10.1145/375551.375608

[2]

ALON N, UNPUB PROBLEMS RES 1

[3]

[Anonymous], 1984, CONTEMP MATH

[4]

Arriaga R. I., 1999, P 40 ANN S FDN COMP, P616