An elementary proof of a theorem of Johnson and Lindenstrauss

被引：556

作者：

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
[5] A MEASURE OF ASYMPTOTIC EFFICIENCY FOR TESTS OF A HYPOTHESIS BASED ON THE SUM OF OBSERVATIONS
CHERNOFF, H
[J]. ANNALS OF MATHEMATICAL STATISTICS, 1952, 23 (04): : 493 - 507
[6] Dasgupta S., 1999, P 40 ANN S FDN COMP, P634, DOI DOI 10.1109/SFFCS.1999.814639
[7] Engebretsen L, 2002, SIAM PROC S, P705
[8] THE JOHNSON-LINDENSTRAUSS LEMMA AND THE SPHERICITY OF SOME GRAPHS
FRANKL, P
MAEHARA, H
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1988, 44 (03) : 355 - 362
[9] SOME GEOMETRIC APPLICATIONS OF THE BETA DISTRIBUTION
FRANKL, P
MAEHARA, H
[J]. ANNALS OF THE INSTITUTE OF STATISTICAL MATHEMATICS, 1990, 42 (03) : 463 - 474
[10] PROBABILITY-INEQUALITIES FOR SUMS OF BOUNDED RANDOM-VARIABLES
HOEFFDING, W
[J]. JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1963, 58 (301) : 13 - +

← 1 2 →