The Johnson-Lindenstrauss lemma asserts that a set of n points in any high dimensional Euclidean space can be mapped down into an ${\displaystyle O({\frac {logn}{\epsilon ^{2}}})}$ dimensional Euclidean space such that the distance between any two points changes by only a factor of ${\displaystyle (1+\epsilon )}$ for any ${\displaystyle 0<\epsilon <1}$ .

Introduction

Johnson and Lindenstrauss {cite} proved a fundamental mathematical result: any ${\displaystyle n}$ point set in any Euclidean space can be embedded in ${\displaystyle O(\log n/\epsilon ^{2})}$ dimensions without distorting the distances between any pair of points by more than a factor of ${\displaystyle (1+\epsilon )}$ , for any ${\displaystyle 0<\epsilon <1}$ . The original proof of Johnson and Lindenstrauss was much simplified by Frankl and Maehara {cite}, using geometric insights and refined approximation techniques.

Proof

Suppose we have a set of ${\displaystyle n}$ ${\displaystyle d}$ -dimensional points ${\displaystyle p_{1},p_{2},...,p_{n}}$ and we map them down to ${\displaystyle k=C{\frac {\log n}{\epsilon ^{2}}}\ll d}$ dimensions, for appropriate constant ${\displaystyle C>1}$ . Define ${\displaystyle T(.)}$ as the linear map, that is if ${\displaystyle x\in R^{d}}$ , then ${\displaystyle T(x)\in R^{k}}$ . For example ${\displaystyle T}$ could be a ${\displaystyle k\times d}$ matrix.

The general proof framework

All known proofs of the Johnson-Lindenstrauss lemma proceed according to the following scheme: For given ${\displaystyle n}$ and an appropriate ${\displaystyle k}$ , one defines a suitable probability distribution ${\displaystyle F}$ on the set of all linear maps ${\displaystyle T:R^{d}->R^{k}}$ . Then one proves the following statement:

Statement: If any ${\displaystyle T:R^{n}->R^{k}}$ is a random linear mapping drown from the distribution ${\displaystyle F}$ , then for every vector ${\displaystyle x\in R^{d}}$ we have

${\displaystyle Prob[(1-\epsilon )||x||\leq ||T(x)||\leq (1+\epsilon )||x||]\geq 1-{\frac {1}{n^{2}}}}$

Having established this statement for the considered distribution ${\displaystyle F}$ , the JL result follows easily: We choose ${\displaystyle T}$ at random according to F. Then for every ${\displaystyle i<j}$ , using linearity of ${\displaystyle T}$ and the above Statement with ${\displaystyle x=pi-pj}$ , we get that ${\displaystyle T}$ fails to satisfy ${\displaystyle (1-\epsilon )||p_{i}-p_{j}||\leq ||T(p_{i})-T(p_{j})||\leq (1+\epsilon )||p_{i}-p_{j}||}$ with probability at most ${\displaystyle {\frac {1}{n^{2}}}}$ . Consequently, the probability that any of the ${\displaystyle (n2)}$ pairwise distances is distorted by ${\displaystyle T}$ by more than ${\displaystyle 1+\epsilon }$ is at most ${\displaystyle (n2)/n^{2}<{\frac {1}{2}}}$ . Therefore, a random ${\displaystyle T}$ works with probability at least ${\displaystyle {\frac {1}{2}}}$ .

References

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

Given an ${\displaystyle m\times n}$ matrix ${\displaystyle A}$ and an ${\displaystyle n\times p}$ matrix ${\displaystyle B}$ ,we present 2 simple and intuitive algorithms to computean approximation P to the product ${\displaystyle AB}$ , with provablebounds for the norm of the "error matrix" ${\displaystyle P-A\times B}$ .Both algorithms run in ${\displaystyle O(mp+mn+np)}$ time. In bothalgorithms, we randomly pick ${\displaystyle s=O(1)}$ columns of A toform an ${\displaystyle m\times s}$ matrix S and the corresponding rows ofB to form an ${\displaystyle s\times p}$ matrix R. After scaling the columnsof S and the rows of R, we multiply them together toobtain our approximation P . The choice of the probabilitydistribution we use for picking the columns ofA and the scaling are the crucial features which enableus to give fairly elementary proofs of the error bounds.Our rest algorithm can be implemented without storingthe matrices A and B in Random Access Memory,provided we can make two passes through the matrices(stored in external memory). The second algorithm hasa smaller bound on the 2-norm of the error matrix, butrequires storage of A and B in RAM. We also presenta fast algorithm that \describes" P as a sum of rankone matrices if B = A

Boxes

This user is a member of WikiProject Eastern Orthodoxy.

This user is a luxembourgist.

This user has a website, which can be found here.

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!