Unbiased estimation of inner product via higher order count sketch

Count sketch [1] is one of the popular sketching algorithms widely used for frequency estimation in data streams, and pairwise inner product for real-valued vectors [2]. Recently, Shi et al. [3] extended the count sketch (CS) and suggested a higher-order count sketch (HCS) algorithm that compresses input tensors (or vectors) into succinct tensors which closely approximates the value of queried features of the input. The major advantage of HCS is that it is more space-efficient than count sketch. However, their paper didn't comment on estimating pairwise inner product from the sketch. This note demonstrates that HCS also closely approximates the pairwise inner product. We showed that their sketch gives an unbiased estimate of the pairwise inner product, and gives a concentration analysis of the estimate. & COPY; 2023 Elsevier B.V. All rights reserved.

Automated summary

Count sketch is a popular sketching algorithm used for frequency estimation in data streams and pairwise inner product for real-valued vectors. This paper extends count sketch and introduces a higher-order count sketch algorithm, which compresses input tensors to approximate the queried features. It is shown that the higher-order count sketch can also closely approximate the pairwise inner product and provides a concentration analysis of the estimate.