Approximating entropy from sublinear samples

zbMATH Open1302.94024MaRDI QIDQ2934616FDOQ2934616

Authors: Mickey Brautbar, Alex Samorodnitsky 

Publication date: 18 December 2014

Recommendations

• The Complexity of Approximating the Entropy
• Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
• The complexity of estimating Rényi entropy
• Estimating the unseen, improved estimators for entropy and other properties
• A near-optimal algorithm for estimating the entropy of a stream

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Sampling theory in information and communication theory (94A20)

Cited In (5)

• Sublinear algorithms for approximating string compressibility
• Sampling, Metric Entropy, and Dimensionality Reduction
• Strong lower bounds for approximating distribution support size and the distinct elements problem
• Estimating Entropy on<tex>$m$</tex>Bins Given Fewer Than<tex>$m$</tex>Samples
• Guessing probability distributions from small samples

This page was built for publication: Approximating entropy from sublinear samples

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934616)