Johnson-Lindenstrauss lemma

edit

The Johnson-Lindenstrauss lemma asserts that a set of n points in any high dimensional Euclidean space can be mapped down into an   dimensional Euclidean space such that the distance between any two points changes by only a factor of   for any  .

Introduction

edit

Johnson and Lindenstrauss {cite} proved a fundamental mathematical result: any   point set in any Euclidean space can be embedded in   dimensions without distorting the distances between any pair of points by more than a factor of  , for any  . The original proof of Johnson and Lindenstrauss was much simplified by Frankl and Maehara {cite}, using geometric insights and refined approximation techniques.

Proof

edit

Suppose we have a set of    -dimensional points   and we map them down to   dimensions, for appropriate constant  . Define   as the linear map, that is if  , then  . For example   could be a   matrix.

The general proof framework

All known proofs of the Johnson-Lindenstrauss lemma proceed according to the following scheme: For given   and an appropriate  , one defines a suitable probability distribution   on the set of all linear maps  . Then one proves the following statement:

Statement: If any   is a random linear mapping drown from the distribution  , then for every vector   we have

 

Having established this statement for the considered distribution  , the JL result follows easily: We choose   at random according to F. Then for every  , using linearity of   and the above Statement with  , we get that   fails to satisfy   with probability at most  . Consequently, the probability that any of the   pairwise distances is distorted by   by more than   is at most  . Therefore, a random   works with probability at least  .

References

edit
  • S. Dasgupta and A. Gupta, An elementary proof of the Johnson-Lindenstrauss lemma, Tech. Rep. TR-99-06, Intl. Comput. Sci. Inst., Berkeley, CA, 1999.
  • W. Johnson and J. Lindenstrauss. Extensions of Lipschitz maps into a Hilbert space. Contemporary Mathematics, 26:189--206, 1984.

Fast monte-carlo algorithms for MM

edit

Given an   matrix   and an   matrix  , we present 2 simple and intuitive algorithms to compute an approximation P to the product  , with provable bounds for the norm of the "error matrix"  . Both algorithms run in   time. In both algorithms, we randomly pick   columns of A to form an   matrix S and the corresponding rows of B to form an   matrix R. After scaling the columns of S and the rows of R, we multiply them together to obtain our approximation P . The choice of the probability distribution we use for picking the columns of A and the scaling are the crucial features which enable us to give fairly elementary proofs of the error bounds. Our rest algorithm can be implemented without storing the matrices A and B in Random Access Memory, provided we can make two passes through the matrices (stored in external memory). The second algorithm has a smaller bound on the 2-norm of the error matrix, but requires storage of A and B in RAM. We also present a fast algorithm that \describes" P as a sum of rank one matrices if B = A

Boxes

edit
elΜητρική γλώσσα αυτού του χρήστη είναι η ελληνική.
 Wikimedia Commons has a User Page for Zmoboros
 This user strives to maintain a policy of neutrality on controversial issues.
 This user has been helping the Internet not suck since 16:22, 1 July 2005.
1RRThis user prefers discussing changes on the talk page rather than engaging in an edit war.
 This editor is not an administrator and does not wish to be one.
  This user is a member of WikiProject Eastern Orthodoxy.
 This user is a member of Greek and Turkish WCB 
 This user comes from the Balkans.
 This user loves the poetry of Constantine P. Cavafy.
  This user is a luxembourgist.
 This user wants to stop
global warming.
 This user is in love with his girlfriend.
  This user has a website, which can be found here.
 
This user maintains a blog at Black Cat, Red Cat.
 
 This user contributes using Debian GNU/Linux.
 This user contributes with the KDE desktop environment.
xkcdThis user is a reader of the xkcd webcomic.
CThis user can program in C.
JavaThis user can program in Java.
ocaml-This user can program in OCaml.
  This user is a Greek Wikipedian or is a Wikipedian living in Greece.

There are things particularly relevant to Greek-based Wikipedians at the Greek Wikipedians' notice board.

Please feel free to help us improve Greek related articles in Wikipedia!