In mathematics, the Johnson–Lindenstrauss lemma is a result named after William B. Johnson and Joram Lindenstrauss 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 (see vector space model for the case of text). 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
in order to preserve the distances between all pair of points. See 4.
Given 0 < ε < 1, a set X of m points in RN, and a number n > 8 ln(m) / ε 2, there is a linear map ƒ : RN → Rn such that
for all u, v ∈ X.
One proof of the lemma takes ƒ to be a suitable multiple of the orthogonal projection onto a random subspace of dimension n in RN, and exploits the phenomenon of concentration of measure.
Obviously an orthogonal projection will, in general, reduce the average distance between points, but the lemma can be viewed as dealing with relative distances, which do not change under scaling. In a nutshell, you roll the dice and obtain a random projection, which will reduce the average distance, and then you scale up the distances so that the average distance returns to its previous value. If you keep rolling the dice, you will, in polynomial random time, find a projection for which the (scaled) distances satisfy the lemma.
A related lemma is the distributional JL lemma. This lemma states that for any 0<ε,δ<1/2 and positive integer d, there exists a distribution over Rk x d, from which the matrix A is drawn such that for k = O(ε−2log(1/δ)) and for any unit-length vector x ∈ Rd, the claim below holds.
One can obtain the JL lemma from the distributional version by setting and for some pair u,v both in X. Then the JL lemma follows by a union bound over all such pairs.
Speeding up the JL Transform
Given A, computing the matrix vector product takes O(kd) time. There has been a lot of work in coming up with distributions for which the matrix vector product can be computed in less than O(kd) time. There are two major lines of work. The first, Fast Johnson Lindenstrauss Transform (FJLT), was introduced by Ailon and Chazelle in 2006. Another approach is to build a distribution supported over matrices that are sparse.
- For instance, writing about nearest neighbor search in high-dimensional data sets, Jon Kleinberg writes: "The more sophisticated algorithms typically achieve a query time that is logarithmic in n at the expense of an exponential dependence on the dimension d; indeed, even the average case analysis of heuristics such as k-d trees reveal an exponential dependence on d in the query time. Kleinberg, Jon M. (1997), "Two Algorithms for Nearest-neighbor Search in High Dimensions", Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC '97, New York, NY, USA: ACM, pp. 599–608, doi:10.1145/258533.258653, ISBN 0-89791-888-6.
- Johnson, William B.; Lindenstrauss, Joram (1984). "Conference in Modern Analysis and Probability (New Haven, Conn., 1982)". Contemporary Mathematics 26. Providence, RI: American Mathematical Society. pp. 189–206. doi:10.1090/conm/026/737400. MR 737400.
- Ailon, Nir.; Chazelle, Benard (2006). "Proceedings of the 38th ACM Symposium on Theory of Computing(STOC)".
- Kane, Daniel; Nelson, Jelani (2014). "Sparser Johnson-Lindenstrauss Transforms". Journal of the ACM 61 (1). doi:10.1145/2559902. Journal version of a paper previously appearing at SODA 2012.
- Johnson, William B.; Lindenstrauss, Joram (1984), "Extensions of Lipschitz mappings into a Hilbert space", Conference in Modern Analysis and Probability (New Haven, Conn., 1982), Contemporary Mathematics 26, Providence, RI: American Mathematical Society, pp. 189–206, doi:10.1090/conm/026/737400, MR 737400.
- Dasgupta, Sanjoy; Gupta, Anupam (2003), "An elementary proof of a theorem of Johnson and Lindenstrauss" (PDF), Random Structures & Algorithms 22 (1): 60–65, doi:10.1002/rsa.10073, MR 1943859.
- Achlioptas, Dimitris (2003), "Database-friendly random projections: Johnson-Lindenstrauss with binary coins", Journal of Computer and System Sciences 66 (4): 671–687, doi:10.1016/S0022-0000(03)00025-4, MR 2005771. Journal version of a paper previously appearing at PODC 2001.
- Baraniuk, Richard; Davenport, Mark; DeVore, Ronald; Wakin, Michael (2008), "A simple proof of the restricted isometry property for random matrices" (PDF), Constructive Approximation 28 (3): 253–263, doi:10.1007/s00365-007-9003-x, MR 2453366.
- Alon, Noga (2003), "Problems and results in extremal combinatorics. I" (PDF), Discrete Mathematics 273 (1-3): 31–53, doi:10.1016/S0012-365X(03)00227-9, MR 2025940.