Johnson–Lindenstrauss lemma

In mathematics, the Johnson–Lindenstrauss lemma is a result concerning low-distortion embeddings of points from high-dimensional into low-dimensional Euclidean space. The lemma states that a small set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are nearly preserved. The map used for the embedding is at least Lipschitz, and can even be taken to be an orthogonal projection.

The lemma has uses in compressed sensing, manifold learning, dimensionality reduction, and graph embedding. Much of the data stored and manipulated on computers, including text and images, can be represented as points in a high-dimensional space. However, the essential algorithms for working with such data tend to become bogged down very quickly as dimension increases. It is therefore desirable to reduce the dimensionality of the data in a way that preserves its relevant structure. The Johnson–Lindenstrauss lemma is a classic result in this vein.

Also the lemma is tight up to a factor log(1/"ε"), i.e. there exists a set of points of size "m" that needs dimension

: $Omegaleft(frac\{log(m)\}\{varepsilon^2log\; (1/varepsilon)\}\; ight)$

in order to preserve the distances between all pair of points. See 4.

Lemma

Given 0 < "ε" < 1, a set "X" of "m" points in R^"N", and a number "n" > "n"₀ = O(ln("m")/"ε"²), there is a Lipschitz function ƒ : R^"N" → R^"n" such that

: $(1-varepsilon)||u-v||\_\{2\}\; leq\; ||f(u)\; -\; f(v)||\_\{2\}\; leq\; (1+varepsilon)||u-v||\_\{2\}$

for all $u,v\; in\; X$.

One proof of the lemma takes ƒ to be a projection onto a random subspace of dimension "n", and exploits the phenomenon of concentration of measure.

References

* W. Johnson and J. Lindenstrauss. Extensions of Lipschitz maps into a Hilbert space. Contemporary Mathematics, 26:189–206, 1984.
* S. Dasgupta and A. Gupta, [http://www-cse.ucsd.edu/~dasgupta/papers/jl-tr.ps "An elementary proof of the Johnson–Lindenstrauss lemma"] , Technical report 99–006, U. C. Berkeley, March 1999.
* D. Achlioptas, [http://www.sigmod.org/pods/proc01/online/p93.pdf "Database-friendly random projections"] , In: Proc. 20-th Annual ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, (2001), pp. 274–281.
* R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, [http://dsp.rice.edu/cs/jlcs-v03.pdf "The Johnson–Lindenstrauss Lemma Meets Compressed Sensing"]
* N. Alon, [http://www.math.tau.ac.il/~nogaa/PDFS/extremal1.pdf "Problems and results in extremal combinatorics"] , I, Discrete Math. 273 (2003), 31–53.