The Fast Johnson--Lindenstrauss Transform and Approximate Nearest Neighbors

By Nir Ailon, Bernard Chazelle. 2009

582 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

Citations in the corpus

Fastfood: Approximate Kernel Expansions in Loglinear Time (2014, methodology): “The initial HBd − 12 acts as an isometry that densiﬁes the input, as pioneered by Ailon and Chazelle (2009).”
Deep Fried Convnets (2014, background): “Ailon and Chazelle [2] introduced an alternative approach that is not only very efficient, but also preserves most of the desirable theoretical properties of random projections.”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, methodology): “The results can be further extended to (cid:96) s norm for s ∈ [1 , 2] .”
User-Friendly Tail Bounds for Sums of Random Matrices (2010, background): “We have encountered these issues in a wide range of problems from computational mathematics: smoothed analysis of Gaussian elimination [51]; semidefinite relaxation and rounding of quadratic maximization problems [38, 50]; construction of maps for dimensionality reduction [1]; matrix approximation b”
Practical and Optimal LSH for Angular Distance (2015, methodology): “This is similar to pseudo-random rotations used in the context of LSH [21], dimensionality reduction [17], or compressed sensing [22].”
Unifying Orthogonal Monte Carlo Methods (2019, methodology): “These matrices X T (typically with T ∈ { 1 , 2 , 3 } ) have been used recently in the context of dimensionality reduction (Choromanski et al., 2017) (see also (Ailon & Chazelle, 2009)), kernel approximation (Yu et al., 2016), and locality-sensitive hashing (Andoni et al., 2015).”
Are Transformers universal approximators of sequence-to-sequence functions? (2019, background): “The bi-linear projection layer (Gong et al., 2013) is motivated from the ability of random (Gaussian) matrices to map sparse differences to dense vectors (Ailon & Chazelle, 2009).”
Improved Analysis of the subsampled Randomized Hadamard Transform (2010, background): “The design of the SRHT may seem mysterious, but there are clear intuitions to support it [AC09].”
Fast approximation of matrix coherence and statistical leverage (2011, methodology): “or our main results, we will also need a stronger requirement than the simple ǫ-JLT and so we will use a version of the Fast Johnson-Lindenstrauss Transform (FJLT), which was originally introduced in [2, 3]. Consider an orthogonal matrix U ∈Rn×d, viewed as d vectors in Rn. A FJLT projects the vector”
Fast locality-sensitive hashing (2011, methodology): “We first state the following key property of the pre-conditioning step shown in [1], which says that the vector x̂ (Step 1) is sufficiently dense.”
Demystifying Orthogonal Monte Carlo and Beyond (2020, methodology): “Monte Carlo (MC) methods are widely applied in machine learning in such domains as: dimensionality reduction [1, 3, 2], scalable kernel methods with random feature maps [34], generative modeling and variational autoencoders via sliced Wasserstein distances [36], approximating Gaussian smoothings in ”
An Introduction to Matrix Concentration Inequalities (2015, unknown): “Many contemporary variants depend on ideas from [6] and [45].”
A sparse Johnson: Lindenstrauss transform (2010, methodology): “The result and the corresponding proof is similar to that of Ailon and Chazelle [2].”
A variant of the Johnson-Lindenstrauss lemma for circulant matrices (2010, background): “We refer to [6, 1, 2, 3, 9] for details and to [9] for a nice description of the history and the actual “state of the art”.”
Sparser Johnson-Lindenstrauss Transforms (2010, methodology): “ernoulli entries), and thus performing the embedding na¨ıvely takes O(k ·kxk0) time where x has kxk0 non-zero entries. Several works have devised other distributions which give faster embedding times [2, 3, 4, 18, 27, 38], but all these methods require Ω(dlogd) embedding time even for sparse ∗Stanfo”
Randomized partition trees for exact nearest neighbor search (2013, unknown): “It makes use of random projection, which is also the basis of some other approximate NN methods (Kleinberg, 1997; Ailon and Chazelle, 2009).”