Optimality of the Johnson-Lindenstrauss Lemma

For any d, n ≥ 2 and 1=(min{n, d})0.4999

• Publication year

  2016

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2016-09-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FOCS.2017.64arXiv 1609.02094
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Optimal Compression of Approximate Inner Products and Dimension Reduction

  2016cited by this paper
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation

  2014cited by this paper
• Sketching as a Tool for Numerical Linear Algebra

  2014cited by this paper
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

  2014cited by this paper
• On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation

  2012cited by this paper
• Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality

  2012cited by this paper
• Compressed Sensing

  2012cited by this paper
• Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error

  2011cited by this paper
• Randomized Dimensionality Reduction for $k$ -Means Clustering

  2011cited by this paper
• Almost Optimal Explicit Johnson-Lindenstrauss Families

  2011cited by this paper
• Graph sparsification by effective resistances

  2008cited by this paper
• Data streams: algorithms and applications

  2005cited by this paper
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

  2004cited by this paper
• Problems and results in extremal combinatorics--I

  2003cited by this paper
• Efficient search for approximate nearest neighbor in high dimensional spaces

  1998cited by this paper
• Simple Construction of Almost k-wise Independent Random Variables

  1992cited by this paper
• THE VOLUME OF CONVEX BODIES AND BANACH SPACE GEOMETRY (Cambridge Tracts in Mathematics 94)

  1991cited by this paper
• The volume of convex bodies and Banach space geometry

  1989cited by this paper
• Extensions of Lipschitz mappings into Hilbert space

  1984cited by this paper
• Lower bounds on the maximum cross correlation of signals (Corresp.)

  1974cited by this paper

• Cross-Modal Redundancy and the Geometry of Vision-Language Embeddings

  2026cites this paper
• Improving Algorithmic Efficiency using Cryptography

  2025cites this paper
• Beyond Worst-Case Dimensionality Reduction for Sparse Vectors

  2025cites this paper
• Quantization for Vector Search under Streaming Updates

  2025cites this paper
• An Exploratory Study of Bayesian Prompt Optimization for Test-Driven Code Generation with Large Language Models

  2025cites this paper
• GreenMix: Energy-Efficient Serverless Computing via Randomized Sketching on Asymmetric Multi-Cores

  2025cites this paper
• Learning to Instruct: Fine-Tuning a Task-Aware Instruction Optimizer for Black-Box LLMs

  2025cites this paper
• Fast Dimensionality Reduction from ℓ2 to ℓp

  2025influential citation
• Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry

  2025influential citation
• Linear Causal Representation Learning by Topological Ordering, Pruning, and Disentanglement

  2025cites this paper
• Balancing Utility and Privacy: Dynamically Private SGD with Random Projection

  2025influential citation
• Dimension Reduction for Clustering: The Curious Case of Discrete Centers

  2025cites this paper
• Efficient QR-based Column Subset Selection through Randomized Sparse Embeddings

  2025influential citation
• Learning in NN: from fitting most to fitting a few

  2025cites this paper
• Compressibility Barriers to Neighborhood-Preserving Data Visualizations

  2025cites this paper
• Information preservation with wasserstein autoencoders: generation consistency and adversarial robustness

  2025cites this paper
• Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning

  2025cites this paper
• On Extended Concentration Inequalities for Fast JL Embeddings of Infinite Sets

  2025cites this paper
• Almost Right: Making First-layer Kernels Nearly Orthogonal Improves Model Generalization

  2025cites this paper
• Splitting frequency behavior of wireless power transfer for eddy current testing applications

  2025cites this paper
• Perspectives on Large Language Models: Polysemy, Stochasticity, Exponential Expressibility, and Unitary Attention

  2025cites this paper
• Lambda: Learning Matchable Prior For Entity Alignment with Unlabeled Dangling Cases

  2024cites this paper
• Entity Alignment with Unlabeled Dangling Cases

  2024cites this paper
• High-Dimensional Vector Quantization: General Framework, Recent Advances, and Future Directions

  2024cites this paper
• Dynamics-preserving compression for modal flow analysis

  2024cites this paper
• Formal Privacy Proof of Data Encoding: The Possibility and Impossibility of Learnable Encryption

  2024cites this paper
• Optimization Can Learn Johnson Lindenstrauss Embeddings

  2024cites this paper
• Intermediate Outputs Are More Sensitive Than You Think

  2024cites this paper
• Near-Optimal Dimension Reduction for Facility Location

  2024cites this paper
• Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search

  2024cites this paper
• On Continuous Terminal Embeddings of Sets of Positive Reach

  2024influential citation
• Dynamic Metric Embedding into ℓp Space

  2024cites this paper
• Learning in Feature Spaces via Coupled Covariances: Asymmetric Kernel SVD and Nyström method

  2024cites this paper
• RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search

  2024cites this paper
• On outer bi-Lipschitz extensions of linear Johnson-Lindenstrauss embeddings of subsets of RN\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69

  2024cites this paper
• Space Complexity of Euclidean Clustering

  2024cites this paper
• Fuzzy Divergence Weighted Ensemble Clustering With Spectral Learning Based on Random Projections for Big Data

  2024cites this paper
• Sparse Dimensionality Reduction Revisited

  2023cites this paper
• A Nearly-Optimal Bound for Fast Regression with 𝓁∞ Guarantee

  2023cites this paper
• Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation

  2023cites this paper
• Understanding and Leveraging the Learning Phases of Neural Networks

  2023cites this paper
• Moderate Dimension Reduction for k-Center Clustering

  2023cites this paper
• Mental Health Diagnosis in the Digital Age: Harnessing Sentiment Analysis on Social Media Platforms upon Ultra-Sparse Feature Content

  2023cites this paper
• Quantum speedups for linear programming via interior point methods

  2023cites this paper
• Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming

  2023cites this paper
• Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation

  2023cites this paper
• Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

  2023cites this paper
• Comptes Rendus Mathématique

  2023cites this paper
• Sparse Models for Machine Learning

  2023cites this paper
• Random Separating Hyperplane Theorem and Learning Polytopes

  2023cites this paper
• Robust and Space-Efficient Dual Adversary Quantum Query Algorithms

  2023cites this paper
• TopP&R: Robust Support Estimation Approach for Evaluating Fidelity and Diversity in Generative Models

  2023cites this paper
• Nonlinear SVD with Asymmetric Kernels: feature learning and asymmetric Nyström method

  2023cites this paper
• Dimensionality Reduction for General KDE Mode Finding

  2023cites this paper
• Data encoding for healthcare data democratization and information leakage prevention

  2023cites this paper
• A Sparse Johnson-Lindenstrauss Transform using Fast Hashing

  2023cites this paper
• An Analysis of the Johnson-Lindenstrauss Lemma with the Bivariate Gamma Distribution

  2023cites this paper
• Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings

  2023cites this paper
• Robust and fuzzy ensemble framework via spectral learning for random projection-based fuzzy-c-means clustering

  2023cites this paper
• On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of RN

  2022cites this paper
• Fast, low-memory detection and localization of large, polymorphic inversions from SNPs

  2022cites this paper
• The learning phases in NN: From Fitting the Majority to Fitting a Few

  2022cites this paper
• Towards optimal lower bounds for k-median and k-means coresets

  2022influential citation
• The Fast Johnson-Lindenstrauss Transform is Even Faster

  2022cites this paper
• Fast metric embedding into the Hamming cube

  2022cites this paper
• Differentially Private Learning with Margin Guarantees

  2022cites this paper
• Approximate Euclidean lengths and distances beyond Johnson-Lindenstrauss

  2022cites this paper
• Barriers for Faster Dimensionality Reduction

  2022cites this paper
• Random projections for high-dimensional curves

  2022cites this paper
• Modular Paulsen Problem and Modular Projection Problem

  2022cites this paper
• IPS: Instance Profile for Shapelet Discovery for Time Series Classification

  2022cites this paper
• Modular Bourgain-Tzafriri Restricted Invertibility Conjectures and Johnson-Lindenstrauss Flattening Conjecture

  2022influential citation
• Johnson-Lindenstrauss embeddings for noisy vectors - taking advantage of the noise

  2022cites this paper
• \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p$$\end{document}-Adic Welch Bounds and \documentclass[12pt]{minimal}

  2022cites this paper
• On The Relative Error of Random Fourier Features for Preserving Kernel Distance

  2022cites this paper
• Efficient NTK using Dimensionality Reduction

  2022cites this paper
• Discrepancy Minimization in Input-Sparsity Time

  2022cites this paper
• Faster Linear Algebra for Distance Matrices

  2022cites this paper
• A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs

  2022cites this paper
• Learning Mixtures of Markov Chains and MDPs

  2022cites this paper
• Random Projections for Curves in High Dimensions

  2022cites this paper
• Essay on Kashin’s Remarkable 1977 Decomposition Theorem

  2022cites this paper
• Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel

  2022cites this paper
• Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights

  2022cites this paper
• No dimension reduction for doubling subsets of $\ell_q$ when $q>2$ revisited

  2021cites this paper
• Johnson-Lindenstrauss Embeddings with Kronecker Structure

  2021cites this paper
• Optimal (Euclidean) Metric Compression

  2021influential citation
• An Introduction to Johnson-Lindenstrauss Transforms

  2021cites this paper
• Statistical optimality conditions for compressive ensembles

  2021cites this paper
• Lower Bounds on the Low-Distortion Embedding Dimension of Submanifolds of Rn

  2021cites this paper
• Dimensionality Reduction for Wasserstein Barycenter

  2021cites this paper
• Exponentially Improved Dimensionality Reduction for 𝓁1: Subspace Embeddings and Independence Testing

  2021cites this paper
• The specious art of single-cell genomics

  2021cites this paper
• Johnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Survey

  2021cites this paper
• Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures

  2021influential citation
• A new coreset framework for clustering

  2021cites this paper
• Binary Random Projections with Controllable Sparsity Patterns

  2020cites this paper
• Training (Overparametrized) Neural Networks in Near-Linear Time

  2020cites this paper
• Secret Sharing Lower Bound: Either Reconstruction is Hard or Shares are Long

  2020cites this paper
• Sparse, Dense, and Attentional Representations for Text Retrieval

  2020cites this paper