On deterministic sketching and streaming for sparse recovery and norm estimation
From MaRDI portal
Publication:2437337
DOI10.1016/j.laa.2012.12.025zbMath1284.65018MaRDI 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
inner product; streaming algorithms; sparse recovery; data streams; heavy hitters; randomized complexity; norm estimation; Johnson-Lindenstrauss transform
62G05: Nonparametric estimation
15A60: Norms of matrices, numerical range, applications of functional analysis to matrix theory
65Y20: Complexity and performance of numerical algorithms
15A63: Quadratic and bilinear forms, inner products
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
