Please use this identifier to cite or link to this item:
Title: On low-risk heavy hitters and sparse recovery schemes
Authors: Li, Yi
Nakos, Vasileios
Woodruff, David P.
Keywords: Heavy Hitters
Sparse Recovery
Issue Date: 2018
Source: Li, Y., Nakos, V., & Woodruff, D. P. (2018). On low-risk heavy hitters and sparse recovery schemes. Leibniz International Proceedings in Informatics, 116, 19-. doi:10.4230/LIPIcs.APPROX-RANDOM.2018.19
Series/Report no.: Leibniz International Proceedings in Informatics
Abstract: We study the heavy hitters and related sparse recovery problems in the low failure probability regime. This regime is not well-understood, and the main previous work on this is by Gilbert et al. (ICALP'13). We recognize an error in their analysis, improve their results, and contribute new sparse recovery algorithms, as well as provide upper and lower bounds for the heavy hitters problem with low failure probability. Our results are summarized as follows: 1) (Heavy Hitters) We study three natural variants for finding heavy hitters in the strict turnstile model, where the variant depends on the quality of the desired output. For the weakest variant, we give a randomized algorithm improving the failure probability analysis of the ubiquitous Count-Min data structure. We also give a new lower bound for deterministic schemes, resolving a question about this variant posed in Question 4 in the IITK Workshop on Algorithms for Data Streams (2006). Under the strongest and well-studied l_{infty}/ l_2 variant, we show that the classical Count-Sketch data structure is optimal for very low failure probabilities, which was previously unknown. 2) (Sparse Recovery Algorithms) For non-adaptive sparse-recovery, we give sublinear-time algorithms with low-failure probability, which improve upon Gilbert et al. (ICALP'13). In the adaptive case, we improve the failure probability from a constant by Indyk et al. (FOCS '11) to e^{-k^{0.99}}, where k is the sparsity parameter. 3) (Optimal Average-Case Sparse Recovery Bounds) We give matching upper and lower bounds in all parameters, including the failure probability, for the measurement complexity of the l_2/l_2 sparse recovery problem in the spiked-covariance model, completely settling its complexity in this model.
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.19
Rights: © 2018 Yi Li, Vasileios Nakos, and David P. Woodruff; licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
On low-risk heavy hitters and sparse recovery schemes.pdf569.22 kBAdobe PDFThumbnail

Citations 50

Updated on Nov 15, 2022

Page view(s)

Updated on Dec 7, 2022

Download(s) 50

Updated on Dec 7, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.