Wald Lecture I: Counting Bits with Kolmogorov and Shannon
Wald Lecture I: Counting Bits with Kolmogorov and Shannon
复制标题
Wald 讲座一：与 Kolmogorov 和 Shannon 一起计算比特
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
S. Szarek
中科院分区：
文献类型：
--
作者：
D. Donoho;M. Ermakov;R. Gray;I. Johnstone;A. Samarov;S. Szarek
香农的率失真理论描述了近似表示随机过程X = (X(t): t∈t)的典型实现所需的比特数，而Kolmogorov的ǫ-entropy描述了近似表示函数类f的任意成员f = (f(t): t∈t)所需的比特数。对于许多随机过程，我们对速率畸变函数的行为已经有了大量的了解，而对于少数函数类F，我们已经成功地确定了ǫ-entropy的精确渐近性。设w2,0 （γ）表示一类函数f(t)在t = [0,2 π]上具有周期边界条件，且1 2π∫2π 0 f(t)dt + 1 2π∫2π 0 f(t)dt≤γ。我们证明了在L范数中逼近这类函数，我们有精确的Kolmogorov渐近性ǫentropy: h (W m 2,0(γ)) ~ 2m(log2e)(γ/ 2o), o→0。（0.1）这是从香农和柯尔莫哥洛夫理论之间的联系，这使我们能够利用香农的率失真理论的强大的形式主义来获得有关柯尔莫哥洛夫ǫ-entropy的信息。事实上，Kolmogorov ǫ-entropy是渐近等价的，因为在所有随机过程X上，在w2,0 （γ）中有样本路径的最大速率失真R(D，X)，其中我们使校准D = o。有一组高斯过程X * D，当D→0时，渐近地在w2,0 （γ）中实现，并且在指标D处的过程在w2,0 （γ）中的所有过程X中具有本质上最高的率失真R（D，X）。我们评估这个家族成员的率失真函数，给出公式（0.1）。这些结果与现代统计决策理论中的一个关键结果Pinsker定理非常相似。这指出了统计估计理论和数据压缩理论之间的联系，这将是这些讲座的主题。
Shannon’s Rate-Distortion Theory describes the number of bits needed to approximately represent typical realizations of a stochastic process X = (X(t) : t ∈ T ), while Kolmogorov’s ǫ-entropy describes the number of bits needed to approximately represent an arbitrary member f = (f(t) : t ∈ T ) of a functional class F . For many stochastic processes a great deal is known about the behavior of the rate distortion function, while for few functional classes F has there been success in determining, say, the precise asymptotics of the ǫ-entropy. Let W 2,0(γ) denote the class of functions f(t) on T = [0, 2π) with periodic boundary conditions and 1 2π ∫ 2π 0 f(t)dt + 1 2π ∫ 2π 0 f (t)dt ≤ γ. We show that for approximating functions of this class in L norm we have the precise asymptotics of the Kolmogorov ǫentropy: Hǫ(W m 2,0(γ)) ∼ 2m(log2 e)(γ/2ǫ) , ǫ → 0. (0.1) This follows from a connection between the Shannon and Kolmogorov theories, which allows us to exploit the powerful formalism of Shannon’s Rate-Distortion theory to obtain information about the Kolmogorov ǫ-entropy. In fact, the Kolmogorov ǫ-entropy is asymptotically equivalent, as ǫ → 0, to the maximum Rate-Distortion R(D,X) over all stochastic processes X with sample paths in W 2,0(γ), where we make the calibration D = ǫ . There is a family of Gaussian processes X∗ D which asymptotically, as D → 0, take realizations in W 2,0(γ), and for which the process at index D has essentially the highest rate-distortion R(D,X) of all processes X living in W 2,0(γ). We evaluate the rate-distortion function of members of this family, giving formula (0.1). These results strongly parallel a key result in modern statistical decision theory, Pinsker’s theorem. This points to a connection between theories of statistical estimation and data compression, which will be the theme of these Lectures.