Results on the optimal memory-assisted universal compression performance for mixture sources

摘要

In this paper, we consider the compression of a sequence from a mixture of K parametric sources. Each parametric source is represented by a d-dimensional parameter vector that is drawn from Jeffreys' prior. The output of the mixture source is a sequence of length n whose parameter is chosen from one of the K source parameter vectors uniformly at random. We are interested in the scenario in which the encoder and the decoder have a common side information of T sequences generated independently by the mixture source (which we refer to as memory-assisted universal compression problem). We derive the minimum average redundancy of the memory-assisted universal compression of a new random sequence from the mixture source and prove that when K = O(n^d/2(1−ε)) for some ε > 0, the side information provided by the previous sequences results in significant improvement over the universal compression without side information that is a function of n, T , and d. On the other hand, as K grows, the impact of the side information becomes negligible. Specifically, when K = Ω(n^d/2(1+ε)) for some ε > 0, optimal memory-assisted universal compression almost surely offers negligible improvement over the universal compression without side information.