Sketching and Streaming Entropy via Approximation Theory

Details Sketching and Streaming Entropy via Approximation Theory Sketching and Streaming Entropy via Approximation Theory

2008-04-25

arxiv.org/abs/0804.4138v1

Computer Science

Data Structures and Algorithms

Scientific paper

We conclude a sequence of work by giving near-optimal sketching and streaming algorithms for estimating Shannon entropy in the most general streaming model, with arbitrary insertions and deletions. This improves on prior results that obtain suboptimal space bounds in the general model, and near-optimal bounds in the insertion-only model without sketching. Our high-level approach is simple: we give algorithms to estimate Renyi and Tsallis entropy, and use them to extrapolate an estimate of Shannon entropy. The accuracy of our estimates is proven using approximation theory arguments and extremal properties of Chebyshev polynomials, a technique which may be useful for other problems. Our work also yields the best-known and near-optimal additive approximations for entropy, and hence also for conditional entropy and mutual information.

Affiliated with

Also associated with

No associations

Rating

Sketching and Streaming Entropy via Approximation Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sketching and Streaming Entropy via Approximation Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sketching and Streaming Entropy via Approximation Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-728184