Large language model (LLM) tokenizers act as structured compressors: by mapping text to discrete token sequences, they determine token count (and thus compute and context usage) and the statistical structure seen by downstream models. Despite their central role in LLM pipelines, the link between tokenization, compression efficiency and induced structure is not well understood. We empirically demonstrate that tokenizer training scale redistributes entropy: as training data grows, the token stream becomes more diverse in aggregate (higher unigram entropy) yet markedly more predictable in-context (lower higher-order conditional entropies), indicating that tokenization absorbs substantial short-range regularity although these gains degrade under train-test domain mismatch. To ground these observations, we first benchmark i) pretrained GPT-family tokenizers as black-box compressors across various domains, and ii) learned tokenizers across configurations spanning vocabulary size, training scale, and domain. Next, we study tokenization as a transform for universal compression and introduce a compression-aware BPE variant. Finally, we adopt a channel lens and introduce capacity-utilization metrics to analyze tokenizer behaviour and outline implications for downstream modeling. Put together, our results expose various trade-offs between compression, induced structure, and robustness under domain shift, and motivate principled, compression-aware tokenizer design.

We propose and study a family of universal sequential probability assignments on individual sequences, based on the incremental parsing procedure of the Lempel-Ziv (LZ78) compression algorithm. We show that the normalized log loss under any of these models converges to the normalized LZ78 codelength, uniformly over all individual sequences. To establish the universality of these models, we consolidate a set of results from the literature relating finite-state compressibility to optimal log-loss under Markovian and finite-state models. We also consider some theoretical and computational properties of these models when viewed as probabilistic sources. Finally, we present experimental results showcasing the potential benefit of using this family—as models and as sources—for compression, generation, and classification.

We consider the universal discrete filtering problem, where an input sequence generated by an unknown source passes through a discrete memoryless channel, and the goal is to estimate its components based on the output sequence, with limited lookahead or delay. We propose and establish the universality of a family of schemes for this setting. These schemes are induced by universal Sequential Probability Assignments (SPAs), and inherit their computational properties. We show that the schemes induced by LZ78 (a Lempel-Ziv compression algorithm) are practically implementable and well-suited for scenarios with limited computational resources and latency constraints. As a byproduct of our analysis, we obtain novel upper and lower bounds in the purely Bayesian setting using some of the intermediate results.

Recent advances in symbolic music generation primarily rely on deep learning models such as Transformers, GANs, and diffusion models. While these approaches achieve high-quality results, they require substantial computational resources, limiting their scalability. We introduce LZMidi, a lightweight symbolic music generation framework based on a Lempel-Ziv (LZ78)-induced sequential probability assignment (SPA). By leveraging the discrete and sequential structure of MIDI data, our approach enables efficient music generation on standard CPUs with minimal training and inference costs. Theoretically, we establish universal convergence guarantees for our approach, underscoring its reliability and robustness. Compared to state-of-the-art diffusion models, LZMidi achieves competitive Fréchet Audio Distance (FAD), Wasserstein Distance (WD), and Kullback-Leibler (KL) scores, while significantly reducing computational overhead-up to$30 \times$faster training and$300 \times$faster generation. Our results position LZMidi as a significant advancement in compression-based learning, highlighting how universal compression techniques can efficiently model and generate structured sequential data, such as symbolic music, with practical scalability and theoretical rigor.

We consider inferring a stationary ergodic source by lossily compressing observations of the source made through a memoryless noisy channel. By bounding the deviation of the empirical joint distribution of source, observation, and inference output from satisfying a Markov property, we give an exact characterization of the loss achieved. We show that this analysis is applicable to general memoryless noise channels by deliberately choosing the distortion measure for the lossy compressor to match the channel conditional distribution. Consequences of these results are given in the specific cases of MSE and Hamming loss. A comparison is made to an indirect rate-distortion perspective on the problem.

We consider the universal discrete filtering problem, where an input sequence generated by an unknown source passes through a discrete memoryless channel, and the goal is to estimate its components based on the output sequence, with limited lookahead or delay. We propose and establish the uni-versality of a family of schemes for this setting. These schemes are induced by universal Sequential Probability Assignments (SPAs), and inherit their computational properties. We show that the schemes induced by LZ78 are practically implementable and well-suited for scenarios with limited computational re-sources and latency constraints.

Generative modeling of non-negative, discrete data, such as symbolic music, remains challenging due to two persistent limitations in existing methods. Firstly, many approaches rely on modeling continuous embeddings, which is suboptimal for inherently discrete data distributions. Secondly, most models optimize variational bounds rather than exact data likelihood, resulting in inaccurate likelihood estimates and degraded sampling quality. While recent diffusion-based models have addressed these issues separately, we tackle them jointly. In this work, we introduce the Information-Theoretic Discrete Poisson Diffusion Model (ItDPDM), inspired by photon arrival process, which combines exact likelihood estimation with fully discrete-state modeling. Central to our approach is an information-theoretic Poisson Reconstruction Loss (PRL) that has a provable exact relationship with the true data likelihood. ItDPDM achieves improved likelihood and sampling performance over prior discrete and continuous diffusion models on a variety of synthetic discrete datasets. Furthermore, on real-world datasets such as symbolic music and images, ItDPDM attains superior likelihood estimates and competitive generation quality—demonstrating a proof of concept for distribution-robust discrete generative modeling.

Large language models (LLMs) have shown remarkable performance across diverse reasoning and generation tasks, and are increasingly deployed as agents in dynamic environments such as code generation and recommendation systems. However, many real-world applications, such as high-frequency trading and real-time competitive gaming, require decisions under strict latency constraints, where faster responses directly translate into higher rewards. Despite the importance of this latency–quality trade-off, it remains underexplored in the context of LLM-based agents. In this work, we present the first systematic study of this trade-off in real-time decision-making tasks. To support our investigation, we introduce two new benchmarks: HFTBench, a high-frequency trading simulation, and StreetFighter, a competitive gaming platform. Our analysis reveals that optimal latency–quality balance varies by task, and that sacrificing quality for lower latency can significantly enhance downstream performance. To address this, we propose FPX, an adaptive framework that dynamically selects model size and quantization level based on real-time demands. Our method achieves the best performance on both benchmarks, improving win rate by up to 80% in Street Fighter and boosting daily yield by up to 26.52% in trading, underscoring the need for latency-aware evaluation and deployment strategies for LLM-based agents. These results demonstrate the critical importance of latency-aware evaluation and deployment strategies for real-world LLM-based agents.

The high communication cost of sending model updates from the clients to the server is a significant bottleneck for scalable federated learning (FL). Among existing approaches, state-of-the-art bitrate-accuracy tradeoffs have been achieved using stochastic compression methods – in which the client n sends a sample from a client-only probability distribution $q_{\phi^{(n)}}$, and the server estimates the mean of the clients’ distributions using these samples. However, such methods do not take full advantage of the FL setup where the server, throughout the training process, has side information in the form of a global distribution $p_{\theta}$ that is close to the client-only distribution $q_{\phi^{(n)}}$ in Kullback-Leibler (KL) divergence. In this work, we exploit this \emph{closeness} between the clients’ distributions $q_{\phi^{(n)}}$’s and the side information $p_{\theta}$ at the server, and propose a framework that requires approximately $D_{KL}(q_{\phi^{(n)}}|| p_{\theta})$ bits of communication. We show that our method can be integrated into many existing stochastic compression frameworks to attain the same (and often higher) test accuracy with up to 82 times smaller bitrate than the prior work – corresponding to 2,650 times overall compression.

We consider the mutual information between a uniformly-random input and the corresponding output through the deletion channel. We prove an upper bound that’s within approximately 0.1 of the best-known lower bounds for all values of the deletion probabilityd, and much closer for small and larged. We give simulation results which suggest that our upper bound is within 0.05 of the exact value for alld, and within 0.01 ford> 0.75. Despite our upper bounds, based on simulations, we conjecture that the mutual information is positive for all deletion probabilities less than 1. Our results imply impossibility results for the (equivalent) problem of compression of i.i.d. sources correlated via the deletion channel, a relevant model for DNA storage.

Video conferencing tools have seen a significant increase in usage in the past few years but they still consume a significant bandwidth of $\sim 100$ Kbps to a few Mbps. In this work, we present Txt2Vid-Web: a practical, web-based, low bandwidth, video conferencing platform building upon the Txt2Vid work [1]. We introduce multiple improvements over the existing Txt2Vid framework – implementing it on browser application stack making it much more accessible and portable, reducing the implementation complexity of the plat-form via WebGL, and implementing a new WebGL shader for ConvTranspose in ONNX runtime – thereby enabling it to run on web-browsers of modern laptops (Fig. 1a). We use WebRTC to establish peer-to-peer data channels over network connections and utilize SDP’s multimedia negotiation scheme over SRTP connections, allowing our platform to provide high-quality video calls for the majority of connections and fall back to Txt2Vid when bandwidth limitations overconstrain SDP’s chosen codecs. We verified our plat-form via subjective study $(n =126)$ consisting of comparison of five different audio-video (AV) contents compressed via standard codecs and Txt2Vid-Web. We choose bitrates of {6 kbps, 10 kbps} for encoding the audio and bitrates of {15 kbps, 35 kbps, 100 kbps} for encoding the video using standard AV codec. Results show that at similar quality of experience our platform requires $100 - 500 \times$ less bandwidth than H.264 and VP9 as video codec and OPUS as audio codec (Fig. 1b). We envision our platform can open up many novel applications. Towards this end, we also open-source both our new tool as a Github repository (https://github.com/tpulkit/txt2vid_browser), and our subjective study dataset (https://tinyurl.com/SubjectiveStudyDataset).

We study the mean estimation problem under communication and local differential privacy constraints. While previous work has proposed order-optimal algorithms for the same problem (i.e., asymptotically optimal as we spend more bits), exact optimality (in the non-asymptotic setting) still has not been achieved. In this work, we take a step towards characterizing the exact-optimal approach in the presence of shared randomness (a random variable shared between the server and the user) and identify several conditions for exact optimality. We prove that one of the conditions is to utilize a rotationally symmetric shared random codebook. Based on this, we propose a randomization mechanism where the codebook is a randomly rotated simplex -- satisfying the properties of the exact-optimal codebook. The proposed mechanism is based on a $k$-closest encoding which we prove to be exact-optimal for the randomly rotated simplex codebook.

Video represents the majority of internet traffic today, driving a continual race between the generation of higher quality content, transmission of larger file sizes, and the development of network infrastructure. In addition, the recent COVID-19 pandemic fueled a surge in the use of video conferencing tools. Since videos take up considerable bandwidth ($\sim 100$Kbps to a few Mbps), improved video compression can have a substantial impact on network performance for live and pre-recorded content, providing broader access to multimedia content worldwide. We present a novel video compression pipeline, called Txt2Vid, which dramatically reduces data transmission rates by compressing webcam videos (“talking-head videos”) to a text transcript. The text is transmitted and decoded into a realistic reconstruction of the original video using recent advances in deep learning based voice cloning and lip syncing models. Our generative pipeline achieves two to three orders of magnitude reduction in the bitrate as compared to the standard audio-video codecs (encoders-decoders), while maintaining equivalent Quality-of-Experience based on a subjective evaluation by users ($n=242$) in an online study. The Txt2Vid framework opens up the potential for creating novel applications such as enabling audio-video communication during poor internet connectivity, or in remote terrains with limited bandwidth. The code for this work is available athttps://github.com/tpulkit/txt2vid.git.

Compression and efficient storage of neural network (NN) parameters is critical for applications that run on resource-constrained devices. Despite the significant progress in NN model compression, there has been considerably less investigation in the actual physical storage of NN parameters. Conventionally, model compression and physical storage are decoupled, as digital storage media with error-correcting codes (ECCs) provide robust error-free storage. However, this decoupled approach is inefficient as it ignores the overparameterization present in most NNs and forces the memory device to allocate the same amount of resources to every bit of information regardless of its importance. In this work, we investigate analog memory devices as an alternative to digital media – one that naturally provides a way to add more protection for significant bits unlike its counterpart, but is noisy and may compromise the stored model’s performance if used naively. We develop a variety of robust coding strategies for NN weight storage on analog devices, and propose an approach to jointly optimize model compression and memory resource allocation. We then demonstrate the efficacy of our approach on models trained on MNIST, CIFAR-10, and ImageNet datasets for existing compression techniques. Compared to conventional error-free digital storage, our method reduces the memory footprint by up to one order of magnitude, without significantly compromising the stored model’s accuracy.

We study the neural network (NN) compression problem, viewing the tension between the compression ratio and NN performance through the lens of rate-distortion theory. We choose a distortion metric that reflects the effect of NN compression on the model output and then derive the tradeoff between rate (compression ratio) and distortion. In addition to characterizing theoretical limits of NN compression, this formulation shows that pruning, implicitly or explicitly, must be a part of a good compression algorithm. This observation bridges a gap between parts of the literature pertaining to NN and data compression, respectively, providing insight into the empirical success of pruning for NN compression. Finally, we propose a novel pruning strategy derived from our information-theoretic formulation and show that it outperforms the relevant baselines on CIFAR-10 and ImageNet datasets.

Storage-efficient privacy-guaranteed learning is crucial due to enormous amounts of sensitive user data required for increasingly many learning tasks. We propose a framework for reducing the storage cost while at the same time providing privacy guarantees, without essential loss in the utility of the data for learning. Our method comprises noise injection followed by lossy compression. We show that, when appropriately matching the lossy compression to the distribution of the added noise, the compressed examples converge, in distribution, to that of the noise-free training data. In this sense, the utility of the data for learning is essentially maintained, while reducing storage and privacy leakage by quantifiable amounts. We present experimental results on the CelebA dataset for gender classification and find that our suggested pipeline delivers in practice on the promise of the theory: the individuals in the images are unrecognizable (or less recognizable, depending on the noise level), overall storage of the data is substantially reduced, with no essential loss of the classification accuracy. As an added bonus, our experiments suggest that our method yields a substantial boost to robustness in the face of adversarial test data.

With the advent and increasing consolidation of e-commerce, digital advertising has very recently replaced traditional advertising as the main marketing force in the economy. In the past four years, a particularly important development in the digital advertising industry is the shift from second-price auctions to first-price auctions for online display ads. This shift immediately motivated the intellectually challenging question of how to bid in first-price auctions, because unlike in second-price auctions, bidding one's private value truthfully is no longer optimal. Following a series of recent works in this area, we consider a differentiated setup: we do not make any assumption about other bidders' maximum bid (i.e. it can be adversarial over time), and instead assume that we have access to a hint that serves as a prediction of other bidders' maximum bid, where the prediction is learned through some blackbox machine learning model. We consider two types of hints: one where a single point-prediction is available, and the other where a hint interval (representing a type of confidence region into which others' maximum bid falls) is available. We establish minimax optimal regret bounds for both cases and highlight the quantitatively different behavior between the two settings. We also provide improved regret bounds when the others' maximum bid exhibits the further structure of sparsity. Finally, we complement the theoretical results with demonstrations using real bidding data.

Human perception is at the core of lossy video compression and yet, it is challenging to collect data that is sufficiently dense to drive compression. In perceptual quality assessment, human feedback is typically collected as a single scalar quality score indicating preference of one distorted video over another. In reality, some videos may be better in some parts but not in others. We propose an approach for collecting finer-grained user feedback through an interactive tool that allows direct optimization of perceptual quality given a fixed bitrate. To this end, we built a novel web-tool which allows users to paint spatio-temporal importance maps over videos. The tool allows for interactive successive refinement: we iteratively re-encode the original video according to the painted importance maps, while maintaining the same bitrate, thus allowing the user to visually see the trade-off of assigning higher importance to one spatio-temporal part of the video at the cost of others. We use this tool to collect data in-the-wild (10 videos, 17 users) and utilize the obtained importance maps in the context of x264 coding to demonstrate that the tool can indeed be used to generate videos which, at the same bitrate, look perceptually better through a subjective study (n = 26) - and are 1.9 times more likely to be preferred by viewers. We plan on collecting a large-scale dataset using the tool for automated perceptual compression in the future. The code for the tool and dataset can be found at https://github.com/jenyap/video-annotation-tool.git.

COVID-19 has made video communication one of the most important modes of information exchange. While extensive research has been conducted on the optimization of the video streaming pipeline, in particular the development of novel video codecs, further improvement in the video quality and latency is required, especially under poor network conditions. This paper proposes an alternative to the conventional codec through the implementation of a keypoint-centric encoder relying on the transmission of keypoint information from within a video feed, as shown in Figure 1. The decoder uses the streamed keypoints to generate a reconstruction preserving the semantic features in the input feed. Focusing on video calling applications, we detect and transmit the body pose and face mesh information through the network, which are displayed at the receiver in the form of animated puppets. Using efficient pose and face mesh detection in conjunction with skeleton-based animation, we demonstrate a prototype requiring lower than 35 kbps bandwidth, an order of magnitude reduction over typical video calling systems. The added computational latency due to the mesh extraction and animation is below 120ms on a standard laptop, showcasing the potential of this framework for real-time applications. The code for this work is available at https://github.com/shubhamchandak94/digital-puppetry/ and the full version is available on arXiv [1].

Bid Shading has become increasingly important in Online Advertising, with a large amount of commercial [4,12,13,29] and research work [11,20,28] recently published. Most approaches for solving the bid shading problem involve estimating the probability of win distribution, and then maximizing surplus [28]. These generally use parametric assumptions for the distribution, and there has been some discussion as to whether Log-Normal, Gamma, Beta, or other distributions are most effective [8,38,41,44]. In this paper, we show evidence that online auctions generally diverge in interesting ways from classic distributions. In particular, real auctions generally exhibit significant structure, due to the way that humans set up campaigns and inventory floor prices [16,26]. Using these insights, we present a nonparametric method for Bid Shading which enables the exploitation of this deep structure. The algorithm has low time and space complexity, and is designed to operate within the challenging millisecond Service Level Agreements of Real-Time Bid Servers. We deploy it in one of the largest Demand Side Platforms in the United States, and show that it reliably out-performs best in class Parametric benchmarks. We conclude by suggesting some ways that the best aspects of parametric and nonparametric approaches could be combined.

MOTIVATION: Nanopore sequencing provides a real-time and portable solution to genomic sequencing, enabling better assembly, structural variant discovery and modified base detection than second generation technologies. The sequencing process generates a huge amount of data in the form of raw signal contained in fast5 files, which must be compressed to enable efficient storage and transfer. Since the raw data is inherently noisy, lossy compression has potential to significantly reduce space requirements without adversely impacting performance of downstream applications. RESULTS: We explore the use of lossy compression for nanopore raw data using two state-of-the-art lossy time-series compressors, and evaluate the tradeoff between compressed size and basecalling/consensus accuracy. We test several basecallers and consensus tools on a variety of datasets at varying depths of coverage, and conclude that lossy compression can provide 35-50% further reduction in compressed size of raw data over the state-of-the-art lossless compressor with negligible impact on basecalling accuracy (≲0.2% reduction) and consensus accuracy (≲0.002% reduction). In addition, we evaluate the impact of lossy compression on methylation calling accuracy and observe that this impact is minimal for similar reductions in compressed size, although further evaluation with improved benchmark datasets is required for reaching a definite conclusion. The results suggest the possibility of using lossy compression, potentially on the nanopore sequencing device itself, to achieve significant reductions in storage and transmission costs while preserving the accuracy of downstream applications. AVAILABILITYAND IMPLEMENTATION: The code is available at https://github.com/shubhamchandak94/lossy_compression_evaluation. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

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.

We study common randomness generation problems where$n$players aim to generatesamesequences of random coin flips where some subsets of the players share an independent common coin which can be tossed multiple times, and there is a publicly seen blackboard through which the players communicate with each other. We provide a tight representation of the optimal communication rates via linear programming, and more importantly, propose explicit algorithms for the optimal distributed simulation for a wide class of hypergraphs. In particular, the optimal communication rate in complete hypergraphs is still achievable in sparser hypergraphs containing a path-connected cycle-free cluster of topologically connected components. Some key steps in analyzing the upper bounds rely on two different definitions of connectivity in hypergraphs, which may be of independent interest.

Time series data compression is emerging as an important problem with the growth in IoT devices and sensors. Due to the presence of noise in these datasets, lossy compression can often provide significant compression gains without impacting the performance of downstream applications. In this work, we propose an error-bounded lossy compressor, LFZip, for multivariate floating-point time series data that provides guaranteed reconstruction up to user-specified maximum absolute error. The compressor is based on the prediction-quantization-entropy coder framework and benefits from improved prediction using linear models and neural networks. We evaluate the compressor on several time series datasets where it outperforms the existing state-of-the-art error-bounded lossy compressors. The code and data are available at https://github.com/shubhamchandak94/LFZip.

As magnetization and semiconductor based storage technologies approach their limits, bio-molecules, such as DNA, have been identified as promising media for future storage systems, due to their high storage density (petabytes/gram) and long-term durability (thousands of years). Furthermore, nanopore DNA sequencing enables high-throughput sequencing using devices as small as a USB thumb drive and thus is ideally suited for DNA storage applications. Due to the high insertion/deletion error rates associated with base-called nanopore reads, current approaches rely heavily on consensus among multiple reads and thus incur very high reading costs. We propose a novel approach which overcomes the high error rates in basecalled sequences by integrating a Viterbi error correction decoder with the basecaller, enabling the decoder to exploit the soft information available in the deep learning based basecaller pipeline. Using convolutional codes for error correction, we experimentally observed 3x lower reading costs than the state-of-the-art techniques at comparable writing costs.The code, data and Supplementary Material is available at https://github.com/shubhamchandak94/nanopore_dna_storage.

Lossy image compression has been studied extensively in the context of typical loss functions such as RMSE, MS-SSIM, etc. However, it is not well understood what loss function might be most appropriate for human perception. Furthermore, the availability of massive public image datasets appears to have hardly been exploited in image compression. In this work, we perform compression experiments in which one human describes images to another, using publicly available images and text instructions. These image reconstructions are rated by human scorers on the Amazon Mechanical Turk platform and compared to reconstructions obtained by existing image compressors. In our experiments, the humans outperform the state of the art compressor WebP in the MTurk survey on most images, which shows that there is significant room for improvement in image compression for human perception. The images, results and additional data is available at https://compression.stanford.edu/human-compression.

For reliable transmission across a noisy communication channel, classical results from information theory show that it is asymptotically optimal to separate out the source and channel coding processes. However, this decomposition can fall short in the finite bit-length regime, as it requires non-trivial tuning of hand-crafted codes and assumes infinite computational power for decoding. In this work, we propose to jointly learn the encoding and decoding processes using a new discrete variational autoencoder model. By adding noise into the latent codes to simulate the channel during training, we learn to both compress and error-correct given a fixed bit-length and computational budget. We obtain codes that are not only competitive against several separation schemes, but also learn useful robust representations of the data for downstream tasks such as classification. Finally, inference amortization yields an extremely fast neural decoder, almost an order of magnitude faster compared to standard decoding methods based on iterative belief propagation.

MOTIVATION: High-Throughput Sequencing technologies produce huge amounts of data in the form of short genomic reads, associated quality values and read identifiers. Because of the significant structure present in these FASTQ datasets, general-purpose compressors are unable to completely exploit much of the inherent redundancy. Although there has been a lot of work on designing FASTQ compressors, most of them lack in support of one or more crucial properties, such as support for variable length reads, scalability to high coverage datasets, pairing-preserving compression and lossless compression. RESULTS: In this work, we propose SPRING, a reference-free compressor for FASTQ files. SPRING supports a wide variety of compression modes and features, including lossless compression, pairing-preserving compression, lossy compression of quality values, long read compression and random access. SPRING achieves substantially better compression than existing tools, for example, SPRING compresses 195 GB of 25× whole genome human FASTQ from Illumina's NovaSeq sequencer to less than 7 GB, around 1.6× smaller than previous state-of-the-art FASTQ compressors. SPRING achieves this improvement while using comparable computational resources. AVAILABILITY AND IMPLEMENTATION: SPRING can be downloaded from https://github.com/shubhamchandak94/SPRING. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

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.

We show through case studies that it is easier to estimate the fundamental limits of data processing than to construct the explicit algorithms to achieve those limits. Focusing on binary classification, data compression, and prediction under logarithmic loss, we show that in the finite space setting, when it is possible to construct an estimator of the limits with vanishing error with n samples, it may require at least n ln n samples to construct an explicit algorithm to achieve the limits.

We present \emph{Local Moment Matching (LMM)}, a unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance. We construct an efficiently computable estimator that achieves the minimax rates in estimating the distribution up to permutation, and show that the plug-in approach of our unlabeled distribution estimator is “universal" in estimating symmetric functionals of discrete distributions. Instead of doing best polynomial approximation explicitly as in existing literature of functional estimation, the plug-in approach conducts polynomial approximation implicitly and attains the optimal sample complexity for the entropy, power sum and support size functionals.

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 under squared $\ell_2$ loss for a large class of 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, and dense/sparse Gaussian location models 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.

We consider the problem of estimating high-dimensional and nonparametric distributions in distributed networks, where each sensor in the network observes an independent sample from the underlying distribution and can communicate it to a central processor by writing at most k bits on a public blackboard. We obtain matching upper and lower bounds for the minimax risk of estimating the underlying distribution under L1loss. Our results reveal that the minimax risk reduces exponentially in k. Instead of relying on strong data processing inequalities for the converse as commonly done in the literature, we build on a new representation of the communication constraint, which leads to a tight characterization of the problem.

In new applications of data compression, it is desired to have random access to any block of the compressed dataset (without the need to decompress the entire compressed sequence and thus accessing all the stored bits in memory). In this work, we analyze the problem of universal data compression with random access. Building on the work of Mazumdar, Chandar, and Wornell (2015), we discuss a systematic scheme to achieve close to optimal compression with finite random access. We first analyze the performance of the scheme for i.i.d sources. Using the gained intuition, for the more general class of Markov sources, we show the existence of finite random access compression schemes. Finally, we discuss a generic scheme which can be used to convert any universal compressor (e.g., Lempel-Ziv based schemes) into a finite random access universal compressor.

For any Markov source, there exist universal codes whose normalized codelength approaches the Shannon limit asymptotically as the number of samples goes to infinity. This paper investigates how fast the gap between the normalized codelength of the “best” universal compressor and the Shannon limit (i.e. the compression redundancy) vanishes non-asymptotically in terms of the alphabet size and mixing time of the Markov source. We show that, for Markov sources whose relaxation time is at least 1+ [((2+c))/(√k)], where k is the state space size (and c > 0 is a constant), the phase transition for the number of samples required to achieve vanishing compression redundancy is precisely Θ(k2).

Entropy estimation is one of the prototypical problems in distribution property testing. To consistently estimate the Shannon entropy of a distribution on $S$ elements with independent samples, the optimal sample complexity scales sublinearly with $S$ as $\Theta(\frac{S}{\log S})$ as shown by Valiant and Valiant \cite{Valiant--Valiant2011}. Extending the theory and algorithms for entropy estimation to dependent data, this paper considers the problem of estimating the entropy rate of a stationary reversible Markov chain with $S$ states from a sample path of $n$ observations. We show that \begin{itemize} \item Provided the Markov chain mixes not too slowly, \textit{i.e.}, the relaxation time is at most $O(\frac{S}{\ln^3 S})$, consistent estimation is achievable when $n \gg \frac{S^2}{\log S}$. \item Provided the Markov chain has some slight dependency, \textit{i.e.}, the relaxation time is at least $1+\Omega(\frac{\ln^2 S}{\sqrt{S}})$, consistent estimation is impossible when $n \lesssim \frac{S^2}{\log S}$. \end{itemize} Under both assumptions, the optimal estimation accuracy is shown to be $\Theta(\frac{S^2}{n \log S})$. In comparison, the empirical entropy rate requires at least $\Omega(S^2)$ samples to be consistent, even when the Markov chain is memoryless. In addition to synthetic experiments, we also apply the estimators that achieve the optimal sample complexity to estimate the entropy rate of the English language in the Penn Treebank and the Google One Billion Words corpora, which provides a natural benchmark for language modeling and relates it directly to the widely used perplexity measure.

Motivation: New Generation Sequencing (NGS) technologies for genome sequencing produce large amounts of short genomic reads per experiment, which are highly redundant and compressible. However, general-purpose compressors are unable to exploit this redundancy due to the special structure present in the data. Results: We present a new algorithm for compressing reads both with and without preserving the read order. In both cases, it achieves 1.4×-2× compression gain over state-of-the-art read compression tools for datasets containing as many as 3 billion Illumina reads. Our tool is based on the idea of approximately reordering the reads according to their position in the genome using hashed substring indices. We also present a systematic analysis of the read compression problem and compute bounds on fundamental limits of read compression. This analysis sheds light on the dynamics of the proposed algorithm (and read compression algorithms in general) and helps understand its performance in practice. The algorithm compresses only the read sequence, works with unaligned FASTQ files, and does not require a reference. Contact: [email protected]. Supplementary information: Supplementary material are available at Bioinformatics online. The proposed algorithm is available for download at https://github.com/shubhamchandak94/HARC.

Bioinformatics (2015) 31(19), 3122–3129 The authors of the above article wish to inform readers that a post-production correction has been made to add missing funding information: NIH grant U01 CA198943.

We consider the problem of estimating the L1distance 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∥1requires new techniques and insights beyond the approximation-based method of functional estimation by Jiao et al.

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.

The affordability of DNA sequencing has led to unprecedented volumes of genomic data. These data must be stored, processed, and analyzed. The most popular format for genomic data is the SAM format, which contains information such as alignment, quality values, etc. These files are large (on the order of terabytes), which necessitates compression. In this work we propose a new reference-based compressor for SAM files, which can accommodate different levels of compression, based on the specific needs of the user. In particular, the proposed compressor GeneComp allows the user to perform lossy compression of the quality scores, which have been proven to occupy more than half of the compressed file (when losslessly compressed). We show that the proposed compressor GeneComp overall achieves better compression ratios than previously proposed algorithms when working on lossless mode.

Summary form only given. We propose a method and algorithm for lossless compression of tabular data - including, for example, machine learning datasets, server logs and genomic datasets. Superior compression ratios are achieved by exploiting dependencies between the fields (or "features") in the dataset. The algorithm compresses the records w.r.t. a probabilistic graphical model - specifically an optimized forest, where each feature is a node. The work extends a method known as a Chow-Liu tree by incorporating a more accurate correction term to the cost function, which corresponds to the size required to describe the model itself. Additional features of the algorithm are efficient coding of the metadata (such as probability distributions), as well as data relabeling in order to cope with large datasets and alphabets. We test the algorithm on several datasets, and demonstrate an improvement in the compression rates of between 2X and 5X compared to gzip. The larger improvements are observed for very large datasets, such as the Criteo click prediction dataset which was published as part of a recent Kaggle competition.

We propose a framework to analyze and quantify the bias in adaptive data analysis. It generalizes that proposed by Russo and Zou'15, applying to measurements whose moment generating function exists, measurements with a finite p-norm, and measurements in general Orlicz spaces. We introduce a new class of dependence measures which retain key properties of mutual information while more effectively quantifying the exploration bias for heavy tailed distributions. We provide examples of cases where our bounds are nearly tight in situations where the original framework of Russo and Zou'15 does not apply.

Recent advancements in sequencing technology have led to a drastic reduction in genome sequencing costs. This development has generated an unprecedented amount of data that must be stored, processed, and communicated. To facilitate this effort, compression of genomic files has been proposed. Specifically, lossy compression of quality scores is emerging as a natural candidate for reducing the growing costs of storage. A main goal of performing DNA sequencing in population studies and clinical settings is to identify genetic variation. Though the field agrees that smaller files are advantageous, the cost of lossy compression, in terms of variant discovery, is unclear.Bioinformatic algorithms to identify SNPs and INDELs use base quality score information; here, we evaluate the effect of lossy compression of quality scores on SNP and INDEL detection. Specifically, we investigate how the output of the variant caller when using the original data differs from that obtained when quality scores are replaced by those generated by a lossy compressor. Using gold standard genomic datasets and simulated data, we are able to analyze how accurate the output of the variant calling is, both for the original data and that previously lossily compressed. We show that lossy compression can significantly alleviate the storage while maintaining variant calling performance comparable to that with the original data. Further, in some cases lossy compression can lead to variant calling performance that is superior to that using the original file. We envisage our findings and framework serving as a benchmark in future development and analyses of lossy genomic data compressors.

This special issue contains papers on models and methods in the science of information, along with their applications in diverse domains.

We consider the problem of estimating functionals of discrete distributions, and focus on a tight (up to universal multiplicative constants for each specific functional) nonasymptotic analysis of the worst case squared error risk of widely used estimators. We apply concentration inequalities to analyze the random fluctuation of these estimators around their expectations and the theory of approximation using positive linear operators to analyze the deviation of their expectations from the true functional, namely their bias. We explicitly characterize the worst case squared error risk incurred by the maximum likelihood estimator (MLE) in estimating the Shannon entropy H(P) = Σi=1S-piln pi, and the power sum Fα(P) = Σi=1Spiα, α > 0, up to universal multiplicative constants for each fixed functional, for any alphabet size S ≤ ∞ and sample size n for which the risk may vanish. As a corollary, for Shannon entropy estimation, we show that it is necessary and sufficient to have n ≫ S observations for the MLE to be consistent. In addition, we establish that it is necessary and sufficient to consider n ≫ S1/αsamples for the MLE to consistently estimate Fα(P), 01/α/ ln S samples, which implies that the MLE has a strictly sub-optimal sample complexity. When 1-2(α-1)for infinite alphabet size, while the minimax squared error rate is (n ln n)-2(α-1). When α ≥ 3/2, the MLE achieves the minimax optimal rate n-1regardless of the alphabet size. As an application of the general theory, we analyze the Dirichlet prior smoothing techniques for Shannon entropy estimation. In this context, one approach is to plug-in the Dirichlet prior smoothed distribution into the entropy functional, while the other one is to calculate the Bayes estimator for entropy under the Dirichlet prior for squared error, which is the conditional expectation. We show that in general such estimators do not improve over the maximum likelihood estimator. No matter how we tune the parameters in the Dirichlet prior, this approach cannot achieve the minimax rates in entropy estimation. The performance of the minimax rate-optimal estimator with n samples is essentially at least as good as that of Dirichlet smoothed entropy estimators with n ln n samples.

Fundamental relations between information and estimation have been established in the literature for the discrete-time Gaussian and Poisson channels. In this paper, we demonstrate that such relations hold for a much larger class of observation models. We introduce the natural family of discrete-time Lévy channels where the distribution of the output conditioned on the input is infinitely divisible. For Lévy channels, we establish new representations relating the mutual information between the channel input and output to an optimal expected estimation loss, thereby unifying and considerably extending results from the Gaussian and Poisson settings. We demonstrate the richness of our results by working out two examples of Lévy channels, namely the gamma channel and the negative binomial channel, with corresponding relations between information and estimation. Extensions to the setting of mismatched estimation are also presented.

For any binary-input channel with perfect state information at the decoder, if the mutual information between the noisy state observation at the encoder and the true channel state is below a positive threshold determined solely by the state distribution, then the capacity is the same as that with no encoder side information. A complementary phenomenon is revealed for the generalized probing capacity. Extensions beyond binary-input channels are developed.

Massive amounts of sequencing data are being generated thanks to advances in sequencing technology and a dramatic drop in the sequencing cost. Storing and sharing this large data has become a major bottleneck in the discovery and analysis of genetic variants that are used for medical inference. As such, lossless compression of this data has been proposed. Of the compressed data, more than 70% correspond to quality scores, which indicate the sequencing machine reliability when calling a particular basepair. Thus, to further improve the compression performance, lossy compression of quality scores is emerging as the natural candidate. Since the data is used for genetic variants discovery, lossy compressors for quality scores are analyzed in terms of their rate-distortion performance, as well as their effect on the variant callers. Previously proposed algorithms do not do well under all performance metrics, and are hence unsuitable for certain applications. In this work we propose a new lossy compressor that first performs a clustering step, by assuming all the quality scores sequences come from a mixture of Markov models. Then, it performs quantization of the quality scores based on the Markov models. Each quantizer targets a specific distortion to optimize for the overall rate-distortion performance. Finally, the quantized values are compressed by an entropy encoder. We demonstrate that the proposed lossy compressor outperforms the previously proposed methods under all analyzed distortion metrics. This suggests that the effect that the proposed algorithm will have on any downstream application will likely be less noticeable than that of previously proposed lossy compressors. Moreover, we analyze how the proposed lossy compressor affects Single Nucleotide Polymorphism (SNP) calling, and show that the variability introduced on the calls is considerably smaller than the variability that exists between different methodologies for SNP calling.

Massive amounts of sequencing data are being generated thanks to advances in sequencing technology and a dramatic drop in the sequencing cost. Much of the raw data are comprised of nucleotides and the corresponding quality scores that indicate their reliability. The latter are more difficult to compress and are themselves noisy. Lossless and lossy compression of the quality scores has recently been proposed to alleviate the storage costs, but reducing the noise in the quality scores has remained largely unexplored. This raw data is processed in order to identify variants; these genetic variants are used in important applications, such as medical decision making. Thus improving the performance of the variant calling by reducing the noise contained in the quality scores is important. We propose a denoising scheme that reduces the noise of the quality scores and we demonstrate improved inference with this denoised data. Specifically, we show that replacing the quality scores with those generated by the proposed denoiser results in more accurate variant calling in general. Moreover, a consequence of the denoising is that the entropy of the produced quality scores is smaller, and thus significant compression can be achieved with respect to lossless compression of the original quality scores. We expect our results to provide a baseline for future research in denoising of quality scores. The code used in this work as well as a Supplement with all the results are available at http://web.stanford.edu/~iochoa/DCCdenoiser_CodeAndSupplement.zip.

We consider the problem of estimating the L1distance between two discrete probability measures P and Q from empirical data in a nonasymptotic and large alphabet setting. We construct minimax rate-optimal estimators for L1(P,Q) when Q is either known or unknown, and show that the performance of the optimal estimators with n samples is essentially that of the Maximum Likelihood Estimators (MLE) with n ln n samples. Hence, we demonstrate that the effective sample size enlargement phenomenon, discovered and discussed in Jiao et al. (2015), holds for this problem as well. However, the construction of optimal estimators for L1(P,Q) requires new techniques and insights outside the scope of the Approximation methodology of functional estimation in Jiao et al. (2015).

Fundamental relations between information and estimation have been established in the literature for the Gaussian and Poisson channels. In this work, 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 continuous time semi-martingale, and the channel input modulates the characteristics of the semi-martingale. For these channels, which includes as a special case the 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 results in this work can be viewed as the continuous-time analogues of recent generalizations for relations between information and estimation for scalar transformations via Lévy channels.

We define and characterize the “chained” Kullback-Leibler divergence minwD(p||w) + D(w||q) minimized over all intermediate distributions w and the analogous k-fold chained K-L divergence min D(p||wk -1) + ... + D(w2||w1) + D(w1||q) minimized over the entire path (w1, ... wk -1). This quantity arises in a large deviations analysis of a Markov chain on the set of types - the Wright-Fisher model of neutral genetic drift: a population with allele distribution q produces offspring with allele distribution w, which then produce offspring with allele distribution p, and so on. The chained divergences enjoy some of the same properties as the K-L divergence (like joint convexity in the arguments) and appear in k-step versions of some of the same settings as the K-L divergence (like information projections and a conditional limit theorem). We further characterize the optimal k-step "path" of distributions appearing in the definition and apply our findings in a large deviations analysis of the Wright-Fisher process. We make a connection to information geometry via the previously studied continuum limit, where the number of steps tends to infinity, and the limiting path is a geodesic in the Fisher information metric. Finally, we offer a thermodynamic interpretation of the chained divergence (as the rate of operation of an appropriately defined Maxwell's demon) and we state some natural extensions and applications (a k-step mutual information and k-step maximum likelihood inference). We release code for computing the objects we study.

For any binary-input channel with perfect state information at the decoder, if the mutual information between the noisy state observation at the encoder and the true channel state is below a positive threshold determined solely by the state distribution, then the capacity is the same as that with no encoder side information. A complementary phenomenon is revealed for a similarly defined quantity.

Massive amounts of sequencing data are being generated thanks to advances in sequencing technology and a dramatic drop in the sequencing cost. Much of the data are comprised of nucleotides and the corresponding quality scores that indicate their reliability. The latter are more difficult to compress and are themselves noisy. As a result, lossy compression of the quality scores has recently been proposed to alleviate the storage costs. Further, it has been shown that lossy compression, at some specific rates, can achieve a performance on variant calling similar to that achieved with the lossless compressed data. We propose CROMqs, a new lossy compressor for the quality scores with the property of "infinitesimal successive refinability". This property allows the decoder to decompress the data iteratively without the need of agreeing with the encoder on a specific rate prior to compression. This characteristic is particularly amenable in practice, as in most cases the appropriate rate at which the lossy compressor should operate can not be established prior to compression. Further, this property can be of interest in scenarios involving streaming of genomic data. CROMqs is the first infinitesimal successive refinement lossy compressor for the quality scores in the literature, and we show that it obtains a comparable rate-distortion performance to previously proposed algorithms. Moreover, we also show that CROMqs achieves a comparable performance on variant calling to that of the lossless compressed data.

MOTIVATION: Data compression is crucial in effective handling of genomic data. Among several recently published algorithms, ERGC seems to be surprisingly good, easily beating all of the competitors. RESULTS: We evaluated ERGC and the previously proposed algorithms GDC and iDoComp, which are the ones used in the original paper for comparison, on a wide data set including 12 assemblies of human genome (instead of only four of them in the original paper). ERGC wins only when one of the genomes (referential or target) contains mixed-cased letters (which is the case for only the two Korean genomes). In all other cases ERGC is on average an order of magnitude worse than GDC and iDoComp. CONTACT: [email protected], [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: The dramatic decrease in the cost of sequencing has resulted in the generation of huge amounts of genomic data, as evidenced by projects such as the UK10K and the Million Veteran Project, with the number of sequenced genomes ranging in the order of 10 K to 1 M. Due to the large redundancies among genomic sequences of individuals from the same species, most of the medical research deals with the variants in the sequences as compared with a reference sequence, rather than with the complete genomic sequences. Consequently, millions of genomes represented as variants are stored in databases. These databases are constantly updated and queried to extract information such as the common variants among individuals or groups of individuals. Previous algorithms for compression of this type of databases lack efficient random access capabilities, rendering querying the database for particular variants and/or individuals extremely inefficient, to the point where compression is often relinquished altogether. RESULTS: We present a new algorithm for this task, called GTRAC, that achieves significant compression ratios while allowing fast random access over the compressed database. For example, GTRAC is able to compress a Homo sapiens dataset containing 1092 samples in 1.1 GB (compression ratio of 160), while allowing for decompression of specific samples in less than a second and decompression of specific variants in 17 ms. GTRAC uses and adapts techniques from information theory, such as a specialized Lempel-Ziv compressor, and tailored succinct data structures. AVAILABILITY AND IMPLEMENTATION: The GTRAC algorithm is available for download at: https://github.com/kedartatwawadi/GTRAC CONTACT: : [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

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 integer-and 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, the memory 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. AVAILABILITY AND IMPLEMENTATION: The smallWig software can be downloaded from: http://stanford.edu/~zhiyingw/smallWig/smallwig.html, http://publish.illinois.edu/milenkovic/, http://web.stanford.edu/~tsachy/. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The amount of information lost in sub-Nyquist sampling of a continuous-time Gaussian stationary process is quantified. We consider a combined source coding and sub-Nyquist reconstruction problem in which the input to the encoder is a noisy sub-Nyquist sampled version of the analog source. We first derive an expression for the mean squared error in the reconstruction of the process from a noisy and information rate-limited version of its samples. This expression is a function of the sampling frequency and the average number of bits describing each sample. It is given as the sum of two terms: minimum mean square error in estimating the source from its noisy but otherwise fully observed sub-Nyquist samples, and a second term obtained by reverse waterfilling over an average of spectral densities associated with the polyphase components of the source. We extend this result to multi-branch uniform sampling, where the samples are available through a set of parallel channels with a uniform sampler and a pre-sampling filter in each branch. Further optimization to reduce distortion is then performed over the pre-sampling filters, and an optimal set of pre-sampling filters associated with the statistics of the input signal and the sampling frequency is found. This results in an expression for the minimal possible distortion achievable under any analog-to-digital conversion scheme involving uniform sampling and linear filtering. These results thus unify the Shannon-Whittaker-Kotelnikov sampling theorem and Shannon rate-distortion theory for Gaussian sources.

We consider secure multi-terminal source coding problems in the presence of a public helper. Two main scenarios are studied: 1) source coding with a helper where the coded side information from the helper is eavesdropped by an external eavesdropper, 2) triangular source coding with a helper where the helper is considered as a public terminal. We are interested in how the helper can support the source transmission subject to a constraint on the amount of information leaked due to its public nature. We characterize the tradeoff between transmission rate, incurred distortion, and information leakage rate at the helper/eavesdropper in the form of a rate-distortion-leakage region for various classes of problems.

We investigate the second order asymptotics (source dispersion) of the successive refinement problem. Similar to the classical definition of a successively refinable source, we say that a source is strongly successively refinable if successive refinement coding can achieve the second order optimum rate (including the dispersion terms) at both decoders. We establish a sufficient condition for strong successive refinability. We show that any discrete source under Hamming distortion and the Gaussian source under quadratic distortion are strongly successively refinable. We also demonstrate how successive refinement ideas can be used in point-to-point lossy compression problems in order to reduce complexity. We give two examples, the binary-Hamming and Gaussian-quadratic cases, in which a layered code construction results in a low complexity scheme that attains optimal performance. For example, when the number of layers grows with the block length n, we show how to design an O(nlog(n)) algorithm that asymptotically achieves the rate-distortion bound.

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 (n2)/(logβn) per source symbol for β > 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.

We study the problem of compression for the purpose of similarity identification, where similarity is measured by the mean square Euclidean distance between vectors. While the asymptotical fundamental limits of the problem - the minimal compression rate and the error exponent - were found in a previous work, in this paper we focus on the nonasymptotic domain and on practical, implementable schemes. We first present a finite blocklength achievability bound based on shape-gain quantization: The gain (amplitude) of the vector is compressed via scalar quantization and the shape (the projection on the unit sphere) is quantized using a spherical code. The results are numerically evaluated and they converge to the asymptotic values as predicted by the error exponent. We then give a nonasymptotic lower bound on the performance of any compression scheme, and compare to the upper (achievability) bound. For a practical implementation of such a scheme, we use wrapped spherical codes, studied by Hamkins and Zeger, and use the Leech lattice as an example for an underlying lattice. As a side result, we obtain a bound on the covering angle of any wrapped spherical code, as a function of the covering radius of the underlying lattice.

We consider the problem of compressing discrete memory less data sequences for the purpose of similarity identification, first studied by Ahlswede et al. (1997). In this setting, a source sequence is compressed, where the goal is to be able to identify whether the original source sequence is similar to another given sequence (called the query sequence). There is no requirement that the source will be reproducible from the compressed version. In the case where no false negatives are allowed, a compression scheme is said to be reliable if the probability of error (false positive) vanishes as the sequence length grows. The minimal compression rate in this sense, which is the parallel of the classical rate distortion function, is called the identification rate. The rate at which the error probability vanishes is measured by its exponent, called the identification exponent (which is the analog of the classical excess distortion exponent). While an information-theoretic expression for the identification exponent was found in past work, it is uncomputable due to a dependency on an auxiliary random variable with unbounded cardinality. The main result of this paper is a cardinality bound on the auxiliary random variable in the identification exponent, thereby making the quantity computable (solving the problem that was left open by Ahlswede et al.). The new proof technique relies on the fact that the Lagrangian in the optimization problem (in the expression for the exponent) can be decomposed by coordinate (of the auxiliary random variable). Then a standard Caratheodory - style argument completes the proof.

The Dirichlet prior is widely used in estimating discrete distributions and functionals of discrete distributions. In terms of Shannon entropy estimation, one approach is to plug-in the Dirichlet prior smoothed distribution into the entropy functional, while the other one is to calculate the Bayes estimator for entropy under the Dirichlet prior for squared error, which is the conditional expectation. We show that in general they do not improve over the maximum likelihood estimator, which plugs-in the empirical distribution into the entropy functional. No matter how we tune the parameters in the Dirichlet prior, this approach cannot achieve the minimax rates in entropy estimation, as recently characterized by Jiao, Venkat, Han, and Weissman [1], and Wu and Yang [2]. The performance of the minimax rate-optimal estimator with n samples is essentially at least as good as that of the Dirichlet smoothed entropy estimators with n ln n samples. We harness the theory of approximation using positive linear operators for analyzing the bias of plug-in estimators for general functionals under arbitrary statistical models, thereby further consolidating the interplay between these two fields, which was thoroughly exploited by Jiao, Venkat, Han, and Weissman [3] in estimating various functionals of discrete distributions. We establish new results in approximation theory, and apply them to analyze the bias of the Dirichlet prior smoothed plug-in entropy estimator. This interplay between bias analysis and approximation theory is of relevance and consequence far beyond the specific problem setting in this paper.

We consider estimating the Shannon entropy of a discrete distribution P from n i.i.d. samples. Recently, Jiao, Venkat, Han, and Weissman (JVHW), and Wu and Yang constructed approximation theoretic estimators that achieve the minimax L2rates in estimating entropy. Their estimators are consistent given n ≫ S/lnS samples, where S is the support size, and it is the best possible sample complexity. In contrast, the Maximum Likelihood Estimator (MLE), which is the empirical entropy, requires n ≫ S samples. In the present paper we significantly refine the minimax results of existing work. To alleviate the pessimism of minimaxity, we adopt the adaptive estimation framework, and show that the JVHW estimator is an adaptive estimator, i.e., it achieves the minimax rates simultaneously over a nested sequence of subsets of distributions P, without knowing the support size S or which subset P lies in. We also characterize the maximum risk of the MLE over this nested sequence, and show, for every subset in the sequence, that the performance of the minimax rate-optimal estimator with n samples is essentially that of the MLE with n ln n samples, thereby further substantiating the generality of “effective sample size enlargement” phenomenon discovered by Jiao, Venkat, Han, and Weissman. We provide a “pointwise” explanation of the sample size enlargement phenomenon, which states that for sufficiently small probabilities, the bias function of the JVHW estimator with n samples is nearly that of the MLE with n ln n samples.

We analyze the problem of discrete distribution estimation under ℓ1loss. We provide non-asymptotic upper and lower bounds on the maximum risk of the empirical distribution (the maximum likelihood estimator), and the minimax risk in regimes where the alphabet size S may grow with the number of observations n. We show that among distributions with bounded entropy H, the asymptotic maximum risk for the empirical distribution is 2H / ln n, while the asymptotic minimax risk is H / ln n. Moreover, a hard-thresholding estimator, whose threshold does not depend on the unknown upper bound H, is asymptotically minimax. We draw connections between our work and the literature on density estimation, entropy estimation, total variation distance (ℓ1divergence) estimation, joint distribution estimation in stochastic processes, normal mean estimation, and adaptive estimation.

The Maximum Likelihood Estimator (MLE) is widely used in estimating information measures, and involves “plugging-in” the empirical distribution of the data to estimate a given functional of the unknown distribution. In this work we propose a general framework and procedure to analyze the nonasymptotic performance of the MLE in estimating functionals of discrete distributions, under the worst-case mean squared error criterion. We show that existing theory is insufficient for analyzing the bias of the MLE, and propose to apply the theory of approximation using positive linear operators to study this bias. The variance is controlled using the well-known tools from the literature on concentration inequalities. Our techniques completely characterize the maximum L2risk incurred by the MLE in estimating the Shannon entropy H(P) = Σi=1S-piln pi, and Fα(P) = Σi=1Spiαup to a multiplicative constant. As a corollary, for Shannon entropy estimation, we show that it is necessary and sufficient to have n ≪ S observations for the MLE to be consistent, where S represents the support size. In addition, we obtain that it is necessary and sufficient to consider n ≪ S1/αsamples for the MLE to consistently estimate Fα(P); 01/α/ ln S samples, which implies that the MLE is strictly sub-optimal. When 12rate of convergence for the MLE is n-2(α-1)for infinite support size, while the minimax L2rate is (n ln n)-2(α-1). When α ≥ 3/2, the MLE achieves the minimax optimal L2convergence rate n-1regardless of the support size.

We propose a general methodology for the construction and analysis of minimax estimators for functionals of discrete distributions, where the support size S is unknown and may be comparable to the number of observations n. We illustrate the merit of our approach by thoroughly analyzing non-asymptotically the performance of the resulting schemes for estimating two important information measures: the entropy H(P) = Σi=1S-piln piand Fα(P) = Σi=1Spiα, α > 0. We obtain the minimax L2risks for estimating these functionals up to a universal constant. In particular, we demonstrate that our estimator achieves the optimal sample complexity n ≫ S / ln S for entropy estimation. We also demonstrate that the sample complexity for estimating Fα(P), 01/a/ln S, which can be achieved by our estimator and not by the popular plug-in Maximum Likelihood Estimator (MLE). For 12rate for estimating Fα(P) is (n ln n)-2(α-1)regardless of the support size, while the exact L2rate for the MLE is n-2(α-1). For all the above cases, the behavior of the minimax rate-optimal estimators with n samples is essentially that of the MLE with n ln n samples. Finally, we highlight the practical advantages of our schemes for the estimation of entropy and mutual information.

We establish two strong senses of universality of logarithmic loss as a distortion criterion in lossy compression: For any fixed length lossy compression problem under an arbitrary distortion criterion, we show that there is an equivalent lossy compression problem under logarithmic loss. In the successive refinement problem, if the first decoder operates under logarithmic loss, we show that any discrete memoryless source is successively refinable under an arbitrary distortion criterion for the second decoder.

MOTIVATION: Recent advancements in sequencing technology have led to a drastic reduction in the cost of sequencing a genome. This has generated an unprecedented amount of genomic data that must be stored, processed and transmitted. To facilitate this effort, we propose a new lossy compressor for the quality values presented in genomic data files (e.g. FASTQ and SAM files), which comprise roughly half of the storage space (in the uncompressed domain). Lossy compression allows for compression of data beyond its lossless limit. RESULTS: The proposed algorithm QVZ exhibits better rate-distortion performance than the previously proposed algorithms, for several distortion metrics and for the lossless case. Moreover, it allows the user to define any quasi-convex distortion function to be minimized, a feature not supported by the previous algorithms. Finally, we show that QVZ-compressed data exhibit better performance in the genotyping than data compressed with previously proposed algorithms, in the sense that for a similar rate, a genotyping closer to that achieved with the original quality values is obtained. AVAILABILITY AND IMPLEMENTATION: QVZ is written in C and can be downloaded from https://github.com/mikelhernaez/qvz. CONTACT: [email protected] or [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: With the release of the latest next-generation sequencing (NGS) machine, the HiSeq X by Illumina, the cost of sequencing a Human has dropped to a mere $4000. Thus we are approaching a milestone in the sequencing history, known as the $1000 genome era, where the sequencing of individuals is affordable, opening the doors to effective personalized medicine. Massive generation of genomic data, including assembled genomes, is expected in the following years. There is crucial need for compression of genomes guaranteed of performing well simultaneously on different species, from simple bacteria to humans, which will ease their transmission, dissemination and analysis. Further, most of the new genomes to be compressed will correspond to individuals of a species from which a reference already exists on the database. Thus, it is natural to propose compression schemes that assume and exploit the availability of such references. RESULTS: We propose iDoComp, a compressor of assembled genomes presented in FASTA format that compresses an individual genome using a reference genome for both the compression and the decompression. In terms of compression efficiency, iDoComp outperforms previously proposed algorithms in most of the studied cases, with comparable or better running time. For example, we observe compression gains of up to 60% in several cases, including H.sapiens data, when comparing with the best compression performance among the previously proposed algorithms. AVAILABILITY: iDoComp is written in C and can be downloaded from: http://www.stanford.edu/~iochoa/iDoComp.html (We also provide a full explanation on how to run the program and an example with all the necessary files to run it.).

We study the problem of communicating a distributed correlated memoryless source over a memoryless network, from source nodes to destination nodes, under quadratic distortion constraints. We establish the following two complementary results: 1) for an arbitrary memoryless network, among all distributed memoryless sources of a given correlation, Gaussian sources are least compressible, that is, they admit the smallest set of achievable distortion tuples and 2) for any memoryless source to be communicated over a memoryless additive-noise network, among all noise processes of a given correlation, Gaussian noise admits the smallest achievable set of distortion tuples. We establish these results constructively by showing how schemes for the corresponding Gaussian problems can be applied to achieve similar performance for (source or noise) distributions that are not necessarily Gaussian but have the same covariance.

We compare the maximum achievable rates in single-carrier (SC) and orthogonal frequency-division multiplexing (OFDM) modulation schemes, under the practical assumptions of independent identically distributed finite alphabet inputs and linear intersymbol interference with additive Gaussian noise. We show that the Shamai-Laroia approximation serves as a bridge between the two rates: while it is well known that this approximation is often a lower bound on the SC achievable rate, it is revealed to also essentially upper bound the OFDM achievable rate. We apply information-estimation relations in order to rigorously establish this result for both general input distributions and to sharpen it for commonly used pulse-amplitude modulation (PAM) and quadratic-amplitude modulation constellations. To this end, novel bounds on minimum mean-square error estimation of PAM inputs to a scalar Gaussian channel are derived, which may be of general interest. Our results show that, under reasonable assumptions, optimal SC schemes may offer spectral efficiency significantly superior to that of OFDM, motivating further research of such systems.

We consider the problem of discrete distribution estimation under l1loss. We provide tight upper and lower bounds on the maximum risk of the empirical distribution (the maximum likelihood estimator), and the minimax risk in regimes where the support size S may grow with the number of observations n. We show that among distributions with bounded entropy H, the asymptotic maximum risk for the empirical distribution is 2H/ln n, while the asymptotic minimax risk is H/ ln n. Moreover, we show that a hard-thresholding estimator oblivious to the unknown upper bound H, is essentially minimax. However, if we constrain the estimates to lie in the simplex of probability distributions, then the asymptotic minimax risk is again 2H/ ln n. We draw connections between our work and the literature on density estimation, entropy estimation, total variation distance (I1divergence) estimation, joint distribution estimation in stochastic processes, normal mean estimation, and adaptive estimation.

The problem of performing similarity queries on compressed data is considered. We focus on the quadratic similarity measure, and study the fundamental tradeoff between compression rate, sequence length, and reliability of queries performed on the compressed data. For a Gaussian source, we show that the queries can be answered reliably if and only if the compression rate exceeds a given threshold-the identification rate-which we explicitly characterize. Moreover, when compression is performed at a rate greater than the identification rate, responses to queries on the compressed data can be made exponentially reliable. We give a complete characterization of this exponent, which is analogous to the error and excess-distortion exponents in channel and source coding, respectively. For a general source, we prove that, as with classical compression, the Gaussian source requires the largest compression rate among sources with a given variance. Moreover, a robust scheme is described that attains this maximal rate for any source distribution.

We consider a natural measure of relevance: the reduction in optimal prediction risk in the presence of side information. For any given loss function, this relevance measure captures the benefit of side information for performing inference on a random variable under this loss function. When such a measure satisfies a natural data processing property, and the random variable of interest has alphabet size greater than two, we show that it is uniquely characterized by the mutual information, and the corresponding loss function coincides with logarithmic loss. In doing so, our work provides a new characterization of mutual information, and justifies its use as a measure of relevance. When the alphabet is binary, we characterize the only admissible forms the measure of relevance can assume while obeying the specified data processing property. Our results naturally extend to measuring the causal influence between stochastic processes, where we unify different causality measures in the literature as instantiations of directed information.

We propose a general methodology for the construction and analysis of essentially minimax estimators for a wide class of functionals of finite dimensional parameters, and elaborate on the case of discrete distributions, where the support size S is unknown and may be comparable with or even much larger than the number of observations n. We treat the respective regions where the functional is nonsmooth and smooth separately. In the nonsmooth regime, we apply an unbiased estimator for the best polynomial approximation of the functional whereas, in the smooth regime, we apply a bias-corrected version of the maximum likelihood estimator (MLE). We illustrate the merit of this approach by thoroughly analyzing the performance of the resulting schemes for estimating two important information measures: 1) the entropy H(P) = ΣSi=1-piln piand 2) Fα(P) = ΣSi=1pαi, α > 0. We obtain the minimax L2rates for estimating these functionals. In particular, we demonstrate that our estimator achieves the optimal sample complexity n × S/ln S for entropy estimation. We also demonstrate that the sample complexity for estimating Fα(P), 01/α/ln S, which can be achieved by our estimator but not the MLE. For 12rate for estimating Fα(P) is (n ln n)-2(α-1)for infinite support size, while the maximum L2rate for the MLE is n-2(α-1). For all the above cases, the behavior of the minimax rate-optimal estimators with n samples is essentially that of the MLE (plug-in rule) with n ln n samples, which we term “effective sample size enlargement.” We highlight the practical advantages of our schemes for the estimation of entropy and mutual information. We compare our performance with various existing approaches, and demonstrate that our approach reduces running time and boosts the accuracy. Moreover, we show that the minimax rate-optimal mutual information estimator yielded by our framework leads to significant performance boosts over the Chow-Liu algorithm in learning graphical models. The wide use of information measure estimation suggests that the insights and estimators obtained in this paper could be broadly applicable.

We consider compression of sequences in a database so that similarity queries can be performed efficiently in the compressed domain. The fundamental limits for this problem setting, which characterize the trade off between compression rate and reliability of the answers to the queries, have been characterized in past work. However, how to approach these limits in practice has remained largely unexplored. Recently, we proposed a scheme for this task that is based on existing lossy compression algorithms, for the general case where the similarity measure satisfies a triangle inequality. Although it was shown that it achieves the fundamental limits for some cases, it is suboptimal in general. In this paper we propose a new scheme that also uses lossy compression algorithms as a building block, but with a carefully chosen distortion measure that is different than the one defining the similarity between sequences. The new scheme significantly improves the compression rate compared to the previously proposed scheme in many cases. For example, for binary sources and Hamming similarity measure, simulation results show a compression rate close to the fundamental limit, and an improvement over the previously proposed scheme of up to 55% (for the same reliability). The results shed light on the fact that compression for similarity identification is inherently different than classical lossy compression.

We study the problem of compression of a Gaussian vector for the purpose of similarity identification, where similarity is defined by the mean square Euclidean distance between vectors. While the asymptotical fundamental limits of the problem - the minimal compression rate and the error exponent - were found in a previous work, in this paper we focus on the nonasymptotic domain. We first present a finite blocklength achievability bound based on shape-gain quantization: The gain (amplitude) of the vector is compressed via scalar quantization, and the shape (the projection on the unit sphere) is quantized using a spherical code. The results are numerically evaluated, and they converge to the asymptotic values as predicted by the error exponent. For a practical implementation of such a scheme, we use wrapped spherical codes, studied by Hamkins and Zeger, and use the Leech lattice as an example for an underlying lattice. As a side result, we obtain a bound on the covering angle of any wrapped spherical code, as a function of the covering radius of the underlying lattice.

We study the problem of compressing a source for the goal of answering similarity queries from the compressed data. Unlike classical compression, here there is no requirement that the source be reproduced from the compressed form. For discrete memoryless sources and an arbitrary similarity measure, we fully characterize the minimal compression rate that allows query answers, that are reliable in the sense of having a vanishing false-positive probability, when false negatives are not allowed. The result is partially based on a previous work by Ahlswede et al. [1], and the inherently typical subset lemma plays a key role in the converse proof. We then discuss the performance that is attainable by using schemes that use lossy source codes as a building block, and show that such schemes are, in general, suboptimal. Finally, we discuss the problem of computing the fundamental limit, and present numerical results.

Four problems related to information divergence measures defined on finite alphabets are considered. In three of the cases we consider, we illustrate a contrast which arises between the binary-alphabet and larger-alphabet settings. This is surprising in some instances, since characterizations for the larger-alphabet settings do not generalize their binary-alphabet counterparts. For example, we show that f-divergences are not the unique decomposable divergences on binary alphabets that satisfy the data processing inequality, despite contrary claims in the literature.

We consider a natural measure of the benefit of side information: the reduction in optimal estimation risk when side information is available to the estimator. When such a measure satisfies a natural data processing property, and the source alphabet has cardinality greater than two, we show that it is uniquely characterized by the optimal estimation risk under logarithmic loss, and the corresponding measure is equal to mutual information. Further, when the source alphabet is binary, we characterize the only admissible forms the measure of predictive benefit can assume. These results unify many causality measures in the literature as instantiations of directed information, and present a natural axiomatic characterization of mutual information without requiring the sum or recursivity property.

Fundamental relations between information and estimation have been established in the literature for the scalar Gaussian and Poisson channels. In this work, we demonstrate that such relations hold for a much larger class of observation models. We introduce the natural family of scalar Lévy channels where the distribution of the output conditioned on the input is infinitely divisible. For Lévy channels, we establish new representations relating the mutual information between the channel input and output to an optimal estimation loss, thereby unifying and considerably extending results from the Gaussian and Poissonian settings. We demonstrate the richness of our results by working out two examples of Lévy channels, namely the Gamma channel and the Negative Binomial channel, with corresponding relations between information and estimation. Extensions to the setting of mismatched estimation are also presented.

We investigate the second order asymptotics (source dispersion) of the successive refinement problem. Similarly to the classical definition of a successively refinable source, we say that a source is strongly successively refinable if successive refinement coding can achieve the second order optimum rate (including the dispersion terms) at both receivers. We propose a sufficient condition for strong successive refinability. As a corollary, we show that any discrete source with Hamming distortion is strongly successively refinable. For a Gaussian source with quadratic distortion, we show directly that the source is strongly successively refinable.

We study communication over finite state channels (FSCs), where the encoder and the decoder can control the availability or the quality of noise-free feedback, which is fed back from the decoder to the encoder. Specifically, the instantaneous feedback is a function of an action taken by the encoder, an action taken by the decoder, and the channel output. Encoder and decoder actions take values from finite alphabet sets and may be subject to average cost constraints. We prove capacity results for such a setting by constructing a sequence of codes, using a simple scheme based on code tree, which generates channel input symbols along with encoder and decoder actions. We prove that the limit of this sequence exists, and provide an upper bound on the maximum achievable rate. Our upper and lower bounds coincide and hence yield the capacity for the case where the probability of initial state is positive for all states. Next, the capacity is given for indecomposable channels without intersymbol interference as the limit of normalized directed information between the input and output sequences, maximized over an appropriate set of causally conditioned distributions. As a special case of our framework, we characterize the capacity of coding on the backward link in FSCs, i.e., when the decoder sends limited-rate instantaneous coded noise-free feedback on the backward link. Finally, we propose an extension of the Blahut-Arimoto algorithm for evaluating the capacity when actions can be cost constrained and demonstrate its application in a few examples. Among these examples are those of to feed or not to feedback where the encoder takes binary actions that determine whether the current channel output will be fed back to the encoder, with a constraint on the fraction of channel outputs that are fed back.

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.

Four problems related to information divergence measures defined on finite alphabets are considered. In three of the cases we consider, we illustrate a contrast that arises between the binary-alphabet and larger alphabet settings. This is surprising in some instances, since characterizations for the larger alphabet settings do not generalize their binary-alphabet counterparts. In particular, we show that f-divergences are not the unique decomposable divergences on binary alphabets that satisfy the data processing inequality, thereby clarifying claims that have previously appeared in the literature. We also show that Kullback-Leibler (KL) divergence is the unique Bregman divergence, which is also an f-divergence for any alphabet size. We show that KL divergence is the unique Bregman divergence, which is invariant to statistically sufficient transformations of the data, even when nondecomposable divergences are considered. Like some of the problems we consider, this result holds only when the alphabet size is at least three.

Consider a binary modulo-additive noise channel with noiseless feedback. When the noise is a stationary and ergodic process Z, the capacity is 1- H(Z) (H(·) denoting the entropy rate). It is shown analogously that when the noise is a deterministic sequence z∞, the capacity under finite-state encoding and decoding is 1 - ρ̅(z∞), where ρ̅(·) is Lempel and Ziv's finite-state compressibility. This quantity, termed the porosity σ(·) 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.

We investigate the problem of continuous-time causal estimation under a minimax criterion. Let XT= (Xt,0 ≤ t ≤ T) be governed by the probability law Pθfrom a class of possible laws indexed by θ ∈ A, and YTbe the noise corrupted observations of XTavailable 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.

We consider finite state channels, where the state of the channel is its previous output. We refer to these as Previous Output is the STate (POST) channels. We first focus on POST(α) channels. These channels have binary inputs and outputs, where the state determines if the channel behaves as a Z or an S channel, both with parameter α. We show that the nonfeedback capacity of the POST(α) channel equals its feedback capacity, despite the memory of the channel. The proof of this surprising result is based on showing that the induced output distribution, when maximizing the directed information in the presence of feedback, can also be achieved by an input distribution that does not utilize the feedback. We show that this is a sufficient condition for the feedback capacity to equal the nonfeedback capacity for any finite state channel. We show that the result carries over from the POST(α) channel to a binary POST channel, where the previous output determines whether the current channel will be binary with parameters (a, b) or (b, a). Finally, we show that, in general, feedback may increase the capacity of a POST channel.

We consider the setting where actions can be used to modify a state sequence before compression. The minimum rate needed to losslessly describe the optimal modified sequence is characterized when the state sequence is either noncausally or causally available at the action encoder. The achievability is closely related to the optimal channel coding strategy for channel with states. We also extend the analysis to the lossy case.

The problem of performing similarity queries on compressed data is considered. We study the fundamental tradeoff between compression rate, sequence length, and reliability of queries performed on compressed data. For a Gaussian source and quadratic similarity criterion, we show that queries can be answered reliably if and only if the compression rate exceeds a given threshold - the identification rate - which we explicitly characterize. When compression is performed at a rate greater than the identification rate, responses to queries on the compressed data can be made exponentially reliable. We give a complete characterization of this exponent, which is analogous to the error and excess-distortion exponents in channel and source coding, respectively. For a general source, we prove that the identification rate is at most that of a Gaussian source with the same variance. Therefore, as with classical compression, the Gaussian source requires the largest compression rate. Moreover, a scheme is described that attains this maximal rate for any source distribution.

We consider finite state channels where the state of the channel is its previous output. We refer to such channels as POST (Previous Output is the STate) channels. Our focus is on a simple binary POST channel, with binary inputs and outputs where the state determines if the channel behaves as a Z or an S channel (of equal capacities). We show that the non feedback capacity equals the feedback capacity, despite the memory in the channel. The proof of this surprising result is based on showing that the induced output distribution, when maximizing the directed information in the presence of feedback, can also be achieved by an input distribution that is ignorant of the feedback. Indeed, we show that this is a necessary and sufficient condition for the feedback capacity to equal the non feedback capacity for any finite state channel.

We consider the problem of communicating a distributed correlated memoryless source over a memoryless network, from source nodes to destination nodes, under quadratic distortion constraints. We show the following two complementary results: (a) for an arbitrary memoryless network, among all distributed memoryless sources with a particular correlation, Gaussian sources are the worst compressible, that is, they admit the smallest set of achievable distortion tuples, and (b) for any arbitrarily distributed memoryless source to be communicated over a memoryless additive noise network, among all noise processes with a fixed correlation, Gaussian noise admits the smallest achievable set of distortion tuples. In each case, given a coding scheme for the corresponding Gaussian problem, we provide a technique for the construction of a new coding scheme that achieves the same distortion at the destination nodes in a non-Gaussian scenario with the same correlation structure.

We consider a multiple access channel with a large number of transmitters sending symbols from a constellation to the receiver of a multi-antenna base station. We investigate the joint decoding of the signals from all the users using a low complexity convex relaxation of the maximum likelihood decoder (constellation search). We show that, in a rich scattering environment, and in the asymptotic limit of a large number of transmitters, reliable communication is possible even without employing coding at the transmitters.

In this paper, we consider the problem of determining whether sequences X and Y, generated i.i.d. according to PX× PY, are equal given access only to the pair (Y, T(X)), where T(X) is a rate-R compressed version of X. In general, the rate R may not be sufficiently large to reliably determine whether X=Y. We precisely characterize this reliability - i.e., the exponential rate at which an error is made - as a function of R. Interestingly, the exponent turns out to be related to the Bhattacharyya distance between the distributions PXand PY. In addition, the scheme achieving this exponent is universal, i.e. does not depend on PX, PY.

Identities yielding optimal estimation interpretations for mutual information and relative entropy - paralleling those known for minimum mean squared estimation under additive Gaussian noise - were recently discovered for the Poisson channel by Atar and Weissman. We express these identities as equalities between expectations of the associated estimation and information theoretic random variables such as the actual estimation loss and the information density. By explicitly characterizing the relations between these random variables we show that they are related in much stronger pointwise senses that directly imply the known expectation identities while deepening our understanding of them. As an example for the nature of our results, consider the equality between the mutual information and the mean cumulative filtering loss of the optimal filter in continuous-time estimation. We show that the difference between the information density and the cumulative filtering loss is a martingale expressible as a stochastic integral. This explicit characterization not only directly recovers the previously known expectation relation, but allows to characterize other distributional properties of the random variables involved where some of the original objects of interest emerge in new and surprising roles. For example, we find that the increasing predictable part of the Doob-Meyer decomposition of the information density (which is a sub-martinagle) is nothing but the cumulative loss of the optimal filter.

We consider secure multi-terminal source coding problems in the presence of a public helper. Two main scenarios are studied: 1) source coding with a helper where the coded side information from the helper is eavesdropped by an external eavesdropper, 2) triangular source coding with a helper where the helper is considered as a public terminal. We are interested in how the helper can support the source transmission subject to a constraint on the amount of information leaked due to its public nature. We characterize the tradeoff between transmission rate, incurred distortion, and information leakage rate at the helper/eavesdropper in the form of a rate-distortion-leakage region for various classes of problems.

Unsupervised learning may be modeled by an extreme version of the universal channel coding problem. Suppose a channel decoder knows only that a randomly generated block code is being employed at the other end of a discrete memoryless channel. The channel statistics, the codebook, the code distribution, the rate, the blocklength, and even the input alphabet are unknown. Using a novel decoding measure, it is shown that the channel outputs may be correctly clustered with vanishing error probability at all rates under capacity. Results provide theoretical motivation for certain heuristic clustering techniques and, more widely, suggest that there are gains to be had via non-pairwise similarity measures.

We investigate the problem of continuous-time causal estimation under a minimax criterion. Let XT= {Xt, 0 ≤ t ≤ T} be governed by probability law Pθfrom some class of possible laws indexed by θ ∈ S, and YTbe the noise corrupted observations of XTavailable to the estimator. We characterize the estimator minimizing the worst case regret, where regret is the difference between the expected loss of the estimator and that optimized for the true law of XT. We then relate this 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 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. Also, the optimum minimax estimator is the Bayesian estimator assuming the capacity-achieving prior. Moreover, we show that this minimax estimator is not only minimizing the worst case regret but also essentially minimizing the regret for “most” of the other sources in the uncertainty set. We present a couple of examples for the construction of an approximately minimax filter via an approximation of the associated capacity achieving distribution.

We consider mean squared estimation of a continuous-time signal corrupted by additive white Gaussian noise. We investigate the trade-off between lookahead and estimation-loss under this model. We study the 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). The MMSE with lookahead is shown to converge exponentially rapidly to the non-causal error, with the exponent being the reciprocal of the non-causal error. 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.

Summary form only given. Among other extremal properties, Gaussian sources are hardest to compress and communicate over. We review the main results of and exhibiting the generality in which such extremal properties hold in compression, communication and coding over networks. These properties are established via operational arguments, bypassing elusive characterizations of fundamental performance limits: schemes tailored for the Gaussian case are harnessed for constructions of schemes that provably do essentially as well under any other source of the same covariance. The talk will highlight the main ideas behind these constructions and how the results, which were established for memoryless sources and channels, carry over to the presence of memory.

UNLABELLED: 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/

BACKGROUND: Next Generation Sequencing technologies have revolutionized many fields in biology by reducing the time and cost required for sequencing. As a result, large amounts of sequencing data are being generated. A typical sequencing data file may occupy tens or even hundreds of gigabytes of disk space, prohibitively large for many users. This data consists of both the nucleotide sequences and per-base quality scores that indicate the level of confidence in the readout of these sequences. Quality scores account for about half of the required disk space in the commonly used FASTQ format (before compression), and therefore the compression of the quality scores can significantly reduce storage requirements and speed up analysis and transmission of sequencing data. RESULTS: In this paper, we present a new scheme for the lossy compression of the quality scores, to address the problem of storage. Our framework allows the user to specify the rate (bits per quality score) prior to compression, independent of the data to be compressed. Our algorithm can work at any rate, unlike other lossy compression algorithms. We envisage our algorithm as being part of a more general compression scheme that works with the entire FASTQ file. Numerical experiments show that we can achieve a better mean squared error (MSE) for small rates (bits per quality score) than other lossy compression schemes. For the organism PhiX, whose assembled genome is known and assumed to be correct, we show that it is possible to achieve a significant reduction in size with little compromise in performance on downstream applications (e.g., alignment). CONCLUSIONS: QualComp is an open source software package, written in C and freely available for download at https://sourceforge.net/projects/qualcomp.

We study cooperation in multiterminal source coding models involving successive refinement. Specifically, we study the case of a single encoder and two decoders, where the encoder provides a common description to both the decoders and a private description to only one of the decoders. The decoders cooperate via cribbing, i.e., the decoder with access only to the common description is allowed to observe, in addition, a deterministic function of the reconstruction symbols produced by the other. We characterize the fundamental performance limits in the respective settings of noncausal, strictly causal, and causal cribbing. We use a coding scheme, referred to as Forward Encoding and Block Markov Decoding, which builds on one recently used by Cuff and Zhao for coordination via implicit communication. Finally, we use the insight gained to introduce and solve some dual-channel coding scenarios involving multiple-access channels with cribbing.

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.

We consider multiterminal source coding with a single encoder and multiple decoders where either the encoder or the decoders can take cost-constrained actions which affect the quality of the side information present at the decoders. For the scenario where decoders take actions, we characterize the rate-cost tradeoff region for lossless source coding, and give an achievability scheme for lossy source coding for two decoders which is optimum for a variety of special cases of interest. For the case where the encoder takes actions, we characterize the rate-cost tradeoff for a class of lossless source coding scenarios with multiple decoders. Finally, we also consider extensions to other multiterminal source coding settings with actions, and characterize the rate-distortion-cost tradeoff for a case of successive refinement with actions.

We consider the problem of estimating a signal corrupted by independent interference with the assistance of a cost-constrained helper who knows the interference causally or noncausally. When the interference is known causally, we characterize the minimum distortion incurred in estimating the desired signal. In the noncausal case, we present a general achievable scheme for discrete memoryless systems and novel lower bounds on the distortion for the binary and Gaussian settings. Our Gaussian setting coincides with that of assisted interference suppression introduced by Grover and Sahai. Our lower bound for this setting is based on the relation recently established by Verdú between divergence and minimum mean squared error. We illustrate with a few examples that this lower bound can improve on those previously developed. Our bounds also allow us to characterize the optimal distortion in several interesting regimes. Moreover, we show that causal and noncausal estimation are not equivalent for this problem. Finally, we consider the case where the desired signal is also available at the helper. We develop new lower bounds for this setting that improve on those previously developed, and characterize the optimal distortion up to a constant multiplicative factor for some regimes of interest.

Four estimators of the directed information rate between a pair of jointly stationary ergodic finite-alphabet processes are proposed, based on universal probability assignments. The first one is a Shannon–McMillan–Breiman-type estimator, similar to those used by Verdú in 2005 and Caiin 2006 for estimation of other information measures. We show the almost sure and$L_{1}$convergence properties of the estimator for any underlying universal probability assignment. The other three estimators map universal probability assignments to different functionals, each exhibiting relative merits such as smoothness, nonnegativity, and boundedness. We establish the consistency of these estimators in almost sure and$L_{1}$senses, and derive near-optimal rates of convergence in the minimax sense under mild conditions. These estimators carry over directly to estimating other information measures of stationary ergodic finite-alphabet processes, such as entropy rate and mutual information rate, with near-optimal performance and provide alternatives to classical approaches in the existing literature. Guided by these theoretical results, the proposed estimators are implemented using the context-tree weighting algorithm as the universal probability assignment. Experiments on synthetic and real data are presented, demonstrating the potential of the proposed schemes in practice and the utility of directed information estimation in detecting and measuring causal influence and delay.

We investigate the achievable error probability in communication over an AWGN discrete time memoryless channel with noiseless delayless rate-limited feedback. For the case where the feedback rate$R_{\scriptscriptstyle FB}$is lower than the data rate$R$transmitted over the forward channel, we show that the decay of the probability of error is at most exponential in blocklength, and obtain an upper bound for increase in the error exponent due to feedback. Furthermore, we show that the use of feedback in this case results in an error exponent that is at least$R_{\scriptscriptstyle FB}$higher than the error exponent in the absence of feedback. For the case where the feedback rate exceeds the forward rate ($R_{\scriptscriptstyle FB}\geq R$), we propose a simple iterative scheme that achieves a probability of error that decays doubly exponentially with the codeword blocklength$n$. More generally, for some positive integer$L$, we show that a$L$-th order exponential error decay is achievable if$R_{\scriptscriptstyle FB}\geq (L-1)R$. While the above results are proved under an average feedback rate constraint, we show that all the achievability results for$R_{\scriptscriptstyle FB}\geq R$hold in a more restrictive case where the feedback constraint is expressed in terms of the per-channel-use feedback rate. Our results show that the error exponent as a function of$R_{\scriptscriptstyle FB}$has a strong discontinuity at$R$, where it jumps from a finite value to infinity.

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.

We study cooperation in multi terminal source coding models involving successive refinement. Specifically, we study the case of a single encoder and two decoders, where the encoder provides a common description to both the decoders and a private description to only one of the decoders. The decoders cooperate via cribbing, i.e., the decoder with access only to the common description is allowed to observe, in addition, a deterministic function of the reconstruction symbols produced by the other. We characterize the fundamental performance limits in the respective settings of non-causal, strictly-causal and causal cribbing. We use a new coding scheme, referred to as Forward Encoding and Block Markov Decoding, which is a variant of one recently used by Cuff and Zhao for coordination via implicit communication. Finally, we use the insight gained to introduce and solve some dual channel coding scenarios involving Multiple Access Channels with cribbing.

We consider the problem of estimating a signal corrupted by independent interference in which the estimator (decoder) is aided by a helper (encoder) with a limited power budget that has knowledge of the interfering signal noncausally. In the Gaussian case, this problem is equivalent to the problem of Assisted Interference Suppression considered by Grover and Sahai and we obtain an improved lower bound for this problem using Verdú's relationship between mismatched estimation and relative entropy. We also extend our analysis to consider the case when the signal to be estimated, in addition to the interference, is known to the helper. We establish a lower bound that improves on those recently derived by Huang and Narayanan.

We consider the two-encoder multiterminal source coding problem subject to distortion constraints computed under logarithmic loss. We provide a single-letter description of the achievable rate distortion region for arbitrarily correlated sources with finite alphabets. In doing so, we also give the rate distortion region for the CEO problem under logarithmic loss. Notably, the Berger-Tung inner bound is tight in both settings.

We propose four approaches to estimating the directed information rate between a pair of jointly stationary ergodic processes with the help of universal probability assignments. The four approaches yield estimators with different merits such as nonnegativity and boundedness. We establish consistency of these estimators in various senses and derive near-optimal rates of convergence in the minimax sense under mild conditions. The estimators carry over directly to estimating other information measures of stationary ergodic processes, such as entropy rate and mutual information rate, and provide alternatives to classical approaches in the existing literature. Guided by the theoretical results, we use context tree weighting as the vehicle for the implementations of the proposed estimators. Experiments on synthetic and real data are presented, demonstrating the potential of the proposed schemes in practice and the efficacy of directed information estimation as a tool for detecting and measuring causality and delay.

Consider a binary modulo-additive noise channel with noiseless feedback. When the noise is a stationary and ergodic process Z, the capacity is 1 - H(Z) (H(·) denoting the entropy rate). It is shown analogously that when the noise is a deterministic sequence Z∞, the capacity under finite-state encoding and decoding is 1 - ρ̅(Z∞), where ρ̅(·) is Lempel and Ziv's finite-state compressibility. This quantity is termed the porosity ρ̅(·) of an individual noise sequence. A sequence of schemes are presented that universally achieve porosity for any noise sequence. These results may be interpreted both as a channel-coding counterpart to Ziv and Lempel's work in universal source coding, as well as an extension of the work by Lomnitz and Feder and Shayevitz and Feder on communication across modulo-additive channels.

We study the transmission of a single random variable across the Poisson channel, which takes a continuous-time waveform {λt: 0 ≤ λt≤ T} as an input, where 0 ≤ λt≤ A, for all 0 ≤ t ≤ T. The output of the channel is a non-homogeneous Poisson arrival process with rate λT. We explore the class of schemes that are optimal in the distortion exponent sense under mean squared loss. We determine a family of optimal encoders for this channel which achieves the minimum mean squared error. In addition, we characterize the distortion exponent for `separation' based schemes, and also provide an upper bound for the maximal distortion exponent across all joint source channel strategies under this setting.

In this paper we study the degraded broadcast channel with action dependent states and causal side information at the encoder. Two main models are studied: the case where the actions depend only on the messages, and the case where the actions can depend also on past values of the state. The latter model is referred to as actions with feedback. When the actions depend only on the messages, the full capacity region is derived. We then show that if the channel is physically degraded, then dependence of the actions on past values of the state does not increase its capacity region. We further demonstrate by an example that if the channel is stochastically degraded, action feedback can increase its capacity region. This situation resembles previous results on feedback in regular (state-independent) broadcast channels.

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 I-MMSE relationship of Guo et al.; the relative entropy and mismatched estimation relationship of Verdu; the relationship between causal estimation and mutual information of Duncan, and its extension to the presence of feedback by Kadota et al.; the relationship between causal and non-casual estimation of Guo et al., 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 AWGN 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 the mutual information by Duncan's result).

DNA sequencing technology has advanced to a point where storage is becoming the central bottleneck in the acquisition and mining of more data. Large amounts of data are vital for genomics research, and generic compression tools, while viable, cannot offer the same savings as approaches tuned to inherent biological properties. We propose an algorithm to compress a target genome given a known reference genome. The proposed algorithm first generates a mapping from the reference to the target genome, and then compresses this mapping with an entropy coder. As an illustration of the performance: applying our algorithm to James Watson's genome with hg18 as a reference, we are able to reduce the 2991 megabyte (MB) genome down to 6.99 MB, while Gzip compresses it to 834.8 MB.

We consider the k-encoder source coding problem with a quadratic distortion measure. We show that among all source distributions with a given covariance matrix K, the jointly Gaussian source requires the highest rates in order to meet a given set of distortion constraints.

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.

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=\gamma_{0}$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$\gamma_{0}$. 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.

In this paper, we consider the cascade and triangular rate-distortion problems where the same side information is available at the source node and user 1, and the side information available at user 2 is a degraded version of the side information at the source node and user 1. We characterize the rate-distortion region for these problems. For the cascade setup, we show that, at user 1, decoding and rebinning the codeword sent by the source node for user 2 is optimum. We then extend our results to the two-way cascade and triangular setting, where the source node is interested in lossy reconstruction of the side information at user 2 via a rate limited link from user 2 to the source node. We characterize the rate-distortion regions for these settings. Complete explicit characterizations for all settings are given in the quadratic Gaussian case. We conclude with two further extensions: a triangular source coding problem with a helper, and an extension of our two-way cascade setting in the quadratic Gaussian case.

We present a new lossy compressor for finite-alphabet sources. For coding a sequence xn, the encoder starts by assigning a certain cost to each possible reconstruction sequence. It then finds the one that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of each sequence is a linear combination of its distance from the sequence xnand a linear function of its kthorder empirical distribution. The structure of the cost function allows the encoder to employ the Viterbi algorithm to find the sequence with minimum cost. We identify a choice of the coefficients used in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance for any stationary ergodic source, in the limit of large , provided that increases as o(log n). Iterative techniques for approximating the coefficients, which alleviate the computational burden of finding the optimal coefficients, are proposed and studied.

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.

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

We establish results assessing the fundamental limits on reliable communication over Finite State Channels (FSCs), when the encoder and the decoder can control the availability or the quality of the feedback. The instantaneous feedback is a function of a cost constrained action taken by the encoder, a cost constrained action taken by the decoder, and the channel output. Achievability is through construction of a sequence of convergent achievable rates, using a simple scheme based on `code tree' generation, that generates channel input symbols along with encoder and decoder actions. For a given block length N, we give an upper bound on the maximum achievable rate. For stationary indecomposable channels without intersymbol interference (ISI), the capacity is given as the limit of normalized directed information between the input and output sequence, maximized over an appropriate set of causally conditioned distributions. As important special cases, we characterize (a) the framework of `to feed or not to feed back' where either the encoder or the decoder takes binary actions to determine whether current channel output will be fed back to the encoder, with a constraint on the fraction of channel outputs that are fed back, (b) the capacity of `coding on the backward link' in FSCs, i.e., when the decoder sends limited-rate instantaneous coded noise-free feedback on the backward link.

Let X be a non-negative random variable and let the conditional distribution of a random variable Y, given X, be Poisson(γ·X), for a parameter γ ≥ 0. We identify a natural loss function such that: 1. The derivative of the mutual information between X and Y with respect to γ is equal to the minimum mean loss in estimating X based on Y, regardless of the distribution of X. 1 When X ~ P is estimated based on Y by a mismatched estimator that would have minimized the expected loss had X ~ Q, the integral over all values of γ of the excess mean loss is equal to the relative entropy between P and Q. For a continuous time setting where XT= {Xt, 0 ≤ t ≤ T} is a non-negative stochastic process and the conditional law of YT= {Yt, 0 ≤ t ≤ T}, given XT, is that of a non-homogeneous Poisson process with intensity function γ · XT, under the same loss function: 1. The minimum mean loss in causal filtering when γ = γ0is equal to the expected value of the minimum mean loss in non-causal filtering (smoothing) achieved with a channel whose parameter γ is uniformly distributed between 0 and γ0. Bridging the two quantities is the mutual information between XTand YT. 2. This relationship between the mean losses in causal and non-causal filtering holds also in the case where the filters employed are mismatched, i.e., optimized assuming a law on XTwhich 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 YT. Thus, relative entropy quantifies the excess estimation loss due to mismatch in this setting. These results parallel those recently found for the Gaussian channel: the I-MMSE relationship of Guo Shamai and Verdii, the relative entropy and mismatched estimation relationship of Verdii, and the relationship between causal and non-casual mismatched estimation of Weissman.

We consider multi-terminal source coding with a single encoder and multiple decoders where either the encoder or the decoders can take actions which affect the quality or availability of the side information present at the decoders, subjected to an additional cost constraint on the actions taken. For the scenario where a joint action is taken at the decoders, we characterize the rate-cost trade-off region for lossless source coding, and give an achievability scheme for lossy source coding for two decoders which is optimum for several special cases. For the case where the encoder takes actions, we characterize the rate-cost trade-off for a class of lossless source coding scenarios with multiple decoders.

We consider cascade and triangular source coding with side information and causal reconstruction at the end node. When the side information at the source and intermediate nodes are the same, we characterize the rate distortion regions for both the cascade and triangular source coding problems. For the general cascade setting with causal reconstruction at the end node, we characterize the rate region when the sources satisfy a positivity condition, or when a Markov chain holds.

We consider discrete denoising of two-dimensional data with characteristics that may be varying abruptly between regions. Using a quadtree decomposition technique and space-filling curves, we extend the recently developed S-DUDE (Shifting Discrete Universal DEnoiser), which was tailored to one-dimensional data, to the two-dimensional case. Our scheme competes with a genie that has access, in addition to the noisy data, also to the underlying noiseless data, and can employ m different two-dimensional sliding window denoisers along m distinct regions obtained by a quadtree decomposition with m leaves, in a way that minimizes the overall loss. We show that, regardless of what the underlying noiseless data may be, the two-dimensional S-DUDE performs essentially as well as this genie, provided that the number of distinct regions satisfies m = o(n), where n is the total size of the data. The resulting algorithm complexity is still linear in both n and m, as in the one-dimensional case. Our experimental results show that the two-dimensional S-DUDE can be effective when the characteristics of the underlying clean image vary across different regions in the data.

The notion of directed information was recently introduced for stochastic processes in continuous time. The key idea of the definition is to consider all possible time partitions of a given interval. Unlike the definition of mutual information of discrete-time random variables with continuous alphabets where the supremum over all possible partitions of the alphabets plays an important role, here the infimum over all possible time-partition plays an important role. We show that the fundamental limit on reliable communication for a wide class of continuous-time channels with feedback are characterized using the notion of continuous-time directed information.

We consider the problem of optimal probing of states of a channel by transmitter and receiver for maximizing rate of reliable communication. The channel is discrete memoryless (DMC) with i.i.d. states. The encoder takes probing actions dependent on the message. It then uses the state information obtained from probing causally or noncausally to generate channel input symbols. The decoder may also take channel probing actions as a function of the observed channel output and use the channel state information thus acquired, along with the channel output, to estimate the message. We refer to the maximum achievable rate for reliable communication for such systems as the “Probing Capacity”. We characterize this capacity when the encoder and decoder actions are cost constrained. To motivate the problem, we begin by characterizing the trade-off between the capacity and fraction of channel states the encoder is allowed to observe, while the decoder is aware of channel states. In this setting of `to observe or not to observe' state at the encoder, we compute certain numerical examples which exhibit a pleasing phenomenon, where encoder can observe a relatively small fraction of states and yet communicate at maximum rate, i.e., rate when observing states at encoder is not cost constrained.

We study the best exponential decay in the blocklength of the probability of error that can be achieved in the transmission of a single bit over the Gaussian channel with an active noisy Gaussian feedback link. We impose an expected block power constraint on the forward link and study both almost-sure and expected block power constraints on the feedback link. In both cases the best achievable error exponents are finite and grow approximately proportionally to the larger between the signal-to-noise ratios on the forward and feedback links. The error exponents under almost-sure block power constraints are typically strictly smaller than under expected constraints. Some of the results extend to communication at arbitrary rates below capacity and to general discrete memoryless channels.

We investigate the role of directed information in portfolio theory, data compression, and statistics with causality constraints. In particular, we show that directed information is an upper bound on the increment in growth rates of optimal portfolios in a stock market due to causal side information. This upper bound is tight for gambling in a horse race, which is an extreme case of stock markets. Directed information also characterizes the value of causal side information in instantaneous compression and quantifies the benefit of causal inference in joint compression of two stochastic processes. In hypothesis testing, directed information evaluates the best error exponent for testing whether a random processYcausally influences another processXor not. These results lead to a natural interpretation of directed informationI(Yn→Xn) as the amount of information that a random sequenceYn= (Y1,Y2,...,Yn) causally provides about another random sequenceXn= (X1,X2,...,Xn). A new measure, directed lautum information, is also introduced and interpreted in portfolio theory, data compression, and hypothesis testing.

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.

Motivated by the Markov chain Monte Carlo (MCMC) relaxation method of Jalali and Weissman, we propose a lossy compression algorithm for continuous amplitude sources that relies on a finite reproduction alphabet that grows with the input length. Our algorithm asymptotically achieves the optimum rate distortion (RD) function universally for stationary ergodic continuous amplitude sources. However, the large alphabet slows down the convergence to the RD function, and is thus an impediment in practice. We thus propose an MCMC-based algorithm that uses a (smaller) adaptive reproduction alphabet. In addition to computational advantages, the reduced alphabet accelerates convergence to the RD function, and is thus more suitable in practice.

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. For the quadratic Gaussian case, we show that it suffices to consider jointly Gaussian distributions, a fact that leads to an explicit solution.

In a discrete denoising problem, if the denoiser knows the clean source distribution, the Bayes optimal denoiser is the Bayes response of the posterior distribution of the source given the noisy observations. However, in many applications the source distribution is unknown.We consider the Bayes response based on the approximate posterior distribution induced by a universal lossless compression code. Motivated by this approach, we present the empirical conditional entropy-based denoiser. Simulations show that when the source alphabet is small, the proposed denoiser achieves the performance of the Universal Discrete DEnoiser (DUDE). Furthermore, if the alphabet size increases, the proposed denoiser degrades more gracefully than the DUDE.

In this paper, we develop a universal algorithm to estimate Massey's directed information for stationary ergodic processes. The sequential probability assignment induced by a universal source code plays the critical role in the estimation. In particular, we use context tree weighting to implement the algorithm. Some numerical results are provided to illustrate the performance of the proposed algorithm.

The theory of Markov set-chains is applied to derive upper and lower bounds on the capacity of finite-state channels that are tighter than the classic bounds by Gallager. The new bounds coincide and yield single-letter capacity characterizations for a class of channels with the state process known at the receiver, including channels whose long-term marginal state distribution is independent of the input process. Analogous results are established for finite-state multiple access channels.

We consider an agent interacting with an unmodeled environment. At each time, the agent makes an observation, takes an action, and incurs a cost. Its actions can influence future observations and costs. The goal is to minimize the long-term average cost. We propose a novel algorithm, known as the active LZ algorithm, for optimal control based on ideas from the Lempel-Ziv scheme for universal data compression and prediction. We establish that, under the active LZ algorithm, if there exists an integerKsuch that the future is conditionally independent of the past given a window ofKconsecutive actions and observations, then the average cost converges to the optimum. Experimental results involving the game of Rock-Paper-Scissors illustrate merits of the algorithm.

We consider the Wyner-Ziv (WZ) problem of lossy compression where the decompressor observes a noisy version of the source, whose statistics are unknown. A new family of WZ coding algorithms is proposed and their universal optimality is proven. Compression consists of sliding-window processing followed by Lempel-Ziv (LZ) compression, while the decompressor is based on a modification of the discrete universal denoiser (DUDE) algorithm to take advantage of side information. The new algorithms not only universally attain the fundamental limits, but also suggest a paradigm for practical WZ coding. The effectiveness of our approach is illustrated with experiments on binary images, and English text using a low complexity algorithm motivated by our class of universally optimal WZ codes.

Consider the two-way rate-distortion problem in which a helper sends a common limited-rate message to both users based on side information at its disposal. We characterize the region of achievable rates and distortions when the Markov relation (Helper)-(User 1)-(User 2) holds. The main insight of the result is that in order to achieve the optimal rate, the helper may use a binning scheme, as in Wyner-Ziv, where the side information at the decoder is the ¿further¿ user, namely, User 2. We derive these regions explicitly for the Gaussian sources with square error distortion, analyze a tradeoff between the rate from the helper and the rate from the source, and examine a special case where the helper has the freedom to send different messages, at different rates, to the encoder and the decoder. The converse proofs use a technique for verifying Markov relations via undirected graphs.

A continuous-time finite-power process with distributionPis 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 distributionQ. We show that the causal filtering mean-square error (MSE) achieved at SNR levelsnris equal to the average value of the noncausal (smoothing) MSE achieved with a channel whose SNR is chosen uniformly distributed between 0 andsnr. 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, whereP=Q, to generalPandQ. 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.

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.

We present a new lossy compressor for discrete sources. For coding a source sequence xn, the encoder starts by assigning a certain cost to each reconstruction sequence. It then finds the reconstruction that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of a sequence is given by a linear combination of its empirical probabilities of some order k+1 and its distortion relative to the source sequence. The linear structure of the cost in the empirical count matrix allows the encoder to employ a Viterbi-like algorithm for obtaining the minimizing reconstruction sequence simply. We identify a choice of coefficients for the linear combination in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance of any Markov source in the limit of large n, provided k is increased as o(log n).

A side-information scalable model in which each receiver observes its own side-information, while the side-information pair is stochastically degraded with respect to the source, is considered. It is further assumed that a one way conference link with given capacity exists between the decoder observing the higher quality side-information and the one observing the degraded side-information. Our contribution is in deriving an outer bound on the rate-distortion region for this model. Specifically, we propose a modification to the technique presented by Tian-Diggavi which accounts for the presence of the conference channel.

The notion of directed information is introduced for stochastic processes in continuous time. Properties and operational interpretations are presented for this notion of directed information, which generalizes mutual information between stochastic processes in a similar manner as Massey's original notion of directed information generalizes Shannon's mutual information in the discrete-time setting. As a key application, Duncan's theorem is generalized to estimation problems in which the evolution of the target signal is affected by the past channel noise, and the causal minimum mean squared error estimation is related to directed information from the target signal to the observation corrupted by additive white Gaussian noise. An analogous relationship holds for the Poisson channel.

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 non-causally 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 dasiarewritepsila option that may arise naturally in storage for computer memories with defects or in magnetic recoding. A few examples are worked out in detail.

We have formalized and characterized the fundamental limits for the problem of source coding with decoder side information, where the decoder is allowed to choose actions that affect the nature and quality of the side information. In the context of the problem studied, and its motivation, it is natural to also look at the case where actions are taken at the encoder: Based on its observation of the source sequence Xn, the encoder chooses a sequence of actions An. Nature then generates the side information sequence Ynas the output of the memoryless channel PY|X,Awhose input is the pair (Xn, An). The encoder now chooses the index to be given to the decoder on the basis of both the source and the side information sequence. The reconstruction sequence X¿nis then based on the index and on the side information sequence. A challenging aspect of this scenario is that the actions chosen by the encoder not only affect the quality of the side information, but can also be used to directly convey information about the source sequence. This scenario is depicted in Figure 6. In , we characterize the achievable tradeoff between rate, distortion, and cost for this problem setting as well.

Consider the two-way rate-distortion problem in which a helper sends a common limited-rate message to both users based on side information at its disposal. We characterize the region of achievable rates and distortions where a Markov form (Helper)-(User 1)-(User 2) holds. The main insight of the result is that in order to achieve the optimal rate, the helper may use a binning scheme, as in Wyner-Ziv, where the side information at the decoder is the ¿further¿ user, namely, User 2. The converse proofs use a new technique for verifying Markov relations via undirected graphs.

We present a new lossy compression algorithm for discrete sources. The encoder assigns a certain cost to each reconstruction sequence, finds the sequence that minimizes the cost, and describes it losslessly to the decoder via a universal lossless compressor. The cost of a sequence is defined as a linear combination of its empirical probabilities of some order k + 1 and its distortion relative to the source sequence. The linear structure of the cost in the empirical count matrix allows the encoder to employ a Viterbi-like algorithm for obtaining the minimizing reconstruction sequence simply. We identify a choice of coefficients for the linear combination in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance of any Markov source in the limit of large n, provided k is increased as o(log n). Finding the optimal coefficients is complex and requires solving a non-convex optimization problem. As a detour, we propose a simple heuristic iterative procedure, and demonstrate its efficiency through our experimental results.

In this work we study source coding problems where a helper provides rate-limited side information to the involved parties. We first consider the Wyner-Ziv problem, where in addition to the memoryless side information available to the decoder, a helper sends common, rate-limited side information to the encoder and decoder. A single letter characterization of the achievable rates is derived, under certain Markov conditions on the source and side information. We then examine the problem of cascade rate distortion with a helper. Partial results are derived also for the case where the side information is not necessarily common, i.e., when the helper can send different streams of coded side information to the involved parties.

The notion of directed information is introduced for stochastic processes in continuous time. Properties and operational interpretations are presented for this notion of directed information, which generalizes mutual information between stochastic processes in a similar manner as Massey's original notion of directed information generalizes Shannon's mutual information in the discrete-time setting. As a key application, Duncan's theorem is generalized to estimation problems in which the evolution of the target signal is affected by the past channel noise, and the causal minimum mean squared error estimation is related to directed information from the target signal to the observation corrupted by additive white Gaussian noise. An analogous relationship holds for the Poisson channel. The notion of directed information as a characterizing of the fundamental limit on reliable communication for a wide class of continuous-time channels with feedback is discussed.

Inspired by control theory, we attempt to introduce action into a few classical Shannon-theoretic frameworks. This attempt gives rise to problems ranging from source coding with a limited budget of side information measurements, through coding for computer memories with a rewrite option, to communication with non-causal feedback. I will describe these problems, along with some solutions and open questions. Based on recent and ongoing work with Haim Permuter, Yossef Steinberg, and Sergio Verdu

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 tomtimes, 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 thatmis 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 switchesm. 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.

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$\bmod \,2$noise MAC where the noise may have memory, for which feedback does not enlarge the capacity region.

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 XNand the output YN, i.e., C=limNrarrinfin(1/n)max I(XNrarrYN) where the maximization is taken over the causal conditioning probability Q(xNparzN-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.

A successive refinement model in which each receiver observes its own side-information, while the side-information pair is stochastically degraded with respect to the source, is considered. It is further assumed that a one way conference link with given capacity exists between the decoder observing the degraded side-information and the one observing the higher quality side-information. Inner and outer bounds on the rate-distortion region are derived. Our bounds are partially tight in the sense that the characterization of the primary encoder rates is conclusive, the remaining gap being in the characterization of the conference encoder rate.

New upper and lower bounds on the capacity of finite-state channels are established. For a class of channels, these bounds yield a single-letter capacity formula, which is previously unknown in the literature.

We present two results related to the computational complexity of lossy compression. The first result shows that for a memoryless source Ps with rate-distortion function R(D), the rate-distortion pair (R(D) + gamma, D + isin) can be achieved with constant decoding time per symbol and encoding time per symbol proportional to C1(gamma)isin-C2(gamma). The second results establishes that for any given R, there exists a universal lossy compression scheme with O(ng(n)) encoding complexity and O(n) decoding complexity, that achieves the point (R,D(R)) asymptotically for any ergodic source with distortion-rate function D(.), where g(n) is an arbitrary non-decreasing unbounded function. A computationally feasible implementation of the first scheme outperforms many of the best previously proposed schemes for binary sources with blocklengths of the order of 1000.

We propose a new approach to lossy source coding. The idea is to sample a reconstruction sequence from a Boltzmann distribution associated with an energy function that incorporates the distortion between the source and reconstruction, the compressibility of the reconstruction, and the point sought on the rate-distortion curve. To sample from this distribution, we use a heat bath algorithm: Starting from an initial candidate reconstruction (say the original source sequence), at every iteration, an index i is chosen and the ith sequence component is replaced by drawing from the conditional probability distribution for that component given all the rest. At the end of this process, the encoder losslessly conveys the reconstruction to the decoder using universal lossless compression. An appropriate choice of the energy function leads to an algorithm whose complexity, in each iteration, is independent of the sequence length and only linearly dependent on a certain context parameter (which grows sub-logarithmically with the sequence length). The algorithm is universal: for any stationary ergodic source, it achieves the optimal rate-distortion performance in the limits of large number of iterations and sequence length. Initial experimentation shows promising performance in practice.

We study the problem of gambling in horse races with causal side information and show that Masseypsilas directed information characterizes the increment in the maximum achievable capital growth rate due to the availability of side information. This result gives a natural interpretation of directed information I(Ynrarr Xn) as the amount of information that Yncausally provides about Xn. Extensions to stock market portfolio strategies and data compression with causal side information are also discussed.

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 provided a sequence of inner and outer bounds for this region. These bounds are shown to coincide, and hence yield the capacity region for two cases of FS-MACs: (1) when the state process is stationary and ergodic and not affected by the inputs; (2) an indecomposable FS-MAC without feedback. Though the capacity region is "multi-letter" in general, our results yield explicit conclusions when applied to specific scenarios of interest.

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

The problem of discrete universal filtering, in which the components of a discrete signal emitted by an unknown source and corrupted by a known discrete memoryless channel (DMC) are to be causally estimated, is considered. A family of filters are derived, and are shown to be universally asymptotically optimal in the sense of achieving the optimum filtering performance when the clean signal is stationary, ergodic, and satisfies an additional mild positivity condition. Our schemes are comprised of approximating the noisy signal using a hidden Markov process (HMP) via maximum-likelihood (ML) estimation, followed by the use of the forward recursions for HMP state estimation. It is shown that as the data length increases, and as the number of states in the HMP approximation increases, our family of filters attains the performance of the optimal distribution-dependent filter. An extension to the case of channels with memory is also established.

We establish that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio and provide a simple communication scheme that achieves capacity. As part of the analysis, we formulate a class of dynamic programs that characterize capacities of unifilar finite-state channels. The trapdoor channel is an instance that admits a simple closed-form solution.

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.

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.

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 ldquowell-informed antagonist,rdquo 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 ldquosemi-stochasticrdquo 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 I = 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.

Upper and lower bounds are derived on the reliability function of the additive white Gaussian noise channel with output fed back to the transmitter over an independent additive white Gaussian noise channel. Special attention is paid to the regime of very low feedback noise variance and it is shown that the reliability function is asymptotically inversely proportional to the feedback noise variance. This result shows that the noise in the feedback link, however small, renders the communication with noisy feedback fundamentally different from the perfect feedback case. For example, it is demonstrated that with noisy feedback, linear coding schemes fail to achieve any positive rate. In contrast, an asymptotically optimal coding scheme is devised, based on a three-phase detection/retransmission protocol, which achieves an error exponent inversely proportional to the feedback noise variance for any rate less than capacity.

We consider the problem of sequential decision making on random fields corrupted by Additive White Gaussian Noise (AWGN). In particular, we first consider the problem of sequentially filtering an AWGN-corrupted random field. In this scenario, the sequential filter may be given the freedom to choose the path over which it traverses the random field (e.g., noisy image), thus it is natural to ask what is the best achievable performance and how far is the performance of widely used scanning methods from the optimum. We formally define the problem of scanning and filtering, derive a bound on the best achievable performance and quantify the excess loss occurring when non-optimal scanners are used, compared to optimal scanning and filtering. We then discuss the problem of sequential scanning and prediction of noisy random fields. This setting is a natural model for applications such as restoration and coding of noisy images. In this scenario, using predictive coding methods on the noisy image results in both enhancement and compression of the input image, as one expects that the prediction error consists mainly of the noise signal. We formally define the problem of sequential prediction in a noisy array and compute the optimal performance in terms of the clean scandictability defined by Merhav and Weissman.

We consider the Wyner-Ziv (WZ) problem of rate- distortion coding with decoder side information, for the case where the source statistics are unknown or non-existent. A new family of WZ coding algorithms is proposed and its universal optimality is proven. Encoding is based on a sliding window operation followed by LZ compression, while decoding is based on a natural extension of the Discrete Universal DEnoiser (DUDE) algorithm to the case where side information is present. The effectiveness of our approach is illustrated with experiments on binary images using a low complexity algorithm motivated by our class of universally optimal WZ codes.

This paper addresses the problem of bounding the rate-distortion function of a binary symmetric Markov source. We derive a sequence of upper and lower bounds on the rate- distortion function of such sources. The bounds are indexed by k, which corresponds to the dimension of the optimization problem involved. We obtain an explicit bound on the difference between the derived upper and lower bounds as a function of k. This allows to identify the value of k that suffices to compute the rate distortion function to a given desired accuracy. In addition to these bounds, a tighter lower bound which is also a function of k is derived. Our numerical results show that the new bounds improve on the Berger's upper and lower bounds even with small values of k.

We consider the problem of causal estimation, i.e., filtering, of a real-valued signal corrupted by zero mean, i.i.d., real-valued additive noise under the mean square error (MSE) criterion. We build a competitive on-line filtering algorithm whose normalized cumulative MSE, for every bounded underlying signal, is asymptotically as small as the best linear finite-duration impulse response (FIR) filter of order d. We do not assume any stochastic mechanism in generating the underlying signal, and assume only the variance of the noise is known to the filter. The regret of our scheme is shown to decay in the order of O (log n/n), where n is the length of the signal. Moreover, we present a concentration of the average square error of our scheme to that of the best d-th order linear FIR filter. Our analysis combines tools from the problems of universal filtering and competitive on-line regression.

We consider a family of channels, collectively referred to as the 'chemical channel', which generalizes the trapdoor channel. We show that the feedback capacity of the chemical channel can be cast as the solution to a dynamic programming (DP) problem. We obtain numerical values for the feedback capacity of the chemical channel by approximating the solution of the DP problem using value iteration. For the special case of the trapdoor channel, by solving the DP problem analytically, we prove that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio. Further, we describe a simple scheme that achieves the capacity of the trapdoor channel. The scheme has zero probability of error, which allows us to conclude that the logarithm of the golden ratio is also the zero error capacity of the chemical channel.

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 schemes that are much more tractable than the original ones, while retaining their universal optimality properties. The schemes involve a simple preprocessing step of quantizing the noisy symbols to generate quantized contexts which (according to the quantized context value of each symbol) are then used to partition the unquantized symbols to subsequences. A universal context-free denoiser (of zero context length for the unquantized sequences) is then separately employed on each of the subsequences. We identify a rate in which the context length and quantization resolution should be increased so that the resulting scheme is universal in both the semi-stochastic and fully stochastic settings. The proposed family of schemes is computationally attractive, having linear complexity with a proportionality constant that is independent of the context length and the quantization resolution. Experimental results show that these schemes are not only superior from a computational viewpoint, but also achieve better denoising in practice.

We investigate the problem of scanning and prediction (ldquoscandiction,rdquo for short) of multidimensional data arrays. This problem arises in several aspects of image and video processing, such as predictive coding, for example, where an image is compressed by coding the error sequence resulting from scandicting it. Thus, it is natural to ask what is the optimal method to scan and predict a given image, what is the resulting minimum prediction loss, and whether there exist specific scandiction schemes which are universal in some sense. Specifically, we investigate the following problems: first, modeling the data array as a random field, we wish to examine whether there exists a scandiction scheme which is independent of the field's distribution, yet asymptotically achieves the same performance as if this distribution were known. This question is answered in the affirmative for the set of all spatially stationary random fields and under mild conditions on the loss function. We then discuss the scenario where a nonoptimal scanning order is used, yet accompanied by an optimal predictor, and derive bounds on the excess loss compared to optimal scanning and prediction. This paper is the first part of a two-part paper on sequential decision making for multidimensional data. It deals with clean, noiseless data arrays. The second part deals with noisy data arrays, namely, with the case where the decision maker observes only a noisy version of the data, yet it is judged with respect to the original, clean data.

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

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

We consider the problem of image denoising wherein the statistical characterization of the noise corruption mechanism is known. We make no assumptions on the nature or statistics of the underlying noise-free signal. A denoiser is proposed which, although ignorant of the statistical properties of the noise-free image, does essentially as well as a scheme with full knowledge of the statistics. The solution is presented as a sequence of schemes that progressively consider larger neighborhoods (contexts) around a pixel being denoised, to achieve optimum performance under a user-defined distortion measure.

We investigate several problems in scanning of multidimensional data arrays, such as universal scanning and prediction ("scandiction", for short), and scandiction of noisy data arrays. These problems arise in several aspects of image and video processing, such as predictive coding, filtering and denoising. In predictive coding of images, for example, an image is compressed by coding the prediction error sequence resulting from scandicting it. Thus, it is natural to ask what is the optimal method to scan and predict a given image, what is the resulting minimum prediction loss, and if there exist specific scandiction schemes which are universal in some sense. More specifically, we investigate the following problems: first, given a random field, we examine whether there exists a scandiction scheme which is independent of the field's distribution, yet asymptotically achieves the same performance as if this distribution was known. This question is answered in the affirmative for the set of all spatially stationary random fields and under mild conditions on the loss function. We then discuss the scenario where a non-optimal scanning order is used, yet accompanied by an optimal predictor, and derive a bound on the excess loss compared to optimal scandiction. Finally, we examine the scenario where the random field is corrupted by noise, but the scanning and prediction (or filtering) scheme is judged with respect to the underlying noiseless field

We characterize the rate distortion function for the source coding with decoder side information setting when the i-th reconstruction symbol is allowed to depend only on the first i + d side information symbols, for some finite lookahead d, in addition to the index from the encoder. For the case of causal side information, i.e., d = 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 d > 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-Wolf source coding problem with limited side information lookahead, and have some surprising implications. We find that side information is useless for any fixed d when the joint 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 lookahead dnis allowed to grow faster than logarithmic in the block length n, 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 lookahead

We consider channel coding with feedback for the general case where the feedback may be an arbitrary deterministic function of the output samples. Under the assumption that the channel states take values in a finite alphabet, we find an achievable rate and an upper bound on the capacity. We conclude by showing that when the channel is indecomposable, and has no intersymbol interference, its capacity is given by the limit of the maximum of the (normalized) directed information between the input XNand the output YN, i.e. C = limNrarrinfin/1N max I(XNrarr YN), where the maximization is over the causal conditioning probability Q(xN||kN-) defined in this paper

We consider the problem of reconstructing a discrete-time continuous-amplitude signal corrupted by a known memoryless channel with a general output alphabet. We develop a sequence of denoisers that asymptotically achieve optimum performance in a semi-stochastic setting of an unknown individual noiseless signal, where the quality of reconstruction is measured with respect to a general given loss function satisfying mild conditions. We also extend this to the fully stochastic setting and show that our denoiser is asymptotically optimal for any stationary noiseless source. We conclude with some experimental validations of the proposed theory

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 rate of a source is defined as the limit of the normalized erasure entropy. The erasure entropy measures the information content carried by each symbol knowing its context. In the setup of a source observed through an erasure channel, we offer an operational characterization of erasure entropy rate as the minimal amount of bits per erasure required to recover the erased 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. 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 also explored

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, among other things, on past noisy sequence components. We show that this formulation is more challenging than that of an individual noiseless sequence (aka 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. Our noise model allows for channels whose noisy output depends on the l past channel outputs (in addition to the noiseless 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 in the semi-stochastic setting. Hence, our results show that the latter scheme is universal also under the well-informed antagonist.

The goal of a denoising algorithm is to recover a signal from its noise-corrupted observations. Perfect recovery is seldom possible and performance is measured under a given single-letter fidelity criterion. For discrete signals corrupted by a known discrete memoryless channel (DMC), the Discrete Universal DEnoiser (DUDE) was recently shown to perform this task asymptotically optimally, without knowledge of the statistical properties of the source. In the present work, we address the scenario where, in addition to the lack of knowledge of the source statistics, there is also uncertainty in the channel characteristics. We propose a family of discrete denoisers and establish their asymptotic optimality under a minimax performance criterion which we argue is appropriate for this setting. As we show elsewhere, the proposed schemes can also be implemented computationally efficiently.

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.

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

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

We consider the problem of optimally recovering a finite-alphabet discrete-time stochastic process {X/sub t/} from its noise-corrupted observation process {Z/sub t/}. In general, the optimal estimate of X/sub t/ will depend on all the components of {Z/sub t/} on which it can be based. We characterize nontrivial situations (i.e., beyond the case where (X/sub t/,Z/sub t/) are independent) for which optimum performance is attained using "symbol-by-symbol" operations (a.k.a. "singlet decoding"), meaning that the optimum estimate of X/sub t/ depends solely on Z/sub t/. For the case where {X/sub t/} 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 X/sub t/ is allowed to depend only on {Z/sub t'/}/sub t'/spl les/t/) and the denoising problem (where the estimate of X/sub t/ 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 /spl delta//sup */>0 such that the "say-what-you-see" scheme is optimal provided the channel crossover probability is less than /spl delta//sup */. 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).

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+lscr side information symbols, for some finite look-ahead lscr, in addition to the index from the encoder. For the case of causal side information, i.e., lscr=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 lscr>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-Wolf source coding problem with finite side information looka-head, and have some surprising implications. We find that side information is useless for any fixed lscr 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.

Recent work by Orlitsky et al. (2004) has motivated the study of pattern sequences and their compressibility properties. Emphasis in this recent line of work has been on compressing pattern sequences under uncertainty in the source that has generated them, thus focusing on universal schemes and their redundancy. Our interest in this work is in 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 i.i.d. processes over arbitrary alphabets, stationary and ergodic: processes over discrete alphabets, as well as more general processes that can be represented as the output of an additive white-noise channel. For cases where the entropy rate of the pattern process is infinite, we characterize the possible growth rate of the block entropy.

We consider the problem of optimal control of a Kth order Markov process so as to minimize long-term average cost, a framework with many applications in communications and beyond. Specifically, we wish to do so without knowledge of either the transition kernel or even the order K. We develop and analyze two algorithms, based on the Lempel-Ziv scheme for data compression, that maintain probability estimates along variable length contexts. We establish that eventually, with probability 1, the optimal action is taken at each context. Further, in the case of the second algorithm, we establish almost sure asymptotic optimality

The recent study of pattern sequences and their compressibility properties has led to interest in the entropy rate of pattern sequences of stochastic processes, and its relationship to the entropy rate of the original process. In this work we give a complete characterization of this relationship for general discrete Markov processes as well as for a broad family of Markov and additive noise processes over a continuous alphabet

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

We consider the discrete universal filtering problem, where the components of a discrete signal emitted by an unknown source and corrupted by a known DMC are to be causally estimated. We derive a family of filters which we show to be universally asymptotically optimal in the sense of achieving the optimum filtering performance when the clean signal is stationary, ergodic, and satisfies an additional mild positivity condition. Our schemes are based on approximating the noisy signal by a hidden Markov process (HMP) via maximum likelihood (ML) estimation, followed by use of the well-known forward recursions for HMP state estimation. We show that as the data length increases, and as the number of states in the HMP approximation increases, our family of filters attain the performance of the optimal distribution-dependent filter

Recent work by Ordentlich and Weissman put forth a new approach for bounding the entropy rate of a hidden Markov process via the construction of a related Markov process. We use this approach to study the behavior of the filtering error probability and the entropy rate of a hidden Markov process in the rare transitions regime. In this paper, we restrict our attention to the case of a two state Markov chain that is corrupted by a binary symmetric channel. Using this approach we recover the results on the optimal filtering error probability of Khasminskii and Zeitouni. In addition, this approach sheds light on the terms that appear in the expression for the optimal filtering error probability. We then use this approach to obtain tight estimates of the entropy rate of the process in the rare transitions regime. This leads to tight estimates on the capacity of the Gilbert-Elliot channel in the rare transitions regime

Let {Xt} be a stationary finite-alphabet Markov chain and {Zt} denote its noisy version when corrupted by a discrete memoryless channel. We present an approach to bounding the entropy rate of {Zt} by the construction and study of a related measure-valued Markov process. To illustrate its efficacy, we specialize it to the case of a BSC-corrupted binary Markov chain. The bounds obtained are sufficiently tight to characterize the behavior of the entropy rate in asymptotic regimes that exhibit a "concentration of the support". Examples include the 'high SNR', 'low SNR', 'rare spikes', and 'weak dependence' regimes. Our analysis also gives rise to a deterministic algorithm for approximating the entropy rate, achieving the best known precision-complexity tradeoff, for a significant subset of the process parameter space

The classical framework of context-tree models used in sequential decision problems such as compression and prediction is generalized to a setting in which the observations are multi-tracked or multi-directional, and for which it may be beneficial to consider contexts comprised of possibly differing numbers of symbols from each track or direction. Context set definitions, tree representations, and pruning algorithms are all extended from the classical uni-directional setting to the m-directional setting, with an emphasis on the case of m = 2. We provide a simple example suggesting that determining (pruning) the best m-directional context set for m ges 3 is substantially more complex than in the case of m = 2. After briefly describing how the multi-directional framework can be applied to universal data compression, we focus on its application to universal denoising, where we pair the proposed framework with a new technique for estimating the loss of a denoising algorithm based only on noisy observations

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 noiseless 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(n/sup 1+/spl epsiv//) operations (for any /spl epsiv/>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 memoryless channel (DMC).

We study the effect of the introduction of side information into the causal source coding setting of Neuhoff and Gilbert. We find that the spirit of their result, namely, the sufficiency of time-sharing scalar quantizers (followed by appropriate lossless coding) for attaining optimum performance within the family of causal source codes, extends to many scenarios involving availability of side information (at both encoder and decoder, or only on one side). For example, in the case where side information is available at both encoder and decoder, we find that time-sharing side-information-dependent scalar quantizers (at most two for each side-information symbol) attains optimum performance. This remains true even when the reproduction sequence is allowed noncausal dependence on the side information and even for the case where the source and the side information, rather than consisting of independent and identically distributed (i.i.d.) pairs, form, respectively, the output of a memoryless channel and its stationary ergodic input.

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

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.

In the discrete filtering problem, a data sequence over a finite alphabet is assumed to be corrupted by a discrete memoryless channel. The goal is to reconstruct the clean sequence, with as high a fidelity as possible, by way of causal processing of the noisy sequence alone, with the reconstruction at time t depending only on noisy observations occurring no later than t. A universal version of this problem in which no assumptions are made about the distribution of the clean data, which may even be nonstochastic is studied. Using techniques from universal data compression, in particular, the incremental parsing rule of LZ78, and derives a practical and efficient algorithms for the universal filtering of discrete sources. A finite-memory filter of order k has the property that the reconstruction at any time t is a time-invariant function only of noisy observations occurring between times t-k and t, inclusive. The universal filtering algorithms perform essentially as well, in an expected sense (with respect to the noise process), as the best finite-memory filter of any fixed order, determined with full knowledge of the actual clean data sequence, for all such data sequences. Also consider more general finite-state filters and show that any such filter is arbitrarily well approximated by a finite-memory filter of growing order, thereby establishing the universality of the proposed algorithms with respect to this larger class. This result can be viewed as the filtering analogue of the well known optimality of LZ78 relative to the class of finite-state compressors.

We consider the problem of denoising a binary image corrupted by a noisy medium which flips each component in the original image, independently, to its complementary value with some fixed but unknown probability /spl delta/<1/2. We propose a denoiser which assumes no knowledge of statistical properties of the image, yet asymptotically attains the performance of the scheme that knows the noisy image statistics and operates optimally in a minimax sense. The proposed scheme is implementable, with complexity linear in the image size. Preliminary experimental results are presented which indicate that the scheme has the potential to do well on real data.

This paper describes the universal denoising for the finite-input-general-output channel. The present work is in the case where the components of the underlying noise-free signal are still finite valued, yet their noisy observations take values in a general alphabet. This channel is assumed as discrete memoryless in this case. A discrete signal corrupted by a known discrete memoryless channel can be asymptotically optimal and practically denoised with no a-priori knowledge of statistical (or any other) properties of the signal.

The assumption of a known channel was inherent in the structure of the denoising under channel uncertainty (DUDE). There are many scenarios where the DUDE is effective for denoising. A denoising scheme is sought, which will accommodate uncertainty in the statistical characteristics of the noisy medium. Unfortunately, it can be shown that in this setting the task of attaining the performance of the optimum nonuniversal distribution-dependent scheme is impossible, even for a "genie-aided" scheme with complete knowledge of the noisy signal statistics. In this paper, the noise-corrupted signal with the clean components and their values in the finite alphabet are assumed. The corruption mechanism is a discrete memoryless channel (DMC) with an associated invertible channel matrix. It lies in a given uncertainty set.

This paper describes the channel decoding of systematically encoded unknown redundant sources. The redundancy of the data is known at the decoder and the channel decoder incorporates the statistics of the data to enhance the performance. The practical decoders are designed which takes the advantage of the source redundancy of systematically encoded for transmission over a discrete memoryless channel (DMC). The performance is achieved by operating discrete universal denoiser (DUDE) and the experiments involving Reed-Solomon codes show that DUDE-enhanced decoding is very effective at high rates.

This paper describes the optimality of symbol by symbol filtering and denoising and considers the problem of optimally recovering a discrete-time valued stochastic process from a noisy observation process. For binary Markov input process singlet filtering and denoising are optimal. Finally, for the case of memoryless channel, large deviations performance of singlet filtering is obtained.

This paper describes the empirical distribution of rate-constrained source codes. The existence of good code sequences with empirical distributions achieves the minimum mutual information in the rate distortion theory. A source code has entropy of capacity achieving convergence in channel input distributions.

Let {X/sub t/} be a stationary finite-alphabet Markov chain and {Z/sub t/} denote its noisy version when corrupted by a discrete memoryless channel. Let P(X/sub t//spl isin//spl middot/|Z/sub -/spl infin///sup t/) denote the conditional distribution of X/sub t/ given all past and present noisy observations, a simplex-valued random variable. We present a new approach to bounding the entropy rate of {Z/sub t/} by approximating the distribution of this random variable. This approximation is facilitated by the construction and study of a Markov process whose stationary distribution determines the distribution of P(X/sub t//spl isin//spl middot/|Z/sub -/spl infin///sup t/). To illustrate the efficacy of this approach, we specialize it and derive concrete bounds for the case of a binary Markov chain corrupted by a binary symmetric channel (BSC). These bounds are seen to capture the behavior of the entropy rate in various asymptotic regimes.

The classical framework of context-tree models, customary in sequential decision problems such as compression and prediction, is generalized to a setting in which the observations are multi-tracked or multi-directional, and for which it may be beneficial to consider contexts comprised of possibly differing numbers of symbols from each track or direction. The notion of a bi-directional context set is formalized and the generalization of the classical context-tree-based representation for a well defined set of bi-directional contexts is presented, together with an efficient dynamic programming algorithm for determining the best set of bi-directional contexts for a given individual sequence, maximum context depth, and loss function. After briefly describing how this framework can be applied to universal data compression, we focus on its application to universal denoising, where we pair the proposed framework with a new technique for estimating the loss of a denoising algorithm based only on noisy observations.

Consider the problem of rate-constrained reconstruction of a finite-alphabet discrete memoryless signal X/sup n/=(X/sub 1/,...,X/sub n/), based on a noise-corrupted observation sequence Z/sup n/, which is the finite-alphabet output of a discrete memoryless channel (DMC) whose input is X/sup n/. 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 (X/sub i/,Z/sub i/), rather than completely being known, is only known to belong to a set /spl Theta/. Suppose further that the relevant performance criterion is the probability of excess distortion, i.e., letting X/spl circ//sup n/(Z/sup n/) denote the reconstruction, we are interested in the behavior of P/sub /spl theta//(/spl rho/(X/sup n/,X/spl circ//sup n/(Z/sup n/))>d/sub /spl theta//), where /spl rho/ is a (normalized) block distortion induced by a single-letter distortion measure and P/sub /spl theta// denotes the probability measure corresponding to the case where (X/sub i/,Z/sub i/)/spl sim//spl theta/, /spl theta//spl isin//spl Theta/. 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 /spl ges/ 0 and a family of distortion levels {d/sub /spl theta//}/sub /spl theta//spl isin//spl Theta//, we are interested in families of exponential levels {I/sub /spl theta//}/sub /spl theta//spl isin//spl Theta// which are achievable in the sense that for large n there exist rate-R schemes satisfying -1/nlog P/sub /spl theta// (/spl rho/(X/sup n/, X/spl circ//sup n/(Z/sup n/)) > d/sub /spl theta//) /spl ges/ I/sub /spl theta//, for all /spl theta/ /spl isin/ /spl Theta/. Our main result is a complete "single-letter" characterization of achievable levels {I/sub /spl theta//}/sub /spl theta//spl isin//spl Theta// per any given triple (/spl Theta/,R,{d/sub /spl theta//}/sub /spl theta//spl isin//spl Theta//). Equipped with this result, we later turn to addressing the question of the "right" choice of {I/sub /spl theta//}/spl theta//spl isin//spl Theta/. 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 R 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 /spl Theta/ 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.

This paper describes a discrete universal denoiser for two dimensional data and also presents an experimental results of its application to noisy binary images. A discrete universal denoiser (DUDE) is introduced for recovering a signal with finite-valued components corrupted by finite-valued, uncorrelated noise. The DUDE is asymptotically optimal and universal, in the sense of asymptotically achieving, without access to any information on the statistics of the clean signal, the same performance as the best denoiser that does have access to such information. It is also practical, and can be implemented in low complexity.

Consider the problem of finite-rate filtering of a discrete memoryless process {X/sub i/}/sub i/spl ges/1/ based on its noisy observation sequence {Z/sub i/}/sub i/spl ges/1/, which is the output of a discrete memoryless channel (DMC) whose input is {X/sub i/}/sub i/spl ges/1/. When the distribution of the pairs (X/sub i/,Z/sub i/), P/sub X,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. We address the case where P/sub X,Z/, rather than being completely specified, is only known to belong to some set /spl Lambda/. For a fixed encoding rate R, we look at the worst case, over all /spl theta//spl isin//spl Lambda/, of the difference between the expected distortion of a given scheme which is not allowed to depend on the active source /spl theta//spl isin//spl Lambda/ and the value of the distortion-rate function at R corresponding to the noisy source /spl theta/. We study the minimum attainable value achievable by any scheme operating at rate R for this worst case quantity, denoted by D(/spl Lambda/, 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(/spl Lambda/, R) for the case where all members of /spl Lambda/ share the same noisy marginal. For the case of a general /spl Lambda/, we obtain a single-letter characterization of D(/spl Lambda/, R) for the finite-alphabet case. This gives, in particular, a necessary and sufficient condition on the set /spl Lambda/ for the existence of a coding scheme which is universally optimal for all members of /spl Lambda/ and characterizes the approximation-estimation tradeoff for statistical modeling of noisy source coding problems. Finally, we obtain D(/spl Lambda/, R) in closed form for cases where /spl Lambda/ 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 /spl Lambda/ 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.

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 /spl Zopf//sup m/ is defined as the limit of its scandictability on finite "boxes" (subsets of /spl Zopf//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.

Consider the normalized cumulative loss of a predictor F on the sequence x/sup n/=(x/sub 1/,...,x/sub n/), denoted L/sub F/(x/sup n/). For a set of predictors G, let L(G,x/sup n/)=min/sub F/spl isin/G/L/sub F/(x/sup n/) denote the loss of the best predictor in the class on x/sup n/. Given the stochastic process X=X/sub 1/,X/sub 2/,..., we look at EL(G,X/sup n/), termed the competitive predictability of G on X/sup n/. Our interest is in the optimal predictor set of size M, i.e., the predictor set achieving min/sub |G|/spl les/M/EL(G,X/sup n/). When M is subexponential in n, simple arguments show that min/sub |G|/spl les/M/EL(G,X/sup n/) coincides, for large n, with the Bayesian envelope min/sub F/EL/sub F/(X/sup n/). We investigate the behavior, for large n, of min/sub |G|/spl les/e//sup nR/EL(G,X/sup n/), which we term the competitive predictability of X at rate R. We show that whenever X has an autoregressive representation via a predictor with an associated independent and identically distributed (i.i.d.) innovation process, its competitive predictability is given by the distortion-rate function of that innovation process. Indeed, it will be argued that by viewing G as a rate-distortion codebook and the predictors in it as codewords allowed to base the reconstruction of each symbol on the past unquantized symbols, the result can be considered as the source-coding analog of Shannon's classical result that feedback does not increase the capacity of a memoryless channel. For a general process X, we show that the competitive predictability is lower-bounded by the Shannon lower bound (SLB) on the distortion-rate function of X and upper-bounded by the distortion-rate function of any (not necessarily memoryless) innovation process through which the process X has an autoregressive representation. Thus, the competitive predictability is also precisely characterized whenever X can be autoregressively represented via an innovation process for which the SLB is tight. The error exponent, i.e., the exponential behavior of min/sub |G|/spl les/exp(nR)/Pr(L(G,X/sup n/)>d), is also characterized for processes that can be autoregressively represented with an i.i.d. innovation process.

We propose a discrete denoising algorithm, that, based on the observation of the output of a known discrete memoryless channel (DMC), estimates the input sequence to minimize a given fidelity criterion. The algorithm is universal in the sense that it requires no knowledge of the input sequence or its statistical properties. Yet, asymptotically it performs as well as the optimum denoiser that knows the input sequence distribution. The proposed denoising algorithm is practical, and can be implemented in O(n log n) time and O(n/sup 2/3/ log n) storage complexity. Extensions to the case of delay-constrained denoising, and to the case of channel uncertainty, are briefly discussed.

Lossy compression of a discrete memoryless source (DMS) with respect to a single-letter distortion measure is considered. We study the best attainable tradeoff between the exponential rates of the probabilities that the codeword length and that the cumulative distortion exceed respective thresholds for two main cases. The first scenario examined is that where the source is corrupted by a discrete memoryless channel (DMC) prior to reaching the coder. In the second part of this work, we examine the universal setting, where the (noise-free) source is an unknown member P/sub /spl theta// of a given family {P/sub /spl theta//,/spl theta//spl isin//spl Theta/}. Here, inspired by an approach which was proven fruitful previously in the context of composite hypothesis testing, we allow the constraint on the excess-code-length exponent to be /spl theta/-dependent. Corollaries are derived for some special cases of interest, including Marton's (1974) classical source coding exponent and its generalization to the case where the constraint on the rate of the code is relaxed from an almost sure constraint to a constraint on the excess-code-length exponent.

We continue the study of adaptive schemes for the sequential lossy coding of individual sequences which was initiated by Linder and Lugosi (see ibid., p.2533-38, 2001). Specifically, we consider fixed-rate lossy coding systems of fixed (or zero) delay where the encoder (which is allowed to use randomization) and the decoder are connected via a noiseless channel of a given capacity. It is shown that for any finite set of such coding schemes of a given rate, there exists a source code (adhering to the same structural and delay limitations) with the same rate whose distortion is with high probability almost as small as that of the best scheme in that set, uniformly for all individual sequences. Applications of this result to reference classes of special interest are outlined. These include the class of scalar quantizers, trellis encoders with sliding block decoders, and differential pulse code modulator (DPCM)-based source codes. In particular, for the class of all scalar quantizers, a source code is obtained with (normalized) distortion redundancy relative to the best scheme in the reference class of order n/sup -1/3/ log n (where n is the sequence length). This improves the n/sup -1/5/ log n rate achieved by Linder and Lugosi. More importantly, the decoder here is deterministic and, in particular, does not assume a common randomization sequence available at both encoder and decoder. Finally, we consider the case where the individual sequence is corrupted by noise prior to reaching the coding system, whose goal now is to reconstruct a sequence with small distortion relative to the clean individual sequence. It is shown that for the case of a finite alphabet and an invertible channel transition probability matrix, for any finite set of sliding-window schemes of a given rate, there exists a source code (allowed to use randomization yet adhering to the same delay constraints) whose performance is, with high probability, essentially as good as the best scheme in the class, for all individual sequences.

The problem of predicting the next outcome of an individual binary sequence, based on noisy observations of the past, is considered. The goal of the predictor is to perform, for each individual sequence, "almost" as well as the best in a set of experts, where performance is evaluated using a general loss function. A comprehensive approach to prediction in this noisy setting is presented and proven generally efficient under appropriate conditions. As an illustration of the applicability of the approach suggested for concrete situations, two important special cases are explicitly treated. The first is the case where the data-corrupting noise process is binary-valued (where the observed bit is the bitwise XOR of the clean bit and the noise bit). The second case is that of real-valued additive noise. It is shown that even in this more challenging situation, where the information available to the predictor regarding the past sequence is incomplete, a predictor can be guaranteed to successfully compete with a whole set of experts in considerably strong senses.

The problem of predicting the next outcome of an individual binary sequence corrupted by noise using finite memory, is considered. The conditional finite-state (FS) predictability of an infinite individual sequence given its noisy version is defined as the minimum fraction of errors that can be made by any FS predictor fed by the noisy version. It is proved that the conditional FS predictability can be attained almost surely by universal sequential prediction schemes in the case where the noisy version is the output of a binary-symmetric channel (BSC) whose input is the clean individual sequence. In particular, universal predictors of the original noise-free setting, which operate on the noisy sequence, have this property. Moreover, these universal predictors do not depend on the crossover probability characterizing the BSC. It is seen that the noisy setting gives rise to additional criteria by which the performance of prediction schemes can be assessed. Finally, a closer look is taken at the conditional FS predictability, and this quantity is proposed as an additional measure of the complexity of a sequence, perhaps finer and more informative than the predictive complexity of the noise-free setting.

The problem of predicting the next outcome of an individual binary sequence, based on noisy observations of the past is considered.The goal of the predictor is to perform, for each individual clean sequence (almost) as well as the best "expert" in a finite set, where performance is evaluated using a general loss function.This setup is a generalization of that considered extensively by researchers from various disciplines of universal prediction and forecasting for the case where the observation of the past data is corrupted by noise.In this work, we restrict ourselves to the case where the noise is an additive, i.i.d Bernoulli(p) process and where its parameter p is assumed known to the predictor.In the expected loss regime, for a given sequence, we define the regret as the difference between the total expected loss of the predictor on the entire sequence and that of the best expert in the comparison class.We generalize and improve the recent order results of Haussler et al. [7] to this noisy setup for a large class of loss functions and show that under certain conditions on the loss functions, the minimax regret is 0(log N) while under other conditions it is e(Jw), where n is the sequence length and N is the cardinality of the expert class.It is also seen that this new setup, which involves a stochastic noise process, gives rise to additional performance 'This work is part of an M.Sc.