This paper addresses the computational and theoretical challenges of implementing twice-universal prediction in over-parameterized, possibly high-dimensional, linear models with additive white Gaussian noise (AWGN). Building on the theoretical foundations of the Predictive Normalized Maximum Likelihood (pNML) and twice-universal predictors, we propose an efficient local search approximation algorithm to handle the exponential complexity of combining all subsets of a high-dimensional parameter space. We validate our approach through a series of experiments: comparing the twice-universal predictor with pNML and regularized least squares, evaluating the proposed approximation algorithm in terms of accuracy and scalability, and showcasing its application in high-dimensional settings. Despite its advantages, the computational cost remains significant, highlighting the need for further refinements such as restricting reference learners to under-parameterized subfamilies. This work advances the practical applicability of twice-universal prediction and lays the groundwork for future research in scalable universal prediction frameworks11This work has been supported by a grant from the Israeli Science Foundation, number 819/20.

Learning algorithms that divide the data into batches are prevalent in many machine-learning applications, typically offering useful trade-offs between computational efficiency and performance. In this paper, we examine the benefits of batch-partitioning through the lens of a minimum-norm overparametrized linear regression model with isotropic Gaussian features. We suggest a natural small-batch version of the minimum-norm estimator and derive bounds on its quadratic risk. We then characterize the optimal batch size and show it is inversely proportional to the noise level, as well as to the overparametrization ratio. In contrast to minimum-norm, our estimator admits a stable risk behavior that is monotonically increasing in the overparametrization ratio, eliminating both the blowup at the interpolation point and the double-descent phenomenon. We further show that shrinking the batch minimum-norm estimator by a factor equal to the Weiner coefficient further stabilizes it and results in lower quadratic risk in all settings. Interestingly, we observe that the implicit regularization offered by the batch partition is partially explained by feature overlap between the batches. Our bound is derived via a novel combination of techniques, in particular normal approximation in the Wasserstein metric of noisy projections over random subspaces.

This paper presents a one shot analysis to the lossless joint source channel coding problem. Achievable and converse bounds are derived. Both bound are given in term of$F(z)$, the CDF of the random variable$Z=-\log p_{e}(V, X, Y)$where$p_{e}(V, X, Y)$is the the pairwise error probability between two codewords associated with two source symbols. This is an information functional that resembles a similar quantity in the meta-converse form of one shot channel coding, but it depends also on the source$V$in addition to the input$X$and the output$Y$of the channel. The role of$F(z)$is analogous to the role of the information spectrum, but our treatment does not include any asymptotic analysis. Relation to other known bounds is also demonstrated.

Statistical learning theory and the Probably Ap-proximately Correct (PAC) criterion are the common approach to mathematical learning theory. PAC is widely used to ana-lyze learning problems and algorithms, and have been studied thoroughly. Uniform worst case bounds on the convergence rate have been well established using, e.g., VC theory or Radamacher complexity. However, in a typical scenario the performance could be much better. In this paper, we consider PAC learning using a somewhat different tradeoff, the error exponent - a well established analysis method in Information Theory - which describes the exponential behavior of the probability that the risk will exceed a certain threshold as function of the sample size. We focus on binary classification and find, under some stability assumptions, an improved distribution dependent error exponent for a wide range of problems, establishing the exponential behavior of the PAC error probability in agnostic learning. Inter-estingly, under these assumptions, agnostic learning may have the same error exponent as realizable learning. The error exponent criterion can be applied to analyze knowledge distillation, a problem that so far lacks a theoretical analysis.

In this paper we consider the problem of universal batch learning in a misspecification setting with log-loss. In this setting the hypothesis class is a set of models$\Theta$. However, the data is generated by an unknown distribution that may not belong to this set but comes from a larger set of models$\Phi\supset\Theta$. Given a training sample, a universal learner is requested to predict a probability distribution for the next outcome and a log-loss is incurred. The universal learner performance is measured by the regret relative to the best hypothesis matching the data, chosen from$\Theta$. Utilizing the minimax theorem and information theoretical tools, we derive the optimal universal learner, a mixture over the set of the data generating distributions, and get a closed form expression for the min-max regret. We show that this regret can be considered as a constrained version of the conditional capacity between the data and its generating distributions set. We present tight bounds for this min-max regret, implying that the complexity of the problem is dominated by the richness of the hypothesis models$\Theta$and not by the data generating distributions set$\Phi$. We demonstrate our results for the case where the observations come from a$K$-parameters multinomial distributions while the hypothesis class$\Theta$is only a subset of this family of distributions.

Machine learning systems require massive amounts of labeled training data in order to achieve high accuracy rates. Active learning uses feedback to label the most informative data points and significantly reduce the training set size. Many heuristics for selecting data points have been developed in recent years which are usually tailored to a specific task and a general unified framework is lacking. In this work, the individual setting is considered and an active learning criterion is proposed. Motivated by universal source coding, the proposed criterion attempts to find data points which minimize the Predictive Normalized Maximum Likelihood (pNML) regret on an un-labelled test set. It is shown that for binary classification and linear regression, the resulting criterion coincides with well known active learning criteria and thus represents a unified information theoretic active learning approach for general hypothesis classes. Finally, it is shown using real data that the proposed criterion performs better than other active learning criteria in terms of sample complexity.

This paper considers the individual batch learning problem. Batch learning (in contrast to online) refers to the case where there is a "batch" of training data and the goal is to predict a test outcome. Individual learning refers to the case where the data (training and test) is arbitrary, individual. This batch individual setting poses a fundamental issue of defining a plausible criterion for a universal learner since in each experiment there is a single test sample. We propose a permutation invariant criterion that, intuitively, lets the individual training sequence manifest its empirical structure for predicting the test sample. This criterion is essentially a min-max regret, where the regret is based on a leave-one-out approach, minimized over the universal learner and maximized over the outcome sequences (thus agnostic). To show its plausibility, we analyze the criterion and its resulting learner for two cases: Binary Bernoulli and 1-D deterministic barrier. For both cases the regret behaves as O(c/N), N the size of the training and c = 1 for the Bernoulli case and log4 for the 1-D barrier. Interestingly, in the Bernoulli case, the regret in the stochastic setting behaves as O(1/2N) while here, in the individual setting, it has a larger constant.

In recent papers we have proposed an individual setting for the batch learning problem and showed that it is solved by a known variant of the Normalized Maximum Likelihood (NML) which we termed pNML. In this paper we present a different possible definition for the batch learning problem in the individual setting and show that it is solved by another known variant of the normalized maximum likelihood, which we denote by pNML2. We further derive an exact expression of the pNML2 for the linear regression problem. We use this result, along with known results and new upper and lower bounds over the regret of the pNML2 learner, to compare between the two learners.

Universal coding, prediction and learning usually consider the case where the data generating mechanism is unknown or non-existent, and the goal of the universal scheme is to compete with the best hypothesis from a given hypothesis class, either on the average or in a worst-case scenario. Multiple universality considers the case where the hypothesis class is also unknown: there are several hypothesis classes with possibly different complexities. In hierarchical universality, the simpler classes are nested within more complex classes. The main challenge is to correctly define the universality problem. We propose several possible definitions and derive their min-max optimal solutions. Interestingly, the proposed solutions can be used to obtain Elias codes for universal representation of the integers. We also utilize this approach for variable-memory Markov models, presenting a new interpretation for the known bound over the regret of the celebrated context-tree weighting algorithm and proposing a 3-part code that (slightly) out-performs it.

We consider the problem of learning a model from given data samples in which the predictor’s quality is measured by the log loss. We focus on the misspecified setting, in which the true model generating the data is chosen from a set different from the possible models that can be chosen by the learner. We establish minimax expected regret upper and lower bounds in terms of properly defined projected covering and packing entropies, and show their relation to M-projection geometric properties. We exemplify the bounds in a few settings.

We consider the question of sequential prediction under the log-loss in terms of cumulative regret. Namely, given a hypothesis class of distributions, learner sequentially predicts the (distribution of the) next letter in sequence and its performance is compared to the baseline of the best constant predictor from the hypothesis class. The well-specified case corresponds to an additional assumption that the data-generating distribution belongs to the hypothesis class as well. Here we present results in the more general misspecified case. Due to special properties of the log-loss, the same problem arises in the context of competitive-optimality in density estimation, and model selection. For the $d$-dimensional Gaussian location hypothesis class, we show that cumulative regrets in the well-specified and misspecified cases asymptotically coincide. In other words, we provide an $o(1)$ characterization of the distribution-free (or PAC) regret in this case – the first such result as far as we know. We recall that the worst-case (or individual-sequence) regret in this case is larger by an additive constant ${d\over 2} + o(1)$. Surprisingly, neither the traditional Bayesian estimators, nor the Shtarkov’s normalized maximum likelihood achieve the PAC regret and our estimator requires special “robustification” against heavy-tailed data. In addition, we show two general results for misspecified regret: the existence and uniqueness of the optimal estimator, and the bound sandwiching the misspecified regret between well-specified regrets with (asymptotically) close hypotheses classes.

Detecting out-of-distribution (OOD) samples is vital for developing machine learning based models for critical safety systems. Common approaches for OOD detection assume access to some OOD samples during training which may not be available in a real-life scenario. Instead, we utilize the {\em predictive normalized maximum likelihood} (pNML) learner, in which no assumptions are made on the tested input. We derive an explicit expression of the pNML and its generalization error, denoted as the regret, for a single layer neural network (NN). We show that this learner generalizes well when (i) the test vector resides in a subspace spanned by the eigenvectors associated with the large eigenvalues of the empirical correlation matrix of the training data, or (ii) the test sample is far from the decision boundary. Furthermore, we describe how to efficiently apply the derived pNML regret to any pretrained deep NN, by employing the explicit pNML for the last layer, followed by the softmax function. Applying the derived regret to deep NN requires neither additional tunable parameters nor extra data. We extensively evaluate our approach on 74 OOD detection benchmarks using DenseNet-100, ResNet-34, and WideResNet-40 models trained with CIFAR-100, CIFAR-10, SVHN, and ImageNet-30 showing a significant improvement of up to 15.6% over recent leading methods.

This paper presents a one shot analysis of the lossy compression problem under average distortion constraints. We calculate the exact expected distortion of a random code. The result is given as an integral formula using a newly defined functional D̃(z, QY) where QYis the random coding distribution and z ∈ [0, 1]. When we plug in the code distribution as QY, this functional produces the average distortion of the code, thus provide a converse result utilizing the same functional. Two alternative formulas are provided for D̃(z, QY), the first involves a supremum over some auxiliary distribution QXwhich has resemblance to the channel coding meta-converse and the other involves an infimum over channels which resemble the well known Shannon distortion-rate function.

The notion of implicit bias, or implicit regularization, has been suggested as a means to explain the surprising generalization ability of modern-days overparameterized learning algorithms. This notion refers to the tendency of the optimization algorithm towards a certain structured solution that often generalizes well. Recently, several papers have studied implicit regularization and were able to identify this phenomenon in various scenarios. We revisit this paradigm in arguably the simplest non-trivial setup, and study the implicit bias of Stochastic Gradient Descent (SGD) in the context of Stochastic Convex Optimization. As a first step, we provide a simple construction that rules out the existence of a \emph{distribution-independent} implicit regularizer that governs the generalization ability of SGD. We then demonstrate a learning problem that rules out a very general class of \emph{distribution-dependent} implicit regularizers from explaining generalization, which includes strongly convex regularizers as well as non-degenerate norm-based regularizations. Certain aspects of our constructions point out to significant difficulties in providing a comprehensive explanation of an algorithm's generalization performance by solely arguing about its implicit regularization properties.

Typically, real-world stochastic processes are not easy to analyze. In this paper, we study the representation of different stochastic process as a memoryless innovation process triggering a dynamic system. We show that such a representation is always feasible for innovation processes taking values over a continuous set. However, the problem becomes more challenging when the alphabet size of the innovation is finite. In this case, we introduce both lossless and lossy frameworks, and provide closed-form solutions and practical algorithmic methods. In addition, we discuss the properties and uniqueness of our suggested approach. Finally, we show that the innovation representation problem has many applications. We focus our attention on entropic causal inference, which has recently demonstrated promising performance, compared to alternative methods.

The k-vectors algorithm for learning regression functions proposed here is akin to the well-known k-means algorithm. Both algorithms partition the feature space, but unlike the k-means algorithm, the k-vectors algorithm aims to reconstruct the response rather than the feature. The partitioning rule of the algorithm is based on maximizing the correlation (inner product) of the feature vector with a set of k vectors, and generates polyhedral cells, similar to the ones generated by the nearest-neighbor rule of the k-means algorithm. Similarly to k-means, the learning algorithm alternates between two types of steps. In the first type of steps, k labels are determined via a centroid-type rule (in the response space), which uses a surrogate hinge-type loss function to the mean squared error loss function. In the second type of steps, the k vectors which determine the partition are updated according to a multiclass classification rule, in the spirit of support vector machines. It is proved that both steps of the algorithm only require solving convex optimization problems, and that the algorithm is empirically consistent - as the length of the training sequence increases to infinity, fixedpoints of the empirical version of the algorithm tend to fixed points of the population version of the algorithm. Learnability of the predictor class posit by the algorithm is also established.

Linear regression is a classical paradigm in statistics. A new look at it is provided via the lens of universal learning. In applying universal learning to linear regression the hypotheses class represents the label y ∈ ℛ as a linear combination of the feature vector xTθ where x ∈ ℛM, within a Gaussian error. The Predictive Normalized Maximum Likelihood (pNML) solution for universal learning of individual data can be expressed analytically in this case, as well as its associated learnability measure. Interestingly, the situation where the number of parameters M may even be larger than the number of training samples N can be examined. As expected, in this case learnability cannot be attained in every situation; nevertheless, if the test vector resides mostly in a subspace spanned by the eigenvectors associated with the large eigenvalues of the empirical correlation matrix of the training data, linear regression can generalize despite the fact that it uses an "over-parametrized" model. We demonstrate the results with a simulation of fitting a polynomial to data with a possibly large polynomial degree.

Universal supervised learning of individual data is considered from an information theoretic point of view in the standard supervised “batch” learning where prediction is done on a test sample once the entire training data is observed. In this individual setting the features and labels, both in the training and the test, are specific individual, deterministic quantities. Prediction loss is naturally measured by the log-loss. The presented results provide a minimax universal learning scheme, termed the Predictive Normalized Maximum Likelihood (pNML) that competes with a “genie” (or reference) that knows the true test label. In addition, a pointwise learnability measure associated with the pNML, for the specific training and test, is provided. This measure may also indicate the performance of the commonly used Empirical Risk Minimizer (ERM) learner.

In this paper we consider the problem of batch learning with log-loss, in a stochastic setting where given the data features, the outcome is generated by an unknown distribution from a class of models. Utilizing the minimax theorem and information-theoretical tools, we came up with the minimax universal learning solution, a redundancy capacity theorem and an upper bound on the performance of the optimal solution. The resulting universal learning solution is a mixture over the models in the considered class. Furthermore, we get a better bound on the generalization error that decays as O(logN/N), where N is the sample size, instead of O(√logN/N) which is commonly attained in statistical learning theory for the empirical risk minimizer.

In this paper we consider the problem of on-line learning in the stochastic setting under a certain form of hypotheses class. We prove an equivalence between the minimax redundancy and capacity of the channel between the class parameters and the labels conditioned on the data features (side information). Our proof extends Gallager's Redundancy Capacity theorem for universal prediction to on-line learning with the considered form of hypotheses class. Moreover, this result confirms the optimality of previous ad-hoc universal learners, or universal predictors with side information, but more importantly, extends these previous results to more general hypotheses classes.

A minimax-converse has been suggested for the general channel coding problem [1]. This converse comes in two flavors. The first flavor is generally used for the analysis of the coding problem with non-vanishing error probability and provides an upper bound on the rate given the error probability. The second flavor fixes the rate and provides a lower bound on the error probability. Both converses are given as a min-max optimization problem of an appropriate binary hypothesis testing problem. The properties of the first converse were studies in [2] and a saddle point was proved. The minimax solution can also be used in conjunction with random coding to achieve “optimal” [3] coding performance. In this paper we study the properties of the second form, i.e. when the rate is fixed. Necessary and sufficient conditions on the saddle point solution are proved. Moreover, an algorithm for the computation of the saddle point, and hence the bound, is developed. In the DMC case, the algorithm runs in a polynomial time.

In this paper we consider the problem of on-line learning with respect to the logarithmic loss, where the learner provides a probability assignment for the next label given the past and current data samples and the past labels. We consider the problem in the individual and the stochastic settings. Our first result is a class of new universal on-line probability assignment schemes based on the mixture approach. Now, in classical learning, it is well known that there are model classes that can be learned in batch, but cannot be learned sequentially for all data samples sequences. We show that for these model classes the proposed mixture schemes lead to a vanishing regret in the individual setting when the adversary is somewhat constrained. In the stochastic setting we show that any on-line solution for the log-loss may be used to obtain a solution for a wide variety of loss functions.

Low Density Lattice Code (LDLC) uses a lattice with a sparse inverse matrix, which allows a linear complexity decoding. Spatially Coupled Low Density Lattice Code (SC-LDLC) is built by coupling several LDLCs which leads to a smaller Symbol Error Rate (SER) than the LDLC scheme for every tested block length n. In this paper, new constructions of the spatially coupled low density lattice codes are introduced, with benefits over the existing methods.

Large alphabet source coding is a basic and well-studied problem in data compression. It has many applications, such as compression of natural language text, speech, and images. The classic perception of most commonly used methods is that a source is best described over an alphabet, which is at least as large as the observed alphabet. In this paper, we challenge this approach and introduce a conceptual framework in which a large alphabet source is decomposed into “as statistically independent as possible” components. This decomposition allows us to apply entropy encoding to each component separately, while benefiting from their reduced alphabet size. We show that in many cases, such decomposition results in a sum of marginal entropies which is only slightly greater than the entropy of the source. Our suggested algorithm, based on a generalization of the binary independent component analysis, is applicable for a variety of large alphabet source coding setups. This includes the classical lossless compression, universal compression, and high-dimensional vector quantization. In each of these setups, our suggested approach outperforms most commonly used methods. Moreover, our proposed framework is significantly easier to implement in most of these cases.

Encoding a sequence of independent symbols over a large alphabet size is a challenging problem with applications in many fields. The most widely used adaptive entropy coding techniques (namely, arithmetic and Huffman coding) are known to achieve an average codeword length which may be significantly greater than the empirical entropy of the sequence, as the alphabet size increases. In this work we introduce an efficient and easy-to-implement method for large alphabet adaptive encoding. We propose a conceptual framework in which a sequence of symbols, over a large alphabet size, is decomposed into multiple "almost independent" sequences over a smaller alphabet. Then each of these sequences is encoded separately. This way, we allow encoding of small alphabet sequences, at the cost of the "remaining dependence" among the sequences. We demonstrate the advantages of our suggested scheme through a series of theorems and experiments, showing it reduces both the average codeword length and the compression runtime in many large alphabet setups.

An upper bound on the error probability of specific lattices, based on their distance spectrum, is constructed. The derivation is accomplished using a simple alternative to the Minkowski-Hlawka mean-value theorem of the geometry of numbers. In many ways, the new bound greatly resembles the Shulman-Feder bound for linear codes. Based on the new bound, error-exponent and channel-dispersion expressions are derived for specific lattice sequences (of increasing dimension) over the AWGN channel. Measuring a sequence's gap to capacity, using the new asymptotics, is demonstrated. Additional finite dimension results, encountered along the way, are presented.

In 1973, Gallager proved that the random-coding bound is exponentially tight for the random code ensemble at all rates, even below expurgation. This result explained that the random-coding exponent does not achieve the expurgation exponent due to the properties of the random ensemble, irrespective of the utilized bounding technique. It has been conjectured that this same behavior holds true for a random ensemble of linear codes. This conjecture is proved in this paper. In addition, it is shown that this property extends to Poltyrev's random-coding exponent for a random ensemble of lattices.

Classical multiple access channel (MAC) coding schemes assume independent transmitted signals, because the given messages are assumed to be independent and the remote transmitters cannot cooperate. However, when the messages are correlated, or in the extreme case of fully cooperative transmitters, a better performance may be achieved. We explore the performance gain of this collaboration and its connection to transmission synchronization. For totally asynchronous transmitters, we prove that transmitters' collaboration has no performance gain. This result is shown for finite-alphabet memoryless MACs and for the additive white Gaussian noise MAC.

Independent component analysis (ICA) is a statistical method for transforming an observable multi-dimensional random vector into components that are as statistically independent as possible from each other. Usually, the ICA framework assumes a model according to which the observations are generated (such as a linear transformation with additive noise). ICA over finite fields is a special case of ICA in which both the observations and the independent components are over a finite alphabet. In this paper, we consider a generalization of this framework in which an observation vector is decomposed to its independent components (as much as possible) with no prior assumption on the way it was generated. This generalization is also known as Barlow's minimal redundancy representation problem and is considered an open problem. We propose several theorems and show that this hard problem can be accurately solved with a branch and bound search tree algorithm, or tightly approximated with a series of linear problems. Our contribution provides the first efficient set of solutions to Barlow's problem. The minimal redundancy representation (also known as factorial code) has many applications, mainly in the fields of neural networks and deep learning. The binary ICA is also shown to have applications in several domains, including medical diagnosis, multi-cluster assignment, network tomography, and internet resource management. In this paper, we show that this formulation further applies to multiple disciplines in source coding, such as predictive coding, distributed source coding, and coding of large alphabet sources.

Posterior matching (PM) is a sequential horizon-free feedback communication scheme introduced by the authors, who also provided a rather involved optimality proof, showing that it achieves capacity for a large class of memoryless channels. Naghshvar et al. considered a non-sequential variation of PM with a fixed number of messages and a random decision-time, and gave a simpler proof establishing its optimality via a novel extrinsic Jensen-Shannon divergence argument. Another simpler optimality proof was given by Li and El Gamal, who considered a fixed-rate fixed block-length variation of PM with an additional randomization. Both these works also provided error exponent bounds. However, their simpler achievability proofs apply only to discrete memoryless channels, and are restricted to a non-sequential setup with a fixed number of messages. In this paper, we provide a short and transparent proof for the optimality of the fully sequential randomized horizon-free PM scheme over general memoryless channels. Borrowing the key randomization idea of Li and El Gamal, our proof is based on analyzing the random walk behavior of the shrinking posterior intervals induced by a reversed iterated function system decoder.

Many applications of universal compression involve sources such as text, speech and image, whose alphabet is extremely large. In this work we propose a conceptual framework in which a large alphabet memory less source is decomposed into multiple 'as independent as possible' sources whose alphabet is much smaller. This way we slightly increase the average codeword length as the compressed symbols are no longer perfectly independent, but at the same time significantly reduce the overhead redundancy resulted by the large alphabet of the observed source. Our proposed algorithm, based on a generalization of the Binary Independent Component Analysis, shows to efficiently find the ideal trade-off so that the overall compression size is minimal. We demonstrate our framework on memory less draws from a variety of natural languages and show that the redundancy we achieve is remarkably smaller than most commonly used methods.

Achievable and converse bounds for general channels and mismatched decoding are derived. The direct (achievable) bound is derived using random coding and the analysis is tight up to factor 2. The converse is given in term of the achievable bound and the factor between them is given. This gives performance of the best rate-R code with possible mismatched decoding metric over a general channel, up to the factor that is identified. In the matched case we show that the converse equals the minimax meta-converse of Polyanskiy et al. [1].

In this paper, the optimal diversity-multiplexing tradeoff (DMT) is investigated for the multiple-input multiple-output fading multiple-access channel with no power constraints (infinite constellations). For K users (K > 1), M transmit antennas for each user, and N receive antennas, infinite constellations in general and lattices in particular are shown to attain the optimal DMT of finite constellations for N ≥ (K + 1)M - 1, i.e., user limited regime. On the other hand, for Nmax [1, (N - M + 1)/M], considering the shaping region in the decoding process plays a crucial role in pursuing the optimal DMT. By investigating the cases in which the infinite constellations are optimal and suboptimal, this paper also gives a geometrical interpretation to the DMT of infinite constellations in multiple-access channels.

Fiber's nonlinearity fundamentally bounds the achievable information rates in fiber-optic communication systems. In a wavelength-division multiplexed system it induces a nonlinear interference between adjacent channels, an interference that was recently shown to have a strong dependance on the input distribution. In this work we show that a ball shaped input constellation may significantly reduce the nonlinear effects. We study the shaping gains in the fiber-optic channel and show that in certain scenarios the maximum gains may be higher than the 1.53dB ultimate shaping gain in linear additive white Gaussian noise channels. Furthermore, the maximum gain is achieved with a finite-dimensional ball shaping region.

A source-channel separation theorem for a general channel has recently been shown by Aggrawal et al.[1]. This theorem states that if there exists a coding scheme that achieves a maximum distortion level dmaxover a general channel W, then reliable communication can be accomplished over this channel at rates less than R(dmax), where R(·) is the rate distortion function of the source. The source, however, is essentially constrained to be discrete and memoryless (DMS). In this work we prove a stronger claim where the source is general, satisfying only a “sphere packing optimality” feature, and the channel is completely general. Furthermore, we show that if the channel satisfies the strong converse property as defined by Han & Verdú [2], then the same statement can be made with davg, the average distortion level, replacing dmax. Unlike the proofs in [1], we use information spectrum methods and the results can be quite easily extended to other situations.

Consider the following framework of universal decoding suggested in [1]. Given a family of decoding metrics and random coding distribution (prior), a single, universal, decoder is optimal if for any possible channel the average error probability when using this decoder is better than the error probability attained by the best decoder in the family up to a subexponential multiplicative factor. We describe a general universal decoder in this framework. The penalty for using this universal decoder is computed. The universal metric is constructed as follows. For each metric, a canonical metric is defined and conditions for the given prior to be normal are given. A sub-exponential set of canonical metrics of normal prior can be merged to a single universal optimal metric. We provide an example where this decoder is optimal while the decoder of [1] is not.

This work discusses the source broadcasting problem, i.e. transmitting a source to many receivers via a broadcast channel. The optimal rate-distortion region for this problem is unknown. The separation approach divides the problem into two complementary problems: source successive refinement and broadcast channel transmission. We provide bounds on the loss incorporated by applying time-sharing and separation in source broadcasting. If the broadcast channel is degraded, it turns out that separation-based time-sharing achieves at least a factor of the joint source-channel optimal rate, and this factor has a positive limit even if the number of receivers increases to infinity. For the AWGN broadcast channel a better bound is introduced, implying that all achievable joint source-channel schemes have a rate within one bit of the separation-based achievable rate region for two receivers, or within log2T bits for T receivers.

Classical MAC coding schemes assume independent transmitted signals, because the given messages are assumed to be independent and the remote transmitters cannot cooperate. However, when the messages are correlated, or in the extreme case of fully cooperative transmitters, a better performance may be achieved. We explore the performance gain of this collaboration and its connection to transmission synchronization. For totally asynchronous transmitters we prove that transmitters collaboration has no performance gain. This result is proven for discrete-value channels. For continuous-value channels we focus on the collaboration gain of the AWGN MAC, indicating that it is bounded by a single bit and a factor of two. We suggest that this collaboration gain diminishes without synchronization as well.

Independent component analysis (ICA) is a statistical method for transforming an observed multidimensional random vector into components that are as statistically independent as possible from each other. Usually the ICA framework assumes a model according to which the observations are generated (generative function, additive noise). Binary ICA (BICA) is a special case of ICA in which both the observations and the independent components are over the binary field GF(2). In this work we introduce a generalized BICA framework in which an observation vector is decomposed to its independent components (as much as possible) with no prior assumption on the way it was generated. We propose several theorems and show that this NP hard problem can be accurately solved with a branch and bound search tree algorithm, or tightly approximated with a series of linear programs. BICA was shown to have applications in many domains including medical diagnosis, multi-cluster assignment, network tomography and internet resource management. We suggest that BICA also applies in source coding; we argue that instead of generating statistically independent prediction errors, as in predictive coding, an improved encoder shall assemble a vector of observations and apply the generalized BICA on it. This is shown to achieve improved performance at the cost of introducing some time delay (working in batch).

The problem of universally predicting an individual continuous sequence using a deterministic finite-state machine (FSM) is considered. The empirical mean is used as a reference as it is the constant that fits a given sequence within a minimal square error. A reasonable prediction performance is the regret, namely the excess square-error over the reference loss. This paper analyzes the tradeoff between the number of states of the universal FSM and the attainable regret. This paper first studies the case of a small number of states. A class of machines, termed degenerated tracking memory (DTM), is defined and shown to be optimal for small enough number of states. Unfortunately, DTM machines become suboptimal and their regret does not vanish as the number of available states increases. Next, the exponential decaying memory (EDM) machine, previously used for predicting binary sequences, is considered. While the EDM machine has poorer performance for small number of states, it achieves a vanishing regret for large number of states. Following that, an asymptotic lower bound of O(k-2/3) on the achievable regret of any k-state machine is derived. This bound is attained asymptotically by the EDM machine. Finally, the enhanced exponential decaying memory machine is presented and shown to outperform the EDM machine for any number of states.

Consider communication over a channel whose probabilistic model is completely unknown vector-wise and is not assumed to be stationary. Communication over such channels is challenging because knowing the past does not indicate anything about the future. The existence of reliable feedback and common randomness is assumed. In a previous paper, it was shown that the Shannon capacity cannot be attained, in general, if the channel is not known. An alternative notion of capacity was defined, as the maximum rate of reliable communication by any block-coding system used over consecutive blocks. This rate was shown to be achievable for the modulo-additive channel with an individual, unknown noise sequence, and not achievable for some channels with memory. In this paper, this capacity is shown to be achievable for general channel models possibly including memory, as long as this memory fades with time. In other words, there exists a system with feedback and common randomness that, without knowledge of the channel, asymptotically performs as well as any block code, which may be designed knowing the channel. For channels in which memory does not fade with time, a weaker type of capacity is shown to be achievable.

The penalty incurred by imposing a finite delay constraint in lossless source coding of a memoryless source is investigated. It is well known that for the so-called block-to-variable and variable-to-variable codes, the redundancy decays at best polynomially with the delay, where in this case the delay is identified with the source block length or maximal source phrase length, respectively. In stark contrast, it is shown that for sequential codes (e.g., a delay-limited arithmetic code) the redundancy can be made to decay exponentially with the delay constraint. The corresponding redundancy-delay exponent is shown to be at least as good as the Rényi entropy of order 2 of the source, but (for almost all sources) not better than a quantity depending on the minimal source symbol probability and the alphabet size.

Is it a good idea to use the frequency of events in the past, as a guide to their frequency in the future (as we all do anyway)? In this paper the question is attacked from the perspective of universal prediction of individual sequences. It is shown that there is a universal sequential probability assignment, such that for a large class loss functions (optimization goals), the predictor minimizing the expected loss under this probability, is a good universal predictor. The proposed probability assignment is based on randomly dithering the empirical frequencies of states in the past, and it is easy to show that randomization is essential. This yields a very simple universal prediction scheme which is similar to Follow-the-Perturbed-Leader (FPL) and works for a large class of loss functions, as well as a partial justification for using probabilistic assumptions.

Memoryless processes hold many theoretical and practical advantages. They are easy to describe, analyze, store and encrypt. They can also be seen as the essence of a family of regression processes, or as an innovation process triggering a dynamic system. The Gram-Schmidt procedure suggests a linear sequential method of whitening (decorrelating) any stochastic process. Applied on a Gaussian process, memorylessness (that is, statistical independence) is guaranteed. It is not clear however, how to sequentially construct a memoryless process from a non-Gaussian process. In this paper we present a non-linear sequential method to generate a memoryless process from any given Markov process under varying objectives and constraints. We differentiate between lossless and lossy methods, closed form and algorithmic solutions and discuss the properties and uniqueness of our suggested methods.

This paper presents a new fading model for multi-input multi-output channels: the Jacobi fading model. It asserts thatH, the transfer matrix which couples themtinputs intomroutputs, is a submatrix of anm×mrandom (Haar-distributed) unitary matrix. The (squared) singular values ofHfollow the law of the classical Jacobi ensemble of random matrices, hence the name of the channel. One motivation to define such a channel comes from multimode/multicore optical fiber communication. It turns out that this model can be qualitatively different from the Rayleigh model, leading to interesting practical and theoretical results. This paper first evaluates the ergodic capacity of the channel. Then, it considers the nonergodic case, where it analyzes the outage probability and the diversity-multiplexing tradeoff. In the case wherek=mt+mr-m> 0, it is shown that at leastkdegrees of freedom are guaranteed not to fade for any channel realization, enabling a zero-outage probability or infinite diversity order at the corresponding rates. A simple scheme utilizing (a possibly outdated) channel state feedback is provided, attaining the no-outage guarantee. Finally, noting that asmincreases, the Jacobi model approaches the Rayleigh model, the paper discusses the applicability of the model in other communication scenarios.

In the setting of a Gaussian channel without power constraints, proposed by Poltyrev in 1994, the codewords are points in ann-dimensional Euclidean space (an infinite constellation) and the tradeoff between their density and the error probability is considered. The normalized log density (NLD) plays the role of the communication rate, and capacity as well as error exponent bounds for this setting are known. This paper considers the infinite constellation setting in the finite block-length (dimension) regime. A simplified expression for Poltyrev's achievability bound is found and it is shown to be closely related to the sphere converse bound and to a recently proposed achievability bound based on point processes. The bounds are then analyzed asymptotically for growingn: for fixed NLD, the bounds turn out to be extremely tight compared to previous error exponent analysis. For fixed error probability ε, it is shown that the gap of the highest achievable NLD to the optimal NLD (Poltyrev's capacity) is approximately √{[1/(2n)]}Q-1(ε) , whereQis the standard complementary Gaussian cumulative distribution function, thus extending the channel dispersion analysis to infinite constellations. Connections to the error exponent of the power-constrained Gaussian channel and to the volume-to-noise ratio as a figure of merit are discussed. Finally, the new tight bounds are compared to state-of-the-art coding schemes.

Consider the problem of universally communicating over an arbitrarily varying channel, i.e., a channel comprised of an unknown, arbitrary sequence of memoryless channels. It is shown that there is a communication system using feedback and common randomness that asymptotically attains, with high probability, the capacity of the time-averaged channel, universally for every sequence of channels. This attainable rate is optimal under certain conditions. While no prior knowledge of the channel sequence is assumed, the capacity of the time-averaged channel meets or exceeds the traditional arbitrarily varying channel (AVC) capacity for every memoryless AVC defined over the same alphabets, and therefore, the system universally attains the random code AVC capacity, without knowledge of the AVC parameters. The presented system combines rateless coding with a universal prediction scheme for the input “prior” distribution, from which the codebook is randomly drawn. Because at each point in time, the future of the channel sequence is unknown to the communicators, the adaptation of the input behavior, by universally predicting the prior, plays a major role in the result.

Which communication rates can be attained over a channel whose output is an unknown (possibly stochastic) function of the input that may vary arbitrarily in time with no a priori model? Following the spirit of the finite-state compressibility of a sequence, defined by Lempel and Ziv, a “capacity” is defined for such a channel as the highest rate achievable by a designer knowing the particular relation that indeed exists between the input and output for all times, yet is constrained to use a fixed finite-length block communication scheme without feedback, i.e., use the same encoder and decoder over each block. In the case of the modulo additive channel, where the output sequence is obtained by modulo addition of an unknown individual sequence to the input sequence, this capacity is upper bounded by a function of the finite state compressibility of the noise sequence. A universal communication scheme with feedback that attains this capacity universally, without prior knowledge of the noise sequence, is presented.

Universal rateless coding over unknown discrete memoryless channels (DMC) is considered. In rateless codes each codeword is infinitely long, and the decoding time depends on the confidence level of the decoder. This work considers the finite message set case where a finite number of bits are transmitted over an unknown discrete memoryless channel, with a fix allowed error probability. Using rateless codes along with sequential universal decoding that utilizes a mixture probability law instead of the unknown channel law, an optimal universal scheme is obtained. The analysis specifies explicitly the attainable rate, at each message set size and allowed error probability, which reflects the cost of universality.

In the Jacobi MIMO channel the transfer matrix H which couples the mtinputs into mroutputs is a sub-matrix of an m×m random (Haar-distributed) unitary matrix. The (squared) singular values of H follow the law of the classical Jacobi ensemble of random matrices; hence the name of the channel. A motivation to define such a channel comes from multimode/multicore optical fiber communication. It turns out that this model is qualitatively different than the Rayleigh model, leading to interesting practical and theoretical results. This work first evaluates the ergodic capacity of the channel. In the non-ergodic case, it analyzes the outage probability and the diversity-multiplexing tradeoff. In the case where k = mt+mr-m >; 0 at least k degrees of freedom are guaranteed not to fade for any channel realization enabling a zero outage probability or infinite diversity order at the corresponding rates. Finally, we note that the Jacobi channel may provide a new fading model to other applications.

An upper bound on the error probability of specific lattices, based on their distance spectrum, is constructed. The derivation is accomplished using a simple alternative to the Minkowski-Hlawka mean-value theorem of the geometry of numbers. In many ways, the new bound greatly resembles the Shulman-Feder bound for linear codes. Based on the new bound, an error exponent is derived for specific lattice sequences (of increasing dimension) over the AWGN channel. Measuring the sequence's gap to capacity, using the new exponent, is demonstrated.

Consider communication over a channel whose probabilistic model is completely unknown vector-wise and is not assumed to be stationary. Communication over such channels is challenging because knowing the past does not indicate anything about the future. The existence of reliable feedback and common randomness is assumed. In a previous paper it was shown that the Shannon capacity cannot be attained, in general, if the channel is not known. An alternative notion of “capacity” was defined, as the maximum rate of reliable communication by any block-coding system used over consecutive blocks. This rate was shown to be achievable for the modulo-additive channel with an individual, unknown noise sequence, and not achievable for some channels with memory. In this paper this “capacity” is shown to be achievable for general channel models possibly including memory, as long as this memory fades with time. In other words, there exists a system with feedback and common randomness that, without knowledge of the channel, asymptotically performs as well as any block-coding system, which may be designed knowing the channel. For non-fading memory channels a weaker type of “capacity” is shown to be achievable.

A max-product algorithm for approximating maximum-likelihood lattice decoding of low density lattice codes is derived, operating directly in the Euclidean space. First we derive the max-product algorithm for continuous channels by taking a factor graph based approach. Then, for the additive white Gaussian noise channel we show the relation between the sum-product and max-product algorithms for low density lattice codes. In both algorithms the messages consist of the same Gaussians. While in the sum-product algorithm we sum the Gaussians in each message, for the max-product we take the maximal envelope of these Gaussians. Finally, we extend the parametric approach to efficiently implement the max-product algorithm, and show decrease in the word error rate (WER).

In this paper we consider the problem of universal prediction of individual continuous sequences with square-error loss, using a deterministic finite-state machine (FSM). The goal is to attain universally the performance of the best constant predictor tuned to the sequence, which predicts the empirical mean and incurs the empirical variance as the loss. The paper analyzes the tradeoff between the number of states of the universal FSM and the excess loss (regret). We first present a machine, termed Exponential Decaying Memory (EDM) machine, used in the past for predicting binary sequences, and show bounds on its performance. Then we consider a new class of machines, Degenerated Tracking Memory (DTM) machines, find the optimal DTM machine and show that it outperforms the EDM machine for a small number of states. Incidentally, we prove a lower bound indicating that even with large number of states the regret of the DTM machine does not vanish. Finally, we show a lower bound on the achievable regret of any FSM, and suggest a new machine, the Enhanced Exponential Decaying Memory, which attains the bound and outperforms the EDM for any number of states.

In the setting of a Gaussian channel without power constraints, proposed by Poltyrev, the codewords are points in an n-dimensional Euclidean space (an infinite constellation) and their optimal density is considered. Poltyrev's “capacity” is the highest achievable normalized log density (NLD) with vanishing error probability. This capacity as well as error exponents for this setting are known. In this work we consider the optimal NLD for a fixed, nonzero error probability, as a function of the codeword length (dimension) n. We show that as n grows, the gap to capacity is inversely proportional (up to the first order) to the square-root of n where the proportion constant is given by the inverse Q-function of the allowed error probability, times the square root of 1/2. In an analogy to similar result in channel coding, the dispersion of infinite constellations is 1/2 nat2per channel use. We show that this optimal convergence rate can be achieved using lattices, therefore the result holds for the maximal error probability as well. Connections to the error exponent of the power constrained Gaussian channel and to the volume-to-noise ratio as a figure of merit are discussed.

We consider the problem of communicating over an unknown and arbitrarily varying channel, using feedback. This paper focuses on the problem of determining the input behavior, or more specifically, a prior which is used to randomly generate a codebook. We pose the problem of setting the prior as a sequential universal prediction problem using information theoretic abstractions of the communication channel. For the case where the channel is block-wise constant, we show it is possible to asymptotically approach the best rate that can be attained by any system using a fixed prior. For the case where the channel may change on each symbol, we combine a rateless coding scheme with a prior predictor and asymptotically approach the capacity of the average channel universally for every sequence of channels.

Which communication rates can be attained over a channel whose output is an unknown (possibly stochastic) function of the input that may vary arbitrarily in time with no a-priori model? Following the spirit of the finite-state compressibility of a sequence defined by Lempel and Ziv, we define a “capacity” for such a channel as the highest rate achievable by a designer knowing the particular relation that indeed exists between the input and output for all times, yet is constrained to use a fixed finite-length block communication scheme (i.e., use the same scheme over each block). In the case of the binary modulo additive channel, where the output sequence is obtained by modulo addition of an unknown individual sequence to the input sequence, this capacity is upper bounded by 1 - ρ where ρ is the finite state compressibility of the noise sequence. We present a communication scheme with feedback that attains this rate universally without prior knowledge of the noise sequence.

In a previous work, a universal decoder in a competitive minimax sense was developed for unknown block fading linear white Gaussian channels. For a given codebook (with finite blocklength), a high SNR optimal metric for the decoder was found, whose direct calculation requires solving a non-convex optimization problem and may be formidable. In this paper, the metric calculation problem is facilitated by semidefinite programming, which leads to a low-complexity approximation for the metric. The competitive minimax performance of the optimal decoder (i.e., its worst case power loss compared to the maximum likelihood decoder, which has full knowledge of the channel) is evaluated, and upper lower bounds are derived for the performance evaluation of non-optimal decoders - the training sequence and the generalized likelihood test decoders.

The fundamental and natural connection between the infinite constellation (IC) dimension and the best diversity order it can achieve is investigated in this paper. In the first part of this work we develop an upper bound on the diversity order of IC for any dimension and any number of transmit and receive antennas. In the second part of this work we prove that by choosing the correct dimensions, IC in general and lattices in particular can achieve the optimal diversity-multiplexing tradeoff of finite constellations. This work gives a framework for designing lattices for multiple-antenna channels using lattice decoding.

A communication problem in considered, where no mathematical model is specified for the channel. The achievable rates are determined as a function of the channel input and output sequences known a-posteriori, without assuming any a-priori relation between them. For discrete channels the empirical mutual information between the input and output sequences is shown to be achievable, while for continuous channels the achievable rate is based on the empirical correlation between the sequences. A rate-adaptive scheme employing feedback which achieves these rates asymptotically with a guaranteed reliability, without prior knowledge of the channel behavior, is presented.

The coded modulation scheme proposed in this paper has a simple construction: an integer sequence, representing the information, is convolved with a fixed, continuous-valued, finite impulse response (FIR) filter to generate the codeword - a lattice point. Due to power constraints, the code construction includes a shaping mechanism inspired by precoding techniques such as the Tomlinson-Harashima filter. We naturally term these codes “convolutional lattice codes” or alternatively “signal codes” due to the signal processing interpretation of the code construction. Surprisingly, properly chosen short FIR filters can generate good codes with large minimal distance. Decoding can be done efficiently by sequential decoding or for better performance by bidirectional sequential decoding. Error analysis and simulation results indicate that for the additive white Gaussian noise (AWGN) channel, convolutional lattice codes with computationally reasonable decoders can achieve low error rate close to the channel capacity.

In this paper, we introduce a fundamental principle for optimal communication over general memoryless channels in the presence of noiseless feedback, termed posterior matching. Using this principle, we devise a (simple, sequential) generic feedback transmission scheme suitable for a large class of memoryless channels and input distributions, achieving any rate below the corresponding mutual information. This provides a unified framework for optimal feedback communication in which the Horstein scheme (BSC) and the Schalkwijk-Kailath scheme (AWGN channel) are special cases. Thus, as a corollary, we prove that the Horstein scheme indeed attains the BSC capacity, settling a longstanding conjecture. We further provide closed form expressions for the error probability of the scheme over a range of rates, and derive the achievable rates in a mismatch setting where the scheme is designed according to the wrong channel model. Several illustrative examples of the posterior matching scheme for specific channels are given, and the corresponding error probability expressions are evaluated. The proof techniques employed utilize novel relations between information rates and contraction properties of iterated function systems.

An extension of the class of low density lattice codes (LDLC's) to the complex case (i.e. complex lattices) is presented. We propose an extended belief-propagation decoding algorithm and present a complex parametric decoder. The complex decoder attains better performance for small dimensions, and for LDLC's with small degrees. This extension is also required in order to use LDLC's as a lattice space time codes.

We consider the problem of communicating over a multiple-input multiple-output (MIMO) real valued channel for which no mathematical model is specified, and achievable rates are given as a function of the channel input and output sequences known a-posteriori. This paper extends previous results regarding individual channels by presenting a rate function for the MIMO individual channel, and showing its achievability in a fixed transmission rate communication scenario.

Universal portfolio algorithms find investment strategies competitive against any CRP (constant rebalanced portfolio) for each and every market sequence. This work studies the problem of competitiveness over a subset of realistic, non-pathological, market sequences observed in many settings, e.g., high-frequency trading. Competitive investment in this setting will be shown to be more an extension of the easier universal 0-1 loss problem than of universal gambling (or coding). Analysis of realism-agnostic investment algorithms will show that they perform much better on in-hindsight realistic sequences than previously demonstrated. We suggest that this implies that the study of realistic universal portfolio algorithms must involve a comparison to a stronger adversary than the CRP adversary: an adversary that rebalances a portfolio often enough to avoid pathological sequences, but not so frequently that transaction costs dominate.

This paper introduces an efficient polynomial-time code construction algorithm for cyclic networks, which achieves the optimal multicast rate. Until this work, no explicit capacity-achieving polynomial-time code construction forcyclicnetworks has been known. This new construction algorithm has the additional advantage that as sinks are added or removed from the network, it can modify the existing code in an efficient localized manner, which is beneficial also for acyclic networks. For decoding this code, a polynomial-time sequential decoder for convolutional network codes is also proposed.

When transmitting a Gaussian source over an AWGN channel with an input power constraint and a quadratic distortion measure, it is well known that optimal performance can be obtained using an analog joint source-channel scalar scheme which merely scales the input and output signals. In the case of bandwidth expansion, such a joint source-channel analog scheme attaining optimal performance is no longer simple. However, when feedback is available a simple and sequential analog linear procedure based on the Schalkwijk-Kailath scheme for communication, is optimal. Recently, we have introduced a fundamental feedback communication scheme, termedposteriormatching, which generalizes the Schalkwijk-Kailath scheme to arbitrary memoryless channels and input distributions. In this paper, we show how the posterior matching scheme can be adapted to the joint source-channel coding setting with bandwidth expansion and a general distortion measure, when feedback is available.

The capacity and random coding error exponent of multilevel coding (MLC) with multistage decoding (MSD) are analyzed. General discrete memoryless channels with arbitrary input distributions are considered. The capacities of MLC with maximum likelihood decoding and with MSD are calculated, and it is shown that using MLC may result in loss in the achievable rate for reliable communication. Necessary and sufficient conditions for the rate loss to be zero are derived. A new random coding error exponent is derived for MLC with MSD. For the special case of uniform inputs, the new error exponent can be easily calculated by its inverse function, which is given by the sum of the inverse error exponents of the conditional sub-channels.

We consider the problem of communicating over a channel for which no mathematical model is specified. We present achievable rates as a function of the channel input and output sequences known a-posteriori for discrete and continuous channels. Furthermore we present a rate-adaptive scheme employing feedback which achieves these rates asymptotically without prior knowledge of the channel behavior.

We consider a real-valued additive channel with an individual unknown noise sequence. We present a simple sequential communication scheme based on the celebrated Schalkwijk-Kailath scheme, which varies the transmit power according to the power of the sequence, so that asymptotically the relation between the SNR and the rate matches the Gaussian channel capacity R ¿ 1/2 log(1 + SNR) for almost every noise sequence.

A new efficient parametric algorithm for implementing the low density lattice codes belief propagation decoder is presented. In the new algorithm the messages passed over the edges are represented by Gaussian parameters lists, and the decoding algorithm uses the low density lattice codes propagation properties in order to group lists efficiently according to a new criteria. The new algorithm attains essentially the same performance as the quantized decoder, proposed in previous work. The new algorithm advantage in comparison to previous works is its smaller storage requirements and its relatively low computational complexity.

In this work we introduce a construction and analysis of network codes for two sources. The region of achievable rates for this problem is still unknown. The scheme we suggest is based on modifying the multicommodity flow solution and thus improving the achievable rate region, w.r.t the uncoded case. The similarity to the flow problem allows our method to be implemented distributively. We show how the construction algorithm can be combined with distributed backpressure routing algorithms for wireless ad-hoc networks. For both the nondistributed case and the distributed case, the computational complexity of our algorithm for network coding is comparable to that of the parallel multicommodity flow problem. We provide non trivial upper and lower bounds on the performance of our scheme, using random coding techniques.

Most of the existing methods that are used to solve the closest lattice point problem are based on an efficient search of the lattice points. In this paper a novel alternative approach is suggested where the closest point to a given vector is found by calculating which Voronoi cell contains this vector in an iterative manner. Each iteration is made of simple “slicing” operations, using a list of the Voronoi relevant vectors that define the basic Voronoi cell of the lattice. The algorithm is guaranteed to converge to the closest lattice point in a finite number of steps. The method is suitable, for example, for decoding of multi-input multi-output (MIMO) communication problems. The average computational complexity of the proposed method is comparable to that of the efficient variants of the sphere decoder, but its computational variability is smaller.

We address the problem of universal communications over an unknown channel with an instantaneous noiseless feedback, and show how rates corresponding to the empirical behavior of the channel can be attained, although no rate can be guaranteed in advance. First, we consider a discrete modulo-additive channel with alphabet${\cal X}$, where the noise sequence$Z^n$isarbitrary and unknownand may causally depend on the transmitted and received sequences and on the encoder's message, possibly in an adversarial fashion. Although the classical capacity of this channel is zero, we show that rates approaching theempirical capacity$\log{\vert {\cal X}\vert}-H_{\rm emp}(Z^n)$can be universally attained, where$H_{\rm emp}(Z^n)$is the empirical entropy of$Z^n$. For the more general setting, where the channel can map its input to an output in an arbitrary unknown fashion subject only to causality, we model the empirical channel actions as the modulo-addition of a realized noise sequence, and show that the same result applies if common randomness is available. The results are proved constructively, by providing a simple sequential transmission scheme approaching the empirical capacity.

In a previous paper we derived an upper bound on the redundancy of an arithmetic-type encoder for a memoryless source, designed to meet a finite end- to-end strict delay constraint. It was shown that the redundancy decays exponentially with the delay constraint and that the redundancy-delay exponent is lower bounded by log(1/alpha) where alpha is the probability of the most likely source symbol. In this work, we prove a corresponding upper bound for the redundancy-delay exponent, C - log 1/beta where beta is the probability of the least likely source symbol. This bound is valid for almost all memoryless sources and for all arithmetic-type (possibly time-varying, memory dependent) lossless delay-constrained encoders. We also shed some light on the difference between our exponential bounds and the polynomial O(d-5'3) upper bound on the redundancy with an average delay constraint d, derived in an elegant paper by Bugeaud, Drmota and Szpankowski for another class of variable-to-variable encoders, and show that the difference is due to the precision needed to memorize the encoder's state.

In this work we consider joint source-channel coding (JSCC) schemes that are limited to work in blocks of finite length. We focus on the high resolution and high signal to noise ratio (SNR) regime, and derive new lower bounds for the distortion of JSCC schemes over rth-moment constrained additive noise channels. These new bounds are based on the method of Ziv and Zakai [11], combined with the Renyi information measure, as was recently proposed by Leibowitz and Zamir [5]. Numerical results are presented for the case of Gaussian source and channel, and it is shown that the new bounds improve upon Shannon's original bound in several cases, including bandwidth expansion and reduction.

Recently, we have introduced a sequential communication scheme for general memoryless channels with feedback based on the idea of posterior matching, providing a unified framework in which the known Horstein and Schalkwijk-Kailath schemes are special cases. In this paper, we show that the posterior matching scheme achieves the mutual information for a large family of channels and input distributions, and provide closed-form expressions for the attainable error probability over a range of rates. Moreover, we derive the achievable rates in a mismatched setting, where the scheme is designed according to the wrong channel model. In particular, our results hold for discrete memoryless channels, thereby confirming a longstanding conjecture that the Horstein scheme achieves capacity. The proof techniques employed utilize novel relations between information rates and convergence properties of iterated function systems.

We consider the memory requirements of stock-market investment algorithms through their finite state machine (FSM) implementations. The regret of an online algorithm is the limit difference between its capital growth rate and that of the optimal (in hindsight) constant rebalanced portfolio. Let ℓ, ∈, and m be the number of states, the regret, and the number of stocks, respectively. We consider the relationships between ∓ and ∈ for large m. For individual markets (with no underlying distributions) and deterministic FSMs, we show that any ∈-regret FSM must have Ω ((1/∈)m−1/m−1/2) states, and also show an ∈-regret FSMs with O ((1/∈)4m) states. These space-complexity questions are especially pertinent to state portfolio algorithms, where both market history and side-information are taken into account.

We address the problem of communicating over an unknown linear fading channel with additive white Gaussian noise, in the high SNR regime. A block fading model is adopted where the channel fading vector is unknown, yet assumed constant during the block. For a given codebook, a competitive minimax criterion is used to find a decoder ignorant of the specific channel fading prevailing, yet its performance, relative to the Maximum Likelihood decoder, has the best worst case. For a codebook with two codewords, the decoder is found explicitly, and a numerical method is described to find its performance.

Low-density lattice codes (LDLC) are novel lattice codes that can be decoded efficiently and approach the capacity of the additive white Gaussian noise (AWGN) channel. In LDLC a codeword x is generated directly at the n-dimensional Euclidean space as a linear transformation of a corresponding integer message vector b, i.e., x = Gb-1, where H = G-1is restricted to be sparse. The fact that H is sparse is utilized to develop a linear-time iterative decoding scheme which attains, as demonstrated by simulations, good error performance within ~0.5 dB from capacity at block length of n =100,000 symbols. The paper also discusses convergence results and implementation considerations.

In this work we consider dimension reducing mappings that can be used for joint source-channel coding (JSCC) systems. In such systems, the source coding and the channel coding is performed as a single operation. Although it is known by Shannon's separation theorem that asymptotically JSCC is not required for attaining the optimal performance, utilizing such schemes is beneficial for practical reasons such as delay and implementation simplicity. We specifically focus on the bandwidth reduction case, where the bandwidth of the data is greater than the bandwidth of the channel. More specifically, we focus on bandwidth reduction mappings, where the JSCC operation is performed using a single nonlinear operation. A modification of the spiral mapping is presented, so the power at the output is proportional to that of the input

We address the problem of a finite delay constraint in an arithmetic coding system. Due to the nature of the arithmetic coding process, source sequences causing arbitrarily large encoding or decoding delays exist. Therefore, to meet a finite delay constraint, it is necessary to intervene with the normal flow of the coding process, e.g., to insert fictitious symbols. This results in an inevitable coding rate redundancy. In this paper, we derive an upper bound on the achievable redundancy for a memoryless source. We show that this redundancy decays exponentially as a function of the delay constraint, and thus it is clearly superior to block to variable methods in that aspect. The redundancy-delay exponent is shown to be lower bounded by log(1/alpha), where alpha is the probability of the most likely source symbol. Our results are easily applied to practical problems such as the compression of English text

Motivated by applications of rateless coding, decision feedback, and automatic repeat request (ARQ), we study the problem of universal decoding for unknown channels in the presence of an erasure option. Specifically, we harness the competitive minimax methodology developed in earlier studies, in order to derive a universal version of Forney's classical erasure/list decoder, which in the erasure case, optimally trades off between the probability of erasure and the probability of undetected error. The proposed universal erasure decoder guarantees universal achievability of a certain fraction xi of the optimum error exponents of these probabilities. A single-letter expression for xi, which depends solely on the coding rate and the Neyman-Pearson threshold, is provided. The example of the binary symmetric channel is studied in full detail, and some conclusions are drawn.

In this paper we describe a general algorithmic scheme for communication over any memoryless channel in the presence of noiseless feedback. The scheme is based on the idea of posterior matching, in which the information still missing at the receiver is extracted from the a-posteriori density function, and matched to any desirable input distribution. We analyze the error probability attained by this scheme for additive noise channels, and show that the well-known Schalkwijk-Kailath scheme for the AWGN channel with average power constraint and the Horstein scheme for the BSC, can be derived as special cases.

Most of the existing methods to solve the closest lattice point problem are based on an efficient search of the lattice points. In this paper, a novel alternative approach is suggested where the closest point to a given vector is found by calculating which Voronoi cell contains this vector in an iterative manner. Each iteration is made of simple "slicing" operations, using a list of the Voronoi relevant vectors that define the basic Voronoi cell of the lattice. The algorithm is guaranteed to converge to the closest lattice point in a finite number of steps. The method is suitable, for example, for decoding of multi-input multi-output (MIMO) communication problems. The average computational complexity of the proposed method is comparable to that of the efficient variants of the sphere decoder, but its computational variability is smaller.

Motivated by applications of rateless coding, decision feedback, and automatic repeat request (ARQ), we study the problem of universal decoding for unknown channels in the presence of an erasure option. Specifically, we harness the competitive minimax methodology developed in earlier studies, in order to derive a universal version of Forney's classical erasure/list decoder, which in the erasure case, optimally trades off between the probability of erasure and the probability of undetected error. The proposed universal erasure decoder guarantees universal achievability of a certain fraction xi of the optimum error exponents of these probabilities (in a sense to be made precise in the sequel). A single-letter expression for xi, which depends solely on the coding rate and the Neyman-Pearson threshold (to be defined), is provided. The example of the binary-symmetric channel is studied in full detail, and some conclusions are drawn

In this work we consider the problem of universal prediction of individual sequences where the universal predictor is a deterministic finite state machine, with a fixed, relatively small, number of states. We examine the case of self-information loss, where the predictions are probability assignments which is equivalent to universal data compression. While previous results in that area are asymptotic only, we examine a class of machine structures and find an optimal method for allocating the probabilities to the machine states which achieves minimal redundancy w.r.t. the constant predictors class. We show analytic bounds for the redundancy of machines from that class, and construct machines with redundancy that is arbitrarily close to these bounds. Finally, we compare our machines to previously proposed machines and show that our machine with 300 states achieves smaller redundancy than the best machine known so far with 6000 states.

A concatenated additive white gaussian noise (AWGN) relay channel is considered. The different relays are only allowed to carry out simple symbol manipulation (e.g. hard limiter, linear amplifier or any symbol-wise analog scheme). The decay of the overall capacity as a function of the number of concatenated relays is explored. Contrary to point-to-point channels, where using a refined constellation can only increase the capacity, we show that the larger the constellation the faster the capacity decays. Since the initial point-to-point capacity of refined constellations is larger and their decay is faster, there is a tradeoff that leads to an optimal constellation size which is a function of the SNR and the number of relays.

We consider the problem of universal prediction of individual binary sequences where the universal predictor is a deterministic finite state machine with a fixed number of states. We examine the case of self-information loss, where the predictions are probability assignments. The performance of the predictors is measured by their redundancy w.r.t. the constant predictors class. We obtain an improved lower bound on the redundancy of any finite state (FS) predictor with K states. We construct a FS predictor based on the lower bound and compare the performance of the predictor to the lower bound. Numerical results show that the redundancy of the proposed FS predictor is close to that predicted by the lower bound

A simple backward adaptation method for constructing adaptive scalar quantizers is presented. The method needs no excess memory apart from that used to describe the current state of the quantizer and its complexity is linear in the length of the sequence to be quantized. Furthermore, it is direct and does not go through auxiliary steps such as probability density function (PDF) estimations. The basic idea is that if the current value of the sequence belongs to a certain cell (the cell is "hit"), we shrink that cell by a certain factor (with a certain probability, assuming joint randomness) and stretch all the other cells to fill the remaining space. The probability of shrinking a cell is optimally set to be proportional to 1/length(cell)2. In the high resolution limit, the equilibrium of the quantizer is reached when the length of the quantizer cells is proportional to 1/PDF(cell)1/3which is the optimal density of a scalar quantizer. This method is shown to converge to the optimal quantizer even for probability density functions for which the Lloyd-Max algorithm converges to a local minimum, e.g., mixed Gaussian with different weights

We address the problem of delay in an arithmetic coding system. Due to the nature of the arithmetic coding process, source sequences causing arbitrarily large encoding or decoding delays exist. This phenomena raises the question of just how large is the expected input to output delay in these systems, i.e., once a source sequence has been encoded, what is the expected number of source letters that should be further encoded to allow full decoding of that sequence. In this paper, we derive several new upper bounds on the expected delay for a memoryless source, which improve upon a known bound due to Gallager. The bounds provided are uniform in the sense of being independent of the sequence's history. In addition, we give a sufficient condition for a source to admit a bounded expected delay, which holds for a stationary ergodic Markov source of any order

Low density lattice codes (LDLC) are novel lattice codes that can approach the capacity of the additive white Gaussian noise (AWGN) channel and be decoded efficiently. In LDLC a codeword x is generated directly at the n-dimensional Euclidean space as a linear transformation of a corresponding integer message vector b, i.e., x = Gb, where H = G-1is restricted to be sparse. The fact that H is sparse is utilized to develop a linear-time iterative decoding scheme which attains, as demonstrated by simulations, good error performance within ~ 0.5 dB from capacity at block length of n = 100,000 symbols. The paper also discusses convergence results and implementation considerations

We consider the problem of broadcasting a single Gaussian source to two listeners over a Gaussian broadcast channel, with rho channel uses per source sample, where rho>1. A distortion pair (D1,D2) is said to be achievable if one can simultaneously achieve a mean-squared error (MSE) D1at receiver 1 and D2at receiver 2. The main result of this correspondence is an outer bound for the set of all achievable distortion pairs. That is, we find necessary conditions under which (D1,D2) is achievable. We then apply this result to the problem of point-to-point transmission over a Gaussian channel with unknown signal-to-noise ratio (SNR) and rho>1. We show that if a system must be optimal at a certain SNRmin, then, asymptotically, the system distortion cannot decay faster than O(1/SNR). As for achievability, we show that a previously reported scheme, due to Mittal and Phamdo (2002), is optimal at high SNR. We introduce two new schemes for broadcasting with bandwidth expansion, combining digital and analog transmissions. We finally show how a system with a partial feedback, returning from the bad receiver to the transmitter and to the good receiver, achieves a distortion pair that lies on the outer bound derived here

We address the problem of decoding in unknown frequency selective fading channels, using an OFDM signaling scheme and adopting a block fading model. For a given codebook, we seek a decoder independent of the channel fading, whose worst case performance, relative to a maximum likelihood (ML) decoder that knows the channel, is optimal. Specifically, the decoder is selected from a family of quadratic decoders, and the optimal decoder is referred to as a quadratic minimax (QMM) decoder for that family. The intuitively appealing QMM decoding procedure is derived for the case where the fading is unknown, and also for the case where the fading coefficients satisfy some general constraints. The QMM decoder is also shown to outperform the generalized likelihood ratio test (GLRT), while maintaining a comparable complexity. Simulations verify the superiority of the proposed decoder over the GLRT and over the practically used training sequence approach.

In this work we address the problem of network codes for cyclic networks. We show that network codes can be constructed for cyclic networks as long as at least one edge in each cycle has a delay, but it is not required that every edge would have a delay. We then present the algorithm for constructing an optimal multicast network code, developed in our previous work, and analyze its computational complexity, showing that it is polynomial in the graph size. We discuss the properties of the resulting codes, and show the ability to modify the code in a localized manner when sinks are added or removed. This property is also applicable to acyclic networks. Finally, we propose the sequential decoding algorithm we developed in an earlier work for decoding the resulting codes. For this we analyze its decoding delay, for both acyclic and cyclic networks

Communications over a binary channel with an additive (modulo 2) individual noise sequence and a full causal feedback link is explored. A randomized sequential transmission scheme that adapts its rate to the individual noise realization is presented. The decoding rate is analyzed for a special case, and shown to asymptotically approach 1 - hb(pemp) with a vanishing probability of error w.r.t. the scheme's randomization, where hb(pemp) is the empirical entropy of the noise sequence. Therefore, while the classical capacity of this channel is zero, information may be reliably transmitted over the channel by not committing to a rate in advance, but rather decoding at a rate dictated by the realized noise sequence

The problem of finding the closest lattice point arises in several communication problems, and is known to be NP-hard. Existing methods to solve the problem are based on the sphere decoder, which searches for all the lattice points in a sphere around the received point. The sphere decoder is general and does not exploit the noise properties of the communication channel. In this paper we suggest to use sequential decoding algorithms for this problem. In particular, we propose an algorithm based on the well known Fano algorithm that naturally exploits the noise structure, hence offers a significant complexity reduction with respect to the sphere decoder with only a small penalty in error performance. Two further improvements are suggested. The first is bidirectional stack decoding, where the stack is implemented using a heap data structure to avoid sorting. The second is interleaved decoding, where the possibility to choose an arbitrary search order along the lattice coordinates is used to interleave noise bursts at the receiver. Finally, a lower bound is found for the computational cutoff rate of sequential lattice decoding

We address the problem of universal decoding in unknown frequency-selective fading channels, using an orthogonal frequency-division multiplexing (OFDM) signaling scheme. A block-fading model is adopted, where the bands' fading coefficients are unknown yet assumed constant throughout the block. Given a codebook, we seek a decoder independent of the channel parameters whose worst case performance relative to a maximum-likelihood (ML) decoder that knows the channel is optimal. Specifically, the decoder is selected from a family of quadratic decoders, and the optimal decoder is referred to as a quadratic minimax (QMM) decoder for that family. As the QMM decoder is generally difficult to find, a suboptimal QMM decoder is derived instead. Despite its suboptimality, the proposed decoder is shown to outperform the generalized likelihood ratio test (GLRT), which is commonly used when the channel is unknown, while maintaining a comparable complexity. The QMM decoder is also derived for the practical case where the fading coefficients are not entirely independent but rather satisfy some general constraints. Simulations verify the superiority of the proposed QMM decoder over the GLRT and over the practically used training sequence approach.

The problem of assigning a probability to the next outcome of an individual binary sequence under the constraint that the universal predictor has a finite number of states, is explored. The two main loss functions that are considered are the square error loss and the self-information loss. Universal prediction w.r.t. the self-information loss can be combined with arithmetic encoding to construct a universal encoder, thus explores the universal coding problem. The performance of randomized time-invariant K-state universal predictors, and provide performance bounds in terms of the number of states K for long enough sequences is analyzed. In the case where the comparison class consists of constant predictors for the square error loss, the tight bounds indicating that the optimal asymptotic expected redundancy is O(1/K) is provided. An upper bound on the coding redundancy of O((log K)/K) and a lower bound of O(1/K) is shown for the self-information loss.

Convolutional network codes are considered for cyclic graphs. In CNC each node receives several streams and generates output streams whose current symbols depend on the current input symbols and previous input symbols in the node memory. A multicast CNC can be constructed using an algorithm, in order to minimize the memory and overhead, coefficients of lower polynomial degree are drawn to consideration. For CNC the overhead is the initial delay before the sinks start receiving symbols. CNC with the sequential decoder achieves good performance for some networks.

A coding scheme with feedback for the colored Gaussian noise channel, extending the earlier schemes of Schalkijk and Butman is discussed. By showing a relation between the scheme parameters and the capacity formula we show that this scheme can achieve the channel capacity in its optimal configuration. Using suboptimal configurations, a series of lower bounds for the feedback channel capacity can be constructed.

We derive upper bounds on the maximum achievable rate of low-density parity-check (LDPC) codes used over the binary erasure channel (BEC) under Gallager's decoding algorithm, given their right-degree distribution. We demonstrate the bounds on the ensemble of right-regular LDPC codes and compare them with an explicit left-degree distribution constructed from the given right degree.

The problem of predicting the next outcome of an individual binary sequence under the constraint that the universal predictor has a finite memory, is explored. In this analysis, the finite-memory universal predictors are either deterministic or random time-invariant finite-state (FS) machines with K states (K-state machines). The paper provides bounds on the asymptotic achievable regret of these constrained universal predictors as a function of K, the number of their states, for long enough sequences. The specific results are as follows. When the universal predictors are deterministic machines, the comparison class consists of constant predictors, and prediction is with respect to the 0-1 loss function (Hamming distance), we get tight bounds indicating that the optimal asymptotic regret is 1/(2K). In that case of K-state deterministic universal predictors, the constant predictors comparison class, but prediction is with respect to the self-information (code length) and the square-error loss functions, we show an upper bound on the regret (coding redundancy) of O(K/sup -2/3/) and a lower bound of /spl Theta/(K/sup -4/5/). For these loss functions, if the predictor is allowed to be a random K-state machine, i.e., a machine with random state transitions, we get a lower bound of /spl Theta/(1/K) on the regret, with a matching upper bound of O(1/K) for the square-error loss, and an upper bound of O(logK/K) Throughout the paper for the self-information loss. In addition, we provide results for all these loss functions in the case where the comparison class consists of all predictors that are order-L Markov machines.

In this correspondence, we discuss the properties of the uniform prior as a universal prior, i.e., a prior that induces a mutual information that is simultaneously close to the capacity for all channels. We determine bounds on the amount of the mutual information loss in using the uniform prior instead of the capacity-achieving prior. Specifically, for the class of binary input channels with any output alphabet, we show that the Z-channel has the minimal mutual information with uniform prior, out of all channels with a given capacity. From this, we conclude that the degradation of the mutual information with respect to the capacity is at most 0.011 bit, and as was shown previously, at most 6%. A related result is that the capacity-achieving prior, for any channel, is not far from uniform. Some of these results are extended to channels with nonbinary input.

Motivated by signal processing, we present a new class of channel codes, called signal codes, for continuous-alphabet channels. We analyze the codes and provide simulation results indicating that these codes can be practical and are an attractive alternative to trellis-code techniques.

In this work, we consider the decoding problem for unknown Gaussian linear channels. Important examples of linear channels are the intersymbol interference (ISI) channel and the diversity channel with multiple transmit and receive antennas employing space-time codes (STC). An important class of decoders is based on the generalized likelihood ratio test (GLRT). Our work deals primarily with a decoding algorithm that uniformly improves the error probability of the GLRT decoder for these unknown linear channels. The improvement is attained by increasing the minimal distance associated with the decoder. This improvement is uniform, i.e., for all the possible channel parameters, the error probability is either smaller by a factor (that is exponential in the improved distance), or for some, may remain the same. We also present an algorithm that improves the average (over the channel parameters) error probability of the GLRT decoder. We provide simulation results for both decoders.

The Slepian-Wolf scheme for source coding with side information at the receiver, assures that the sender can send the source X at a rate of only the conditional entropy H(X|Y-) bits per source symbol, which is the minimal possible rate even if the sender knew the side information Y. However, the Slepian-Wolf result requires knowledge of the optimal required rate. In this paper we consider a situation where this rate is not known, possibly since the source is broadcasted to many heterogeneous receivers. The approach is based on recent results regarding sending a common information over a broadcast channel.

In a deletion channel, some symbols might be "dropped off" during transmission. The receiver knows that some symbols were omitted, but does not know either their values or their positions. This differs from the more widely studied erasure channel, where the positions of errors are known, and so all of the symbols that have been successfully received are known to be in their correct positions. In recent years, the interest in deletion channels has grown, possibly due to the fact that networks' packet loss can be modelled as deletions. Codes and bounds for this error model have been studied. One of the most fundamental works on deletions is that of Levenshtein (1965). This work contains bounds on the size of a maximal binary-alphabet codebook of length n words resilient to s deletions. This paper discusses bounds which are an extension of these bounds to a size q alphabet.

A novel approach is presented for the long-standing problem of composite hypothesis testing. In composite hypothesis testing, unlike in simple hypothesis testing, the probability function of the observed data, given the hypothesis, is uncertain as it depends on the unknown value of some parameter. The proposed approach is to minimize the worst case ratio between the probability of error of a decision rule that is independent of the unknown parameters and the minimum probability of error attainable given the parameters. The principal solution to this minimax problem is presented and the resulting decision rule is discussed. Since the exact solution is, in general, hard to find, and a fortiori hard to implement, an approximation method that yields an asymptotically minimax decision rule is proposed. Finally, a variety of potential application areas are provided in signal processing and communications with special emphasis on universal decoding.

Suppose that we want to send a description of a single source to two listeners through a Gaussian broadcast channel, where the channel is used once per source sample. The problem of joint source-channel coding is to design a communication system to minimize the distortion D/sub 1/ at receiver 1 and at the same time minimize the distortion D/sub 2/ at receiver 2. If the source is Gaussian, the optimal solution is well known, and it is achieved by an uncoded "analog" scheme. We consider a Gaussian mixture source. We derive inner and outer bounds for the distortion region of all (D/sub 1/, D/sub 2/) pairs that are simultaneously achievable. The outer bound is based on the entropy power inequality, while the inner bound is attained by a digital-over-analog encoding scheme, which we present. We also show that if the modes of the Gaussian mixture are highly separated, our bounds are tight, and hence, our scheme attains the entire distortion region. This optimal region exceeds the region attained by separating source and channel coding, although it does not contain the "ideal" point (D/sub 1/, D/sub 2/)=(R/sup -1/(C/sub 1/), R/sup -1/(C/sub 2/)).

We consider the problem of sequential linear prediction of real-valued sequences under the square-error loss function. For this problem, a prediction algorithm has been demonstrated whose accumulated squared prediction error, for every bounded sequence, is asymptotically as small as the best fixed linear predictor for that sequence, taken from the class of all linear predictors of a given order p. The redundancy, or excess prediction error above that of the best predictor for that sequence, is upper-bounded by A/sup 2/P ln(n)/n, where n is the data length and the sequence is assumed to be bounded by some A. We provide an alternative proof of this result by connecting it with universal probability assignment. We then show that this predictor is optimal in a min-max sense, by deriving a corresponding lower bound, such that no sequential predictor can ever do better than a redundancy of A/sup 2/p ln(n)/n.

In this work we consider the problem of universal sequential probability assignment, under self-information loss, where the machine for performing the universal probability assignment is constrained to have a finite memory. Sequential probability assignment is equivalent to lossless source coding if we ignore the number of states required to convert the probability estimate into code bits. We consider both the probabilistic setting where the sequence is generated by a probabilistic source (either Bernoulli IID source or q-th order Markov source), and the deterministic setting where the sequence is a deterministic individual sequence. We also consider the case where the universal machine is deterministic, randomized, time-invariant or time-variant. We provide in most cases lower bounds and describe finite memory universal machines whose performance, in terms of the memory size, is compared to these bounds.

An improved upper bound on the error probability (first error event) of time-invariant convolutional codes, and the resulting error exponent, is derived. The improved error bound depends on both the delay of the code K and its width (the number of symbols that enter the delay line in parallel) b. Determining the error exponent of time-invariant convolutional codes is an open problem. While the previously known bounds on the error probability of time-invariant codes led to the block-coding exponent, we obtain a better error exponent (strictly better for b>1). In the limit b/spl rarr//spl infin/ our error exponent equals the Yudkin-Viterbi (1967, 1971, 1965) exponent derived for time-variant convolutional codes. These results are also used to derive an improved error exponent for periodically time-variant codes.

Many applications require high-quality color images. In order to alleviate storage space and transmission time, while preserving high quality, these images are losslessly compressed. Most of the image compression algorithms treat the color image, usually in RGB format, as a set of independent gray-scale images. SICLIC is a novel inter-color coding algorithm based on a LOCO-like algorithm. It combines the simplicity of Golomb-Rice coding with the potential of context models in both intra-color and inter-color encoding. It also supports intra-color and inter-color alphabet extension, in order to reduce the redundancy of the code. SICLIC attains compression ratios superior to those obtained with most of the state-of-the-art compression algorithms and achieves compression ratios very close to those of inter-band CALIC, with much lower complexity. With arithmetic coding, SICLIC attains better compression than inter-band CALIC.

This work presents an analysis of Papoulis' (1977) generalized sampling expansion (GSE) for a wide-sense stationary signal with a known power spectrum in the presence of quantization noise. We find the necessary and sufficient conditions for a GSE system to produce the minimum mean squared error while using the optimal linear estimation filter. This is actually an extension of the optimal linear equalizer (linear source/channel optimization) to the case of M parallel channels.

This work provides techniques to apply the channel coding theorem and the resulting error exponent, which was originally derived for totally random block-code ensembles, to ensembles of codes with less restrictive randomness demands. As an example, the random coding technique can even be applied for an ensemble that contains a single code. For a specific linear code, we get an upper bound for the error probability, which equals Gallager's (1968) random coding bound, up to a factor determined by the maximum ratio between the weight distribution of the code, and the expected random weight distribution.

No abstract available.

The relationship between prediction and data compression can be extended to universal prediction schemes and universal data compression. Previous work shows that minimizing the sequential squared prediction error for individual sequences can be achieved using the same strategies which minimize the sequential code length for data compression of individual sequences. Defining a "probability" as an exponential function of sequential loss, results from universal data compression can be used to develop universal linear prediction algorithms. Specifically, we present an algorithm for linear prediction of individual sequences which is twice-universal, over parameters and model orders.

Data compression and prediction are closely related. Thus prediction methods based on data compression algorithms have been suggested for the branch prediction problem. In this work we consider two universal compression algorithms: prediction by partial matching (PPM), and a recently developed method, context tree weighting (CTW). We describe the prediction algorithms induced by these methods. We also suggest adaptive algorithms variations of the basic methods that attempt to fit limited memory constraints and to match the non-stationary nature of the branch sequence. Furthermore, we show how to incorporate address information and to combine other relevant data. Finally, we present simulation results for selected programs from the SPECint95, SYSmark/32, SYSmark/NT, and transactional processing benchmarks. Our results are most promising in programs with difficult to predict branch behavior.

This work extends Papoulis' (1977) general sampling expansion to the vector case where N band-limited signals are passed through a multi-input multi-output (MIMO) linear time invariant (LTI) system that generates M (M/spl ges/N) output signals. We find necessary and sufficient conditions for reconstructing the N input signals from the samples of the M output signals, all sampled at N/M the Nyquist rate. A surprising necessary condition is that M/N must be an integer. This condition is no longer necessary when each of the output signals can be sampled at a different rate.

A universal decoder for a parametric family of channels is a decoder whose structure depends on the family but not on the individual channel over which transmission takes place, and it yet attains the same random-coding error exponent as the maximum-likelihood receiver tuned to the channel in use. The existence and structure of such decoders is demonstrated under relatively mild conditions of continuity of the channel law with respect to the parameter indexing the family. It is further shown that under somewhat stronger conditions on the family of channels, the convergence of the performance of the universal decoder to that of the optimal decoder is uniform over the set of channels. Examples of families for which universal decoding is demonstrated include the family of finite-state channels and the family of Gaussian intersymbol interference channels.

This paper consists of an overview on universal prediction from an information-theoretic perspective. Special attention is given to the notion of probability assignment under the self-information loss function, which is directly related to the theory of universal data compression. Both the probabilistic setting and the deterministic setting of the universal prediction problem are described with emphasis on the analogy and the differences between results in the two settings.

We derive a version of the Brunn-Minkowski inequality which gives a nontrivial lower bound on the volume of the Minkowski sum of degenerate sets, namely, line sets. This inequality parallels a recently obtained matrix generalization of the entropy-power inequality.

Universal lossy compression of a data sequence can be obtained by fitting to the source sequence a "simple" reconstruction sequence that can be encoded efficiently and yet be within a tolerable distortion from the given source sequence. We develop iterative algorithms to find such a reconstruction sequence, for a given source sequence, using different criteria of simplicity for the reconstruction sequence. As a result we obtain a practical universal lossy compression method. The proposed method can be applied to source sequences defined over finite or continuous alphabets. We discuss the relation between our method and quantization techniques like entropy coded vector quantization (ECVQ) and trellis coded quantization (TCQ).

This work extends Papoulis' (1977) general sampling expansion to the vector case where N band-limited signals are passed through a multi-input multi-output (MIMO) linear time invariant (LTI) system that generates M (M/spl ges/N) output signals. We find necessary and sufficient conditions for reconstructing the N input signals from the samples of the M output signals, all sampled at N/M the Nyquist rate. A surprising necessary condition is that M/N must be an integer. This condition is no longer necessary when each of the output signals can be sampled at a different rate.

In an earlier paper, we proved a strong version of the redundancy-capacity converse theorem of universal coding, stating that for "most" sources in a given class, the universal coding redundancy is essentially lower-bounded by the capacity of the channel induced by this class. Since this result holds for general classes of sources, it extends Rissanen's (1986) strong converse theorem for parametric families. While our earlier result has established strong optimality only for mixture codes weighted by the capacity-achieving prior, our first result herein extends this finding to a general prior. For some cases our technique also leads to a simplified proof of the above mentioned strong converse theorem. The major interest in this paper, however, is in extending the theory of universal coding to hierarchical structures of classes, where each class may have a different capacity. In this setting, one wishes to incur redundancy essentially as small as that corresponding to the active class, and not the union of classes. Our main result is that the redundancy of a code based on a two-stage mixture (first, within each class, and then over the classes), is no worse than that of any other code for "most" sources of "most" classes. If, in addition, the classes can be efficiently distinguished by a certain decision rule, then the best attainable redundancy is given explicitly by the capacity of the active class plus the normalized negative logarithm of the prior probability assigned to this class. These results suggest some interesting guidelines as for the choice of the prior. We also discuss some examples with a natural hierarchical partition into classes.

We present several results regarding the properties of a random vector, uniformly distributed over a lattice cell. This random vector is the quantization noise of a lattice quantizer at high resolution, or the noise of a dithered lattice quantizer at all distortion levels. We find that for the optimal lattice quantizers this noise is wide-sense-stationary and white. Any desirable noise spectra may be realized by an appropriate linear transformation ("shaping") of a lattice quantizer. As the dimension increases, the normalized second moment of the optimal lattice quantizer goes to 1/2/spl pi/e, and consequently the quantization noise approaches a white Gaussian process in the divergence sense. In entropy-coded dithered quantization, which can be modeled accurately as passing the source through an additive noise channel, this limit behavior implies that for large lattice dimension both the error and the bit rate approach the error and the information rate of an additive white Gaussian noise (AWGN) channel.

We consider encoding of a source with pre-specified second-order statistics, but otherwise arbitrary, by entropy-coded dithered (lattice) quantization (ECDQ) incorporating linear pre- and post-filters. In the design and analysis of this scheme we utilize the equivalent additive-noise channel model of the ECDQ. For Gaussian sources and a square error distortion measure, the coding performance of the pre/post filtered ECDQ approaches the rate-distortion function, as the dimension of the (optimal) lattice quantizer becomes large; actually, in this case the proposed coding scheme simulates the optimal forward channel realization of the rate-distortion function. For non-Gaussian sources and finite-dimensional lattice quantizers, the coding rate exceeds the rate-distortion function by at most the sum of two terms: the "information divergence of the source from Gaussianity" and the "information divergence of the quantization noise from Gaussianity". Additional bounds on the excess rate of the scheme from the rate-distortion function are also provided.

The minimum redundancy attainable by universal lossless codes for finite-state arbitrarily varying sources (AVS), and, in general, for an hierarchy of model classes, is investigated. In the AVS case, if the space of all possible underlying state sequences is partitioned into types, then the minimum universal coding redundancy can be essentially lower bounded by a quantity that decomposes into two terms, the first of which is the minimum redundancy within the type class (i.e., intra-type class redundancy), and the second is the minimum redundancy associated with a class of sources that can be thought of as "representatives" of the different types (i.e., inter-type class redundancy). This behavior can be generalized to universal coding for hierarchy of model classes, where each model class in the hierarchy has an increasing complexity. The lower bound for coding with respect to hierarchy of models is achievable by a Shannon code w.r.t an appropriate two-stage mixture, where the first stage mixture is over the sources in each class, and the second is a mixture over the indices of the model classes.

We investigate the application of EM algorithm to the classical problem of multiple target tracking (MTT) for a known number of targets. Conventional algorithms, have a computational complexity that depends exponentially on the targets' number, and usually divide the problem into a localization stage and a tracking stage. The new algorithms achieve a linear dependency, and integrate those hire stages. Three major optimization criteria are proposed, using deterministic and stochastic dynamic models for the targets.

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.>

An irreducible parameterization for a finite memory source is constructed in the form of a tree machine. A universal information source for the set of finite memory sources is constructed by a predictive modification of an earlier studied algorithm-Context. It is shown that this universal source incorporates any minimal data-generating tree machine in an asymptotically optimal manner in the following sense: the negative logarithm of the probability it assigns to any long typical sequence, generated by any tree machine, approaches that assigned by the tree machine at the best possible rate.>

The rate-distortion characteristics of a scheme for encoding continuous-time band limited stationary sources, with a prescribed band, is considered. In this coding procedure the input is sampled at Nyquist's rate or faster, the samples undergo dithered uniform or lattice quantization, using subtractive dither, and the quantizer output is entropy-coded, The rate-distortion performance, and the tradeoff between the sampling rate and the quantization accuracy is investigated, utilizing the observation that the coding scheme is equivalent to an additive noise channel. It is shown that the mean-square error of the scheme is fixed as long as the product of the sampling period and the quantizer second moment is kept constant, while for a fixed distortion the coding rate generally increases when the sampling rate exceeds the Nyquist rate. Finally, as the lattice quantizer dimension becomes large, the equivalent additive noise channel of the scheme tends to be white Gaussian, and both the rate and the distortion performance become invariant to the sampling rate.>

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 w.r.t this class, both in the minimax sense and in the Bayesian (maximin) sense. The authors main contribution is a relatively simple proof that the 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) lower bound for parametric families. Finally, the authors demonstrate the applicability of this result in several examples.>

Presents several results regarding the properties of a random vector, uniformly distributed over a lattice cell. This random vector is the quantization noise associated with dithered lattice quantization, and at high resolution it is the noise generated in regular lattice quantization of "smooth" sources. The authors find that the noise associated with the optimal lattice quantizers is wide-sense stationary and white. Any desirable noise spectra may be realized by an appropriate linear transformation ("shaping") of a lattice quantizer. As the dimension increases, the normalized second moment of the optimal lattice quantizer goes to 1/2/spl pi/e, and consequently the quantization noise approaches a white Gaussian process. Actually, in entropy coded dithered quantization where the quantization procedure can be modeled as an additive noise channel, this limit behavior implies that both the asymptotic MSE distortion and the mutual-information between input and output of the quantization channel, approaches the MSE and the mutual-information between input and output of an additive white Gaussian noise (AWGN) channel.>

Active noise cancellation is an approach to noise reduction in which a secondary noise source that destructively interferes with the unwanted noise is introduced. In general, active noise cancellation systems rely on multiple sensors to measure the unwanted noise field and the effect of the cancellation. This paper develops an approach that utilizes a single sensor. The noise field is modeled as a stochastic process, and a time-adaptive algorithm is used to adaptively estimate the parameters of the process. Based on these parameter estimates, a canceling signal is generated. In general, the transfer function characteristics from the canceling source to the error sensor need to be accounted for. If these can be accurately measured in advance and are invertible except for the propagation delay between the source and sensor, then the essential problem becomes one of predicting future values of the noise field. The algorithm developed is evaluated with both artificially generated noise and with recordings of aircraft noise.>

Quadtree decomposition is a simple technique used to obtain an image representation at different resolution levels. This representation can be useful for a variety of image processing and image compression algorithms. This paper presents a simple way to get better compression performances (in MSE sense) via quadtree decomposition, by using near to optimal choice of the threshold for quadtree decomposition; and bit allocation procedure based on the equations derived from rate-distortion theory. The rate-distortion performance of the improved algorithm is calculated for some Gaussian field, and it is examined vie simulation over benchmark gray-level images. In both these cases, significant improvement in the compression performances is shown.

The relation between the entropy of a discrete random variable and the minimum attainable probability of error made in guessing its value is examined. While Fano's inequality provides a tight lower bound on the error probability in terms of the entropy, the present authors derive a converse result/spl mdash/a tight upper bound on the minimal error probability in terms of the entropy. Both bounds are sharp, and can draw a relation, as well, between the error probability for the maximum a posteriori (MAP) rule, and the conditional entropy (equivocation), which is a useful uncertainty measure in several applications. Combining this relation and the classical channel coding theorem, the authors present a channel coding theorem for the equivocation which, unlike the channel coding theorem for error probability, is meaningful at all rates. This theorem is proved directly for DMCs, and from this proof it is further concluded that for R/spl ges/C the equivocation achieves its minimal value of R/spl minus/C at the rate of n/sup 1/spl sol/2/ where n is the block length.>

The problem of sequential probability assignment for individual sequences is investigated. The authors compare the probabilities assigned by any sequential scheme to the performance of the best "batch" scheme (model) in some class. For the class of finite-state schemes and other related families, they derive a deterministic performance bound, analogous to the classical (probabilistic) minimum description length (MDL) bound. It holds for "most" sequences, similarly to the probabilistic setting, where the bound holds for "most" sources in a class. It is shown that the bound can be attained both pointwise and sequentially for any model family in the reference class and without any prior knowledge of its order. This is achieved by a universal scheme based on a mixing approach. The bound and its sequential achievability establish a completely deterministic significance to the concept of predictive MDL.>

Identification of an unknown system and recovery of the input signals from observations of the outputs of an unknown multiple-input, multiple-output linear system are considered. Attention is focused on the two-channel case, in which the outputs of a 2*2 linear time invariant system are observed. The approach consists of reconstructing the input signals by assuming that they are statistically uncorrelated and imposing this constraint on the signal estimates. In order to restrict the set of solutions, additional information on the true signal generation and/or on the form of the coupling systems is incorporated. Specific algorithms are developed and tested. As a special case, these algorithms suggest a potentially interesting modification of Widrow's (1975) least-squares method for noise cancellation, where the reference signal contains a component of the desired signal.>

Sequential decision algorithms are investigated in relation to a family of additive performance criteria for individual data sequences. Simple universal sequential schemes are known, under certain conditions, to approach optimality uniformly as fast as n/sup -1/ log n, where n is the sample size. For the case of finite-alphabet observations, the class of schemes that can be implemented by finite-state machines (FSMs) is studied. It is shown that Markovian machines with sufficiently long memory exist, which are asymptotically nearly as good as any given deterministic or randomized FSM for the purpose of sequential decision. For the continuous-valued observation case, a useful class of parametric schemes is discussed with special attention to the recursive least squares algorithm.>

Universal predictions of the next outcome of a binary sequence drawn from a Markov source with unknown parameters is considered. For a given source, the predictability is defined as the least attainable expected fraction of prediction errors. A lower bound is derived on the maximum rate at which the predictability is asymptotically approached uniformly over all sources in the Markov class. This bound is achieved by a simple majority predictor. For Bernoulli sources, bounds on the large deviations performance are investigated. A lower bound is derived for the probability that the fraction of errors will exceed the predictability by a prescribed amount Delta >0. This bound is achieved by the same predictor if Delta is sufficiently small.>

The authors prove the following generalization of the entropy power inequality: h(ax)>or=h(Ax) where h(.) denotes (joint-) differential-entropy x=x/sub 1/...x/sub n/, is a random vector with independent components, x=x...x/sub n/, is a Gaussian vector with independent components such that h(x/sub i/)=h(x/sub i/), i=1...n, and A is any matrix. This generalization of the entropy-power inequality is applied to show that a non-Gaussian vector with independent components becomes "closer" to Gaussianity after a linear transformation, where the distance to Gaussianity is measured by the information divergence. Another application is a lower bound, greater than zero, for the mutual-information between nonoverlapping spectral components of a non-Gaussian white process. They also describe a dual generalization of the Fisher information inequality.>

Sequential learning and decision algorithms are investigated, with various application areas, under a family of additive loss functions for individual data sequences. Simple universal sequential schemes are known, under certain conditions, to approach optimality uniformly as fast as n-1logn, where n is the sample size. For the case of finite-alphabet observations, the class of schemes that can be implemented by finite-state machines (FSM's), is studied. It is shown that Markovian machines with sufficiently long memory exist that are asymptotically nearly as good as any given FSM (deterministic or randomized) for the purpose of sequential decision. For the continuous-valued observation case, a useful class of parametric schemes is discussed with special attention to the recursive least squares (RLS) algorithm.

The authors analyze a scheme for encoding continuous time band-limited signals in which the input is sampled at Nyquist's rate or faster, the samples undergo dithered uniform or lattice quantization and the quantizer output is entropy coded. This analysis leads to explicit expressions for the trade-off between sampling rate and quantization accuracy. Also, they provide expression for the scheme's redundancy (i.e. its excess rate over the rate distortion function) in terms of the both the sampling rate and quantization resolution parameters.>

The authors develop an approach to active noise cancellation using a single microphone. The noise field is modelled as a stochastic process, and a time-adaptive algorithm based on a modification of the block-estimate-maximize (EM) algorithm is used to adaptively estimate the parameters of this process. Based on these parameter estimates a canceling signal is generated. The algorithm developed is evaluated with recordings of aircraft noise, and has been implemented in real time with a single AT&T DSP32C chip.>

A bound on the probability that the length of any source code will be shorter than the self information by gamma bits is easily obtained using a Chebyshev-type argument. From this bound, one can establish the competitive optimality of the self information and of the Shannon-Fano code (up to one bit). In general, however, the Huffman code cannot be examined using this technique. Nevertheless, in the present work, the competitive optimality (up to one bit) of the Huffman code for general sources is also established using a different technique.>

The problem of predicting the next outcome of an individual binary sequence using finite memory is considered. The finite-state predictability of an infinite sequence is defined as the minimum fraction of prediction errors that can be made by any finite-state (FS) predictor. It is proven that this FS predictability can be achieved by universal sequential prediction schemes. An efficient prediction procedure based on the incremental parsing procedure of the Lempel-Ziv data compression algorithm is shown to achieve asymptotically the FS predictability. Some relations between compressibility and predictability are discussed, and the predictability is proposed as an additional measure of the complexity of a sequence.>

Uniform quantization with dither, or lattice quantization with dither in the vector case, followed by a universal lossless source encoder (entropy coder), is a simple procedure for universal coding with distortion of a source that may take continuously many values. The rate of this universal coding scheme is examined, and a general expression is derived for it. An upper bound for the redundancy of this scheme, defined as the difference between its rate and the minimal possible rate, given by the rate distortion function of the source, is derived. This bound holds for all distortion levels. Furthermore, a composite upper bound on the redundancy as a function of the quantizer resolution that leads to a tighter bound in the high rate (low distortion) case is presented.>

Sequential gambling schemes in which the amount wagered on the future outcome is determined by a finite state (FS) machine are defined and analyzed. It is assumed that the FS machine determines the fraction of the capital wagered at each time instance i on the outcome at the next time instance, i+1, and that wagers are paid at even odds. The maximal capital achieved by any FS machine is found and its dependence on an empirical entropy measure, H/sup FS/(x), defined as the finite state complexity of x, is shown. A specific gambling scheme is then proposed based on the Lempel-Ziv method for universal compression. The capital gained by this method is found and it is observed that, asymptotically, its exponential growth rate dominates the experimental growth rate achieved by gambling using any FS machine. Furthermore, this specific scheme suggests a class of gambling methods, based on a class of variable-to-variable length lossless compression methods, in which the capital is doubled for every bit compressed. These results emphasize the relation between gambling and data compression.>

The authors propose a stabilized method for limited angle reconstruction. The algorithm provides a framework that makes it possible to incorporate prior information and to account for the noise; this framework is the reason for the method's stability. The method entails the following steps: a space of reconstruction solutions is generated, either analytically or by Monte Carlo simulation; representatives of the solutions are found by clustering the solution space; and these representatives are scored, using the a priori information, to define the final solution. Simulation results are presented for a simple 1-D deconvolution problem.>

The authors use methods of stochastic approximation to convert iterative algorithms for maximizing the Kullback-Liebler information measure (1959) into sequential algorithms. Special attention is given to the case of incomplete data, and a variety of algorithms are presented to deal with situations of that kind. The authors consider the application of these algorithms to the identification of finite-impulse-response (FIR) systems.>

A class of sequential and adaptive algorithms for parameter estimation are presented that are based on the iterative estimate-maximize (EM) algorithm. In some cases sequential algorithms are derived that perform an exact EM step in each recursion; an example for these cases is given for the linear least-squares problem. In general, however, it is necessary to approximate the EM iteration in order to develop sequential algorithms. The application of this class of algorithms to the two-microphone noise cancellation problem is described.>

Single microphone speech enhancement systems have typically shown limited performance, while multiple microphone systems based on a least-squares error criterion have shown encouraging results in some contexts. In this paper we formulate a new approach to multiple microphone speech enhancement. Specifically, we formulate a maximum likelihood (ML) problem for estimating the parameters needed for canceling the noise in a two microphone speech enhancement system. This ML problem is solved via the iterative EM (Estimate-Maximize) technique. The resulting algorithm shows encouraging results when applied to the speech enhancement problem.

A computationally efficient scheme for multi-path and multiple source location estimation, based on the EM algorithm is presented. The proposed scheme is optimal in the sense that it converges iteratively to the exact Maximum Likelihood of all source location parameters simultaneously.

The Maximum Entropy (ME) and Maximum Likelihood (ML) criteria are the bases for two approaches to statistical inference problems. A new criterion, called the Minimum Description Length (MDL), has been recently introduced. This criterion generalizes the ML method so it can be applied to more general situations, e.g., when the number of parameters is unknown. It is shown that ME is also a special case of the MDL criterion; maximizing the entropy subject to some constraints on the underlying probability function is identical to minimizing the code length required to represent all possible i.i.d, realizations of the random variable such that the sample frequencies (or histogram) satisfy those given constraints.

We developed an algorithm for multiple source localization based on the Estimate-Maximize (EM) method. The EM method is an iterative algorithm that converges to the Maximum Likelihood (ML) estimate of the unknown parameters by exploiting the stochastic syctem under consideration. In our case the algorithm will converge to the exact ML estimates of the various sources location parameters, where each iteration increases the likelihood of those parameters.