For and any points in a Hilbert space, there is a linear map into Euclidean dimension that multiplies every pairwise distance by a factor between and .
The unit sphere of an -dimensional normed space has a -net of size at most . If on this net and , then
If has independent Rademacher entries, then for fixed and ,Applying a union bound to all pairwise differences embeds fixed points into dimension while preserving every squared distance within a factor with probability at least .
For a standard normal variable and ,The exponential Markov inequality consequently gives Gaussian concentration for averages of independent copies of .
The random matrixsatisfiesA net argument shows that permits a linear embedding of distortion below .
Every -point metric space embeds into with distortion . Apply the Bourgain embedding theorem, reduce its Euclidean dimension to with the Johnson–Lindenstrauss lemma, and use an Almost-isometric Gaussian embedding from l2 into l1.
Articles by others on the same topic
The Johnson–Lindenstrauss (JL) lemma is a result in mathematics and computer science that states that a set of high-dimensional points can be embedded into a lower-dimensional space in such a way that the distances between the points are approximately preserved. More formally, the lemma asserts that for any set of points in a high-dimensional Euclidean space, there exists a mapping to a lower-dimensional Euclidean space that maintains the pairwise distances between points within a small factor.