Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform

By Nir Ailon, Bernard Chazelle. 2006

554 citations recorded by the source corpus.

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

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

In Algorithms & Complexity

Citations in the corpus

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “s (b-bit) minwise hashing and one permutation hashing [3, 24]. • Fast hashing for MIPS: Our proposed hash function uses random projection as the main hashing scheme. There is a rich set of literature [21, 1, 8, 24, 29] on making hashing faster. Evaluations of these new faster techniques will further”
cpSGD: Communication-efficient and differentially-private distributed SGD (2018, positive): “The following lemma follows from [3].”
Distributed Mean Estimation with Limited Communication (2016, methodology): “The lemma is similar to that of [1], and we give the proof in Appendix A for completeness.”
Orthogonal Random Features (2016, methodology): “Structured matrices have been used for speeding up dimensionality reduction [1], binary embedding [27], deep neural networks [5] and kernel approximation [13, 28, 7].”
Compressed Least-Squares Regression (2009, unknown): “[2, 1]).”
Circulant Binary Embedding (2014, methodology): “SupposeHk(x1,x2) is the normalized Hamming distance betweenk-bit codes of a pair of points x1,x2 ∈ Rd: Hk(x1,x2)= 1 k k−1 ∑ i=0 ∣ ∣sign(Ri·x1)−sign(Ri·x2) ∣ ∣/2, (11) andRi· is thei-th row ofR, R = circ(r).”
Faster least squares approximation (2007, methodology): “Its construction depends on a sparsity parameter, and it is identical to the “sparse projection” matrix in Matoušek’s version of the Ailon-Chazelle result [1, 13].”
On variants of the Johnson–Lindenstrauss lemma (2008, background): “For part (i), we essentially reproduce the neat argument in [2], for the reader’s convenience and delight.”
Relative-Error CUR Matrix Decompositions (2007, methodology): “Most recently, we learned of work by Sarlos [57], who used ideas from the recently developed fast Johnson-Lindenstrauss transform of Ailon and Chazelle [5] to yield further improvements to a CX matrix decomposition.”
The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings (2017, methodology): “For dimensionality reduction, Ailon and Chazelle (2006) used a single HD block as a way to spread out the mass of a vector over all dimensions before applying a sparse Gaussian matrix.”
Sketching as a Tool for Numerical Linear Algebra (2014, methodology): “or matrixmatrix multiplication. Tama´s Sarlo´s observed [105] that one can in fact choose S to come from a much more structured random family of matrices, called fast Johnson-Lindenstrauss transforms [2]. These led to roughly O(ndlogd)+poly(d/ε) time algorithms for the least squares regression probl”
Initialization matters: Orthogonal Predictive State Recurrent Neural Networks (2018, background): “Several other structured constructions were known before (Ailon & Chazelle, 2006; Hinrichs & Vybı́ral, 2011; Vybı́ral, 2011; Zhang & Cheng, 2013; Choromanski & Sindhwani, 2016; Choromanska et al., 2016; Bojarski et al., 2017), however these were motivated by computational and space complexity gains…”
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”
Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix (2011, methodology): “= max |Fij |[Ailon and Chazelle 2006; Avron et al. 2010].”