A strong version of the redundancy-capacity theorem of universalcoding

The capacity of the channel induced by a given class of sources is well known to be an attainable lower bound on the redundancy of universal codes with respect to this class, both in the minimax sense and in the Bayesian (maximin) sense. We show that this capacity is essentially a lower bound also in a stronger sense, that is, for “most” sources in the class. This result extends Rissanen's (1984, 1986) lower bound for parametric families. We demonstrate the applicability of this result in several examples, e.g., parametric families with growing dimensionality, piecewise-fixed sources, arbitrarily varying sources, and noisy samples of learnable functions. Finally, we discuss implications of our results to statistical inference     

Authors' reply to “Comments on `Min-Norm interpretations andconsistency of MUSIC, MODE, and ML'”

For original article see Ephraim et al. (IEEE Trans. Signal Processing, vol.43, p.2937-42, December 1995). For comments to original article see Stoica and Ottersten (IEEE Trans. Signal Processing, vol.46, p.2262-3, August 1998). In the present reply to the comments the authors note that the signal subspace fitting approach of Ephraim et al. (1995) is different from that of Viberg and Ottersten (1991), and the consistency proof in Ephraim et al. contains the missing steps in the proofs of Viberg and Ottersten, and Stoica and Nehorai (1989). These facts, as well as the correctness of the results in Ephraim et al., are not disputed in Stoica and Ottersten. Stoica and Ottersten rather assert that the results in Ephraim et al. were either known or obvious     

A large-deviations notion of perfect secrecy

We consider the Shannon cipher system with a variable key rate, and study the necessary and sufficient conditions for perfect secrecy in the sense that the exponential rate of the probability of breaking into the system would not be improved by observing the cryptogram. For a memoryless plain text source, we derive achievable lower bounds on the number of key bits needed for almost every plain text sequence in every type class. The corresponding minimum achievable average key rate turns out to be the negative logarithm of the probability of the most likely plain text letter, which is in general, smaller than the entropy.     

Estimating the number of states of a finite-state source

The problem of estimating the number of states of a finite-alphabet, finite-state source is investigated. An estimator is developed that asymptotically attains the minimum probability of understanding the number of states, among all estimators with a prescribed exponential decay rate of overestimation probability. The proposed estimator relies on the Lempel-Ziv data compression algorithm in an intuitively appealing manner     

On the capacity game of public watermarking systems

Watermarking codes are analyzed as a game between two players: an information hider and a decoder, on the one hand, and an attacker on the other hand. It is assumed that the covertext (the original data within which the message is hidden) is drawn from a memoryless stationary source and its realization is available at the information hider only. The information hider is allowed to cause some tolerable level of distortion to the covertext, and the resulting distorted data can suffer some additional amount of distortion caused by an attacker who aims at erasing the message. Motivated by a worst case approach, we assume that the attacker is informed of the hiding strategy taken by the information hider and the decoder, while they are uninformed of the attacking scheme. The capacity is expressed as the limit of a sequence of single-letter expressions under the assumption that the encoder uses constant composition codes.     

Two-way successively refined joint source-channel coding

Consider a source, {X/sub i/,Y/sub i/}/sub i=1//sup /spl infin//, producing independent copies of a pair of jointly distributed random variables (RVs). The {X/sub i/} part of the process is observed at some location, say A, and is supposed to be reproduced at a different location, say B, where the {Y/sub i/} part of the process is observed. Similarly, {Y/sub i/} should be reproduced at location A. The communication between the two locations is carried out across two memoryless channels in K iterative bi-directional rounds. In each round, the source components are reconstructed at the other locations based on the information exchanged in all previous rounds and the source component known at that location, and it is desired to find the amount of information that should be exchanged between the two locations in each round, so that the distortions incurred (in each round) will not exceed given thresholds. Our setting extends the results of Steinberg and Merhav as well as Kaspi, combining the notion of successive refinement with this of two-way interactive communication. We first derive a single-letter characterization of achievable rates for a pure source-coding problem with successive refinement. Then, for a joint source-channel coding setting, we prove a separation theorem, asserting that in the limit of long blocks, no optimality is lost by first applying lossy (two-way) successive-refinement source coding, regardless of the channels, and then applying good channel codes to each one of the resulting bitstreams, regardless of the source.     

On the estimation of the order of a Markov chain and universal datacompression

The authors estimate the order of a finite Markov source based on empirically observed statistics. The performance criterion adopted is to minimize the probability of underestimating the model order while keeping the overestimation probability exponent at a prescribed level. A universal asymptotically optimal test, in the sense just defined, is proposed for the case where a given integer is known to be the upper bound of the true order. For the case where such a bound is unavailable, an alternative rule based on the Lempel-Ziv data compression algorithm is shown to be asymptotically optimal also and computationally more efficient     

On Context-Tree Prediction of Individual Sequences

Motivated by the evident success of context-tree based methods in lossless data compression, we explore, in this correspondence, methods of the same spirit in universal prediction of individual sequences. By context-tree prediction, we refer to a family of prediction schemes, where at each time instant t, after having observed all outcomes of the data sequence x₁,...,x_t-1, but not yet x_t , the prediction is based on a "context" (or a state) that consists of the k most recent past outcomes x_t-k,...,x_t-1, where the choice of k may depend on the contents of a possibly longer, though limited, portion of the observed past, x_t-kmax,...,x_t-1. This is different from the study reported in the paper by Feder, Merhav, and Gutman (1992), where general finite-state predictors as well as "Markov" (finite-memory) predictors of fixed order, were studied in the regime of individual sequences. Another important difference between this study and the work of Feder is the asymptotic regime. While in their work, the resources of the predictor (i.e., the number of states or the memory size) were kept fixed regardless of the length N of the data sequence, here we investigate situations where the number of contexts, or states, is allowed to grow concurrently with N. We are primarily interested in the following fundamental question: What is the critical growth rate of the number of contexts, below which the performance of the best context-tree predictor is still universally achievable, but above which it is not? We show that this critical growth rate is linear in N. In particular, we propose a universal context-tree algorithm that essentially achieves optimum performance as long as the growth rate is sublinear, and show that, on the other hand, this is impossible in the linear case     

A Bayesian classification approach with application to speechrecognition

A Bayesian approach to classification of parametric information sources whose statistics are not explicitly given is studied and applied to recognition of speech signals based upon Markov modeling. A classifier based on generalized likelihood ratios, which depends only on the available training and testing data, is developed and shown to be optimal in the sense of achieving the highest asymptotic exponential rate of decay of the error probability. The proposed approach is compared to the standard classification approach used in speech recognition, in which the parameters for the sources are first estimated from the given training data, and then the maximum a posteriori decision rule is applied using the estimated statistics