Optimal entropy estimation on large alphabet: fundamental limits and fast algorithms

Consider the problem of estimating the Shannon entropy of a distribution over k elements from n independent samples. We obtain the minimax mean- square error within universal multiplicative constant factors if n exceeds a constant factor of k/log(k); otherwise there exists no consistent estimator. This refines the recent result of Valiant and Valiant (2011) that the mini- mal sample size for consistent entropy estimation scales. The apparatus of best polynomial approximation plays a key role in both the construction of optimal estimators and, via a duality argument, the minimax lower bound.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2016

Author dc:creator

• Yang, Pengkun

Contributors dc:contributor

• Wu, Yihong

• entropy estimation
• large alphabet

Statement dc:rights

• Copyright 2016 Pengkun Yang

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/90776

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/90776