Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
DOI10.1145/2483699.2483706zbMATH Open1301.68162OpenAlexW2132032691WikidataQ130983756 ScholiaQ130983756MaRDI QIDQ2933656FDOQ2933656
Authors: T. S. Jayram, David P. Woodruff 
Publication date: 5 December 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2483699.2483706
Recommendations
- Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error
- Almost Optimal Explicit Johnson-Lindenstrauss Families
- Sparser Johnson-Lindenstrauss transforms
- An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
- Optimal bounds for Johnson-Lindenstrauss transformations
Analysis of algorithms and problem complexity (68Q25) Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (20)
- Streaming Complexity of SVMs
- Title not available (Why is that?)
- Sparser Johnson-Lindenstrauss transforms
- Dimensionality reduction with subgaussian matrices: a unified theory
- A Framework for Adversarially Robust Streaming Algorithms
- Tracking the l_2 Norm with Constant Update Time
- Perfect \(L_p\) sampling in a data stream
- Optimal bounds for Johnson-Lindenstrauss transformations
- Almost Optimal Explicit Johnson-Lindenstrauss Families
- Optimal (Euclidean) Metric Compression
- Simple analyses of the sparse Johnson-Lindenstrauss transform
- Continuous monitoring of \(\ell_p\) norms in data streams
- Title not available (Why is that?)
- Real-valued embeddings and sketches for fast distance and similarity estimation
- Optimality of the Johnson-Lindenstrauss dimensionality reduction for practical measures
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Improved linear embeddings via Lagrange duality
- Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error
- Title not available (Why is that?)
- The Simultaneous Communication of Disjointness with Applications to Data Streams
This page was built for publication: Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933656)
