On deterministic sketching and streaming for sparse recovery and norm estimation

DOI10.1016/J.LAA.2012.12.025MaRDI QIDQ2437337zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(8)

• Improved concentration bounds for count-sketch
• Efficient sketches for the set query problem
• How robust are linear sketches to adaptive inputs?
• On deterministic sketching and streaming for sparse recovery and norm estimation
• Nearly-optimal bounds for sparse recovery in generic norms, with applications to \(k\)-median sketching
• Spectral sparsification in the semi-streaming setting
• Deterministic heavy hitters with sublinear query time
• On low-risk heavy hitters and sparse recovery schemes

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)