On variants of the Johnson–Lindenstrauss lemma

By Jirí Matousek. Random Struct. Algorithms, 2008

300 citations recorded by the source corpus.

Subfields: Atomic and Molecular Physics, and Optics, Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

View Paper: https://www.semanticscholar.org/paper/0a65097bcb2dd400a27a65d42608658dc9f6898d

How researchers see this paper

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

In Atomic and Molecular Physics, and Optics

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

Citations in the corpus

Feature hashing for large scale multitask learning (2009, unknown): “e only requires 1 3 of that computation by designing a matrix consisting only of entries {−1,0,1}. Pioneered by (Ailon & Chazelle, 2006), there has been a line of work (Ailon & Liberty, 2008; Matousek, 2008) on improving the complexity of random projection by using various code-matrices in o”
Sparser Johnson-Lindenstrauss Transforms (2010, background): “…simple constructions for dimensionality reduction in £2 via linear mappings that are sparse: only an O(e)-fraction of entries in each column of our embedding matrices are non-zero to achieve distortion 1 +e with high probability, while still achieving the asymptotically optimal number of rows.”
The Fast Johnson--Lindenstrauss Transform and Approximate Nearest Neighbors (2009, background): “Matousek [36] recently showed that this is indeed possible without extra cost for the ( 2 → 2) embedding case and with a multiplicative cost of an additional ε−1 for the ( 1 → 1) case (also affecting the ε-ANN application).”
Faster least squares approximation (2007, methodology): “This transform is described more precisely in Sections 2 and 3.3, and it was used recently as one step in the development of a “fast” version of the Johnson-Lindenstrauss lemma [1, 13 ].”
Part-based modelling of compound scenes from images (2015, methodology): “We also evaluate a random projection matrix motivated by [12] where the elements of Φ are sampled independently from {0, 1} such that the density of the 1’s may be specified.”
A survey on unsupervised outlier detection in high‐dimensional numerical data (2012, unknown): “Matoušek [87] further improves these error bounds.”
Distance geometry and data science (2019, background): “2006; Kane and Nelson 2014; Matoušek 2008; Allen-Zhu et al.”
A sparse Johnson: Lindenstrauss transform (2010, methodology): “The resulting running time for an input vector x having n nz ( x ) non-zeros is ˜ O (cid:16) n nz ( x ) ǫ (cid:17) — better than the running time obtained by [22,23] for sparse vectors in terms of the sparsity ratio n nz ( x ) d as well as by the factor 1 ǫ .”
A variant of the Johnson-Lindenstrauss lemma for circulant matrices (2010, background): “2 of [9]) states that Pb(Z ≥ 2 √ 2||μ||2 √ t+ 2||μ||∞t) ≤ exp(−t).”
Demystifying Orthogonal Monte Carlo and Beyond (2020, methodology): “Dimensionality Reduction [JLT]: Johnson-Lindenstrauss dimensionality reduction techniques (JLT) [1, 25, 29] rely on embeddings of high-dimensional feature vectors via random projections given by vectors ω ∼ N (0 , I d ) .”