Almost Optimal Explicit Johnson-Lindenstrauss Families

DOI10.1007/978-3-642-22935-0_53zbMath1343.68304arXiv1011.6397OpenAlexW1746783006MaRDI QIDQ3088132

Daniel M. Kane, Raghu Meka, Jelani Nelson

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.6397

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (13)

Sparser Johnson-Lindenstrauss Transforms ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions ⋮ A variant of the Johnson-Lindenstrauss lemma for circulant matrices ⋮ Unnamed Item ⋮ Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time ⋮ Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. ⋮ Tracking the l_2 Norm with Constant Update Time ⋮ High Probability Frequency Moment Sketches ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Optimal Bounds for Johnson-Lindenstrauss Transformations ⋮ Simple and efficient pseudorandom generators from gaussian processes ⋮ Unnamed Item

Cites Work

• The space complexity of approximating the frequency moments
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• An algorithmic theory of learning: Robust concepts and random projection
• Explicit Dimension Reduction and Its Applications
• Extensions of Lipschitz mappings into a Hilbert space
• On variants of the Johnson–Lindenstrauss lemma
• Algorithmic derandomization via complexity theory
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Numerical linear algebra in the streaming model
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Almost Optimal Explicit Johnson-Lindenstrauss Families