Count Sketch with Zero Checking: Efficient Recovery of Heavy Components
Count Sketch with Zero Checking: Efficient Recovery of Heavy Components
复制标题
DOI：
10.1109/icassp39728.2021.9413853
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Guanqiang Zhou;Zhi Tian
中科院分区：
文献类型：
--
作者：
Guanqiang Zhou;Zhi Tian
从压缩数据中恢复高维向量的重分量是一个广泛应用的问题，如在有限的计算内存下的特征提取和在有限的带宽下的分布式学习。近年来，一种被称为计数草图的压缩算法在各个领域得到了广泛的应用。在本文中，我们仔细分析计数草图，并说明其默认恢复方法，即中值滤波，具有明显的误报错误模式。为了消除这种错误模式，我们提出了一种新的零检测方案，该方案采用两步恢复方法来提高检测假阳性的概率。我们提出的技术建立在严格的误差分析基础上，这使我们能够优化关键设计参数的选择，以获得最大的性能增益。实验结果表明，该方法比中值滤波具有更好的恢复精度，并且需要较少的样本即可准确恢复重分量。
The problem of recovering heavy components of a high-dimensional vector from compressed data is of great interest in broad applications, such as feature extraction under scarce computing memory and distributed learning under limited bandwidth. Recently, a compression algorithm called count sketch has gained wide popularity to recover heavy components in various fields. In this paper, we carefully analyze count sketch and illustrate that its default recovery method, namely median filtering, has a distinct error pattern of reporting false positives. To counteract this error pattern, we propose a new scheme called zero checking which adopts a two-step recovery approach to improve the probability of detecting false positives. Our proposed technique builds on rigorous error analysis, which enables us to optimize the selection of a key design parameter for maximum performance gain. The empirical results show that our scheme achieves better recovery accuracy than median filtering and requires less samples to accurately recover heavy components.