Towards Analytic Information Theory: Data Compression, Prediction and Universal Coding Through Analytic Methods

信息论迎来了50周年诞辰。尽管以任何标准衡量，这都是一个成熟的研究领域，但由于新的应用和新的理论发展，出现了新的挑战。(例如，人们对多媒体应用程序的源代码编码重新产生了兴趣。)在1997年的香农讲座中，Jacob Ziv提出了令人信服的论点，主张在一定程度上从信息系统的(一阶)渐近分析中“后退”，以便预测我们总是面对有限(通常是很小)长度的序列、文件、代码等的真实系统的行为。克服这些困难的一种方法是通过用完全的渐近展开和更准确的分析(例如，大偏差、中心极限定律)来取代一阶分析(例如，平均码长的前导项)来提高渐近分析的精度。我们建议通过用分析方法探索信息论的问题来实现这一目标，也就是说，在这些问题中，复分析起着关键作用。在其他方面，我们提出了无损Lempel-Ziv方案、Lempel-Ziv方案的有损扩展(基于近似模式匹配)、上下文量化(旨在将上下文树权重扩展到有损环境)、基于模式匹配的预测方案以及冗余率的分级等研究。这里讨论的分析方法有：泛函-微分方程的渐近分析，泊松和解泊散化，以及复渐近。

Information theory celebrates its 50-th birthday. Although it is a mature area of research by any standard, new challenges arise due to new applications and new theoretical developments. (For example, there is a resurgence of interest in source coding for multimedia applications.) In the 1997 Shannon Lecture Jacob Ziv presented compelling arguments for "backing off" to a certain degree from the (first-order) asymptotic analysis of information systems in order to predict the behavior of real systems where we always face finite (and often small) lengths of sequences, files, codes, etc. One way to overcome these difficulties is to increase the accuracy of asymptotic analysis by replacing first- order analyses (e.g., a leading term of the average code length) by full asymptotic expansions and more accurate analyses (e.g., large deviations, central limit laws). We propose to accomplish this goal by exploring problems of information theory by analytic methods, that is, those in which complex analysis plays a pivotal role. Among others we propose research on lossless Lempel-Ziv schemes, lossy extension of Lempel-Ziv schemes (based on approximate pattern matching), context quantization (which aims at extending context-tree weighting to the lossy environment), prediction schemes based on pattern matching, and hierarchy of redundancy rates. Analytic methods discussed here are: asymptotic analysis of functional-differential equations, poissonization and depoissonization, and complex asymptotics.