Almost Optimal Explicit Johnson-Lindenstrauss Families
From MaRDI portal
Publication:3088132
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
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