On Estimating the Rate-Distortion Function
Matthew Tom Harrison, Ioannis Kontoyiannis · 2006
Suppose a string XEn1= (X1, X2, ..., Xn) is generated by a stationary memoryless source (Xn)nges1with unknown distribution P. When the source is finite-valued, the problem of estimating the entropy H(P) using the data XEn1has received a lot of attention. Perhaps the simplest method is the so-called plug-in estimator H(PXn), where PXEn1is the empirical distribution of the data XEn1. This estimator is always strongly consistent, that is, H(PXEn1)rarrH(P) with probability one, as nrarrinfin. In this work we consider the natural generalization of estimating the rate-distortion function R(D, P). Our motivation comes from questions in lossy data compression and from cases where the data under consideration do not take values in a discrete alphabet. Our primary focus is the asymptotic behavior of the plug-in estimator R(PXEn1, D). This estimator need not be consistent, but in many cases it is. Several extensions are also considered, including stationary ergodic sources, and instances where the rate-distortion function is defined over a restricted class of coding distributions