Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error

DOI10.1145/2483699.2483706MaRDI QIDQ2933656zbMATHOpenAlexWikidataFDO

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

zbMATH Keywords

entropydata streamsfrequency momentscommunication complexitydistinct elements

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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

Cited in

(20)

• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error
• Streaming Complexity of SVMs
• Tracking the l_2 Norm with Constant Update Time
• Perfect \(L_p\) sampling in a data stream
• Optimal bounds for Johnson-Lindenstrauss transformations
• Improved linear embeddings via Lagrange duality
• scientific article; zbMATH DE number 7758337 (Why is no real title available?)
• Simple analyses of the sparse Johnson-Lindenstrauss transform
• Optimality of the Johnson-Lindenstrauss dimensionality reduction for practical measures
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• Continuous monitoring of \(\ell_p\) norms in data streams
• scientific article; zbMATH DE number 7650128 (Why is no real title available?)
• RidgeSketch: a fast sketching based solver for large scale ridge regression
• A Framework for Adversarially Robust Streaming Algorithms
• Optimal (Euclidean) Metric Compression
• scientific article; zbMATH DE number 7559216 (Why is no real title available?)
• Sparser Johnson-Lindenstrauss transforms
• Real-valued embeddings and sketches for fast distance and similarity estimation
• Dimensionality reduction with subgaussian matrices: a unified theory
• 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)