The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors

2009/01/01 by Nir Ailon, Bernard Chazelle · 52 citations
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Advanced Image and Video Retrieval Techniques #Computational Geometry and Mesh Generation

paper · doi:10.1137/060673096

Abstract

We introduce a new low-distortion embedding of ℓ₂^d into ℓ_p^{O(log n)} (p=1,2) called the fast Johnson–Lindenstrauss transform (FJLT). The FJLT is faster than standard random projections and just as easy to implement. It is based upon the preconditioning of a sparse projection matrix with a randomized Fourier transform. Sparse random projections are unsuitable for low-distortion embeddings. We overcome this handicap by exploiting the “Heisenberg principle” of the Fourier transform, i.e., its local-global duality. The FJLT can be used to speed up search algorithms based on low-distortion embeddings in ℓ₁ and ℓ₂. We consider the case of approximate nearest neighbors in ℓ₂^d. We provide a faster algorithm using classical projections, which we then speed up further by plugging in the FJLT. We also give a faster algorithm for searching over the hypercube.

Citations

• Database-friendly random projections: Johnson-Lindenstrauss with binary coins
• Monte Carlo sampling methods using Markov chains and their applications

Cited by

• On Geometric Asymmetry and Information in Sequential Dimension Reduction
• Improving Algorithmic Efficiency using Cryptography
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace\n embeddings
• Fast & Accurate Randomized Algorithms for Linear Systems and Eigenvalue Problems
• Simple Analysis of Johnson-Lindenstrauss Transform under Neuroscience Constraints
• Unbiased estimators for random design regression
• Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors
• DRIVE: One-bit Distributed Mean Estimation
• Deep Fried Convnets
• Compressed Sensing using Generative Models
• Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
• Compressive Sensing with Redundant Dictionaries and Structured\n Measurements
• Tighter Fourier Transform Complexity Tradeoffs
• RSN: Randomized Subspace Newton
• Sparse sketches with small inversion bias
• In Situ Training of Implicit Neural Compressors for Scientific Simulations via Sketch-Based Regularization
• Fast Dimensionality Reduction from ℓ₂ to ℓ_p
• Dimension reduction by random hyperplane tessellations
• Distributed Mean Estimation with Limited Communication
• Johnson-Lindenstrauss lemma for circulant matrices
• Binarized Johnson-Lindenstrauss embeddings
• Fast approximation of matrix coherence and statistical leverage
• Tight and Robust Private Mean Estimation with Few Users
• Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry
• Optimal approximate matrix product in terms of stable rank
• Utility-Diversity Aware Online Batch Selection for LLM Supervised Fine-tuning
• Structured Random Models for Phase Retrieval with Optical Diffusers
• A Sparse Johnson--Lindenstrauss Transform
• How many integrals should be evaluated at least in two-dimensional hyperinterpolation?
• Randomized algorithms for matrices and data
• Compressed Bayesian Tensor Regression
• Acceleration of Randomized Kaczmarz Method via the Johnson-Lindenstrauss\n Lemma
• Sketching in Bayesian High Dimensional Regression With Big Data Using Gaussian Scale Mixture Priors
• FlyLoRA: Boosting Task Decoupling and Parameter Efficiency via Implicit Rank-Wise Mixture-of-Experts
• Data selection: at the interface of PDE-based inverse problem and randomized linear algebra
• Fast Rank Adaptive CUR via a Recycled Small Sketch
• Feature Hashing for Large Scale Multitask Learning
• Toward Efficient Influence Function: Dropout as a Compression Tool
• Semi-supervised Embedding Learning for High-dimensional Bayesian Optimization
• Sparsity Lower Bounds for Dimensionality Reducing Maps
• Sequential Least-Squares Estimators with Fast Randomized Sketching for Linear Statistical Models
• Demystifying Orthogonal Monte Carlo and Beyond
• Faster Binary Embeddings for Preserving Euclidean Distances
• Random Sampling for Distributed Coded Matrix Multiplication
• Are Transformers universal approximators of sequence-to-sequence functions?
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation
• Sparse Linear Networks with a Fixed Butterfly Structure: Theory and\n Practice
• Compressive Meta-Learning
• Practical and Optimal LSH for Angular Distance
• Near neighbor preserving dimension reduction for doubling subsets of ℓ₁
• Dimensionality Reduction for Wasserstein Barycenter
• Efficient Anomaly Detection via Matrix Sketching

Related

• The Fast Johnson-Lindenstrauss Transform is Even Faster
• Barriers for Faster Dimensionality Reduction
• Fast Nearest Neighbor Preserving Embeddings
• A Sparse Johnson-Lindenstrauss Transform using Fast Hashing
• A Sparse Johnson--Lindenstrauss Transform