Almost Optimal Explicit Johnson-Lindenstrauss Families

DOI10.1007/978-3-642-22935-0_53zbMath1343.68304arXiv1011.6397MaRDI 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

68W40: Analysis of algorithms

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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