Files in this item



application/pdfYANG-THESIS-2016.pdf (438kB)
(no description provided)PDF


Title:Optimal entropy estimation on large alphabet: fundamental limits and fast algorithms
Author(s):Yang, Pengkun
Advisor(s):Wu, Yihong
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):entropy estimation
large alphabet
Abstract: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.
Issue Date:2016-04-19
Rights Information:Copyright 2016 Pengkun Yang
Date Available in IDEALS:2016-07-07
Date Deposited:2016-05

This item appears in the following Collection(s)

Item Statistics