Jump to content

User:Zmoboros

From Wikipedia, the free encyclopedia

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 studies at the National Technical University of Athens.
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.
KDEThis 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.
View of Greece 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!