Search

We begin by presenting a simple lossy compressor operating at near-zero rate: The encoder merely describes the indices of the few maximal source components, while the decoder’s reconstruction is a natural estimate of the source components based on this information. This scheme turns out to be near optimal for the memoryless Gaussian source in the sense of achieving the zero-rate slope of its distortion-rate function. Motivated by this finding, we then propose a scheme comprised of iterating the above lossy compressor on an appropriately transformed version of the difference between the source and its reconstruction from the previous iteration. The proposed scheme achieves the rate distortion function of the Gaussian memoryless source (under squared error distortion) when employed on any finite-variance ergodic source. It further possesses desirable properties, and we, respectively, refer to as infinitesimal successive refinability, ratelessness, and complete separability. Its storage and computation requirements are of order no more than (n^2)/(\log ^\beta n) per source symbol for $\beta >0$ at both the encoder and the decoder. Though the details of its derivation, construction, and analysis differ considerably, we discuss similarities between the proposed scheme and the recently introduced Sparse Regression Codes of Venkataramanan et al. [ABSTRACT FROM AUTHOR]

We consider mean squared estimation with lookahead of a continuous-time signal corrupted by additive white Gaussian noise. We show that the mutual information rate function, i.e., the mutual information rate as function of the signal-to-noise ratio (SNR), does not, in general, determine the minimum mean squared error (MMSE) with fixed finite lookahead, in contrast to the special cases with 0 and infinite lookahead (filtering and smoothing errors), respectively, which were previously established in the literature. Further, we investigate the simple class of continuous-time stationary Gauss-Markov processes (Ornstein-Uhlenbeck processes) as channel inputs, and explicitly characterize the behavior of the minimum mean squared error (MMSE) with finite lookahead and signal-to-noise ratio (SNR). We extend our results to mixtures of Ornstein–Uhlenbeck processes, and use the insight gained to present lower and upper bounds on the MMSE with lookahead for a class of stationary Gaussian input processes, whose spectrum can be expressed as a mixture of Ornstein–Uhlenbeck spectra. [ABSTRACT FROM AUTHOR]

Contributions: We developed a new lossless compression method for WIG data, named smallWig, offering the best known compression rates for RNA-seq data and featuring random access functionalities that enable visualization, summary statistics analysis and fast queries from the compressed files. Our approach results in order of magnitude improvements compared with bigWig and ensures compression rates only a fraction of those produced by cWig. The key features of the smallWig algorithm are statistical data analysis and a combination of source coding methods that ensure high flexibility and make the algorithm suitable for different applications. Furthermore, for general-purpose file compression, the compression rate of smallWig approaches the empirical entropy of the tested WIG data. For compression with random query features, smallWig uses a simple block-based compression scheme that introduces only a minor overhead in the compression rate. For archival or storage space-sensitive applications, the method relies on context mixing techniques that lead to further improvements of the compression rate. Implementations of smallWig can be executed in parallel on different sets of chromosomes using multiple processors, thereby enabling desirable scaling for future transcriptome Big Data platforms. Motivation: The development of next-generation sequencing technologies has led to a dramatic decrease in the cost of DNA/RNA sequencing and expression profiling. RNA-seq has emerged as an important and inexpensive technology that provides information about whole transcriptomes of various species and organisms, as well as different organs and cellular communities. The vast volume of data generated by RNA-seq experiments has significantly increased data storage costs and communication bandwidth requirements. Current compression tools for RNA-seq data such as bigWig and cWig either use general-purpose compressors (gzip) or suboptimal compression schemes that leave significant room for improvement. To substantiate this claim, we performed a statistical analysis of expression data in different transform domains and developed accompanying entropy coding methods that bridge the gap between theoretical and practical WIG file compression rates. Results: We tested different variants of the smallWig compression algorithm on a number of integerand real- (floating point) valued RNA-seq WIG files generated by the ENCODE project. The results reveal that, on average, smallWig offers 18-fold compression rate improvements, up to 2.5-fold compression time improvements, and 1.5-fold decompression time improvements when compared with bigWig. On the tested files, thememory usage of the algorithm never exceeded 90 KB. When more elaborate context mixing compressors were used within smallWig, the obtained compression rates were as much as 23 times better than those of bigWig. For smallWig used in the random query mode, which also supports retrieval of the summary statistics, an overhead in the compression rate of roughly 3-17% was introduced depending on the chosen system parameters. An increase in encoding and decoding time of 30% and 55% represents an additional performance loss caused by enabling random data access. We also implemented smallWig using multi-processor programming. This parallelization feature decreases the encoding delay 2-3.4 times compared with that of a single-processor implementation, with the number of processors used ranging from 2 to 8; in the same parameter regime, the decoding delay decreased 2-5.2 times. [ABSTRACT FROM AUTHOR]

We investigate the problem of continuous-time causal estimation under a minimax criterion. Let \(X^T = \{X_t,0\leq t\leq T\}\) be governed by the probability law \(P_{\theta }\) from a class of possible laws indexed by \(\theta \in \Lambda \) , and \(Y^T\) be the noise corrupted observations of \(X^T\) available to the estimator. We characterize the estimator minimizing the worst case regret, where regret is the difference between the causal estimation loss of the estimator and that of the optimum estimator. One of the main contributions of this paper is characterizing the minimax estimator, showing that it is in fact a Bayesian estimator. We then relate minimax regret to the channel capacity when the channel is either Gaussian or Poisson. In this case, we characterize the minimax regret and the minimax estimator more explicitly. If we further assume that the uncertainty set consists of deterministic signals, the worst case regret is exactly equal to the corresponding channel capacity, namely the maximal mutual information attainable across the channel among all possible distributions on the uncertainty set of signals. The corresponding minimax estimator is the Bayesian estimator assuming the capacity-achieving prior. Using this relation, we also show that the capacity achieving prior coincides with the least favorable input. In addition, we show that this minimax estimator is not only minimizing the worst case regret, but also essentially minimizing regret for most of the other sources in the uncertainty set. We present a couple of examples for the construction of a minimax filter via an approximation of the associated capacity achieving distribution. [ABSTRACT FROM PUBLISHER]

Consider a binary modulo-additive noise channel with noiseless feedback. When the noise is a stationary and ergodic process \bf Z , the capacity is 1-\BBH(\bf Z) ( \BBH(\cdot) denoting the entropy rate). It is shown analogously that when the noise is a deterministic sequence z^{\infty} , the capacity under finite-state encoding and decoding is 1-\overline{\rho}(z^{\infty}) , where \overline\rho(\cdot) is Lempel and Ziv's finite-state compressibility. This quantity, termed the porosity \underline\sigma(\cdot) of the channel, holds as the fundamental limit to communication—even when the encoder is designed with knowledge of the noise sequence. A sequence of schemes are presented that universally achieve porosity for any noise sequence. These results, both converse and achievability, may be interpreted as a channel-coding counterpart to Ziv and Lempel's work in universal source coding, and also as an extension to existing work on communicating across modulo-additive channels with an individual noise sequence. In addition, a potentially more practical architecture is suggested that draws a connection with finite-state predictability, as introduced by Feder, Gutman, and Merhav. [ABSTRACT FROM PUBLISHER]

We consider the classical two-encoder multiterminal source coding problem where distortion is measured under logarithmic loss. We provide a single-letter description of the achievable rate distortion region for all discrete memoryless sources with finite alphabets. By doing so, we also give the rate distortion region for the m-encoder CEO problem (also under logarithmic loss). Several applications and examples are given. [ABSTRACT FROM PUBLISHER]

Summary: The number of human genomes that have been sequenced completely for different individuals has increased rapidly in recent years. Storing and transferring complete genomes between computers for the purpose of applying various applications and analysis tools will soon become a major hurdle, hindering the analysis phase. Therefore, there is a growing need to compress these data efficiently. Here, we describe a technique to compress human genomes based on entropy coding, using a reference genome and known Single Nucleotide Polymorphisms (SNPs). Furthermore, we explore several intrinsic features of genomes and information in other genomic databases to further improve the compression attained. Using these methods, we compress James Watson’s genome to 2.5 megabytes (MB), improving on recent work by 37%. Similar compression is obtained for most genomes available from the 1000 Genomes Project. Our biologically inspired techniques promise even greater gains for genomes of lower organisms and for human genomes as more genomic data become available.Availability: Code is available at sourceforge.net/projects/genomezip/Contact: golan.yona@stanford.eduSupplementary information: Supplementary data are available at Bioinformatics online. [ABSTRACT FROM AUTHOR]

A real-time coding system with lookahead consists of a memoryless source, a memoryless channel, an encoder, which encodes the source symbols sequentially with knowledge of future source symbols up to a fixed finite lookahead d, with or without feedback of the past channel output symbols and a decoder, which sequentially constructs the source symbols using the channel output. The objective is to minimize the expected per-symbol distortion. For a fixed finite lookahead d\geq 1, we invoke the theory of controlled Markov chains to obtain an average cost optimality equation (ACOE), the solution of which, denoted by D(d), is the minimum expected per-symbol distortion. With increasing d, D(d) bridges the gap between causal encoding, d=0, where symbol-by-symbol encoding–decoding is optimal and the infinite lookahead case, d=\infty, where Shannon Theoretic arguments show that separation is optimal. We extend the analysis to a system with finite-state decoders, with or without noise-free feedback. For a Bernoulli source and binary symmetric channel, under Hamming loss, we compute the optimal distortion for various source and channel parameters, and thus obtain computable bounds on D(d). We also identify regions of source and channel parameters where symbol-by-symbol encoding–decoding is suboptimal. Finally, we demonstrate the wide applicability of our approach by applying it in additional coding scenarios, such as the case where the sequential decoder can take cost-constrained actions affecting the quality or availability of side information about the source. [ABSTRACT FROM PUBLISHER]

A notion of directed information between two continuous-time processes is proposed. A key component in the definition is taking an infimum over all possible partitions of the time interval, which plays a role no less significant than the supremum over “space” partitions inherent in the definition of mutual information. Properties and operational interpretations in estimation and communication are then established for the proposed notion of directed information. For the continuous-time additive white Gaussian noise channel, it is shown that Duncan's classical relationship between causal estimation error and mutual information continues to hold in the presence of feedback upon replacing mutual information by directed information. A parallel result is established for the Poisson channel. The utility of this relationship is demonstrated in computing the directed information rate between the input and output processes of a continuous-time Poisson channel with feedback, where the channel input process is constrained to be constant between events at the channel output. Finally, the capacity of a wide class of continuous-time channels with feedback is established via directed information, characterizing the fundamental limit on reliable communication. [ABSTRACT FROM AUTHOR]

Many of the classical and recent relations between information and estimation in the presence of Gaussian noise can be viewed as identities between expectations of random quantities. These include the relationship between mutual information and minimum mean square error (I-MMSE) of Guo ; the relative entropy and mismatched estimation relationship of Verdú; the relationship between causal estimation and mutual information of Duncan, and its extension to the presence of feedback by Kadota ; the relationship between causal and non-casual estimation of Guo , and its mismatched version of Weissman. We dispense with the expectations and explore the nature of the pointwise relations between the respective random quantities. The pointwise relations that we find are as succinctly stated as—and give considerable insight into—the original expectation identities. As an illustration of our results, consider Duncan's 1970 discovery that the mutual information is equal to the causal MMSE in the additive white Gaussian noise channel, which can equivalently be expressed saying that the difference between the input–output information density and half the causal estimation error is a zero-mean random variable (regardless of the distribution of the channel input). We characterize this random variable explicitly, rather than merely its expectation. Classical estimation and information theoretic quantities emerge with new and surprising roles. For example, the variance of this random variable turns out to be given by the causal MMSE (which, in turn, is equal to twice the mutual information by Duncan's result). [ABSTRACT FROM PUBLISHER]

We propose an approach to lossy compression of finite-alphabet sources that utilizes Markov chain Monte Carlo (MCMC) and simulated annealing methods. The idea is to define an energy function over the space of reconstruction sequences. The energy of a candidate reconstruction sequence is defined such that it incorporates its distortion relative to the source sequence, its compressibility, and the point sought on the rate-distortion curve. The proposed algorithm samples from the Boltzmann distribution associated with this energy function using the "heat-bath" algorithm. The complexity of each iteration is independent of the sequence length and is only linearly dependent on a certain context parameter, which grows sub-logarithmically with the sequence length. We show that the proposed algorithm achieves optimum rate-distortion performance in the limits of large number of iterations, and sequence length, when employed on any stationary ergodic source. Inspired by the proposed block-coding algorithm, we also propose an algorithm for constructing sliding-block (SB) codes using similar ideas. [ABSTRACT FROM AUTHOR]

We consider the cascade and triangular rate-distortion problem where side information is known to the source encoder and to the first user but not to the second user. We characterize the rate-distortion region for these problems, as well as some of their extensions. For the quadratic Gaussian case, we show that it is sufficient to consider jointly Gaussian distributions, which leads to an explicit solution. [ABSTRACT FROM PUBLISHER]

It has been established in the literature, in various theoretical and asymptotic senses, that universal lossy compression followed by some simple postprocessing results in universal denoising, for the setting of a stationary ergodic source corrupted by additive white noise. However, this interesting theoretical result has not yet been tested in practice in denoising simulated or real data. In this paper, we employ a recently developed MCMC-based universal lossy compressor to build a universal compression-based denoising algorithm. We show that applying this iterative lossy compression algorithm with appropriately chosen distortion measure and distortion level, followed by a simple derandomization operation, results in a family of denoisers that compares favorably (both theoretically and in practice) with other MCMC-based schemes, and with the discrete universal denoiser DUDE. [ABSTRACT FROM AUTHOR]

Let X be a nonnegative random variable and let the conditional distribution of a random variable Y, given X, be Poisson (\gamma\cdot X), for a parameter \gamma\geq 0. We identify a natural loss function such that: 1) the derivative of the mutual information between X and Y with respect to \gamma is equal to the minimum mean loss in estimating X based on Y, regardless of the distribution of X; 2) when X\sim P is estimated based on Y by a mismatched estimator that would have minimized the expected loss had X\sim Q, the integral over all values of \gamma of the excess mean loss is equal to the relative entropy between P and Q. For a continuous time setting where X is a nonnegative stochastic process and the conditional law of Y, given X, is that of a non-homogeneous Poisson process with intensity function \gamma\cdot X, under the same loss function: 1) the minimum mean loss in causal filtering when \gamma=\gamma0 is equal to the expected value of the minimum mean loss in noncausal filtering (smoothing) achieved with a channel whose parameter \gamma is uniformly distributed between 0 and \gamma0. Bridging the two quantities is the mutual information between X and Y; 2) this relationship between the mean losses in causal and noncausal filtering holds also in the case where the filters employed are mismatched, i.e., optimized assuming a law on X which is not the true one. Bridging the two quantities in this case is the sum of the mutual information and the relative entropy between the true and the mismatched distribution of Y. Thus, relative entropy quantifies the excess estimation loss due to mismatch in this setting. These results are parallel to those recently found for the Gaussian channel: the I-MMSE relationship of Guo , the relative entropy and mismatched estimation relationship of Verdú, and the relationship between causal and noncasual mismatched estimation of Weissman. [ABSTRACT FROM AUTHOR]

We study source coding in the presence of side information, when the system can take actions that affect the availability, quality, or nature of the side information. We begin by extending the Wyner-Ziv problem of source coding with decoder side information to the case where the decoder is allowed to choose actions affecting the side information. We then consider the setting where actions are taken by the encoder, based on its observation of the source. Actions may have costs that are commensurate with the quality of the side information they yield, and an overall per-symbol cost constraint may be imposed. We characterize the achievable tradeoffs between rate, distortion, and cost in some of these problem settings. Among our findings is the fact that even in the absence of a cost constraint, greedily choosing the action associated with the “best” side information is, in general, suboptimal. A few examples are worked out. [ABSTRACT FROM AUTHOR]

We consider channels with action-dependent states: Given the message to be communicated, the transmitter chooses an action sequence that affects the formation of the channel states, and then creates the channel input sequence based on the state sequence. We characterize the capacity of such a channel both for the case where the channel inputs are allowed to depend noncausally on the state sequence and the case where they are restricted to causal dependence. Our setting covers previously considered scenarios involving transmission over channels with states known at the encoder, as well as various new coding scenarios for channels with a “rewrite” option that may arise naturally in storage for computer memories with defects or in magnetic recoding. A few examples are worked out in detail. [ABSTRACT FROM PUBLISHER]

A continuous-time finite-power process with distribution P is observed through an AWGN channel, at a given signal-to-noise ratio (SNR), and is estimated by an estimator that would have minimized the mean-square error if the process had distribution Q. We show that the causal filtering mean-square error (MSE) achieved at SNR level \ssr snr is equal to the average value of the noncausal (smoothing) MSE achieved with a channel whose SNR is chosen uniformly distributed between 0 and \ssr snr. Emerging as the bridge for equating these two quantities are mutual information and relative entropy. Our result generalizes that of Guo, Shamai, and Verdú (2005) from the nonmismatched case, where P=Q, to general P and Q. Among our intermediate results is an extension of Duncan's theorem, that relates mutual information and causal MMSE, to the case of mismatched estimation. Some further extensions and implications are discussed. Key to our findings is the recent result of Verdú on mismatched estimation and relative entropy. [ABSTRACT FROM PUBLISHER]

We introduce S-DUDE, a new algorithm for denoising discrete memoryless channel (DMC)-corrupted data. The algorithm, which generalizes the recently introduced DUDE (Discrete Universal DEnoiser), aims to compete with a genie that has access, in addition to the noisy data, also to the underlying clean data, and that can choose to switch, up to m times, between sliding-window denoisers in a way that minimizes the overall loss. When the underlying data form an individual sequence, we show that the S-DUDE performs essentially as well as this genie, provided that m is sublinear in the size of the data. When the clean data are emitted by a piecewise stationary process, we show that the S-DUDE achieves the optimum distribution-dependent performance, provided that the same sublinearity condition is imposed on the number of switches. To further substantiate the universal optimality of the S-DUDE, we show that when the number of switches is allowed to grow linearly with the size of the data, any (sequence of) scheme(s) fails to compete in the above sense. Using dynamic programming, we derive an efficient implementation of the S-DUDE, which has complexity (time and memory) growing linearly with the data size and the number of switches m. Preliminary experimental results are presented, suggesting that S-DUDE has the capacity to improve on the performance attained by the original DUDE in applications where the nature of the data abruptly changes in time (or space), as is often the case in practice. [ABSTRACT FROM AUTHOR]

The capacity region of the finite-state multiple-access channel (FS-MAC) with feedback that may be an arbitrary time-invariant function of the channel output samples is considered. We characterize both an inner and an outer bound for this region, using Massey's directed information. These bounds are shown to coincide, and hence yield the capacity region, of indecomposable FS-MACs without feedback and of stationary and indecomposable FS-MACs with feedback, where the state process is not affected by the inputs. Though "multiletter" in general, our results yield explicit conclusions when applied to specific scenarios of interest. For example, our results allow us to do the following. * Identify a large class of FS-MACs, that includes the additive mod2 noise MAC where the noise may have memory, for which feedback does not enlarge the capacity region. * Deduce that, for a general FS-MAC with states that are not affected by the input, if the capacity (region) without feedback is zero, then so is the capacity (region) with feedback. * Deduce that the capacity region of a MAC that can be decomposed into a "multiplexer" concatenated by a point-to-point channel (with, without, or with partial feedback), the capacity region is given by ¿m Rm ¿ C, where C is the capacity of the point to point channel and m. indexes the encoders. Moreover, we show that for this family of channels source-channel coding separation holds. [ABSTRACT FROM AUTHOR]

We revisit the problem of denoising a discrete-time, continuous-amplitude signal corrupted by a known memoryless channel. By modifying our earlier approach to the problem, we obtain a scheme that is much more tractable than the original one and at the same time retains the universal optimality properties. The universality refers to the fact that the proposed denoiser asymptotically (with increasing block length of the data) achieves the performance of an optimum denoiser that has full knowledge of the distribution of a source generating the underlying clean sequence; the only restriction being that the distribution is stationary. The optimality, in a sense we will make precise, of the denoiser also holds in the case where the underlying clean sequence is unknown and deterministic and the only source of randomness is in the noise. The schemes involve a simple preprocessing step of quantizing the noisy symbols to generate quantized contexts. The quantized context value corresponding to each sequence component is then used to partition the unquantized symbols into subsequences. A universal symbol-by-symbol denoiser (for unquantized sequences) is then separately employed on each of the subsequences. We identify a rate at which the context length and quantization resolution should be increased so that the resulting scheme is universal. The proposed family of schemes is computationally attractive with an upper bound on complexity which is independent of the context length and the quantization resolution. Initial experimentation seems to indicate that these schemes are not only superior from a computational viewpoint, but also achieve better denoising in practice. [ABSTRACT FROM AUTHOR]

We consider the problem of causal estimation, i.e., filtering, of a real-valued signal corrupted by zero mean, time-independent, real-valued additive noise, under the mean-squared error (MSE) criterion. We build a universal filter whose per-symbol squared error, for every bounded underlying signal, is essentially as small as that of the best finite-duration impulse response (FIR) filter of a given order. We do not assume a stochastic mechanism generating the underlying signal, and assume only that the variance of the noise is known to the filter. The regret of the expected MSE of our scheme is shown to decay as O(log n/n), where it is the length of the signal. Moreover, we present a stronger concentration result which guarantees the performance of our scheme not only in expectation, but also with high probability. Our result implies a conventional stochastic setting result, i.e., when the underlying signal is a stationary process, our filter achieves the performance of the optimal FIR filter. We back our theoretical findings with several experiments showcasing the potential merits of our universal filter in practice. Our analysis combines tools from the problems of universal filtering and competitive on-line regression. [ABSTRACT FROM AUTHOR]

We consider capacity of discrete-time channels with feedback for the general case where the feedback is a time-invariant deterministic function of the output samples. Under the assumption that the channel states take values in a finite alphabet, we find a sequence of achievable rates and a sequence of upper bounds on the capacity. The achievable rates and the upper bounds are computable for any N, and the limits of the sequences exist. We show that when the probability of the initial state is positive for all the channel states, then the capacity is the limit of the achievable-rate sequence. We further show that when the channel is stationary, indecomposable, and has no intersymbol interference (ISI), its capacity is given by the limit of the maximum of the (normalized) directed information between the input XN and the output YN, i.e., "Multiple line equation(s) cannot be represented in ASCII text " where the maximization is taken over the causal conditioning probability Q(xN∥zN-1) defined in this paper. The main idea for obtaining the results is to add causality into Gallager's results on finite state channels. The capacity results are used to show that the source-channel separation theorem holds for time-invariant determinist feedback, and if the state of the channel is known both at the encoder and the decoder, then feedback does not increase capacity. [ABSTRACT FROM AUTHOR]

We consider the problem of reconstructing a discrete-time signal (sequence) with continuous-valued components corrupted by a known memoryless channel. When performance is measured using a per-symbol loss function satisfying mild regularity conditions, we develop a sequence of denoisers that, although independent of the distribution of the underlying "clean" sequence, is universally optimal in the limit of large sequence length. This sequence of denoisers is universal in the sense of performing as well as any sliding-window denoising scheme which may be optimized for the underlying clean signal. Our results are initially developed in a "semi-stochastic" setting, where the noiseless signal is an unknown individual sequence, and the only source of randomness is due to the channel noise. It is subsequently shown that in the fully stochastic setting, where the noiseless sequence is a stationary stochastic process, our schemes universally attain optimum performance. The proposed schemes draw from nonparametric density estimation techniques and are practically implementable. We demonstrate efficacy of the proposed schemes in denoising Gray-scale images in the conventional additive white Gaussian noise (AWGN) setting, with additional promising results for less conventional noise distributions. [ABSTRACT FROM AUTHOR]

We consider the problem of sequential decision making for random fields corrupted by noise. In this scenario, the decision maker observes a noisy version of the data, yet judged with respect to the clean data. In particular, we first consider the problem of scanning and sequentially filtering noisy random fields. In this case, the sequential filter is given the freedom to choose the path over which it traverses the random field (e.g., noisy image or video sequence), thus it is natural to ask what is the best achievable performance and how sensitive this performance is to the choice of the scan. We formally define the problem of scanning and filtering, derive a bound on the best achievable performance, and quantify the excess loss occurring when nonoptimal scanners are used, compared to optimal scanning and filtering. We then discuss the problem of scanning and prediction for noisy random fields. This setting is a natural model for applications such as restoration and coding of noisy images. We formally define the problem of scanning and prediction of a noisy multidimensional array and relate the optimal performance to the clean scandictability defined by Merhav and Weissman. Moreover, bounds on the excess loss due to suboptimal scans are derived, and a universal prediction algorithm is suggested. This paper is the second part of a two-part paper. The first paper dealt with scanning and sequential decision making on noiseless data arrays. [ABSTRACT FROM AUTHOR]

We consider sources and channels with memory observed through erasure channels. In particular, we examine the impact of sporadic erasures on the fundamental limits of lossless data compression, lossy data compression, channel coding, and denoising. We define the erasure entropy of a collection of random variables as the sum of entropies of the individual variables conditioned on all the rest. The erasure entropy measures the information content carried by each symbol knowing its context. The erasure entropy rate is shown to be the minimal amount of bits per erasure required to recover the lost information in the limit of small erasure probability. When we allow recovery of the erased symbols within a prescribed degree of distortion, the fundamental tradeoff is described by the erasure rate-distortion function which we characterize. We show that in the regime of sporadic erasures, knowledge at the encoder of the erasure locations does not lower the rate required to achieve a given distortion. When no additional encoded information is available, the erased information is reconstructed solely on the basis of its context by a denoiser. Connections between erasure entropy and discrete denoising are developed. The decrease of the capacity of channels with memory due to sporadic memoryless erasures is also characterized in wide generality. [ABSTRACT FROM AUTHOR]

We present coding strategies, which are variants of the Schalkwijk—Kailath scheme, for communicating reliably over additive white noise channels in the presence of corrupted feedback. Our framework comprises an additive white forward channel and a feedback link. We consider two types of corruption mechanisms in the feedback link. The first is quantization noise, i.e., the encoder receives the quantized values of the past outputs of the forward channel. The quantization is uniform, memoryless and time invariant. The second corruption mechanism is an arbitrarily distributed additive bounded noise. Here we allow symbol-by-symbol encoding at the input to the feedback link. We propose explicit schemes featuring positive information rate and positive error exponent. If the forward channel is additive white Gaussian (AWGN) then, as the amplitude of the noise at the feedback link decreases to zero, the rate of our schemes converges to the capacity of the channel. Moreover, the probability of error is shown to converge to zero at a doubly exponential rate. If the forward channel is AWGN and the feedback link consists of an additive bounded noise channel, with signal-to-noise ratio (SNR) constrained symbol-by-symbol encoding, then our schemes achieve rates arbitrarily close to capacity, in the limit of high SNR (at the feedback link). [ABSTRACT FROM AUTHOR]

We consider causally estimating (filtering) the components of a noise-corrupted sequence relative to a reference class of filters. The noiseless sequence to be filtered is designed by a "well-informed antagonist," meaning it may evolve according to an arbitrary law, unknown to the filter, based on past noiseless and noisy sequence components. We show that this setting is more challenging than that of an individual noiseless sequence (a.k.a. the "semi-stochastic" setting) in the sense that any deterministic filter, even one guaranteed to do well on every noiseless individual sequence, fails under some well-informed antagonist. On the other hand, we constructively establish the existence of a randomized filter which successfully competes with an arbitrary given finite reference class of filters, under every antagonist. Thus, unlike in the semi-stochastic setting, randomization is crucial in the antagonist framework. Our noise model allows for channels whose noisy output depends on the l past channel outputs (in addition to the noiseless channel input symbol). Memoryless channels are obtained as a special case of our model by taking l = 0. In this case, our scheme coincides with one that was recently shown to compete with an arbitrary reference class when the underlying noiseless sequence is an individual sequence. Hence, our results show that the latter scheme is universal not only for the semi-stochastic setting in which it was originally proposed, but also under the well-informed antagonist. [ABSTRACT FROM AUTHOR]

We consider the filtering problem, where a finite-alphabet individual sequence is corrupted by a discrete memoryless channel, and the goal is to causally estimate each sequence component based on the past and present noisy observations. We establish a correspondence between the filtering problem and the problem of prediction of individual sequences which leads to the following result: Given an arbitrary finite set of filters, there exists a filter which performs, with high probability, essentially as well as the best in the set, regardless of the underlying noiseless individual sequence. We use this relationship between the problems to derive a filter guaranteed of attaining the "finite-state filterability" of any individual sequence by leveraging results from the prediction problem. [ABSTRACT FROM AUTHOR]

Subclasses of finite alphabet denoising and filtering (causal denoising) schemes are compared. Performance is measured by the normalized cumulative loss (a.k.a. distortion), as measured by a single-letter loss function. We aim to minimize the probability that the normalized cumulative loss exceeds a given threshold. We call this quantity the probability of excess loss. Specifically, we consider a scheme to be optimal if it attains the maximal exponential decay rate of the probability of excess loss. This provides another way of comparing schemes that complements and contrasts previous work which considered the expected value of the normalized cumulative loss. In particular, the question of whether the optimal denoiser is symbol-by-symbol for an independent and identically distributed (i.i.d.) source and a discrete memoryless channel (DMC) is investigated. For Hamming loss, the optimal denoiser is proven to be symbol-by-symbol. Perhaps somewhat counterintuitively, for a general single letter loss function, the optimal scheme need not be symbol-by-symbol. The optimal denoiser requires unbounded delay and unbounded look-ahead while symbol-by-symbol schemes mandate zero delay and look-ahead. It is natural to wonder about the effect of limited delay and limited look-ahead. Consequently, finite sliding-window denoisers and finite block denoisers are defined. They are shown to perform no better than symbol-by-symbol denoisers. Finally, the effect of causality is investigated. While it is difficult to characterize the performance of filters with unbounded memory explicitly, it is shown that finite memory filters perform no better than symbol-by-symbol filters. [ABSTRACT FROM AUTHOR]

We characterize the rate distortion function for the source coding with decoder side information setting when the ith reconstruction symbol is allowed to depend only on the first i + ℓ side information symbols, for some finite look-ahead ℓ, in addition to the index from the encoder. For the case of causal side information, i.e., ℓ = 0, we find that the penalty of causality is the omission of the subtracted mutual information term in the Wyner-Ziv rate distortion function. For ℓ > 0, we derive a computable ‘infinite-letter’ expression for the rate distortion function. When specialized to the near-lossless case, our results characterize the best achievable rate for the Slepian-WoIf source coding problem with finite side information looka-head, and have some surprising implications. We find that side information is useless for any fixed ℓ when the joint probability mass function (PMF) of the source and side information satisfies the positivity condition P(x, y) > 0 for all (x, y). More generally, the optimal rate depends on the distribution of the pair X, Y only through the distribution of X and the bipartite graph whose edges represent the pairs x, y for which P(x, y) > 0. On the other hand, if side information look-ahead is allowed to grow faster than logarithmic in the block length, then H (X ∣ Y) is achievable. Finally, we apply our approach to derive a computable expression for channel capacity when state information is available at the encoder with limited look-ahead. [ABSTRACT FROM AUTHOR]

We consider zero-delay joint source-channel coding of individual source sequences for a general known channel. Given an arbitrary finite set of schemes with finite-memory (not necessarily time-invariant) decoders, a scheme is devised that does essentially as well as the best in the set on all individual source sequences. Using this scheme, we construct a universal zero-delay joint source-channel coding scheme that is guaranteed to achieve, asymptotically, the performance of the best zero-delay encoding-decoding scheme with a finite-state encoder and a Markov decoder, on all individual sequences. For the case where the channel is a discrete memoryless channel (DMC), we construct an implementable zero-delay joint source-channel coding scheme that is based on the ‘follow the perturbed leader’ scheme of György et al. for lossy source coding of individual sequences. Our scheme is guaranteed to attain asymptotically the performance of the best in the set of all encoding-decoding schemes with a ‘symbol-by-symbol’ decoder (and arbitrary encoder), on all individual sequences. [ABSTRACT FROM AUTHOR]

We consider both channel coding and source coding, with perfect past feedback/feedforward, in the presence of side information. it is first observed that feedback does not increase the capacity of the Gel'fand-Pinsker channel, nor does feedforward improve the achievable rate-distortion performance in the Wyner-Ziv problem. We then focus on the Gaussian case showing that, as in the absence of side information, feedback/feedforward allows to efficiently attain the respective performance limits. In particular, we derive schemes via variations on that of Schalkwijk and Kailath. These variants, which are as simple as their origin and require no binning, are shown to achieve, respectively, the capacity of Costa's channel, and the Wyner-Ziv rate distortion function. Finally, we consider the finite-alphabet setting and derive schemes for both the channel and the source coding problems that attain the fundamental limits, using variations on schemes of Ahlswede and Ooi and Wornell, and of Martinian and Wornell, respectively. [ABSTRACT FROM AUTHOR]

We study the entropy rate of pattern sequences of stochastic processes, and its relationship to the entropy rate of the original process. We give a complete characterization of this relationship for independent and identically distributed (i.i.d.) processes over arbitrary alphabets, stationary ergodic processes over discrete alphabets, and a broad family of stationary ergodic processes over uncountable alphabets. For cases where the entropy rate of the pattern process is infinite, we characterize the possible growth rate of the block entropy. [ABSTRACT FROM AUTHOR]

We consider the problem of optimally recovering a finite-alphabet discrete-time stochastic process {Xt} from its noise-corrupted observation process {Zt}. In general, the optimal estimate of Xt will depend on all the components of {Zt} on which it can be based. We characterize nontrivial situations (i.e., beyond the case where (Xt, Zt) are independent) for which optimum performance is attained using "symbol-by-symbol" operations (a.k.a. "singlet decoding"), meaning that the optimum estimate of Xt depends solely on Zt. For the case where {Xt} is a stationary binary Markov process corrupted by a memoryless channel, we characterize the necessary and sufficient condition for optimality of symbol-by-symbol operations, both for the filtering problem (where the estimate of Xt is allowed to depend only on {Zt'}t≤t) and the denoising problem (where the estimate of Xt is allowed dependence on the entire noisy process). It is then illustrated how our approach, which consists of characterizing the support of the conditional distribution of the noise-free symbol given the observations, can be used for characterizing the entropy rate of the binary Markov process corrupted by the binary-symmetric channel (BSC) in various asymptotic regimes. For general noise-free processes (not necessarily Markov), general noise processes (not necessarily memoryless), and general index sets (random fields) we obtain an easily verifiable sufficient condition for the optimality of symbol-by-symbol operations and illustrate its use in a few special cases. For example, for binary processes corrupted by a BSC, we establish, under mild conditions, the existence of a δ* > 0 such that the "say-what-you-see" scheme is optimal provided the channel crossover probability is less than δ*. Finally, we show how for the case of a memoryless channel the large deviations (LD) performance of a symbol-by-symbol filter is easy to obtain, thus characterizing the LD behavior of the optimal schemes when these are singlet decoders (and constituting the only known cases where such explicit characterization is available). [ABSTRACT FROM AUTHOR]

Let X = (X1,…) be a stationary ergodic finite- alphabet source, Xn denote its first n symbols, and Yn be the codeword assigned to Xn by a lossy source code. The empirical kth-order joint distribution Qk[Xn, Yn](Xk, Yk) is defined as the frequency of appearances of pairs of k-strings (xk, yk) along the pair (Xn, Yn). Our main interest is in the sample behavior of this (random) distribution. Letting I(Qk) denote the mutual information I(Xk; Yk) when (Xk, yk) ∼ Qk we show that for any (sequence of) lossy source code(s) of rate ≤ R ... where ... (X) denotes the entropy rate of X. This is shown to imply, for a large class of sources including all independent and identically distributed (i.i.d). sources and all sources satisfying the Shannon lower bound with equality, that for any sequence of codes which is good in the sense of asymptotically attaining a point on the rate distortion curve ... whenever PXk,Ỹk is the unique distribution attaining the minimum in the definition of the kth-order rate distortion function. Consequences of these results include a new proof of Kieffer's sample converse to lossy source coding, as well as performance bounds for compression-based denoisers. [ABSTRACT FROM AUTHOR]

We consider the problem of reconstructing a finite-alphabet signal corrupted by a known memoryless channel with a general output alphabet. The goodness of the reconstruction is measured by a given loss function. We (constructively) establish the existence of a universal (sequence of) denoiser(s) attaining asymptotically the optimum distribution-dependent performance for any stationary source that may be generating the noise- less signal. We show, in fact, that there is a whole family of denoiser sequences with this property. These schemes are shown to be universal also in a semistochastic setting, where the only randomness assumed is that associated with the channel noise. The scheme is practical, requiring O(n1+c) operations (for any e > 0) and working storage size sublinear in the input data length. This extends recent work that presented a discrete universal denoiser for recovering a discrete source corrupted by a discrete memory- less channel (DMC). [ABSTRACT FROM AUTHOR]

A discrete denoising algorithm estimates the input sequence to a discrete memoryless channel (DMC) based on the observation of the entire output sequence. For the case in which the DMC is known and the quality of the reconstruction is evaluated with a given single-letter fidelity criterion, we propose a discrete denoising algorithm that does not assume knowledge of statistical properties of the input sequence. Yet, the algorithm is universal in the sense of asymptotically performing as well as the optimum denoiser that knows the input sequence distribution, which is only assumed to be stationary. Moreover, the algorithm is universal also in a semi-stochastic setting, in which the input is an individual sequence, and the randomness is due solely to the channel noise. The proposed denoising algorithm is practical, requiring a linear number of register-level operations and sublinear working storage size relative to the input data length. [ABSTRACT FROM AUTHOR]

Consider the problem of rate-constrained reconstruction of a finite-alphabet discrete memoryless signal Xn= (X1,... , Xn, based on a noise-corrupted observation sequence Zn, which is the finite-alphabet output of a discrete memoryless channel (DMC) whose input is Xn. Suppose that there is some uncertainty in the source distribution, in the channel characteristics, or in both. Equivalently, suppose that the distribution of the pairs (Xi, Zi), rather than completely being known, is only known to belong to a set Θ. Suppose further that the relevant performance criterion is the probability of excess distortion, i.e., letting &Xsline;n (Zn) denote the reconstruction, we are interested in the behavior of Pθ (ρ(Xn,&Xcirc;n(zn)) > dθ), where ρ is a (normalized) block distortion induced by a single-letter distortion measure and Pθ denotes the probability measure corresponding to the case where (Xi, Zi) ∼ θ, θ ϵ Θ. Since typically this probability will either not decay at all or do so at an exponential rate, it is the rate of this decay which we focus on. More concretely, for a given rate R ≥ 0 and a family of distortion levels {dθ}θϵΘ, we are interested in families of exponential levels {Iθ}θϵΘ which are achievable in the sense that for large n there exist rate-R schemes satisfying -&frac1n; log Pθ(ρ(Xn,&Xcirc;n (Zn)) > dθ)≥ Iθ for all θ ϵ Θ. Our main result is a complete "single-letter" characterization of achievable levels {Iθ}θϵΘ per any given triple (Θ,R, {dθ}θϵΘ). Equipped with this result, we later turn to addressing the question of the "right" choice of {Iθ}θϵΘ. Relying on methodology recently put forth by Feder and Merhav in the context of the composite hypothesis testing problem, we propose a competitive minimax approach for the choice of these levels and apply our main result for characterizing the associated key quantities. Subsequently, we apply the main result to characterize optimal performance in a Neyman-Pearson-like setting, where there are two possible noise- corrupted signals. In this problem, the goal of the observer of the noisy signal, rather than having to determine which of the two it is (as in the hypothesis testing problem), is to reproduce the underlying clean signal with as high a fidelity as possible (e.g., lowest number of symbol errors when distortion measure is Hamming), under the assumption that one source is active, while operating at a limited information rate II and subject to a constraint on the fidelity of reconstruction when the other source is active. Finally, we apply our result to characterize a sufficient condition for the source class S to be universally encodable in the sense of the existence of schemes attaining the optimal distribution-dependent exponent,, Simultaneously for all sources in the class. This condition was shown in an earlier work to suffice for universality in expectation. [ABSTRACT FROM AUTHOR]

Consider the normalized cumulative loss of a predictor F on the sequence x[supn] = (x[sub1],&hellipi,x[subn]), denoted LF(s[supn]). For a set of predictors G, let L(G, x[supn]) = min[subF∊g], L[subF](x[supn]) denote the loss of the best predictor in the class on x[supn]. Given the stochastic process X = X[sub1], X[sub2]…, we look at EL(G, X[supn]), termed the competitive predictability of G on X[supn]. Our interest is In the optimal predictor set of size M, i.e., the predictor set achieving min[sub|g|≤]M EL(G, X[supn]). When M is subexponential in n, simple arguments show that min[sub|g&berbar;≤]M EL(G, X[supn]) coincides, for large n, with the Bayesian envelope min[subF] EL[subF](X[supn])). We investigate the behavior, for large n, of min[sub|g|

Consider the problem of finite-rate filtering of a discrete memoryless process {X[SUBi]}[SUBi≥1] based on its noisy observation sequence {X[SUBi]}[SUBi≥1], which is the output of a discrete memoryless channel (DMC) whose input is {X[SUBi]}[SUBi≥1]. When the distribution of the pairs (X[SUBi], Z[SUBi]), P[SUBx,z] is known, and for a given distortion measure, the solution to this problem is well known to be given by classical rate-distortion theory upon the introduction of a modified distortion measure. In this work, we address the case where P[SUBx,z] rather than being completely specified, is only known to belong to some set A. For a fixed encoding rate R, we look at the worst case, over all θ ∊ Λ, of the difference between the expected distortion of a given scheme which is not allowed to depend on the active source θ ∊ Λ and the value of the distortion-rate function at R corresponding to the noisy source θ. We study the minimum attainable value achievable by any scheme operating at rate R for this worst case quantity, denoted by D(Λ, R). Linking this problem and that of source coding under several distortion measures, we prove a coding theorem for the latter problem and apply it to characterize D(Λ, H) for the case where all members of Λ share the same noisy marginal. For the case of a general Λ, we obtain a single-letter characterization of D(Λ, H) for the finite-alphabet case. This gives, in particular, a necessary and sufficient condition on the set Λ for the existence of a coding scheme which is universally optimal for all members of Λ and characterizes the approximation-estimation tradeoff for statistical modeling of noisy source coding problems. Finally, we obtain D(Λ, H) in closed form for cases where A consists of distributions on the (channel) input-output pair of a Bernoulli source corrupted by a binary-symmetric channel (BSC). In particular, for the case where A consists of two sources: the all-zero source corrupted by a BSC with crossover probability r and the Bernoulli(r) source with a noise-free channel; we find that universality becomes increasingly hard with increasing rate. [ABSTRACT FROM AUTHOR]

The problem of sequentially scanning and predicting data arranged in a multidimensional array is considered. We introduce the notion of a scandictor, which is any scheme for the sequential scanning and prediction of such multidimensional data. The scandictability of any finite (probabilistic) data array is defined as the best achievable expected "scandiction" performance on that array. The scandictability of any (spatially) stationary random field on Z[sup m] is defined as the limit of its scandictability on finite "boxes" (subsets of Z[sup m]), as their edges become large. The limit is shown to exist for any stationary field, and essentially be independent of the ratios between the box dimensions. Fundamental limitations on scandiction performance in both the probabilistic and the deterministic settings are characterized for the family of difference loss functions. We find that any stochastic process or random field that can be generated autoregressively with a maximum-entropy innovation process is optimally "scandicted" the way it was generated. These results are specialized for cases of particular interest. The scandictability of any stationary Gaussian field under the squared-error loss function is given a single-letter expression in terms of its spectral measure and is shown to be attained by the raster scan. For a family of binary Markov random fields (MRFs), the scandictability under the Hamming distortion measure is fully characterized. [ABSTRACT FROM AUTHOR]

Presents a study of adaptive schemes for the sequential lossy coding of individual sequences. Problem formulation for the noise-free setting; Application of the sliding block and trellis source codes; Discussion of time-invariant sliding-window schemes.

Focuses on a study which considered a lossy compression of a discrete memoryless source with respect to a single-letter distortion measure. Notation and preliminaries; Error exponent for universal lossy coding; Conclusion.

Presents a study which considered the problem of predicting the next outcome of an individual binary sequence based on noisy observations of the past. Approach to the prediction problem in the noisy setting and the derivation of results assessing the merits of this approach; Details on binary-valued noise; Information on real-valued noise.

Presents information on a study which considered the problem of predicting the next outcome of an individual binary sequence corrupted by noise using finite memory. Notation conventions; Introduction of the noisy setting for universal prediction; Conclusions.

We consider parameter estimation in distributed networks, where each sensor in the network observes an independent sample from an underlying distribution and has $k$ bits to communicate its sample to a centralized processor which computes an estimate of a desired parameter. We develop lower bounds for the minimax risk of estimating the underlying parameter for a large class of losses and distributions. Our results show that under mild regularity conditions, the communication constraint reduces the effective sample size by a factor of $d$ when $k$ is small, where $d$ is the dimension of the estimated parameter. Furthermore, this penalty reduces at most exponentially with increasing $k$ , which is the case for some models, e.g., estimating high-dimensional distributions. For other models however, we show that the sample size reduction is re-mediated only linearly with increasing $k$ , e.g. when some sub-Gaussian structure is available. We apply our results to the distributed setting with product Bernoulli model, multinomial model, Gaussian location models, and logistic regression which recover or strengthen existing results. Our approach significantly deviates from existing approaches for developing information-theoretic lower bounds for communication-efficient estimation. We circumvent the need for strong data processing inequalities used in prior work and develop a geometric approach which builds on a new representation of the communication constraint. This approach allows us to strengthen and generalize existing results with simpler and more transparent proofs. [ABSTRACT FROM AUTHOR]

We propose an efficient algorithm for approximate computation of the profile maximum likelihood (PML), a variant of maximum likelihood maximizing the probability of observing a sufficient statistic rather than the empirical sample. The PML has appealing theoretical properties, but is difficult to compute exactly. Inspired by observations gleaned from exactly solvable cases, we look for an approximate PML solution, which, intuitively, clumps comparably frequent symbols into one symbol. This amounts to lower-bounding a certain matrix permanent by summing over a subgroup of the symmetric group rather than the whole group during the computation. We extensively experiment with the approximate solution, and the empirical performance of our approach is competitive and sometimes significantly better than state-of-the-art performances for various estimation problems. [ABSTRACT FROM AUTHOR]

We consider the problem of estimating the $L_{1}$ distance between two discrete probability measures $P$ and $Q$ from empirical data in a nonasymptotic and large alphabet setting. When $Q$ is known and one obtains $n$ samples from $P$ , we show that for every $Q$ , the minimax rate-optimal estimator with $n$ samples achieves performance comparable to that of the maximum likelihood estimator with $n\ln n$ samples. When both $P$ and $Q$ are unknown, we construct minimax rate-optimal estimators, whose worst case performance is essentially that of the known $Q$ case with $Q$ being uniform, implying that $Q$ being uniform is essentially the most difficult case. The effective sample size enlargement phenomenon, identified by Jiao et al., holds both in the known $Q$ case for every $Q$ and the $Q$ unknown case. However, the construction of optimal estimators for $\|P-Q\|_{1}$ requires new techniques and insights beyond the approximation-based method of functional estimation by Jiao et al. [ABSTRACT FROM AUTHOR]

Fundamental relations between information and estimation have been established in the literature for the continuous time Gaussian and Poisson channels. In this paper, we demonstrate that such relations hold for a much larger family of continuous-time channels. We introduce the family of semi-martingale channels where the channel output is a semi-martingale stochastic process, and the channel input modulates the characteristics of the semi-martingale. For these channels, which includes as a special case the continuous time Gaussian and Poisson models, we establish new representations relating the mutual information between the channel input and output to an optimal causal filtering loss, thereby unifying and considerably extending results from the Gaussian and Poisson settings. Extensions to the setting of mismatched estimation are also presented where the relative entropy between the laws governing the output of the channel under two different input distributions is equal to the cumulative difference between the estimation loss incurred by using the mismatched and optimal causal filters, respectively. The main tool underlying these results is the Doob–Meyer decomposition of a class of sub-martingales. The results in this paper can be viewed as the continuous-time analogues of recent generalizations for relations between information and estimation for discrete-time Lévy channels. [ABSTRACT FROM AUTHOR]