Fixed-rate universal lossy source coding and rates of convergencefor memoryless sources

A fixed-rate universal lossy coding scheme is introduced for independent and identically distributed (i.i.d.) sources. It is shown for finite alphabet sources and arbitrary single letter distortion measures that as the sample size n grows the expected distortion obtained using this universal scheme converges to Shannon's distortion rate function D(R) at a rate O(log n/n). The scheme can be extended to universal quantization of real i.i.d sources subject to a squared error criterion. It is shown in this case that the per-letter distortion converges to D(R) at a rate O(√(log n/n)) both in expectation and almost surely for any real-valued bounded i.i.d. source     

Multidimensional incremental parsing for universal source coding

A multidimensional incremental parsing algorithm (MDIP) for multidimensional discrete sources, as a generalization of the Lempel-Ziv coding algorithm, is investigated. It consists of three essential component schemes, maximum decimation matching, hierarchical structure of multidimensional source coding, and dictionary augmentation. As a counterpart of the longest match search in the Lempel-Ziv algorithm, two classes of maximum decimation matching are studied. Also, an underlying behavior of the dictionary augmentation scheme for estimating the source statistics is examined. For an m-dimensional source, m augmentative patches are appended into the dictionary at each coding epoch, thus requiring the transmission of a substantial amount of information to the decoder. The property of the hierarchical structure of the source coding algorithm resolves this issue by successively incorporating lower dimensional coding procedures in the scheme. In regard to universal lossy source coders, we propose two distortion functions, the local average distortion and the local minimax distortion with a set of threshold levels for each source symbol. For performance evaluation, we implemented three image compression algorithms based upon the MDIP; one is lossless and the others are lossy. The lossless image compression algorithm does not perform better than the Lempel-Ziv-Welch coding, but experimentally shows efficiency in capturing the source structure. The two lossy image compression algorithms are implemented using the two distortion functions, respectively. The algorithm based on the local average distortion is efficient at minimizing the signal distortion, but the images by the one with the local minimax distortion have a good perceptual fidelity among other compression algorithms. Our insights inspire future research on feature extraction of multidimensional discrete sources.     

An implementable lossy version of the Lempel-Ziv algorithm. I.Optimality for memoryless sources

A new lossy variant of the fixed-database Lempel-Ziv coding algorithm for encoding at a fixed distortion level is proposed, and its asymptotic optimality and universality for memoryless sources (with respect to bounded single-letter distortion measures) is demonstrated: as the database size m increases to infinity, the expected compression ratio approaches the rate-distortion function. The complexity and redundancy characteristics of the algorithm are comparable to those of its lossless counterpart. A heuristic argument suggests that the redundancy is of order (log log m)/log m, and this is also confirmed experimentally; simulation results are presented that agree well with this rate. Also, the complexity of the algorithm is seen to be comparable to that of the corresponding lossless scheme. We show that there is a tradeoff between compression performance and encoding complexity, and we discuss how the relevant parameters can be chosen to balance this tradeoff in practice. We also discuss the performance of the algorithm when applied to sources with memory, and extensions to the cases of unbounded distortion measures and infinite reproduction alphabets     

Markov types and minimax redundancy for Markov sources

Redundancy of universal codes for a class of sources determines by how much the actual code length exceeds the optimal code length. In the minimax scenario, one designs the best code for the worst source within the class. Such minimax redundancy comes in two flavors: average minimax or worst case minimax. We study the worst case minimax redundancy of universal block codes for Markovian sources of any order. We prove that the maximal minimax redundancy for Markov sources of order r is asymptotically equal to 1/2m/sup r/(m-1)log/sub 2/n+log/sub 2/A/sub m//sup r/-(lnlnm/sup 1/(m-1)/)/lnm+o(1), where n is the length of a source sequence, m is the size of the alphabet, and A/sub m//sup r/ is an explicit constant (e.g., we find that for a binary alphabet m=2 and Markov of order r=1 the constant A/sub 2//sup 1/=16/spl middot/G/spl ap/14.655449504 where G is the Catalan number). Unlike previous attempts, we view the redundancy problem as an asymptotic evaluation of certain sums over a set of matrices representing Markov types. The enumeration of Markov types is accomplished by reducing it to counting Eulerian paths in a multigraph. In particular, we propose exact and asymptotic formulas for the number of strings of a given Markov type. All of these findings are obtained by analytic and combinatorial tools of analysis of algorithms.     

On the redundancy of lossy source coding with abstract alphabets

The redundancy problem of lossy source coding with abstract source and reproduction alphabets is considered. For coding at a fixed rate level, it is shown that for any fixed rate R>0 and any memoryless abstract alphabet source P satisfying some mild conditions, there exists a sequence {C_n}_n=1^∞ of block codes at the rate R such that the distortion redundancy of C_n (defined as the difference between the performance of C_n and the distortion rate function d(P, R) of P) is upper-bounded by |(∂d(P,R))/(∂R)| ln n/2n+o(ln n/n). For coding at a fixed distortion level, it is demonstrated that for any d>0 and any memoryless abstract alphabet source P satisfying some mild conditions, there exists a sequence {C_n}_n=1^∞ of block codes at the fixed distortion d such that the rate redundancy of C_n (defined as the difference between the performance of C _n and the rate distortion function R(P,d) of P) is upper-bounded by (7ln n)/(6n)+o(ln n/n). These results strengthen the traditional Berger's (1968, 1971) abstract alphabet source coding theorem, and extend the positive redundancy results of Zhang, Yang, and Wei (see ibid., vol.43, no.1, p.71-91, 1997, and ibid., vol.42, p.803-21, 1996) on lossy source coding with finite alphabets and the redundancy result of Wyner (see ibid., vol.43, p.1452-64, 1997) on block coding of memoryless Gaussian sources     

Performance analysis of grammar-based codes revisited

The compression performance of grammar-based codes is revisited from a new perspective. Previously, the compression performance of grammar-based codes was evaluated against that of the best arithmetic coding algorithm with finite contexts. In this correspondence, we first define semifinite-state sources and finite-order semi-Markov sources. Based on the definitions of semifinite-state sources and finite-order semi-Markov sources, and the idea of run-length encoding (RLE), we then extend traditional RLE algorithms to context-based RLE algorithms: RLE algorithms with k contexts and RLE algorithms of order k, where k is a nonnegative integer. For each individual sequence x, let r/sup *//sub sr,k/(x) and r/sup *//sub sr|k/(x) be the best compression rate given by RLE algorithms with k contexts and by RLE algorithms of order k, respectively. It is proved that for any x, r/sup *//sub sr,k/ is no greater than the best compression rate among all arithmetic coding algorithms with k contexts. Furthermore, it is shown that there exist stationary, ergodic semi-Markov sources for which the best RLE algorithms without any context outperform the best arithmetic coding algorithms with any finite number of contexts. Finally, we show that the worst case redundancies of grammar-based codes against r/sup *//sub sr,k/(x) and r/sup *//sub sr|k/(x) among all length- n individual sequences x from a finite alphabet are upper-bounded by d/sub 1/loglogn/logn and d/sub 2/loglogn/logn, respectively, where d/sub 1/ and d/sub 2/ are constants. This redundancy result is stronger than all previous corresponding results.     

Asymptotically optimal low-complexity sequential lossless codingfor piecewise-stationary memoryless sources .I. The regular case

The lower bound on the redundancy for lossless universal coding of regular memoryless sources with a bounded number of abrupt changes in the statistics is shown to be asymptotically achievable using a fixed per-letter computational complexity sequential compression scheme with fixed storage complexity. The scheme which outperforms any other known fixed-complexity scheme when regularity conditions hold is presented, and its redundancy is upper-bounded. Although the upper bounds are merely asymptotic, simulation results show that even for relatively short sequences, the redundancy obtained by asymptotically optimal schemes of higher complexity can still be achieved with fixed per-letter complexity. Furthermore, in practice, a fixed-complexity scheme based on the proposed scheme can in most cases achieve optimal redundancy even when the regularity conditions do not hold     

Low-complexity sequential lossless coding for piecewise-stationarymemoryless sources

Three strongly sequential, lossless compression schemes, one with linearly growing per-letter computational complexity, and two with fixed per-letter complexity, are presented and analyzed for memoryless sources with abruptly changing statistics. The first method, which improves on Willems' (1994) weighting approach, asymptotically achieves a lower bound on the redundancy, and hence is optimal. The second scheme achieves redundancy of O(log N/N) when the transitions in the statistics are large, and O (log log N/log N) otherwise. The third approach always achieves redundancy of O (√log N/N). Obviously, the two fixed complexity approaches can be easily combined to achieve the better redundancy between the two. Simulation results support the analytical bounds derived for all the coding schemes     

The empirical distribution of rate-constrained source codes

Let X = (X/sub 1/,...) be a stationary ergodic finite-alphabet source, X/sup n/ denote its first n symbols, and Y/sup n/ be the codeword assigned to X/sup n/ by a lossy source code. The empirical kth-order joint distribution Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rceil/(x/sup k/,y/sup k/) is defined as the frequency of appearances of pairs of k-strings (x/sup k/,y/sup k/) along the pair (X/sup n/,Y/sup n/). Our main interest is in the sample behavior of this (random) distribution. Letting I(Q/sup k/) denote the mutual information I(X/sup k/;Y/sup k/) when (X/sup k/,Y/sup k/)/spl sim/Q/sup k/ we show that for any (sequence of) lossy source code(s) of rate /spl les/R lim sup/sub n/spl rarr//spl infin//(1/k)I(Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rfloor/) /spl les/R+(1/k)H (X/sub 1//sup k/)-H~(X) a.s. where H~(X) denotes the entropy rate of X. This is shown to imply, for a large class of sources including all independent and identically distributed (i.i.d.). sources and all sources satisfying the Shannon lower bound with equality, that for any sequence of codes which is good in the sense of asymptotically attaining a point on the rate distortion curve Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rfloor//spl rArr//sup d/P(X/sup k/,Y~/sup k/) a.s. whenever P(/sub X//sup k//sub ,Y//sup k/) is the unique distribution attaining the minimum in the definition of the kth-order rate distortion function. Consequences of these results include a new proof of Kieffer's sample converse to lossy source coding, as well as performance bounds for compression-based denoisers.     

The universality of grammar-based codes for sources with countably infinite alphabets

In this paper, we investigate the performance of grammar-based codes for sources with countably infinite alphabets. Let /spl Lambda/ denote an arbitrary class of stationary, ergodic sources with a countably infinite alphabet. It is shown that grammar-based codes can be modified so that they are universal with respect to any /spl Lambda/ if and only if there exists a universal code for /spl Lambda/. Moreover, upper bounds on the worst case redundancies of grammar-based codes among large sets of length-n individual sequences from a countably infinite alphabet are established. Depending upon the conditions satisfied by length-n individual sequences, these bounds range from O(loglogn/logn) to O(1/log/sup 1-/spl alpha//n) for some 0相似文献   

On the redundancy of the fixed-database Lempel-Ziv algorithm forφ-mixing sources

The redundancy problem of the fixed-database Lempel-Ziv (1977) algorithm is considered. It is demonstrated that for a class of φ-mixing sources which includes Markov sources, unifilar sources, and finite-state sources as special cases, the redundancy of the fixed-database Lempel-Ziv algorithm with database size n is lower-bounded by H(loglogn)/logn+O((logloglogn)/logn) and upper-bounded by 2H(loglogn)/logn+O((logloglogn)/logn) where H is the entropy rate of the source. The method of proof is new and uses the concept of variable-length to variable-length codes     

The minimax distortion redundancy in empirical quantizer design

We obtain minimax lower and upper bounds for the expected distortion redundancy of empirically designed vector quantizers. We show that the mean-squared distortion of a vector quantizer designed from n independent and identically distributed (i.i.d.) data points using any design algorithm is at least Ω(n^-1/2) away from the optimal distortion for some distribution on a bounded subset of ℛ ^d. Together with existing upper bounds this result shows that the minimax distortion redundancy for empirical quantizer design, as a function of the size of the training data, is asymptotically on the order of n^-1/2. We also derive a new upper bound for the performance of the empirically optimal quantizer     

Simple universal lossy data compression schemes derived from theLempel-Ziv algorithm

Two universal lossy data compression schemes, one with fixed rate and the other with fixed distortion, are presented, based on the well-known Lempel-Ziv algorithm. In the case of fixed rate R, the universal lossy data compression scheme works as follows: first pick a codebook B_n consisting of all reproduction sequences of length n whose Lempel-Ziv codeword length is ⩽nR, and then use B_n to encode the entire source sequence n-block by n-block. This fixed-rate data compression scheme is universal in the sense that for any stationary, ergodic source or for any individual sequence, the sample distortion performance as n→∞ is given almost surely by the distortion rate function. A similar result is shown in the context of fixed distortion lossy source coding     

On the MDL principle for i.i.d. sources with large alphabets

Average case universal compression of independent and identically distributed (i.i.d.) sources is investigated, where the source alphabet is large, and may be sublinear in size or even larger than the compressed data sequence length n. In particular, the well-known results, including Rissanen's strongest sense lower bound, for fixed-size alphabets are extended to the case where the alphabet size k is allowed to grow with n. It is shown that as long as k=o(n), instead of the coding cost in the fixed-size alphabet case of 0.5logn extra code bits for each one of the k-1 unknown probability parameters, the cost is now 0.5log(n/k) code bits for each unknown parameter. This result is shown to be the lower bound in the minimax and maximin senses, as well as for almost every source in the class. Achievability of this bound is demonstrated with two-part codes based on quantization of the maximum-likelihood (ML) probability parameters, as well as by using the well-known Krichevsky-Trofimov (KT) low-complexity sequential probability estimates. For very large alphabets, kGtn, it is shown that an average minimax and maximin bound on the redundancy is essentially (to first order) log(k/n) bits per symbol. This bound is shown to be achievable both with two-part codes and with a sequential modification of the KT estimates. For k=Theta(n), the redundancy is Theta(1) bits per symbol. Finally, sequential codes are designed for coding sequences in which only m相似文献   

Symbol-intersecting codes

We consider codes consisting of arrays over an alphabet F, in which certain intersecting subsets of n/spl times/m coordinates are required to form codewords of length n in prescribed codes over the alphabet F/sup m/. Two specific cases are studied. In the first case, referred to as a singly-intersecting coding scheme, the user data is mapped into n/spl times/(2m-1) arrays over an alphabet F, such that the n/spl times/m subarray that consists of the left (respectively, right) m columns forms a codeword of a prescribed code of length n over F/sup m/; in particular, the center column is shared by the left and right subarrays. Bounds are obtained on the achievable redundancy region of singly-intersecting coding schemes, and constructions are presented that approach-and sometimes meet-these bounds. It is shown that singly-intersecting coding schemes can be applied in a certain model of broadcast channels to guarantee reliable communication. The second setting, referred to as a fully-intersecting coding scheme, maps the user data into n/spl times/m/spl times/m three-dimensional arrays in which parallel n/spl times/m subarrays are all codewords of the same prescribed code over F/sup m/. Bounds and constructions are presented for these codes, with the analysis based on representing the n/spl times/m/spl times/m arrays as vectors over certain algebras on m/spl times/m matrices.     

Context-dependent multilevel pattern matching for lossless image compression

In this paper, the multilevel pattern matching (MPM) code for compression of one-dimensional (1D) sequences is first generalized to compress two-dimensional (2D) images, resulting in a 2D multilevel pattern matching (MPM) code. It is shown that among all images of n pixels, the worst case redundancy of the 2D MPM code against any finite-template-based arithmetic code is O(1//spl radic/logn). This result contrasts unfavorably with the fact that among all 1D sequences of length n, the MPM code has a worst case redundancy of O(1/logn) against any finite-state arithmetic code; this is caused by the so-called 2D boundary effect. To alleviate the 2D boundary effect, we extend the 2D MPM code to the case of context modeling, yielding a context-dependent 2D MPM code. It is shown that among all images of n pixels, the context-dependent 2D MPM code has an O(1/logn) worst case redundancy against any finite-template-based arithmetic code satisfying a mild condition; this redundancy is better than that of the 2D MPM code without context models. Experimental results demonstrate that the context-dependent 2D MPM code significantly outperforms the 2D MPM code without context models for bi-level images. It is also demonstrated that, in terms of compression rates, the context-dependent 2D MPM code performs significantly better than the progressive coding mode of JBIG1 for both textual and bi-level images, and better than or comparably to the sequential coding mode of JBIG1 and JBIG2. In addition to its excellent compression performance, the context-dependent 2D MPM code allows progressive transmission of images.     

On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms

We clarify, extend, and solve a long-standing open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We first focus on the difference between the time a packet finishes service in a scheduling algorithm and its virtual finish time under a GPS (General Processor Sharing) scheduler, called GPS-relative delay. We prove that, under a slightly restrictive but reasonable computational model, the lower bound computational complexity of any scheduling algorithm that guarantees O(1) GPS-relative delay bound is /spl Omega/(logn). We also discover that, surprisingly, the complexity lower bound remains the same even if the delay bound is relaxed to O(n/sup a/) for 0相似文献   

Precise minimax redundancy and regret

Recent years have seen a resurgence of interest in redundancy of lossless coding. The redundancy (regret) of universal fixed-to-variable length coding for a class of sources determines by how much the actual code length exceeds the optimal (ideal over the class) code length. In a minimax scenario one finds the best code for the worst source either in the worst case (called also maximal minimax) or on average. We first study the worst case minimax redundancy over a class of stationary ergodic sources and replace Shtarkov's bound by an exact formula. Among others, we prove that a generalized Shannon code minimizes the worst case redundancy, derive asymptotically its redundancy, and establish some general properties. This allows us to obtain precise redundancy for memoryless, Markov, and renewal sources. For example, we present the exact constant of the redundancy for memoryless and Markov sources by showing that the integer nature of coding contributes log(logm/(m-1))/logm+o(1) where m is the size of the alphabet. Then we deal with the average minimax redundancy and regret. Our approach here is orthogonal to most recent research in this area since we aspire to show that asymptotically the average minimax redundancy is equivalent to the worst case minimax redundancy for some classes of sources. After formulating some general bounds relating these two redundancies, we prove our assertion for memoryless and Markov sources. Nevertheless, we provide evidence that maximal redundancy of renewal processes does not have the same leading term as the average minimax redundancy (however, our general results show that maximal and average regrets are asymptotically equivalent).     

How to fool an unbounded adversary with a short key

The symmetric encryption problem which manifests itself when two parties must securely transmit a message m with a short shared secret key is considered in conjunction with a computationally unbounded adversary. As the adversary is unbounded, any encryption scheme must leak information about m; in particular, the mutual information between m and its ciphertext cannot be zero. Despite this, a family of encryption schemes is presented that guarantee that for any message space in {0,1}/sup n/ with minimum entropy n-/spl lscr/ and for any Boolean function h:{0,1}/sup n/ /spl rarr/ {0,1}, no adversary can predict h(m) from the ciphertext of m with more than 1/n/sup /spl omega/(1)/ advantage; this is achieved with keys of length /spl lscr/+/spl omega/(logn). In general, keys of length /spl lscr/+s yield a bound of 2/sup -/spl Theta/(s)/ on the advantage. These encryption schemes rely on no unproven assumptions and can be implemented efficiently. Applications of this to cryptosystems based on complexity-theoretic assumptions are discussed and, in addition, a simplified proof of a fundamental "elision lemma" of Goldwasser and Micali is provided.