Estimating entropy of distributions in constant space
We consider the task of estimating the entropy of k-ary distributions from samples in the streaming model, where space is limited. Our main contribution is an algorithm that requires O ( klog(1"3/")2 ) samples and a constant O(1) memory words of space and outputs a ±" estimate of H(p)...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Neural Information Processing Systems Foundation
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129554 |