On deterministic sketching and streaming for sparse recovery and norm estimation

DOI10.1016/J.LAA.2012.12.025zbMATH Open1284.65018OpenAlexW2097796125MaRDI QIDQ2437337FDOQ2437337

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 productsparse recoverydata streamsheavy hittersstreaming algorithmsrandomized complexitynorm estimationJohnson-Lindenstrauss transform

Mathematics Subject Classification ID

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 𝑘-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)

• Spectral sparsification in the semi-streaming setting

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)