This paper addresses lossy transmission of a common source over a broadcast channel when there is correlated side information at the receivers, with emphasis on the quadratic Gaussian and binary Hamming cases. A digital scheme that combines ideas from the lossless version of the problem, i.e., Slepian-Wolf coding over broadcast channels, and dirty paper coding, is presented and analyzed. This scheme uses layered coding where the common layer information is intended for both receivers and the refinement information is destined only for one receiver. For the quadratic Gaussian case, a quantity characterizing the combined quality of each receiver is identified in terms of channel and side information parameters. It is shown that it is more advantageous to send the refinement information to the receiver with ¿better¿ combined quality. In the case where all receivers have the same overall quality, the presented scheme becomes optimal. Unlike its lossless counterpart, however, the problem eludes a complete characterization.

The successive refinement problem is extended to vector sources where individual distortion constraints are posed on each vector component. For vector Gaussian sources with squared-error distortion, a single-letter rate-distortion characterization is inherited from the previously studied Gaussian multiple descriptions problem with covariance distortion constraints. Though this characterization is amenable to well-known numerical convex optimization techniques, an analytical solution is difficult to obtain in full generality even for 2-D sources. In this work, the special case of successive refinability is addressed analytically. Specifically, vector Gaussian sources are shown to benotsuccessively refinable everywhere unlike scalar Gaussian sources. It is also shown that, for 2-D Gaussian sources, the rate loss at the second stage can be as high as 0.5 b/sample in a ¿degenerate¿ scenario corresponding to what is known as sequential coding of correlated sources. Finally, analysis of 2-D binary symmetric sources with Hamming distortion reveals that the behavior of these sources with respect to successive refinability exhibits remarkable similarity to their 2-D Gaussian counterparts.

The rate-distortion (RD) problem for two-layer coding of a pair(X,Y) of correlated sources is considered. The first layer information enables reconstruction ofXwithin a certain distortionDX, while reception of both layers additionally enables reconstruction ofYwithin distortionDY. Although this problem is a special case of the successive refinement problem, the computation of the RD region for this scenario is nontrivial. Using a general class of outer bounds (analogous to Shannon lower bound in the classical RD theory) to the successive refinement rate-distortion region, the successive coding RD region for the case where(X,Y) is a jointly Gaussian pair and the distortion measure is squared-error is explicitly characterized.

It has been recently discovered that complementary graph entropy characterizes (and offers new insights into) the minimum asymptotic rate for zero-error source coding with decoder side information. This paper presents new results that build on and complement this discovery. Specifically, i) previously unknown subadditivity properties of complementary graph entropy are derived, and ii) zero-error coding rates are characterized in terms of complementary graph entropy for two multiterminal coding scenarios. For both scenarios, the rate characterization implies no rate loss relative to point-to-point source coding.

This paper deals with the design of coding schemes for transmitting a source over a broadcast channel when there is source side information at the receivers. Based on Slepian-Wolf coding over broadcast channels, three hybrid digital/analog schemes are proposed and their power-distortion tradeoff is investigated for Gaussian sources and Gaussian broadcast channels. All three transmit the same digital and analog information but with varying coding order. Although they are not provably optimal in general, they can significantly outperform uncoded transmission and separate source and channel coding.

This paper analyzes the problem of hierarchical channel coding for memoryless channels: given a codebook at a particular power level, if the allowed power level is increased, the expanded codebook is generated by pairwise addition of elements from the existing codebook and an auxiliary codebook. This is the counterpart of the problem of additive successive refinement in source coding. The supported set of rates in the channel coding scenario is fully characterized in this paper. The behavior of hierarchical coding schemes is analyzed for some representative channels. It is shown that for many common channels, hierarchical coding does not entail a loss of capacity at either layer.

This paper deals with the design of scalar quantizers for source coding with side information at the decoder. In the fixed length scenario, under high-resolution assumptions, the optimal level density is shown to be periodic. The operational rate-distortion performance is then characterized. The performance of variable length codes with uniform quantization is also characterized.

This paper deals with the design of coding schemes for lossy transmission of a source over a broadcast channel when there is correlated side information at the receivers. Using ideas from Slepian-Wolf coding over broadcast channels and dirty paper coding, new schemes are presented and their rate-distortion performance is derived. For the binary Hamming and quadratic Gaussian scenarios, when the source and the channel bandwidths are equal, it is shown that these schemes are sometimes optimal and that they can outperform both separate source and channel coding, and uncoded transmission.

This paper deals with spatial prediction in Wyner-Ziv video coding. Coding structures that extend DPCM to the distributed coding scenario are presented. Using a high resolution approximation, the optimal prediction filters for these structures are derived. The resulting predictive coder is employed to compress the DC component of a transform based distributed video coding system. Preliminary results show rate-distortion gains compared to the case without spatial prediction.

We consider the problem of storing data from multiple correlated sources in a database, so as to enable efficient future retrieval of data from select subsets of the sources, where only statistical information about queries may be available in advance. This setting poses new challenges in terms of the precise tradeoffs between storage rate, retrieval rate and distortion. We derive a gradient descent algorithm to optimize the joint encoding (storage) procedure, the decoder, and the retrieval procedure via mapping from queries to subsets of the stored data to retrieve and decode, so that the average retrieval rate-distortion cost is minimized, given a pre-specified overall storage capacity (or rate). Experiments conducted on real and synthetic data-sets demonstrate that our selective retrieval procedure is able to achieve significantly better trade-offs than joint compression, with retrieval speed-ups reaching 5X and distortion gains of up to 3.5 dB possible.

The rate-distortion problem for two-layer coding of a pair (X,Y) of correlated sources is considered. The first layer information enables reconstruction of X within a certain distortion Dx, while reception of both layers additionally enables reconstruction of Y within distortion Dy. While this problem is a special case of the successive refinement problem, the computation of the rate-distortion region for this scenario is non- trivial. Using a general class of outer bounds to the successive refinement rate-distortion region, the successive coding rate- distortion region for the case where (X, Y) is a jointly Gaussian pair and the distortion measure is squared-error is explicitly characterized.

This paper addresses the problem of optimal minimum mean-squared error reconstruction of quantised samples in Wyner-Ziv video coding systems. Closed-form expressions of the optimal reconstructed values are derived for a Laplacian correlation model. The method is used for both single and multiple side information scenarios (the latter is also referred to as multi-hypothesis Wyner-Ziv decoding). The efficiency of the proposed optimal reconstruction method is confirmed by rate-distortion performance results, showing significant decrease of the distortion of the decoded sequence, compared to simple reconstruction methods that have been employed so far.

This paper considers the design of efficient quantizers for a distributed source coding system. The information is encoded at independent terminals and transmitted across separate channels, any of which may fail. The scenario subsumes a wide range of vector quantization problems. Greedy descent methods rely heavily on initialization, and the presence of numerous 'poor' local optima on the distortion cost surface strongly motivates the use of a global design algorithm. We propose a deterministic annealing approach for the design of all components of a generic distributed source coding system. Our approach avoids many poor local optima, is independent of initialization, and does not assume any prior information on the underlying source distribution. Simulation results show significant gains over an iterative greedy algorithm.

The focus of this work is on the design of efficient quantizers for correlated sources subject to complexity limitations on the encoding terminals. Existing iterative descent methods rely heavily on initialization, and the prevalence of numerous 'poor' local optima strongly motivates the use of a global design algorithm. We propose a multiple-prototype based deterministic annealing approach for the joint design of all components of a generic distributed source coding system. Our approach avoids many poor local optima, is independent of initialization and does not assume any prior information on the underlying source distribution. Simulation results show substantial gains over a Lloyd-like iterative algorithm

This correspondence presents a novel application of the theta function defined by Lovasz. The problem of coding for transmission of a source through a channel without error when the receiver has side information about the source is analyzed. Using properties of the Lovasz theta function, it is shown that separate source and channel coding is asymptotically suboptimal in general. By contrast, in the case of vanishingly small probability of error, separate source and channel coding is known to be asymptotically optimal. For the zero-error case, it is further shown that the joint coding gain can in fact be unbounded. Since separate coding simplifies code design and use, conditions on sources and channels for the optimality of separate coding are also derived

Motivated by the sensor network setting, we consider lossless storage of correlated discrete memoryless sources. The underlying tradeoff is between exploitation of inter-source correlation for low rate storage and efficient (low rate) selective retrieval from the fusion storage. We define the problem of shared descriptions (SD) source coding and relate it to the storage and retrieval problem. We present an achievable rate region for the SD problem and use it to characterize the storage vs. retrieval tradeoff

This correspondence investigates the behavior of the compound channel under a zero-error constraint. We derive expressions for the capacity when a) neither the encoder nor decoder has side-information about the channel; b) when only the encoder has such side-information. These expressions are given in terms of capacities of appropriately defined sets of graphs. We clarify that an earlier treatment of the zero-error capacity of a compound channel corresponds to the case where the decoder has side-information about the channel. We also characterize the minimum asymptotic rate for the source coding dual of the compound channel problem, namely, source coding with compound side information. Finally, we contrast the zero-error and asymptotically vanishing error capacities of the compound channel.

This correspondence focuses on a significant distinction between two hierarchical type covering strategies, namely, weak and strong covering, and on the impact of this distinction on known results. In particular, it is demonstrated that the rate region for weak covering, whose natural use is in scalable source coding, is generally larger than the rate region for strong covering, which is primarily useful in hierarchical guessing. This correspondence also presents a corrected converse result for the hierarchical guessing problem.

The compound channel is one of the simplest generalizations of the discrete memoryless channel (DMC). In this paper, we characterize the zero-error capacity when neither the encoder nor the decoder is informed of the choice of DMC s. We present a complete characterization of the compound channel capacities

A basic problem in information theory is source coding under a distortion constraint when the decoder has side-information about the source. In this paper the problem of variable length coding of a memoryless source under a maximum distortion constraint when there is side-information solely at the decoder is focused. Using a combinatorial approach, a nonsingle-letter expression for the minimum asymptotic average rate as well as single-letter bounds on this rate is derived

This paper describes the guessing subject to rate-distortion theory. The concept of type covering is the set of vectors with the identical distortion balls. The main use of hierarchical type covering was the determination of achievable error exponents in scalable source coding. Weak covering is sufficient for that purpose. Strong covering is necessary for hierarchical guessing. The two covering strategies and their characterizations lead to different rate regions.

There exists a huge demand for multimedia goods and services in the Internet. Currently available bandwidth speeds can support sale of downloadable content like CDs, e-books, etc. as well as services like video-on-demand. In the future, such services will be prevalent in the Internet. Since costs are typically fixed, maximizing revenue can maximize profits. A primary determinant of revenue in such econtent markets is how much value the customers associate with the content. Though marketing surveys are useful, they cannot adapt to the dynamic nature of the Internet market. In this work, we examine how to learn customer valuations in close to real-time. Our contributions in this paper are threefold: (1) we develop a probabilistic model to describe customer behavior, (2) we develop a framework for pricing e-content based on basic economic principles, and (3) we propose a price discovering algorithm that learns customer behavior parameters and suggests prices to an e-content provider. We validate our algorithm using simulations. Our simulations indicate that our algorithm generates revenue close to the maximum expectation. Further, they also indicate that the algorithm is robust to transient customer behavior. 1.

A deterministic annealing algorithm for the design of tiedmixture HMM recognizers is proposed, which reduces the training sensitivity to parameter initialization, automatically smoothes the classification error cost function to allow gradientbased optimization, and seeks better solutions than known techniques. The new approach introduces randomness into the classification rule during the training process, and minimizes the expected error rate while controlling the level of randomness via a constraint on the Shannon entropy. As the entropy constraint is gradually relaxed, the effective cost function converges to the classification error rate and the system becomes a hard (nonrandom) recognizer. Experiments show that the proposed method outperforms design by maximum likelihood reestimation and by generalized probabilistic descent.