TY - JOUR
T1 - Universal divergence estimation for finite-alphabet sources
AU - Cai, Haixia
AU - Kulkarni, Sanjeev R.
AU - Verdú, Sergio
N1 - Funding Information:
Manuscript received November 18, 2004; revised April 3, 2006. This work was supported in part by ARL MURI under Grant DAAD19-00-1-0466, Draper Laboratory under IR&D 6002 Grant DL-H-546263, and the National Science Foundation under Grant CCR-0312413. The authors are with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: [email protected]; [email protected]; [email protected]). Communicated by M. Effros, Associate Editor for Source Coding. Digital Object Identifier 10.1109/TIT.2006.878182
PY - 2006/8
Y1 - 2006/8
N2 - This paper studies universal estimation of divergence from the realizations of two unknown finite-alphabet sources. Two algorithms that borrow techniques from data compression are presented. The first divergence estimator applies the Burrows-Wheeler block sorting transform to the concatenation of the two realizations; consistency of this estimator is shown for all finite-memory sources. The second divergence estimator is based on the Context Tree Weighting method; consistency is shown for all sources whose memory length does not exceed a known bound. Experimental results show that both algorithms perform similarly and outperform string-matching and plug-in methods.
AB - This paper studies universal estimation of divergence from the realizations of two unknown finite-alphabet sources. Two algorithms that borrow techniques from data compression are presented. The first divergence estimator applies the Burrows-Wheeler block sorting transform to the concatenation of the two realizations; consistency of this estimator is shown for all finite-memory sources. The second divergence estimator is based on the Context Tree Weighting method; consistency is shown for all sources whose memory length does not exceed a known bound. Experimental results show that both algorithms perform similarly and outperform string-matching and plug-in methods.
KW - Block sorting
KW - Burrows-Wheeler transform
KW - Context tree weighting method
KW - Divergence estimation
KW - Information divergence
KW - Markov sources
KW - Universal methods
UR - http://www.scopus.com/inward/record.url?scp=33746656746&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33746656746&partnerID=8YFLogxK
U2 - 10.1109/TIT.2006.878182
DO - 10.1109/TIT.2006.878182
M3 - Article
AN - SCOPUS:33746656746
SN - 0018-9448
VL - 52
SP - 3456
EP - 3475
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 8
ER -