An elementary proof of a theorem of Johnson and Lindenstrauss

2002/11/25 by Sanjoy Dasgupta, Anupam Gupta · 16 citations

paper · doi:10.1002/rsa.10073

Abstract

Abstract A result of Johnson and Lindenstrauss [13] shows that a set of n points in high dimensional Euclidean space can be mapped into an O( log n/ϵ 2 )‐dimensional Euclidean space such that the distance between any two points changes by only a factor of (1 ± ϵ). In this note, we prove this theorem using elementary probabilistic techniques. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 22: 60–65, 2002

Cited by

• Emergent Sparsity in Frozen Random CNN Feature Extractors for Deep Reinforcement Learning
• Behavioral alignment as an organizing principle in sensory coding
• Compressed Bayesian Tensor Regression
• LLM DNA: Tracing Model Evolution via Functional Representations
• Wavelet-Induced Rotary Encodings: RoPE Meets Graphs
• A short survey on almost orthogonal vectors in a few specific large dimensions
• Random Projection Flows for Efficient Manifold Density Estimation
• Graph Coloring for Multi-Task Learning
• Dimension Reduction for Clustering: The Curious Case of Discrete Centers
• Random functions as data compressors for machine learning of molecular processes
• Graph Random Features for Scalable Gaussian Processes
• Metric spaces of walks and Lipschitz duality on graphs
• Beyond Trade-offs: A Unified Framework for Privacy, Robustness, and Communication Efficiency in Federated Learning
• Compressibility Barriers to Neighborhood-Preserving Data Visualizations
• Efficiently Constructing Sparse Navigable Graphs
• Raptor: Scalable Train-Free Embeddings for 3D Medical Volumes Leveraging Pretrained 2D Foundation Models

Related

• Improving the Johnson-Lindenstrauss Lemma
• Optimal Bounds for Johnson-Lindenstrauss Transformations
• Using the Johnson-Lindenstrauss lemma in linear and integer programming
• A Quantized Johnson Lindenstrauss Lemma: The Finding of Buffon's Needle
• Bulk Johnson-Lindenstrauss Lemmas