Files in this item

FilesDescriptionFormat

application/pdf

application/pdfYANG-THESIS-2016.pdf (438kB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Optimal entropy estimation on large alphabet: fundamental limits and fast algorithms
Author(s):Yang, Pengkun
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
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
Type:Thesis
URI:http://hdl.handle.net/2142/90776
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