Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
DOI10.1145/2483699.2483706zbMATH Open1301.68162OpenAlexW2132032691WikidataQ130983756 ScholiaQ130983756MaRDI QIDQ2933656FDOQ2933656
David P. Woodruff, T. S. Jayram
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 (18)
- Streaming Complexity of SVMs
- Title not available (Why is that?)
- Dimensionality reduction with subgaussian matrices: a unified theory
- A Framework for Adversarially Robust Streaming Algorithms
- Perfect $L_p$ Sampling in a Data Stream
- Tracking the l_2 Norm with Constant Update Time
- Sparser Johnson-Lindenstrauss Transforms
- Continuous Monitoring of l_p Norms in Data Streams
- Simple Analyses of the Sparse Johnson-Lindenstrauss Transform.
- Almost Optimal Explicit Johnson-Lindenstrauss Families
- RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression
- Optimal (Euclidean) Metric Compression
- Title not available (Why is that?)
- Real-valued embeddings and sketches for fast distance and similarity estimation
- Improved linear embeddings via Lagrange duality
- Optimal Bounds for Johnson-Lindenstrauss Transformations
- 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)
