An elementary proof of a theorem of Johnson and Lindenstrauss

By Sanjoy Dasgupta, Anupam Gupta. 2003

1,149 citations recorded by the source corpus.

Subfields: Applied Mathematics, Computer Graphics and Computer-Aided Design, Signal Processing, Pure Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computer Graphics and Computer-Aided Design

In Signal Processing

In Pure Mathematics

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, background): “If elements of W are drawn from an appropriate distribution p(w), the Johnson-Lindenstrauss Lemma (Dasgupta and Gupta 2003, Blum 2005) ensures that this transformation will preserve similarity between data points.”
cpSGD: Communication-efficient and differentially-private distributed SGD (2018, background): “, when Xi is uniform on the unit sphere, Xmax is O ⇣p (log d)/d ⌘ (whp) [10].”
Making AI Forget You: Data Deletion in Machine Learning (2019, background): “In some situations, metric-preserving dimensionality reduction techniques [45, 28] could potentially be used.”
Analysis of universal adversarial perturbations (2017, neutral): “We ﬁrst start by recalling a result from [7], which is based on [17].”
An Exponential Learning Rate Schedule for Deep Learning (2019, background): “This Chernoff-bound based proof is a special case of Dasgupta & Gupta (2003).”
Cancelable Biometrics: A review (2015, background): “In recent years, various improvements in the proof and the statement of the JL lemma have been made (see [20] and [21] for more details).”
Understanding the Sparsity: Augmented Matrix Factorization with Sampled Constraints on Unobservables (2014, background): “Generally, it is proven in [7, 11] that, whenever the entries Aij are independently and identically distributed with zero mean and finite fourth moment, the maximum singular value of the constraint matrix A is almost surely 1 + √ d/p for d that is sufficiently large, and thus the matrix A and the co”
Towards Total Recall in Industrial Anomaly Detection (2021, methodology): “To further reduce coreset selection time, we follow [49], making use of the Johnson-Lindenstrauss theorem [11] to reduce dimensionalities of elements m ∈ M through random linear projections ψ : R → Rd with d∗ < d.”
A Method of Moments for Mixture Models and Hidden Markov Models (2012, background): “This is a special case of Lemma 2.2 from Dasgupta and Gupta (2003).”
Compressed sensing, sparsity, and dimensionality in neuronal information processing and data analysis. (2012, background): “The celebrated Johnson-Lindenstrauss ( JL) lemma ( Johnson & Lindenstrauss 1984, Indyk & Motwani 1998, Dasgupta & Gupta 2003) provides a striking answer.”