Theoretical results show that Bayesian methods can achieve lower bounds on regret for online logistic regression. In practice, however, such techniques may not be feasible especially for very large feature sets. Various approximations that, for huge sparse feature sets, diminish the theoretical advantages, must be used. Often, stochastic gradient methods is used with hyper-parameters that must be tuned on some surrogate loss, defeating theoretical advantages of Bayesian methods. The surrogate loss, defined to approximate the mixture, requires techniques as Monte Carlo sampling, increasing computations per example. We propose low complexity algorithm for sparse online logistic and probit regressions that runs linearly in time horizon. Unlike variational inference and other methods, our methods use analytical closed forms, substantially lowering computations. Unlike dense solutions, as Gaussian Mixtures, our methods allow for sparse problems with huge feature sets without increasing complexity. With the analytical closed forms, there is also no need for applying stochastic gradient methods on surrogate losses, and for tuning and balancing learning and regularization hyper-parameters. Empirical results top the performance of the more computationally involved methods.

We study online logistic regression with binary labels and general feature values in which a learner tries to predict an outcome/ label based on data/ features received in rounds. Our goal is to evaluate precisely the (maximal) minimax regret which we analyze using a unique and novel combination of information-theoretic and analytic combinatorics tools such as Fourier transform, saddle point method, and Mellin transform in the multi-dimensional settings. To be more precise, the pointwise regret of an online algorithm is defined as the (excess) loss it incurs over a constant comparator which is used for prediction. In the minimax scenario we seek the best learning distribution for the worst label sequence. For dimension d = o(T1/3) we show that the maximal minimax regret grows as $d/2 \cdot \log (2T/\pi ) + {C_d} + O\left({{d^{3/2}}/\sqrt T }\right)$ where T is the number of rounds of running a training algorithm and Cdis explicitly computable constant that depends on dimension d and feature values. We compute explicitly the constant Cdfor features uniformly distributed on a d-dimensional sphere or ball.

We initiate a formal study of reproducibility in optimization. We define a quantitative measure of reproducibility of optimization procedures in the face of noisy or error-prone operations such as inexact or stochastic gradient computations or inexact initialization. We then analyze several convex optimization settings of interest such as smooth, non-smooth, and strongly-convex objective functions and establish tight bounds on the limits of reproducibility in each setting. Our analysis reveals a fundamental trade-off between computation and reproducibility: more computation is necessary (and sufficient) for better reproducibility.

A fundamental challenge in learning is the presence of nonlinear redundancies and dependencies in the data. To address this, we propose a Fourier-based approach to characterize feature redundancies, in unsupervised learning, and feature-label dependencies, in the supervised variant of the problem. We first develop a novel Fourier expansion for functions (more generally stochastic mappings) of correlated binary random variables. This is a generalization of the standard Fourier expansion on the Boolean cube beyond product probability spaces. As an important application of this analysis, we investigate learning with feature subset selection. In the unsupervised variant of this problem, we characterize feature redundancies via the Shannon entropy and group the features into sufficiently informative and redundant. Then, we make a connection to the proposed Fourier expansion and derive an upper bound on the joint entropy. Based on that, we propose a measure to quantify feature redundancies and present an unsupervised learning algorithm. We test our method on various real-world and synthetic datasets and demonstrate improvements on conventional unsupervised feature selection techniques. Then, we investigate the supervised feature subset selection and reformulate it in the Fourier domain. Bridging the Bayesian error rate with the Fourier coefficients, we demonstrate that the Fourier expansion provides a powerful tool to characterize nonlinear feature-label dependencies. Further, we introduce a computationally efficient measure for selecting relevant features. Via a theoretical analysis, we show that our proposed measure finds provablyasymptotically optimalfeature subsets. Lastly, we present an algorithm based on this measure and via numerical experiments demonstrate its improvements on various supervised feature selection algorithms.

We study logistic regression with binary labels and categorical (discrete) feature values. Our goal is to evaluate precisely the (maximal) minimax regret. We express it as the so called Shtarkov sum known in information theory. To the best of our knowledge such a sum was never computed in the context of logistic regression. To be more precise, the pointwise regret of an online algorithm is defined as the (excess) loss it incurs over some value of a constant comparator (weight vector) that is used for prediction. It depends on the feature values, label sequence, and the learning algorithm. In the maximal minimax scenario we seek the best weights for the worst label sequence over all possible learning algorithms/ distributions, therefore it constitutes a lower bound for the pointwise regret. For finite dimension $d$ and $N$ distinct feature vectors we show that the maximal minimax regret grows as $$ \frac{d}{2} \log (T/2\pi)+C_d + O(N/\sqrt{T}) $$ where $T$ is the number of rounds of running a training algorithm and $C_d$ is explicitly computable constant that depends on the feature values and dimension $d$. We also extend these results to non-binary labels. The {\it precise} maximal minimax regret presented here is the first result of this kind. Our findings are obtained using tools of analytic combinatorics and information theory.

A fundamental obstacle in learning information from data is the presence of nonlinear redundancies and dependencies in it. To address this, we propose a Fourier-based approach to extract relevant information in the supervised setting. We first develop a novel Fourier expansion for functions of correlated binary random variables. This expansion is a generalization of the standard Fourier analysis on the Boolean cube beyond product probability spaces. We further extend our Fourier analysis to stochastic mappings. As an important application of this analysis, we investigate learning with feature subset selection. We reformulate this problem in the Fourier domain and introduce a computationally efficient measure for selecting features. Bridging the Bayesian error rate with the Fourier coefficients, we demonstrate that the Fourier expansion provides a powerful tool to characterize nonlinear dependencies in the features-label relation. Via theoretical analysis, we show that our proposed measure finds provably asymptotically optimal feature subsets. Lastly, we present an algorithm based on our measure and verify our findings via numerical experiments on various datasets.

We take an information-theoretic approach to identify nonlinear feature redundancies in unsupervised learning. We define a subset of features as sufficiently-informative when the joint entropy of all the input features equals that of the chosen subset. We argue that the rest of the features are redundant as all the accessible information about the data can be captured from sufficiently-informative features. Next, instead of directly estimating the entropy, we propose a Fourier-based characterization. For that, we develop a novel Fourier expansion on the Boolean cube incorporating correlated random variables. This generalization of the standard Fourier analysis is beyond product probability spaces. Based on our Fourier framework, we propose a measure of redundancy for features in the unsupervised settings. We then consider a variant of this measure with a search algorithm to reduce its computational complexity as low as$O$(nd) with$n$being the number of samples and$d$the number of features. Besides the theoretical justifications, we test our method on various real-world and synthetic datasets. Our numerical results demonstrate that the proposed method outperforms state-of-the-art feature selection techniques.

We study logistic regression with binary features in which the number (or degree) of occurring features determines the label probability. This model fits one of social networks, where the number of friends determines the likelihood of outcomes instead of the identity of the friends, or more generally, a graph model, where the degree of a node can determine its structure. It includes the case in which weights can be viewed as i.i.d. (e.g., in Bayesian modeling). For such a model, we introduce the maximal minimax regret that we analyze using a unique combination of analytic combinatorics and information theory. More importantly, the resulting regret is a general lower bound for the pointwise regret of a general logistic regression over all algorithms (learning distributions). We show that the introduced worst case (maximum over feature sequences) maximal minimax regret grows asymptotically as$(d/2)\log(T/d)+(d/2)\log(\pi/2)+O(d/\sqrt{T})$for dimensionality$d=o(\sqrt{T})$, which is a lower bound for a regret of a general logistic regression. We extend our results to loss functions other than logistic loss and non-binary labels.

We address the problem of the achievable regret rates with online logistic regression. We derive lower bounds with logarithmic regret under $L_1$, $L_2$, and $L_\infty$ constraints on the parameter values. The bounds are dominated by $d/2 \log T$, where $T$ is the horizon and $d$ is the dimensionality of the parameter space. We show their achievability for $d=o(T^{1/3})$ in all these cases with Bayesian methods, that achieve them up to a $d/2 \log d$ term. Interesting different behaviors are shown for larger dimensionality. Specifically, on the negative side, if $d = \Omega(\sqrt{T})$, any algorithm is guaranteed regret of $\Omega(d \log T)$ (greater than $\Theta(\sqrt{T})$) under $L_\infty$ constraints on the parameters (and the example features). On the positive side, under $L_1$ constraints on the parameters, there exist Bayesian algorithms that can achieve regret that is sub-linear in $d$ for the asymptotically larger values of $d$. For $L_2$ constraints, it is shown that for large enough $d$, the regret remains linear in $d$ but no longer logarithmic in $T$. Adapting the \emph{redundancy-capacity\/} theorem from information theory, we demonstrate a principled methodology based on grids of parameters to derive lower bounds. Grids are also utilized to derive some upper bounds. Our results strengthen results by Kakade and Ng (2005) and Foster et al. (2018) for upper bounds for this problem, introduce novel lower bounds, and adapt a methodology that can be used to obtain such bounds for other related problems. They also give a novel characterization of the asymptotic behavior when the dimension of the parameter space is allowed to grow with $T$. They additionally strengthen connections to the information theory literature, demonstrating that the actual regret for logistic regression depends on the richness of the parameter class, where even within this problem, richer classes lead to greater regret.

Constellation shaping is necessary to approach channel capacity for information rates above 1 bit/dim. Probabilistic shaping shows a small gap to capacity, however a complex distribution matcher is required to modify the source distribution. Spherical shaping of lattice constellations also reduces the gap to capacity, but practical Voronoi shaping is feasible in small dimensions only. In this paper, our codebook is a real geometrically non-uniform Gaussian-like constellation. We prove that this discrete codebook achieves channel capacity when the number of points goes to infinity. Then we build a special mapping to interface between non-binary low-density codes and the codebook, allowing the code alphabet size to be equal to the square root of the codebook size. Excellent performance is shown with fast-encoding and practical iterative probabilistic decoding, e.g. 0.7 dB gap to capacity at 6 bits/s/Hz with a code defined over the ring Z/8Z.

We study universal compression of sequences generated by monotonic distributions. We show that for a monotonic distribution over an alphabet of size k, each probability parameter costs essentially 0.5log(n/k3) bits, where n is the coded sequence length, as long as k=o(n1/3). Otherwise, for k=O(n), the total average sequence redundancy is O(n1/3+ε) bits overall. We then show that there exists a sub-class of monotonic distributions over infinite alphabets for which redundancy of O(n1/3+ε) bits overall is still achievable. This class contains fast decaying distributions, including many distributions over the integers such as the family of Zipf distributions and geometric distributions. For some slower decays, including other distributions over the integers, redundancy of o(n) bits overall is achievable. A method to compute specific redundancy rates for such distributions is derived. The results are specifically true for finite entropy monotonic distributions. Finally, we study individual sequence redundancy behavior assuming a sequence is governed by a monotonic distribution. We show that for sequences whose empirical distributions are monotonic, individual redundancy bounds even tighter than those in the average case can be obtained. The relation of universal compression with monotonic distributions to universal compression of patterns of sequences is demonstrated.

Utilization of redundancy left in a channel coded sequence can improve channel decoding performance. Stronger improvement can usually be achieved with nonsystematic encoding. However, nonsystematic codes recently proposed for this problem are not robust to the statistical parameters governing a sequence and thus should not be used without prior knowledge of these parameters. In this work, decoders of nonsystematic quick-look-in turbo codes are adapted to extract and exploit redundancy left in coded data to improve channel decoding performance. Methods, based on universal compression and denoising, for extracting the governing statistical parameters for various source models are integrated into the channel decoder by also taking advantage of the code structure. Simulation results demonstrate significant performance gains over standard systematic codes that can be achieved with the new methods for a wide range of statistical models and governing parameters. In many cases, performance almost as good as that with perfect knowledge of the governing parameters is achievable.

In this paper, two fixed per-information symbol complexity lossless source coding algorithms are modified for estimation and incremental LT decoding over piecewise stationary memoryless channels (PSMC's) with a bounded number of abrupt changes in channel statistics. In particular, as a class of PSMC's, binary symmetric channels are considered with a crossover probability that changes a bounded number of times with no repetitions in the statistics. Simulation results are given which illustrate the benefits of using our algorithms, both in terms of probability of error and in terms of redundancy.

Two low-complexity methods are proposed for sequential probability assignment for binary independent and identically distributed (i.i.d.) individual sequences with empirical distributions whose governing parameters are known to be bounded within a limited interval. The methods can be applied to different problems where fast accurate estimation of the maximizing sequence probability is very essential to minimizing some loss. Such applications include applications in finance, learning, channel estimation and decoding, prediction, and universal compression. The application of the new methods to universal compression is studied, and their universal coding redundancies are analyzed. One of the methods is shown to achieve the minimax redundancy within the inner region of the limited parameter interval. The other method achieves better performance on the region boundaries and is more robust numerically to outliers. Simulation results support the analysis of both methods. While non-asymptotically the gains may be significant over standard methods that maximize the probability over the complete parameter simplex, asymptotic gains are in second order. However, these gains translate to meaningful significant factor gains in other applications, such as financial ones. Moreover, the methods proposed generate estimators that are constrained within a given interval throughout the complete estimation process which are essential to applications such as sequential binary channel crossover estimation. The results for the binary case lay the foundation to studying larger alphabets.

Tight bounds on the block entropy of patterns of sequences generated by independent and identically distributed (i.i.d.) sources are derived. A pattern of a sequence is a sequence of integer indices with each index representing the order of first occurrence of the respective symbol in the original sequence. Since a pattern is the result of data processing on the original sequence, its entropy cannot be larger. Bounds derived here describe the pattern entropy as function of the original i.i.d. source entropy, the alphabet size, the symbol probabilities, and their arrangement in the probability space. Matching upper and lower bounds derived provide a useful tool for very accurate approximations of pattern block entropies for various distributions, and for assessing the decrease of the pattern entropy from that of the original i.i.d. sequence.

Nonuniform sources can be found in real world applications as uncompressed speech, text and medical images. In this paper we compare the performance of three different methods for the transmission of such sources over AWGN and Rayleigh channels. One of the methods is the classical one considering separation between source and channel coding. The two other methods are based on source-controlled channel decoding, where data is not compressed prior to transmission and redundancy is exploited at receiver. The three methods make use of turbo codes as the channel code. Simulation results show that, in some cases and in terms of bit error rate, it may be more advantageous not to compress data prior to transmission.

We study universal compression for sequences generated by monotonic distributions. We show that for a monotonic distribution over an alphabet of size k, each probability parameter costs essentially 0.5 log (n/k3) bits, where n is the coded sequence length, as long as k = o(n1/3). Otherwise, for k = O(n), the total average sequence redundancy is O(n1/3+epsiv) bits overall. We then show that there exists a sub-class of monotonic distributions over infinite alphabets for which redundancy of O(n1/3+epsiv) bits overall is still achievable. This class contains fast decaying distributions, including distributions over the integers and geometric distributions. For some slower decays, redundancy of o(n) bits overall is achievable.

We consider channel decoding of redundant data with context based memory with the recently proposed class of nonsystematic split-LDPC codes. Methods based on denoising techniques and context estimation from universal source coding are used to extract redundancy between decoding iterations of split-LDPC codes. Simulation results show that the use of nonsystematic split-LDPC codes gains in most cases on standard systematic LDPC codes even without prior knowledge of the source statistics. Different context extraction methods are considered, including a novel approach that is used to capture different types of context based redundancy.

We study the block entropy of patterns of sequences generated by uniform and monotonic memoryless source distributions. In the former case, the pattern entropy decreases the most from the memoryless entropy, and in the latter the least. General upper and lower bounds are presented and then applied to these distributions. Tighter bounds are derived for a uniform case. All bounds provide almost precise characterization of the pattern entropies of uniform distributions, distributions over the integers, and the geometric distribution. Of specific interest are distributions over the integers that have infinite entropy rates in the memoryless case but bounded pattern block entropies

Nonsystematic channel codes are superior to systematic codes in the presence of source redundancy. We study the performance of split-LDPC codes (we recently proposed), which are based on splitting redundant data bits into coded bits. We propose a novel method to build extrinsic information transfer (EXIT) chart to approximate the thresholds of such codes. EXIT charts provide a fast and close to accurate prediction of the thresholds of split-LDPC codes for nonuniform sources. The thresholds approximated by fast EXIT chart analysis are very close to those obtained by density evolution (DE) analysis that we recently proposed for split-LDPC codes. The EXIT chart analysis can thus be used to efficiently search for good split-LDPC codes. Simulations verify good performance close to the approximate thresholds predicted by the EXIT charts

An iterative estimation and decoding technique for memoryless additive white Gaussian noise (AWGN) channels with several abrupt changes in noise variance during transmission of a codeword is introduced. A technique developed for source coding of piecewise-stationary memoryless sources is adapted to estimate the unknown channel transition points. Then, maximum-likelihood (ML) estimation is used to estimate the unknown noise variance in each segment This process is carried out on an estimated noise sequence of the currently hypothesized codeword. Simulations using turbo codes show performance almost as good as that of a receiver with perfect knowledge of the channel

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

Universal compression of patterns of sequences generated by independent and identically distributed (i.i.d.) sources with unknown, possibly large, alphabets is investigated. A pattern is a sequence of indices that contains all consecutive indices in increasing order of first occurrence. If the alphabet of a source that generated a sequence is unknown, the inevitable cost of coding the unknown alphabet symbols can be exploited to create the pattern of the sequence. This pattern can in turn be compressed by itself. It is shown that if the alphabet size k is essentially small, then the average minimax and maximin redundancies as well as the redundancy of every code for almost every source, when compressing a pattern, consist of at least 0.5log(n/k3) bits per each unknown probability parameter, and if all alphabet letters are likely to occur, there exist codes whose redundancy is at most 0.5log(n/k2) bits per each unknown probability parameter, where n is the length of the data sequences. Otherwise, if the alphabet is large, these redundancies are essentially at least Theta(n-2/3) bits per symbol, and there exist codes that achieve redundancy of O(n-1/2) bits per symbol. Two suboptimal low-complexity sequential algorithms for compression of patterns are presented and their description lengths analyzed, also pointing out that the pattern average universal description length can decrease below the underlying i.i.d. entropy for large enough alphabets

Summary form only given. In many channel decoding applications, redundancy is left in the channel coded data. A new method for utilizing this redundancy in channel decoding is proposed. The method is based on the Burrows-Wheeler transform (BWT) and on universal compression techniques for piecewise stationary memoryless sources (PSMS), and is applied to regular low-density parity-check (LDPC) codes. Two settings are proposed. In the first, the BWT-PSMS loop is in the decoder, while in the second, the rearrangement of the data is performed with the BWT before channel encoding, and then the decoder is designed for extracting statistics in a PSMS. After the last iteration, the data is reassembled with the inverse BWT. Simulations show that the bit error rate performance of the new method (in either setting) is almost as good as genie-aided decoding with perfect knowledge of the statistics.

Summary form only given. In this paper, we consider channel decoding of sequences generated by i.i.d. sources and piecewise stationary memoryless sources (PSMSs). We design a turbo decoder that utilizes compression techniques for PSMSs, and use codes that have the quick-look-in (QLI) property, where two parity sequences generated by one of the constituent recursive convolutional codes sum modulo-2 to the systematic message sequence. During the first decoding iterations, source statistics are obtained between iterations by segmentation of the PSMS data, estimation of the i.i.d. statistics in each segment, and then enhancement of these estimates by reversing the channel transition probabilities. Then, during later iterations, the extrinsic information can be used for the same algorithm without need to reverse the channel. To improve code performance, an interleaver, that diversifies the channel code from the PSMS structure, is included in the encoder between the source output and the channel code.

Messages coded and transmitted over a channel may contain some redundancy, which is usually not utilized by standard channel decoding techniques. Non-systematic codes have a potential for significant advantage over systematic codes if a method is found to utilize such redundancy. We propose a novel general encoder/decoder structure for non-systematic low-density parity-check (LDPC) codes, that can be used in several different configurations for efficiently exploiting redundancy in decoding of redundant data sequences. Simulation results for one configuration of this method demonstrate clear performance gains over standard systematic LDPC codes when a decoder utilizes the source redundancy for decoding of redundant data sequences. These gains increase as the non-uniformity of the source increases, and also with use of some of the other configurations of the new general method

Non-systematic channel codes can have a significant advantage over systematic codes when utilizing redundancy left in the data for channel decoding. However, results previously attained show that even with such codes there is a performance gap to the theoretical limits. We propose a method that combines unequal energy allocation with source controlled decoding of non-systematic turbo codes. The method benefits from both (non-systematic codes and unequal energy allocation) to improve channel decoding performance in the presence of redundancy. Simulations demonstrate superior performance to the performances attained by each of the methods separately. A significant advantage is demonstrated over using non-systematic codes with equal energy allocation. At moderate (more practical) non-uniformities, there is also a clear advantage to the new method over unequal energy allocation with systematic turbo codes

We consider strategies for universal utilization of context based redundancy left in channel coded data to improve channel decoding of non-systematic turbo codes. The statistical parameters of the sequence are extracted using such strategies and passed to an iterative decoder. Simulation results demonstrate significant coding gains obtained by utilization of this redundancy, which usually increase with well designed nonsystematic codes. Different context based strategies are compared

The redundancy rate of the Lempel-Ziv algorithm has been widely investigated. Much of the data compression community believed that the redundancy rate of the LZ78 algorithm should be O((log n)-1), where n is the data length. However, until the present paper, this conjecture had not been proved for sources beyond Markov sources. In this paper, we investigate the upper bound on the pointwise redundancy rate of the Lempel-Ziv algorithm for mixing sources and finite-state sources. The technique we applied in this paper is simple. By studying the dictionary tree resulting from the LZ78 algorithm, we derive certain relationships between the self-information of a sequence emitted by a source and the number of phrases resulting from the LZ78 parsing of the sequence. From these relationships, upper bounds on the pointwise redundancy rate of the LZ78 algorithm on mixing sources and finite-state sources can be obtained. These results show that for mixing sources and finite-state sources, the pointwise redundancy rate is upper bounded by O((log n)-1) for the LZ78 algorithm. We also compare our results with previous results of Savari and Kieffer-Yang

Bounds on the entropy of patterns of sequences generated by independently identically distributed (i.i.d.) sources are derived. A pattern is a sequence of indices that contains all consecutive integer indices in increasing order of first occurrence. If the alphabet of a source that generated a sequence is unknown, the inevitable cost of coding the unknown alphabet symbols can be exploited to create the pattern of the sequence. This pattern can in turn be compressed by itself. The bounds derived here are functions of the i.i.d. source entropy, alphabet size, and letter probabilities. It is shown that for large alphabets, the pattern entropy must decrease from the i.i.d. one. The decrease is in many cases more significant than the universal coding redundancy bounds derived in prior works. The pattern entropy is confined between two bounds that depend on the arrangement of the letter probabilities in the probability space. For very large alphabets whose size may be greater than the coded pattern length, all low probability letters are packed into one symbol. The pattern entropy is upper and lower bounded in terms of the i.i.d. entropy of the new packed alphabet. Correction terms, which are usually negligible, are provided for both upper and lower bounds.

Non-systematic turbo codes have a large potential advantage over systematic codes when coding redundant sequences. However, to utilize this potential universally, when sequence statistics are unknown in advance, they need to be properly designed. We consider design criteria for non-systematic turbo codes that can allow universal utilization of redundancy in the encoded messages. We apply these criteria to decoding of independently identically distributed (i.i.d.) nonuniform sequences, and of piecewise stationary memoryless sequences. Simulation results are presented for both classes for rate 1/2 and 1/3 codes. They demonstrate that with proper designs, full (or almost full) utilization of the redundancy can be achieved for these source classes even universally, and the performance with unknown statistics is (almost) as good as that with initially known statistics.

This paper proposes iterative estimation and decoding techniques for memoryless channels with a bounded number of abrupt changes in channel statistics. Specifically, the channel under consideration is a binary symmetric channel with a crossover probability that changes a bounded number of times during the transmission of a codeword; the channel state information to be estimated consists of the crossover probabilities of the different segments and the location(s) of the transition point(s). To estimate the transition points, a technique developed for source coding of piecewise-stationary memoryless sources is adapted; then the expectation-maximization algorithm is used to estimate the crossover probabilities. This segmentation/estimation is carried out on the error sequence of the currently hypothesized frame. Simulation results using turbo codes indicate that the proposed receiver performs almost as well as a receiver that has perfect knowledge of the channel.

A pattern is a sequence of indices that contains all consecutive integer indices up to some integer k in increasing order of first occurrence. If the alphabet of a source that generated a sequence is unknown, the inevitable cost of coding the unknown alphabet symbols can be exploited to create the pattern of the sequence, which, in turn, can be compressed by itself. In this paper, two low-complexity sequential schemes are proposed for universally compressing patterns that are obtained from sequences generated by independently identically distributed (i.i.d.) sources with unknown (possibly large) alphabets of unknown size. The description lengths both schemes assign to a pattern are investigated and bounded by rigorous closed form expressions in terms of the maximum likelihood (ML) probability of the underlying i.i.d. sequence. In particular, each distinct index in the pattern is shown to cost 0.5 log(n/k/sup 3/)+1.59 log e bits above the i.i.d. ML cost. This results in description length for unknown parameters that is shorter than the minimum code length of an i.i.d. sequence if there are more than e/sup 19/18//spl middot/n/sup 1/3/ indices in the pattern. The sequential performance results are then used to establish a connection between the pattern entropy and the underlying i.i.d. entropy. This final result points out that for large alphabets (including those larger than n), recently derived universal coding redundancy bounds for coding patterns are negligible compared to the reduction in entropy from the underlying i.i.d. one.

Bounds on the average redundancy are derived for universal coding of patterns of sequences generated by independently identically distributed (i.i.d.) sources with unknown, possibly large, alphabets. Sequential approached for compression of patterns are proposed, and the relation between pattern entropy and that of i.i.d. sequences is studied.

This paper proposes the use of universal lossless compression techniques based on probability assignment to utilize source redundancy and improve performance of channel decoding techniques when channel coded sequences contain redundancy.

A lower bound is derived on the achievable redundancy for universal lossless coding of parametric sources with piecewise stationary, abruptly changing, occasionally repeating statistics. In particular, it is shown that if the number of repeating statistical parameter vectors (or states) is not too large, for any uniquely decipherable code, for almost every set of states that govern all the different segments in the data sequence, for almost every arrangement of these states in the different segments, and for almost every vector of transition times, the minimum achievable redundancy is composed of 0.5 log d extra code bits for each unknown component of each state, log m extra code bits for each unknown transition time, and log s extra code bits for each repetition of a state, where d is the average duration of each state in the input string, TO is the average length of a segment, and s is the total number of states. If s is essentially large compared to TO, it is shown that the minimum redundancy is composed of 0.5 log 77i bits for each unknown component in each segment and log TO bits for each unknown transition time, which is the same lower bound as that of general piecewise stationary sources (PSSs). These results are true also in the minimax and maximin senses. The lower bound is shown to be achievable through construction of mixture and estimation based codes. Different special cases are reviewed, and it is shown that unless s is essentially large compared to m, optimal codes that are designed particularly for sources with repeating statistics outperform codes designed for PSSs when coding sources with repeating statistics. In particular, the bound for general PSSs is shown to be a special case of the new bound.

An asymptotically optimal low-complexity strongly sequential compression scheme is proposed for universal lossless coding of memoryless sources with piecewise stationary abruptly changing statistics. The scheme is shown to achieve the lower bound for this universal coding problem even in a strongly sequential regime, where the horizon (i.e., the length of the data sequence to be encoded) is unknown when the algorithm starts to compress the data. Simulation results support the analytical results.

Universal lossless compression of parametric piecewise stationary sources with slow changes in the statistics between stationary segments that take place in unknown time intervals is investigated. The minimum description length (MDL) principle is derived for two different settings of this problem under the assumption that the parameter changes are linear over the change interval. In the first setting, it is assumed that all changes are of equal known in advance duration d, and in the second setting all statistics changes are of unknown durations. While in both cases the redundancy for most sources for each unknown statistical parameter in each segment remains lower bounded, as in the case of abruptly changing statistics, by 0.5 log m extra code bits, where m is the mean segment length, the minimum extra code-length required for each unknown transition interval decreases to log m-0.5 log d in the first setting, but surprisingly remains log m, as in the case of abruptly changing statistics, in the second. Schemes that achieve the lower bounds in both settings are demonstrated.

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.

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 (/spl radic/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.