Search Results for « Johnson-Lindenstrauss Lemma »

Abstract The Johnson–Lindenstrauss lemma asserts that an n ‐point set in any Euclidean space can be mapped to a Euclidean space of dimension k = O (ε ‐2 log n ) so that all distances are preserved up to a multiplicative factor between 1 − ε and 1 + ε. Known proofs obtain such a mapping as a linear map R n → R k with a suitable random matrix. We give a simple and self‐contained proof of a version of the Johnson–Lindenstrauss lemma that subsumes a basic versions by Indyk and Motwani and a version more suitable for efficient computations due to Achlioptas. (Another proof of this result, slightly different but in a similar spirit, was given independently by Indyk and Naor.) An even more general result was established by Klartag and Mendelson using considerably heavier machinery. Recently, Ailon and Chazelle showed, roughly speaking, that a good mapping can also be obtained by composing a suitable Fourier transform with a linear mapping that has a sparse random matrix M ; a mapping of this form can be evaluated very fast. In their result, the nonzero entries of M are normally distributed. We show that the nonzero entries can be chosen as random ± 1, which further speeds up the computation. We also discuss the case of embeddings into R k with the ℓ 1 norm. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008

Abstract The widely discussed and applied Johnson–Lindenstrauss (JL) Lemma has an existential form saying that for each set of data points Q in n -dimensional space, there exists a transformation f into an $$n'$$ n ′ -dimensional space ( $$n'<n$$ n ′ < n ) such that for each pair $$\mathbf {u},\mathbf {v} \in Q$$ u , v ∈ Q $$(1-\delta )\Vert \mathbf {u}-\mathbf {v}\Vert ^2 \le \Vert f(\mathbf {u})-f(\mathbf {v})\Vert ^2 \le (1+\delta )\Vert \mathbf {u}-\mathbf {v}\Vert ^2 $$ ( 1 - δ ) ‖ u - v ‖ 2 ≤ ‖ f ( u ) - f ( v ) ‖ 2 ≤ ( 1 + δ ) ‖ u - v ‖ 2 for a user-defined error parameter $$\delta $$ δ . Furthermore, it is asserted that with some finite probability the transformation f may be found as a random projection (with scaling) onto the $$n'$$ n ′ dimensional subspace so that after sufficiently many repetitions of random projection, f will be found with user-defined success rate $$1-\epsilon $$ 1 - ϵ . In this paper, we make a novel use of the JL Lemma. We prove a theorem stating that we can choose the target dimensionality in a random projection-type JL linear transformation in such a way that with probability $$1-\epsilon $$ 1 - ϵ all of data points from Q fall into predefined error range $$\delta $$ δ for any user-predefined failure probability $$\epsilon $$ ϵ when performing a single random projection. This result is important for applications such as data clustering where we want to have a priori dimensionality reducing transformation instead of attempting a (large) number of them, as with traditional Johnson–Lindenstrauss Lemma. Furthermore, we investigate an important issue whether or not the projection according to JL Lemma is really useful when conducting data processing, that is whether the solutions to the clustering in the projected space apply to the original space. In particular, we take a closer look at the k -means algorithm and prove that a good solution in the projected space is also a good solution in the original space. Furthermore, under proper assumptions local optima in the original space are also ones in the projected space. We investigate also a broader issue of preserving clusterability under JL Lemma projection. We define the conditions for which clusterability property of the original space is transmitted to the projected space, so that a broad class of clustering algorithms for the original space is applicable in the projected space.

Abstract We prove a variant of a Johnson‐Lindenstrauss lemma for matrices with circulant structure. This approach allows to minimize the randomness used, is easy to implement and provides good running times. The price to be paid is the higher dimension of the target space k = O (ε −2 log 3 n ) instead of the classical bound k = O (ε −2 log n ). © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011