Unbiased estimation of inner product via higher order count sketch |
| |
| Affiliation: | 1. Indian Institute of Technology Mandi, Himachal Pradesh, India;2. Indian Institute of Technology Hyderabad, Telangana, India;1. Department of Mathematics, Federal University of Ceará, Fortaleza, Brazil;2. CMUC, Department of Mathematics, University of Coimbra, Coimbra, Portugal;3. Department of Computer Science, Federal University of Ceará, Fortaleza, Brazil;1. Department of Applied Mathematics, Computer Science and Statistics, Ghent University, Krijgslaan 281 - S9, 9000 Ghent, Belgium;2. Department of Mathematics, Babe?-Bolyai University, Cluj-Napoca, Romania;1. Shantou University, China;2. Univ Rennes, INRIA, CNRS, IRISA, France;1. The Institute of Mathematical Sciences (CI of Homi Bhabha National Institute, Mumbai), CIT Campus, Taramani, Chennai, 600113, TN, India;2. Indian Institute of Technology Hyderabad, Kandi, Sangareddy, Hyderabad, 502285, Telangana, India |
| |
| Abstract: | 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. |
| |
| Keywords: | Count sketch Higher order count sketch Inner product Randomized algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
