The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors

2009/01/01 by Nir Ailon, Bernard Chazelle · 498 citations
Computer Science · Engineering · Mathematics · #Advanced Image and Video Retrieval Techniques #Algorithm #Artificial intelligence #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Distortion (music) #Embedding #Fourier transform #Hypercube #Mathematical analysis #Mathematics #Random projection #Sparse and Compressive Sensing Techniques

paper · doi:10.1137/060673096

published in SIAM Journal on Computing 39(1), 302-322 (Society for Industrial and Applied Mathematics)

openalex publication_date 2009/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/20

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 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 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
• Almost Optimal Explicit Johnson-Lindenstrauss Transformations
• Foundations of Vector Retrieval
• On Convolutional Approximations to Linear Dimensionality Reduction Operators for Large Scale Data Processing
• Randomized LU decomposition
• Fast One-Pass Sparse Approximation of the Top Eigenvectors of Huge Low-Rank Matrices? Yes, MAM^*!
• Worst-case Prediction Performance Analysis of the Kalman Filter
• Label-Aware Neural Tangent Kernel: Toward Better Generalization and Local Elasticity
• Learning with Neural Tangent Kernels in Near Input Sparsity Time
• Unified Linear Parametric Map Modeling and Perception-aware Trajectory Planning for Mobile Robotics
• Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores
• Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• Mask6D: Masked Pose Priors For 6D Object Pose Estimation
• Subspace Embeddings and ℓ_p-Regression Using Exponential Random Variables
• Optimal Sub-sampling with Influence Functions
• SIGIR 2025 -- LiveRAG Challenge Report
• New Bounds For Distributed Mean Estimation and Variance Reduction
• Circulant Binary Embedding
• Two new Probability inequalities and Concentration Results
• On the computation of tensor functions under tensor-tensor multiplications with linear maps
• Generalized Reference Kernel With Negative Samples For Support Vector One-class Classification
• Deterministic matrix sketches for low-rank compression of high-dimensional simulation data
• Consistent Weighted Sampling Made Fast, Small, and Easy
• Random Projections for k-means Clustering
• A fast algorithm for computing minimal-norm solutions to underdetermined systems of linear equations
• Scaling Neural Tangent Kernels via Sketching and Random Features
• Fast Multi-label Learning
• A Fast Randomized Algorithm for Massive Text Normalization
• Finding the Mode of a Kernel Density Estimate
• Compressed Sensing with Coherent and Redundant Dictionaries
• Tensorized Random Projections
• Bayesian Data Sketching for Varying Coefficient Regression Models
• Fast L1-NMF for Multiple Parametric Model Estimation
• GraSS: Scalable Data Attribution with Gradient Sparsification and Sparse Projection
• Randomized LU Decomposition
• Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments
• Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection
• Optimal Las Vegas Approximate Near Neighbors in ℓ_p
• Fast and RIP-optimal transforms
• Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
• Instance-optimal Mean Estimation Under Differential Privacy
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• Fast Cross-Polytope Locality-Sensitive Hashing
• When Quantization Is Free: An int4 KV Cache That Outruns fp16 on Apple Silicon
• Oblivious Subspace Injection Is Not Enough for Relative Error
• RidgeSketch: A Fast sketching based solver for large scale ridge regression
• User-Friendly Tail Bounds for Sums of Random Matrices
• Random features for Grassmannian kernel approximation with bounded rank-one projections
• Lower bounds for oblivious subspace embeddings
• Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order
• Principal Component Analysis and Higher Correlations for Distributed\n Data
• The Effectiveness of Johnson-Lindenstrauss Transform for High Dimensional Optimization With Adversarial Outliers, and the Recovery
• Rademacher Random Projections with Tensor Networks
• Proofs of Useful Work from Arbitrary Matrix Multiplication

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