On deterministic sketching and streaming for sparse recovery and norm estimation

DOI10.1016/j.laa.2012.12.025zbMath1284.65018OpenAlexW2097796125MaRDI QIDQ2437337

Huy L. Nguyen, David P. Woodruff, Jelani Nelson

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

zbMATH Keywords

inner productstreaming algorithmssparse recoverydata streamsheavy hittersrandomized complexitynorm estimationJohnson-Lindenstrauss transform

Mathematics Subject Classification ID

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two are better than one: fundamental parameters of frame coherence
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• A simple proof of the restricted isometry property for random matrices
• Fast dimension reduction using Rademacher series on dual BCH codes
• Finding repeated elements
• The space complexity of approximating the frequency moments
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Problems and results in extremal combinatorics. I.
• Finding frequent items in data streams
• Compressed sensing and best 𝑘-term approximation
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Extensions of Lipschitz mappings into a Hilbert space
• On sparse reconstruction from Fourier and Gaussian measurements
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Simple Constructions of Almost k-wise Independent Random Variables
• An improved data stream summary: the count-min sketch and its applications
• Communication Complexity
• Matching pursuits with time-frequency dictionaries
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Nonrandom binary superimposed codes

This page was built for publication: On deterministic sketching and streaming for sparse recovery and norm estimation