Extensions of Lipschitz mappings into Hilbert space

By William B. Johnson, J. Lindenstrauss. 1984

How researchers see this paper

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

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, background): “A classic result of Johnson and Lindenstrauss [76], for instance, shows that high-dimensional points can be randomly projected onto a logarithmic number of dimensions while approximately preserving the distances between them.”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, methodology): “Furthermore, in case of the `s norm for s ∈ {1, 2} we can use the Johnson-Lindenstrauss lemma [JL84] to reduce d to O(log n/ 2).”
Making AI Forget You: Data Deletion in Machine Learning (2019, background): “[45] W.”
On Invariance and Selectivity in Representation Learning (2015, positive): “First, note that for the sake of simplicity, and in analogy to the basic statement of the Johnson–Linderstrauss lemma [24], in the above result we consider a finite set of points; however, the same argument can be readily extended to any compact set I0 ⊂ I .”
Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions (2009, background): “We have already described a third class of examples: the randomized embeddings of Johnson–Lindenstrauss [75] and of Bourgain [15].”
Deep neural network based malware detection using two dimensional binary program features (2015, methodology): “Potentially the feature space can become large, in those cases methods like locality-sensitive hashing [21, 6], feature hashing (aka hashing “trick”) [34, 22], or random projections [23, 21, 15, 11] have been used in malware detection.”
Signal Processing With Compressive Measurements (2010, unknown): “We construct our random matrices as follows: given and , we generate random matrices by choosing the entries as independent and identically distributed (i.i.d.) random variables.”
Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces (2004, methodology): “In [29] it is asked if there is a nonlinear analog of Maurey’s extension theorem.”
Seismic wave extrapolation using lowrank symbol approximation (2013, background): “One of the most celebrated theorems in high dimensional geometry and probability is the following Johnson-Lindenstrauss lemma (Johnson and Lindenstrauss 1984).”
Adaptive computation and machine learning (1998, background): “The classical representer theorem is due to Kimeldorf and Wahba [1971]. A generalization to non-quadratic cost functions was stated by Wahba [1990]. The general form presented in this chapter was given by Schölkopf, Herbrich, Smola, and Williamson [2000]. Rational kernels were introduced by Cortes, ”
Challenges of Big Data Analysis (2013, methodology): “Random projection (Johnson and Lindenstrauss, 1984) is an efficient dimension reduction technique for this purpose, and is closely related to the celebrated idea of compress sensing (Donoho, 2006; Tsaig and Donoho, 2006; Lustig et al.”
TRAK: Attributing Model Behavior at Scale (2023, unknown): “To reduce the dimensionality of this problem, we leverage a classic result of Johnson & Lindenstrauss (1984).”