On deterministic sketching and streaming for sparse recovery and norm estimation
DOI10.1016/J.LAA.2012.12.025zbMATH Open1284.65018OpenAlexW2097796125MaRDI QIDQ2437337FDOQ2437337
Authors: Jelani Nelson, Huy L. Nguyen, David P. Woodruff 
Publication date: 3 March 2014
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.laa.2012.12.025
Recommendations
- On deterministic sketching and streaming for sparse recovery and norm estimation
- Deterministic heavy hitters with sublinear query time
- Nearly-optimal bounds for sparse recovery in generic norms, with applications to \(k\)-median sketching
- On the exact space complexity of sketching and streaming small norms
- Improved concentration bounds for count-sketch
inner productsparse recoverydata streamsheavy hittersstreaming algorithmsrandomized complexitynorm estimationJohnson-Lindenstrauss transform
Nonparametric estimation (62G05) Complexity and performance of numerical algorithms (65Y20) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Quadratic and bilinear forms, inner products (15A63)
Cites Work
- Extensions of Lipschitz mappings into a Hilbert space
- Matching pursuits with time-frequency dictionaries
- A simple proof of the restricted isometry property for random matrices
- Fast dimension reduction using Rademacher series on dual BCH codes
- The space complexity of approximating the frequency moments
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Compressed sensing and best \(k\)-term approximation
- The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
- Finding repeated elements
- Finding frequent items in data streams
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Simple Constructions of Almost k-wise Independent Random Variables
- An improved data stream summary: the count-min sketch and its applications
- Nonrandom binary superimposed codes
- On sparse reconstruction from Fourier and Gaussian measurements
- Communication Complexity
- Problems and results in extremal combinatorics. I.
- Title not available (Why is that?)
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
- Perturbed Identity Matrices Have High Rank: Proof and Applications
- Modern computer algebra
- Two are better than one: fundamental parameters of frame coherence
- Title not available (Why is that?)
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (1)
This page was built for publication: On deterministic sketching and streaming for sparse recovery and norm estimation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437337)
