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

信息论迎来了它的50岁生日。 虽然它是一个成熟的研究领域的任何标准，新的挑战出现，由于新的应用和新的理论发展。 (For例如，对多媒体应用的信源编码的兴趣正在复苏。 在1997年的香农演讲中，雅各布·齐夫提出了令人信服的论点，即在一定程度上从信息系统的（一阶）渐近分析中“后退”，以预测真实的系统的行为，在这种系统中，我们总是面对有限（通常很小）长度的序列、文件、代码等。 克服这些困难的一种方法是通过替换一阶分析（例如，平均码长的首项）通过完全渐近展开和更精确的分析（例如， 大偏差，中心极限定律）。 我们建议通过用分析方法探索信息论问题来实现这一目标，即复分析在其中起着关键作用的问题。 其中，我们提出了无损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.