| Paper ID | SPTM-6.6 |
| Paper Title |
COUNT SKETCH WITH ZERO CHECKING: EFFICIENT RECOVERY OF HEAVY COMPONENTS |
| Authors |
Guanqiang Zhou, Zhi Tian, George Mason University, United States |
| Session | SPTM-6: Sampling, Multirate Signal Processing and Digital Signal Processing 2 |
| Location | Gather.Town |
| Session Time: | Tuesday, 08 June, 16:30 - 17:15 |
| Presentation Time: | Tuesday, 08 June, 16:30 - 17:15 |
| Presentation |
Poster
|
| Topic |
Signal Processing Theory and Methods: [SMDSP] Sampling, Multirate Signal Processing and Digital Signal Processing |
| IEEE Xplore Open Preview |
Click here to view in IEEE Xplore |
| Virtual Presentation |
Click here to watch in the Virtual Conference |
| Abstract |
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. |
