On Low-Risk Heavy Hitters and Sparse Recovery Schemes

DOI10.4230/LIPICS.APPROX-RANDOM.2018.19OpenAlexW2964227828MaRDI QIDQ5009511

Yi Li, Vasileios Nakos, David P. Woodruff

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1709.02919

zbMATH Keywords

lower boundssparse recoveryheavy hittersspike covariance modelturnstile model

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Randomized approximation of summable sequences -- adaptive and non-adaptive

Cites Work

• Finding frequent items in data streams
• Approximate Sparse Recovery: Optimizing Time and Measurements
• Restricted Isometry Property for General p-Norms
• On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• Algorithms for dynamic geometric problems over data streams
• Coresets in dynamic geometric data streams
• Data Stream Algorithms via Expander Graphs
• CR-precis: A Deterministic Summary Structure for Update Data Streams
• An improved data stream summary: the count-min sketch and its applications
• Improved Algorithms for Adaptive Compressed Sensing
• ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk
• Compressive sensing with local geometric features
• On the Power of Adaptivity in Sparse Recovery
• (1 + eps)-Approximate Sparse Recovery
• Values of Mills' Ratio of Area to Bounding Ordinate and of the Normal Probability Integral for Large Values of the Argument

This page was built for publication: On Low-Risk Heavy Hitters and Sparse Recovery Schemes