Universal entropy estimation via block sorting

Haixiao Cai; Sanjeev R. Kulkarni; Sergio Verdú

doi:10.1109/TIT.2004.830771

Universal entropy estimation via block sorting

Haixiao Cai, Sanjeev R. Kulkarni, Sergio Verdú

Research output: Contribution to journal › Letter › peer-review

51 Scopus citations

Abstract

In this correspondence, we present a new universal entropy estimator for stationary ergodic sources, prove almost sure convergence, and establish an upper bound on the convergence rate for finite-alphabet finite memory sources. The algorithm is motivated by data compression using the Burrows-Wheeler block sorting transform (BWT). By exploiting the property that the BWT output sequence is close to a piecewise stationary memoryless source, we can segment the output sequence and estimate probabilities in each segment. Experimental results show that our algorithm outperforms Lempel-Ziv (LZ) string-matching-based algorithms.

Original language	English (US)
Pages (from-to)	1551-1561
Number of pages	11
Journal	IEEE Transactions on Information Theory
Volume	50
Issue number	7
DOIs	https://doi.org/10.1109/TIT.2004.830771
State	Published - Jul 2004

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Block sorting
Burrows-wheelers transform (BWT)
Entropy estimation
Piecewise stationary memoryless source
Tree source

Access to Document

10.1109/TIT.2004.830771

Cite this

@article{dd7df9cb2d414d96a6fd1b3e29ee11fa,

title = "Universal entropy estimation via block sorting",

abstract = "In this correspondence, we present a new universal entropy estimator for stationary ergodic sources, prove almost sure convergence, and establish an upper bound on the convergence rate for finite-alphabet finite memory sources. The algorithm is motivated by data compression using the Burrows-Wheeler block sorting transform (BWT). By exploiting the property that the BWT output sequence is close to a piecewise stationary memoryless source, we can segment the output sequence and estimate probabilities in each segment. Experimental results show that our algorithm outperforms Lempel-Ziv (LZ) string-matching-based algorithms.",

keywords = "Block sorting, Burrows-wheelers transform (BWT), Entropy estimation, Piecewise stationary memoryless source, Tree source",

author = "Haixiao Cai and Kulkarni, {Sanjeev R.} and Sergio Verd{\'u}",

note = "Funding Information: Manuscript received May 5, 2003; revised March 31, 2004. 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 material in this correspondence was presented in part at the IEEE International Symposium on Information Theory, Lausanne, Switzerland, June/July 2002.",

year = "2004",

month = jul,

doi = "10.1109/TIT.2004.830771",

language = "English (US)",

volume = "50",

pages = "1551--1561",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "7",

}

TY - JOUR

T1 - Universal entropy estimation via block sorting

AU - Cai, Haixiao

AU - Kulkarni, Sanjeev R.

AU - Verdú, Sergio

N1 - Funding Information: Manuscript received May 5, 2003; revised March 31, 2004. 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 material in this correspondence was presented in part at the IEEE International Symposium on Information Theory, Lausanne, Switzerland, June/July 2002.

PY - 2004/7

Y1 - 2004/7

N2 - In this correspondence, we present a new universal entropy estimator for stationary ergodic sources, prove almost sure convergence, and establish an upper bound on the convergence rate for finite-alphabet finite memory sources. The algorithm is motivated by data compression using the Burrows-Wheeler block sorting transform (BWT). By exploiting the property that the BWT output sequence is close to a piecewise stationary memoryless source, we can segment the output sequence and estimate probabilities in each segment. Experimental results show that our algorithm outperforms Lempel-Ziv (LZ) string-matching-based algorithms.

AB - In this correspondence, we present a new universal entropy estimator for stationary ergodic sources, prove almost sure convergence, and establish an upper bound on the convergence rate for finite-alphabet finite memory sources. The algorithm is motivated by data compression using the Burrows-Wheeler block sorting transform (BWT). By exploiting the property that the BWT output sequence is close to a piecewise stationary memoryless source, we can segment the output sequence and estimate probabilities in each segment. Experimental results show that our algorithm outperforms Lempel-Ziv (LZ) string-matching-based algorithms.

KW - Block sorting

KW - Burrows-wheelers transform (BWT)

KW - Entropy estimation

KW - Piecewise stationary memoryless source

KW - Tree source

UR - http://www.scopus.com/inward/record.url?scp=3042515346&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=3042515346&partnerID=8YFLogxK

U2 - 10.1109/TIT.2004.830771

DO - 10.1109/TIT.2004.830771

M3 - Letter

AN - SCOPUS:3042515346

SN - 0018-9448

VL - 50

SP - 1551

EP - 1561

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 7

ER -

Universal entropy estimation via block sorting

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this