This paper investigates the incorporation of fairness considerations, as defined in the behavioral economics literature, into game-theoretic formulations of dynamic pricing algorithms in electricity markets. Traditionally, these markets are modeled using Stackelberg equilibria between electricity producers (companies) and consumers, where the producer acts as the leader by setting the electricity price, and consumers respond by adjusting their load. This conventional order of play inherently limits the producer's ability to arbitrarily increase prices, as the load is price-dependent and the producer commits to supplying a minimum load prior to the interaction. Recent analyses, however, indicate that the order of play may reverse in practical scenarios where players converge to equilibrium through learning dynamics. In this reversed hierarchy, fairness constraints become pivotal in preventing the producer from opportunistically escalating prices without bound. Employing a time-of-use pricing framework established in existing literature, we perform a numerical analysis of the equilibria associated with both orders of play, with particular emphasis on the role of the introduced fairness considerations.

This paper studies a quantization problem between an encoder and a decoder with misaligned objectives, where the quantization indices are transmitted over a noisy channel. Building on the prior results on the non-strategic counterpart of this problem, we characterize the encoding and decoding strategies and expected encoder and decoder distortions at the Stackelberg equilibrium, where the encoder is the leader, and the decoder is the follower. On the design side, we extend the gradient-descent-based solution framework developed for the noiseless setting to this noisy communication scenario, combined with uniformly randomized index mapping. We finally present numerical simulation results to demonstrate the efficacy of the proposed approach. The Matlab codes associated with the design and evaluation of the proposed algorithm are provided at: https://github.com/strategic-quantization/channel-optimized-strategic-quantizer.

This paper quantitatively analyzes a game over a social network of agents (nodes), some of which are controlled by two players who maximize and minimize polarization over this network. Agents' opinions evolve according to the Friedkin-Johnsen model, and players can change only the innate opinion of an agent. Polarization is measured as the sample variance of the agents' steady-state opinions. The game is considered void if the players choose the same agents, which constitutes a zero-sum game. We first analyze the functional properties of this game and characterize the best response for each player given the agent. Fictitious play is used to obtain the equilibria in real social networks. Subsequently, the paper delves into an exploration of the properties of the Nash equilibrium (NE).

This paper is concerned with the quantization setting where the encoder and the decoder have misaligned objectives. While the unconstrained variation of this problem has been well-studied under the theme of information design problems in Economics, the problem becomes more appealing and relevant to engineering applications with a constraint on the cardinality of the message space. We first motivate the problem via a toy example demonstrating the intricacies of the strategic variation of the quantization problem, explicitly showing that the quantization resolution can change the nature of optimal encoding policy and the iterative optimization of the decoder and the encoder mappings may not converge to a local optimum solution, in sharp contrast with the classical quantization problem that admits the Lloyd-Max method as a local optimum solution. As a remedy, we develop a gradient-descent based solution. We analyze the poor local optimal optima issues associated with the optimization method and show that even for well-behaving sources, such as Gaussian, there are multiple local minima, depending on the distortion measures chosen, in sharp contrast with the classical quantization. We finally present numerical results obtained via the proposed algorithm that suggest their validity and demonstrate features of the strategic version of the quantization problem that differentiate it from its classical counterpart.

This paper is concerned with the quantization setting where the encoder and the decoder have misaligned objectives. We first motivate the problem via a toy example which demonstrates the intricacies of the strategic quantization problem, specifically shows that iterative optimization of the decoder and the encoder mappings may not converge to a local optimum. As a remedy, we propose a dynamic programming based optimal optimization method, inspired by the early works in the quantization theory. We then extend our approach to variable-rate (entropy-coded) quantization. We finally present numerical results obtained via the proposed algorithms.

In this paper, we present new results on the achievable rate-distortion regions in networked scalable compression problems, based on a flexible codebook generation and binning method. First, we consider the problem of scalable coding in the presence of decoder side information, for which the prior work analyzed the two important cases the degraded side information where source X and the side information variables (Y1, Y2) form a Markov chain in the order of either X - Y1-Y2or X - Y2- Y1. First, we present an example non-Markov side information scenario where the proposed coding strategy achieves a strictly larger rate-distortion region compared to prior work. We then consider the problem of multi-user successive refinement where different users that are connected to a central server via links with different noiseless capacities strive to reconstruct the source in a progressive fashion. It is shown that a prior rate-distortion region is suboptimal in general, albeit its optimality for a Gaussian source with MSE distortion, and the proposed coding scheme achieves points beyond the achievable region of prior work.

This paper studies the well-known jamming problems in the context of strategic communication, a variation of the Bayesian Persuasion problem information economics. A communication problem with three agents, a transmitter, a receiver and a jammer, is considered. All players have diverging objectives: the transmitter and the receiver want to minimize their individual distortion functions while the jammer aims to maximize a convex combination of these functions. This leads to a hierarchical game whose equilibrium solutions are studied here. Here, the transmitter is the leader and hence announces an encoding strategy with full commitment, where the receiver acts as the follower. The game between the jammer and the transmitter-the receiver pair depends on the ability of this communicating pair to secretly agree on a random event, that is “common randomness”. In the presence of common randomness, the problem becomes a zero-sum game for which a saddle-point solution is sought. The saddle-point solution consists of randomized linear strategies for the communicating pair and additive independent Gaussian noise for the jammer. If common randomness is not available, then this problem does not admit a saddle-point solution. We derive and analyze the Stackelberg equilibrium between the communicating pair and the jammer, and show that equilibrium achieving strategies for all agents are linear/affine.

This paper analyzes the information disclosure problems originated in economics through the lens of information theory. Such problems are radically different from the conventional communication paradigms in information theory since they involve different objectives for the encoder and the decoder, which are aware of this mismatch and act accordingly. This leads, in our setting, to a hierarchical communication game, where the transmitter announces an encoding strategy with full commitment, and its distortion measure depends on a private information sequence whose realization is available at the transmitter. The receiver decides on its decoding strategy that minimizes its own distortion based on the announced encoding map and the statistics. Three problem settings are considered, focusing on the quadratic distortion measures, and jointly Gaussian source and private information: compression, communication, and the simple equilibrium conditions without any compression or communication. The equilibrium strategies and associated costs are characterized. The analysis is then extended to the receiver side information setting and the major changes in structure of optimal strategies are identified. Finally, an extension of the results to the broader context of decentralized stochastic control is presented.

This paper extends the well-known source coding problem of multiple descriptions, in its general and basic setting, to analog source-channel coding scenarios. Encoding-decoding functions that optimally map between the (possibly continuous valued) source and the channel spaces are numerically derived. The main technical tool is a non-convex optimization method, namely, deterministic annealing, which has recently been successfully used in other mapping optimization problems. The obtained functions exhibit several interesting structural properties, map multiple source intervals to the same interval in the channel space, and consistently outperform the known competing mapping techniques.

This paper analyzes the fundamental limits of strategic communication in network settings. Strategic communication differs from the conventional communication paradigms in information theory since it involves different objectives for the encoder and the decoder, which are aware of this mismatch and act accordingly. This leads to a Stackelberg game where both agents commit to their mappings ex-ante. Building on our prior work on the point-to-point setting, this paper studies the compression and communication problems with the receiver and/or the transmitter side information setting. The equilibrium strategies and the associated costs are characterized for the Gaussian variables and quadratic cost functions. Several questions on the benefit of side information in source and joint source-channel coding in such strategic settings are analyzed. Our analysis has uncovered an interesting result on optimality of uncoded communication in strategic source-channel coding in the presence of receiver side information.

Path planning is an important component of autonomous mobile sensing systems. This paper studies upper and lower bounds of communication performance over Gaussian sensor networks, to drive power-distortion metrics for path planning problems. The Gaussian multiple-access channel is employed as a channel model and two source models are considered. In the first setting, the underlying source is estimated with minimum mean-squared-error, while in the second, reconstruction of a random spatial field is considered. For both problem settings, the upper and the lower bounds of sensor power-distortion curve are derived. For both settings, the upper bounds follow from the amplify-and-forward scheme and the lower bounds admit a unified derivation based on data processing inequality and tensorization property of the maximal correlation measure. Next, closed-form solutions of the optimal power allocation problems are obtained under a weighted sum-power constraint. The gap between the upper and the lower bounds is analyzed for both weighted sum and individual power constrained settings. Finally, these metrics are used to drive a path planning algorithm and the effects of power-distortion metrics, network parameters, and power optimization on the optimized path selection are analyzed.

This paper presents a new achievable rate-distortion region for the general L channel multiple descriptions (MDs) problem. A well-known general region for this problem is due to Venkataramani, Kramer, and Goyal (VKG). Their encoding scheme is an extension of the El Gamal-Cover (EC) and Zhang-Berger (ZB) coding schemes to the L channel case and includes a combinatorial number of refinement codebooks, one for each subset of the descriptions. As in ZB, the scheme also allows for a single common codeword to be shared by all descriptions. This paper proposes a novel encoding technique involving combinatorial message sharing (CMS), where every subset of the descriptions may share a distinct common message. This introduces a combinatorial number of shared codebooks along with the refinement codebooks of. These shared codebooks provide a more flexible framework to tradeoff redundancy across the messages for resilience to descriptions loss. We derive an achievable rate-distortion region for the proposed technique, and show that it subsumes the VKG region for general sources and distortion measures. We further show that CMS provides a strict improvement of the achievable region for any source and distortion measures for which some two-description subset is such that ZB achieves points outside the EC region. We then show a more surprising result: CMS outperforms VKG for a general class of sources and distortion measures, including scenarios where the ZB and EC regions coincide for all two-description subsets. In particular, we show that CMS strictly improves on VKG, for the L-channel quadratic Gaussian MD problem, for all L ≥ 3, despite the fact that the EC region is complete for the corresponding two-descriptions problem. Consequently, the correlated quantization scheme (an extreme special case of VKG) that has been proven to be optimal for several cross sections of the L-channel quadratic Gaussian MD problem is strictly suboptimal in general. Using the encoding principles derived, we show that the CMS scheme achieves the complete rate-distortion region for several asymmetric cross sections of the L-channel quadratic Gaussian MD problem.

This paper studies the problem of global optimization of zero-delay source-channel codes that map between the source space and the channel space, under a given transmission power constraint and for the mean-square-error distortion. Particularly, we focus on two well-known network settings: the Wyner-Ziv setting where only a decoder has access to side information and the distributed setting where independent encoders transmit over independent channels to a central decoder. Prior work derived the necessary conditions for optimality of the encoder and decoder mappings, along with a greedy optimization algorithm that imposes these conditions iteratively, in conjunction with the heuristic noisy channel relaxation method to mitigate poor local minima. While noisy channel relaxation is arguably effective in simple settings, it fails to provide accurate global optimization in more complicated settings considered in this paper. We propose a powerful nonconvex optimization method based on the concept of deterministic annealing-which is derived from information theoretic principles and was successfully employed in several problems including vector quantization, classification, and regression. We present comparative numerical results that show strict superiority of the proposed method over greedy optimization methods as well as prior approaches in literature.

This paper considers the problem of optimal zero-delay jamming over an additive noise channel. Building on a sequence of recent results on conditions for linearity of optimal estimation, and of optimal mappings in source-channel coding, the saddle-point solution to the jamming problem is derived for general sources and channels, without recourse to Gaussianity assumptions. The linearity conditions are shown to play a pivotal role in jamming, in the sense that the optimal jamming strategy is to effectively force both the transmitter and the receiver to default to linear mappings, i.e., the jammer ensures, whenever possible, that the transmitter and the receiver cannot benefit from non-linear strategies. This result is shown to subsume the known result for Gaussian source and channel. The conditions and general settings where such unbeatable strategy can indeed be achieved by the jammer are analyzed. Moreover, a numerical procedure is provided to approximate the optimal jamming strategy in the remaining (source-channel) cases where the jammer cannot impose linearity on the transmitter and the receiver. Next, the analysis is extended to vector sources and channels. This extension involves a new aspect of optimization: the allocation of available transmit and jamming power over source and channel components. Similar to the scalar setting, the saddle-point solution is derived using the linearity conditions in vector spaces. The optimal power allocation strategies for the jammer and the transmitter have an intuitive interpretation as the jammer allocates power according to water-filling over the channel eigenvalues, while the transmitter performs water-pouring (reverse water-filling) over the source eigenvalues.

The hidden Markov model (HMM) is widely used to model processes in several real world applications, including speech processing and recognition, image understanding and sensor networks. A problem of concern is that of quantization of the sequence of observations generated by an HMM, which is referred as a hidden Markov source (HMS). Despite the importance of the problem, and the well-defined structure of the process, there has been very limited work addressing the optimal quantization of HMS, and conventional approaches focus on optimization of parameters of known quantization schemes. This paper proposes a method that directly tracks the state probability distribution of the underlying source and optimizes the encoder structure according to the estimated HMS status. Unlike existing approaches, no stationarity assumption is needed, and code parameters are updated on they: with each observation, both the encoder and the decoder refine the estimated probability distribution over the states. The main approach is then specialized to a practical variant involving switched quantizers, and an algorithm that iteratively optimizes the quantize codebooks is derived. Numerical results show superiority of the proposed approach over prior methods.

A limited energy budget is a major obstacle to the practical, wide deployment of sensor networks and hence necessitates the judicious optimization of available resources. In this paper, joint optimization of sensing and communication resources to minimize total energy spent within a sensor network is considered. A particular sensor network model with one Gaussian source observed by many sensors, subject to additive independent Gaussian observation noise, is examined. Sensors communicate with the receiver over an additive Gaussian multiple access channel. The aim of the receiver is to reconstruct the underlying source with minimum mean squared error. The fundamental tradeoff between communication and sensing over this sensor network model is characterized. Under symmetric conditions, for a single sensor, power is shared equally between communication and sensing. As the number of sensors increases, the sensing error dominates the overall error expression, hence sensing takes almost all power. The optimal power scheduling among sensors in the asymmetric case is determined, and it is shown that the power allocation schedule admits a simple decentralized implementation. Numerical results show that joint optimization of communication and sensing power yields significant power savings compared to the conventional approach of optimization of only communication power allocation.

In this paper, a new coding scheme for the multiple access channel (MAC) with noisy cooperative links is proposed. The cooperation cost is modelled by powers spent on exchanging common information at transmitters. The optimal power allocation policy is derived to explore the tradeoff between cooperation and transmission. For some important cases, optimal power allocation that maximizes weighted sum rate, is found analytically. The sufficient and necessary condition for which the sum and the individual rates are simultaneously maximized, is identified. Analytical and numerical results suggest that the transmitter, whose power budget is dominated by that of the other, acts purely as a relay. The cooperation gain becomes more significant when the difference between the power budgets is smaller.

This paper studies the optimization of zero-delay analog mappings in a network setting that involves distributed coding. The cost surface is known to be non-convex, and known greedy methods tend to get trapped in poor locally optimal solutions that depend heavily on initialization. We derive an optimization algorithm based on the principles of “deterministic annealing”, a powerful global optimization framework that has been successfully employed in several disciplines, including, in our recent work, to a simple zero-delay analog communications problem. We demonstrate strict superiority over the descent based methods, as well as present example mappings whose properties lend insights on the workings of the solution and relations with digital distributed coding.

The problem of scalable coding while exploiting the decoder side information is considered. Prior work considered the two important cases concerning the degraded side information where source X and the side information variables (Y1, Y2) form a Markov chain in the order of either X − Y1− Y2or X − Y2− Y1. While the encoding schemes for these settings differ considerably, they are both based on the combination of conditional codebook encoding, a standard tool in scalable coding, and random binning, conventionally used in decoder side information problems. In this paper, an encoding scheme is proposed solely on the basis of random binning, which essentially performs scalable and Wyner-Ziv coding simultaneously. Proposed scheme achieves the rate-distortion regions of prior results. A practical advantage of the unifying scheme is the fact that random binning can be realized via practical tools such as nested lattice codes and channel codes. Finally, motivated by the proposed encoding scheme, a network interpretation of scalable coding is considered. An achievable region is derived for this problem setting and the potential benefits of networked scalable coding are shown.

Exploration versus exploitation in a sensor field with a mobile agent is examined in the context of source coding. The encoder is the low complexity data gathering agent. The decoder is a high complexity fusion center. The encoder first sends a coarse description of the random field, then transmits a refined description of a region of interest, i.e., a subset of the correlated sources in the first stage and so on. The main source coding challenge is that the receiver wants to refine a subset of the correlated sources that is unknown to the encoder a priori. The conventional approach of scalable coding via conditional codebook encoding (CCE) requires a codebook that is exponential in size with respect to the number of sources and also the number of refinement stages. This paper studies an alternative approach, using random binning (RB), in lieu of CCE. The universality of RB plays a key role, as the encoder does not know a priori which sources the decoder wants to refine. It is shown that RB does not introduce any loss and can effectively replace CCE while providing significant storage reduction in terms of the number of codewords stored. Achievable rate regions are derived for the single and the multi-terminal encoding settings.

This paper proposes an optimization method, based on information theoretic ideas, to a class of distributed control problems. As a particular test case, the well-known and numerically “over-mined” problem of decentralized control and implicit communication, commonly referred to as Witsenhausen's counterexample, is considered. The key idea is to randomize the zero-delay mappings. which become “soft”, probabilistic mappings to be optimized in a deterministic annealing process, by incorporating a Shannon entropy constraint in the problem formulation. The entropy of the mapping is controlled and gradually lowered to zero to obtain deterministic mappings, while avoiding poor local minima. For the particular test case, our approach obtains new mappings that shed light on the structure of the optimal solution, as well as achieving a small improvement in total cost over the state of the art in numerical approaches to this problem. Proposed method is general and applicable to any problem of similar nature.

This paper studies the zero-delay source-channel coding problem, and specifically the problem of obtaining the vector transformations that optimally map between the m-dimensional source space and k-dimensional channel space, under a given transmission power constraint and for the mean square error distortion. The functional properties of the cost are studied and the necessary conditions for the optimality of the encoder and decoder mappings are derived. An optimization algorithm that imposes these conditions iteratively, in conjunction with the noisy channel relaxation method to mitigate poor local minima, is proposed. The numerical results show strict improvement over prior methods. The numerical approach is extended to the scenario of source-channel coding with decoder side information. The resulting encoding mappings are shown to be continuous relatives of, and in fact subsume as special case, the Wyner-Ziv mappings encountered in digital distributed source coding systems. A well-known result in information theory pertains to the linearity of optimal encoding and decoding mappings in the scalar Gaussian source and channel setting, at all channel signal-to-noise ratios (CSNRs). In this paper, the linearity of optimal coding, beyond the Gaussian source and channel, is considered and the necessary and sufficient condition for linearity of optimal mappings, given a noise (or source) distribution, and a specified a total power constraint are derived. It is shown that the Gaussian source-channel pair is unique in the sense that it is the only source-channel pair for which the optimal mappings are linear at more than one CSNR values. Moreover, the asymptotic linearity of optimal mappings is shown for low CSNR if the channel is Gaussian regardless of the source and, at the other extreme, for high CSNR if the source is Gaussian, regardless of the channel. The extension to the vector settings is also considered where besides the conditions inherited from the scalar case, additional constraints must be satisfied to ensure linearity of the optimal mappings.

The two most prevalent notions of common information (CI) are due to Wyner and Gács-Körner and both the notions can be stated as two different characteristic points in the lossless Gray-Wyner region. Although the information theoretic characterizations for these two CI quantities can be easily evaluated for random variables with infinite entropy (e.g., continuous random variables), their operational significance is applicable only to the lossless framework. The primary objective of this paper is to generalize these two CI notions to the lossy Gray-Wyner network, which hence extends the theoretical foundation to general sources and distortion measures. We begin by deriving a single letter characterization for the lossy generalization of Wyner's CI, defined as the minimum rate on the shared branch of the Gray-Wyner network, maintaining minimum sum transmit rate when the two decoders reconstruct the sources subject to individual distortion constraints. To demonstrate its use, we compute the CI of bivariate Gaussian random variables for the entire regime of distortions. We then similarly generalize Gács and Körner's definition to the lossy framework. The latter half of this paper focuses on studying the tradeoff between the total transmit rate and receive rate in the Gray-Wyner network. We show that this tradeoff yields a contour of points on the surface of the Gray-Wyner region, which passes through both the Wyner and Gács-Körner operating points, and thereby provides a unified framework to understand the different notions of CI. We further show that this tradeoff generalizes the two notions of CI to the excess sum transmit rate and receive rate regimes, respectively.

This paper considers the problem of minimum cost communication of correlated sources over a network with multiple sinks, which consists of distributed source coding followed by routing. We introduce a new routing paradigm called dispersive information routing (DIR), wherein the intermediate nodes are allowed to split a packet and forward subsets of the received bits on each of the forward paths. This paradigm opens up a rich class of research problems, which focus on the interplay between encoding and routing in a network. Unlike conventional routing methods such as in [1], DIR ensures that each sink receives just the information needed to reconstruct the sources it is required to reproduce. We demonstrate using simple examples that the proposed approach offers better asymptotic performance than conventional routing techniques. We show that, under certain assumptions on the cost function, the problem of finding the minimum cost under DIR essentially reduces to characterizing an achievable rate region for a new multiterminal information theoretic setup. While it is possible to derive an achievable region for this setup using prior results from general multiterminal source coding [3], these techniques do not exploit the underlying problem structure and thereby lead to suboptimal regions. In this paper, we propose a new coding scheme, using principles from multiple descriptions encoding [2], and show that it strictly improves upon a corresponding variant of coding scheme in [3]. We further show that the new coding scheme achieves the complete rate region for certain special cases of the general setup and thereby achieves the minimum communication cost under this routing paradigm.

This paper studies a particular sensor network model which involves one single Gaussian source observed by many sensors, subject to additive independent Gaussian observation noise. Sensors communicate with the receiver over an additive Gaussian multiple access channel. The aim of the receiver is to reconstruct the underlying source with minimum mean squared error. The scenario of interest here is one where some of the sensors act as adversary (jammer): they strive to maximize distortion. We show that the ability of transmitter sensors to secretly agree on a random event, that is “coordination”, plays a key role in the analysis. Depending on the coordination capability of sensors and the receiver, we consider two problem settings. The first setting involves transmitters with “coordination” capabilities in the sense that all transmitters can use identical realization of randomized encoding for each transmission. In this case, the optimal strategy for the adversary sensors also requires coordination, where they all generate the same realization of independent and identically distributed Gaussian noise. In the second setting, the transmitter sensors are restricted to use fixed, deterministic encoders and this setting, which corresponds to a Stackelberg game, does not admit a saddle-point solution. We show that the the optimal strategy for all sensors is uncoded communications where encoding functions of adversaries and transmitters are in opposite directions. For both settings, digital compression and communication is strictly suboptimal.

In this paper, we study the zero-delay source-channel coding problem, and specifically the problem of obtaining the vector transformations that optimally map between the m-dimensional source space and the k-dimensional channel space, under a given transmission power constraint and for the mean square error distortion. We first study the functional properties of this problem and show that the objective is concave in the source and noise densities and convex in the density of the input to the channel. We then present the necessary conditions for optimality of the encoder and decoder mappings. A well known result in information theory pertains to the linearity of optimal encoding and decoding mappings in the scalar Gaussian source and channel setting, at all channel signal-to-noise ratios (CSNRs). In this paper, we study this result more generally, beyond the Gaussian source and channel, and derive the necessary and sufficient condition for linearity of optimal mappings, given a noise (or source) distribution, and a specified power constraint. We also prove that the Gaussian source-channel pair is unique in the sense that it is the only source-channel pair for which the optimal mappings are linear at more than one CSNR value. Moreover, we show the asymptotic linearity of optimal mappings for low CSNR if the channel is Gaussian regardless of the source and, at the other extreme, for high CSNR if the source is Gaussian, regardless of the channel.

This paper focuses on the problem of L-channel quadratic Gaussian multiple description (MD) coding. We recently introduced a new encoding scheme in [1] for general L-channel MD problem, based on a technique called `Combinatorial Message Sharing' (CMS), where every subset of the descriptions shares a distinct common message. The new achievable region subsumes the most well known region for the general problem, due to Venkataramani, Kramer and Goyal (VKG) [2]. Moreover, we showed in [3] that the new scheme provides a strict improvement of the achievable region for any source and distortion measures for which some 2-description subset is such that the Zhang and Berger (ZB) scheme achieves points outside the El-Gamal and Cover (EC) region. In this paper, we show a more surprising result: CMS outperforms VKG for a general class of sources and distortion measures, which includes scenarios where for all 2-description subsets, the ZB and EC regions coincide. In particular, we show that CMS strictly extends VKG region, for the L-channel quadratic Gaussian MD problem for all L ≥ 3, despite the fact that the EC region is complete for the corresponding 2-descriptions problem. Using the encoding principles derived, we show that the CMS scheme achieves the complete rate-distortion region for several asymmetric cross-sections of the L-channel quadratic Gaussian MD problem, which have not been considered earlier.

This paper studies optimization of zero-delay source-channel codes, and specifically the problem of obtaining globally optimal transformations that map between the source space and the channel space, under a given transmission power constraint and for the mean square error distortion. Particularly, we focus on the setting where the decoder has access to side information, whose cost surface is known to be riddled with local minima. Prior work derived the necessary conditions for optimality of the encoder and decoder mappings, along with a greedy optimization algorithm that imposes these conditions iteratively, in conjunction with the heuristic “noisy channel relaxation” method to mitigate poor local minima. While noisy channel relaxation is arguably effective in simple settings, it fails to provide accurate global optimization results in more complicated settings including the decoder with side information as considered in this paper. We propose a global optimization algorithm based on the ideas of “deterministic annealing” - a non-convex optimization method, derived from information theoretic principles with analogies to statistical physics, and successfully employed in several problems including clustering, vector quantization and regression. We present comparative numerical results that show strict superiority of the proposed algorithm over greedy optimization methods as well as over the noisy channel relaxation.

Randomized (dithered) quantization is a method capable of achieving white reconstruction error independent of the source. Dithered quantizers have traditionally been considered within their natural setting of uniform quantization. In this paper we extend conventional dithered quantization to nonuniform quantization, via a subterfage: dithering is performed in the companded domain. Closed form necessary conditions for optimality of the compressor and expander mappings are derived for both fixed and variable rate randomized quantization. Numerically, mappings are optimized by iteratively imposing these necessary conditions. The resulting quantizer renders the reconstruction error white with negligible performance loss compared to the optimal quantizer. The framework is extended to include an explicit constraint that deterministic or randomized quantizers yield reconstruction error that is uncorrelated with the source. Surprising theoretical results show direct and simple connection between the optimal constrained quantizers and their unconstrained counterparts. Numerical results for the Gaussian source provide strong evidence that the proposed constrained randomized quantizer outperforms the conventional dithered quantizer, as well as the constrained deterministic quantizer.

This paper is concerned with transform coding of correlated sources in conjunction with variable rate quantization at high resolution. The approach builds on our prior work on optimality conditions for transform coding in the point-to-point setting. The first contribution involves transform coding with decoder side information. In this setting, side information is only available to the decoder, whereas the encoder knows the joint statistics. The necessary and sufficient condition for optimality of a unitary transform in the side information setting is derived, namely, such transform minimizes a conditional divergence-based measure of inter-dependence of the transform coefficients, given the side information. This optimality result subsumes prior, known results that were restricted to the Gaussian case, where the conditional Karhunen-Loeve transform is optimal. The second contribution involves distributed transform coding, where two correlated sources are to be transform coded separately, but decoded jointly. The necessary and sufficient condition for optimality of unitary transforms in the distributed coding setting is derived. It is then specialized to produce closed form optimal transforms for specific source densities, including the case of jointly Gaussian sources.

This paper is concerned with the optimal linear transforms in zero-delay source channel coding for Gaussian sources and channels. In preparation for the main results, we first consider the classical problem in the point-to-point setting, which had already been solved by Lee and Petersen, where we provide an alternative proof using majorization. We then analyze the performance of linear source-channel coding in the low signal-to-noise ratio (SNR) regime. We show that at asymptotically low SNR, or equivalently as the power tends to zero, the powerdistortion function of zero delay linear coding achieves optimum theoretically achievable performance. Finally, we consider zero-delay source-channel coding with decoder side information. Here, subject to structural constraints on the encoder, we find the optimal encoder-decoder pair in closed form. We analyze two structures: i) the encoder is constrained to be linear where we show that the optimal transform is product of matrices including as factor the conditional Karhunen Loéve transform (KLT) of the source given the side information. ii) the encoder consists of linear transformation followed by individual optimal nonlinear mapping of each transform coefficient. Using majorization principles, we show that the optimal transform does not depend on the nonlinearities introduced, as long as they are scale invariant, hence the optimal transform is also a product involving the conditional KLT of the source.

This paper proposes a new multiple description (MD) coding method and an associated achievable rate-distortion region for L ≥ 2 channels. The proposed scheme randomly bins codebooks chosen from the codebook structure, similar to that of the recently proposed combinatorial message sharing (CMS) scheme designed for conditional codebook encoding. The proposed scheme effectively performs multilayer random binning for each subset of the description, which hence enables to utilize the symmetry of a “subset” of the description rates wherever it exists. The new scheme specializes in to the conventional multilayer random binning as an extreme special case.

The two most prevalent notions of common information are due to Wyner and Gács-Körner and both the notions can be stated as two different characteristic points in the lossless Gray-Wyner region. Although these quantities can be easily evaluated for random variables with infinite entropy (eg. continuous random variables), the operational significance underlying their definition is applicable only to the lossless framework. The primary objective of this paper is to generalize these two notions of common information to the lossy Gray-Wyner network, which extends the theoretical intuition underlying their definitions for general sources and distortion measures. We begin with the lossy generalization of Wyner's common information, defined as the minimum rate on the shared branch of the Gray-Wyner network at minimum sum rate when the two decoders reconstruct the sources subject to individual distortion constraints. We derive a complete single letter information theoretic characterization for this quantity and use it to compute the common information of symmetric bivariate Gaussian random variables. We then derive similar results to generalize Gács-Körner's definition to the lossy framework. These two characterizations allow us to carry the practical insight underlying the two notions of common information to general sources and distortion measures.

There are two common types of encoding paradigms in multiple descriptions (MD) coding: i) an approach based on conditional codebook generation, which was originally initiated by El-Gamal and Cover for the 2 channel setting and later extended to more than 2 channels by Venkataramani, Kramer and Goyal (VKG), ii) and an approach based on Slepian and Wolf's random binning technique, proposed by Pradhan, Puri and Ramchandran (PPR) for L >; 2 descriptions. It is well known that the achievable region due to PPR subsumes the VKG region for the symmetric Gaussian MD problem. Motivated by several practical advantages of random binning based methods over the conditional codebook encoding, this paper focuses on the following important questions: Does a random binning based scheme achieve the performance of conditional codebook encoding, even for the 2 descriptions scenario? Are random binning based approaches beneficial for settings that are not fully symmetric? This paper answers both these questions in the affirmative. Specifically, we propose a 2 descriptions coding scheme, based on random binning, which subsumes the currently known largest region for this problem due to Zhang and Berger. Moreover, we propose its extensions to L >; 2 channels and derive the associated achievable regions. The proposed scheme enjoys the advantages of both encoding paradigms making it particularly useful when there is symmetry only within a subset of the descriptions.

This paper focuses on a new framework for scalable coding of information based on principles derived from common information of two dependent random variables. In the conventional successive refinement setting, the encoder generates two layers of information called the base layer and the enhancement layer. The first decoder, which receives only the base layer, produces a coarse reconstruction of the source, whereas the second decoder, which receives both the layers, uses the enhancement layer to refine the information further leading to a finer reconstruction. It is popularly known that asymptotic rate-distortion optimality at both the decoders is possible if and only if the source-distortion pair is successively refinable. However when the source is not successively refinable under the given distortion metric, it is impossible to achieve rate-distortion optimality at both the layers simultaneously. For this reason, most practical system designers resort to storing two individual representations of the source leading to significant overhead in transmission/storage costs. Inspired by the breadth of applications, in this paper, we propose a new framework for scalable coding wherein a subset of the bits sent to the first decoder is not sent to the second decoder. That is, the encoder generates one common bit stream which is routed to both the decoders, but unlike the conventional successive refinement setting, both the decoders receive an additional individual bitstream. By relating the proposed framework with the problem of common information of two dependent random variables, we derive a single letter characterization for the minimum sum rate achievable for the proposed setting when the two decoders are constrained to receive information at their respective rate-distortion functions. We show using a simple example that the proposed framework provides a strictly better asymptotic sum rate as opposed to the conventional scalable coding setup when the source-distortion pair is not successively refinable.

This paper addresses the L-channel multiple descriptions problem for a Gaussian source under mean squared error (MSE) distortion metric. We focus on particular cross-sections of the general rate-distortion region where a subset the 2L- 1 distortion constraints are not imposed. Specifically, we assume that certain descriptions are never received simultaneously at the decoder and thereby the transmitted codewords require joint typicality only within prescribed subsets. We derive a new encoding scheme and an associated rate-distortion region wherein joint typicality of codewords only within the prescribed subsets is maintained. We show that enforcing joint typicality of all the codewords entails strict suboptimality in the achievable rate-distortion region. Specifically, we consider a 3 descriptions scenario wherein descriptions 1 and 3 are never received simultaneously at the decoder and show that a strictly larger achievable region is obtained when the encoder maintains joint typicality of codewords only within the required subsets. To prove these results, we derive a lemma called the `subset typicality lemma' which plays a critical role in establishing the new achievable region.

When is optimal estimation linear? It is well known that when a Gaussian source is contaminated with Gaussian noise, a linear estimator minimizes the mean square estimation error. This paper analyzes, more generally, the conditions for linearity of optimal estimators. Given a noise (or source) distribution, and a specified signal-to-noise ratio (SNR), we derive conditions for existence and uniqueness of a source (or noise) distribution for which theLpoptimal estimator is linear. We then show that if the noise and source variances are equal, then the matching source must be distributed identically to the noise. Moreover, we prove that the Gaussian source-channel pair is unique in the sense that it is the only source-channel pair for which the mean square error (MSE) optimal estimator is linear at more than one SNR values. Furthermore, we show the asymptotic linearity of MSE optimal estimators for low SNR if the channel is Gaussian regardless of the source and, vice versa, for high SNR if the source is Gaussian regardless of the channel. The extension to the vector case is also considered where besides the conditions inherited from the scalar case, additional constraints must be satisfied to ensure linearity of the optimal estimator.

It is well-known for transform coding of multivariate Gaussian sources, that the Karhunen Loeve transform (KLT) minimizes the mean square error distortion. However, finding the optimal transform for general non-Gaussian sources has been an open problem for decades, despite several important advances that provide some partial answers regarding KLT optimality. In this paper, we present a necessary and sufficient condition for optimality of a transform when high resolution, variable rate quantizers are employed. We present not only a complete characterization of when KLT is optimal, but also a determining condition for optimality of a general (non-KLT) transform. This necessary and sufficient condition is shown to have direct connections to the well studied source separation problem. This observation can impact source separation itself, as illustrated with a new optimality result. Finally, we combine the transform optimality condition with algorithmic tools from source separation, to derive a practical numerical method to search for the optimal transform in source coding.

This paper considers the problem of optimal multi-hop routing of correlated sources over a network with multiple sinks and arbitrary network demands. We recently introduced a new routing paradigm in [10] called `dispersive information routing' (DIR), wherein the intermediate nodes are allowed to split a packet and forward a subset of the received bits on each forward path. DIR ensures that each sink receives just the information it requires to decode the sources it intends to reconstruct, and thereby outperforms conventional routing techniques in the literature. We proposed an encoding scheme called `power binning' which achieves complete rate region and the minimum cost under this paradigm when each sink is allowed to receive packets only from the sources it wants to reconstruct. This paper considers the optimum encoding scheme when every source can (possibly) communicate with every sink irrespective of what the sinks reconstruct. This generalization happens to be considerably more complex and we derive an achievable rate region and an associated achievable cost using principles from distributed source coding and multiple descriptions encoding.

This paper presents a new achievable rate-distortion region for the L-channel multiple descriptions problem. Currently, the most popular region for this problem is due to Venkataramani, Kramer and Goyal [3]. Their encoding scheme is an extension of the Zhang-Berger scheme to the L-channel case and includes a combinatorial number of refinement codebooks, one for each subset of the descriptions. All the descriptions also share a single common codeword, which introduces redundancy, but assists in better coordination of the descriptions. This paper proposes a novel encoding technique involving `Combinatorial Message Sharing', where every subset of the descriptions may share a distinct common message. This introduces a combinatorial number of shared codebooks along with the refinement codebooks of [3]. These shared codebooks provide a more flexible framework to trade off redundancy across the messages for resilience to descriptions loss. We derive an achievable rate-distortion region for the proposed technique, and show that it subsumes the achievable region of [3].

We recently proposed a new coding scheme for the L-channel multiple descriptions (MD) problem for general sources and distortion measures involving `Combinatorial Message Sharing' (CMS) [7] leading to a new achievable rate-distortion region. Our objective in this paper is to establish that this coding scheme strictly subsumes the most popular region for this problem due to Venkataramani, Kramer and Goyal (VKG) [3]. In particular, we show that for a binary symmetric source under Hamming distortion measure, the CMS scheme provides a strictly larger region for all L>; 2. The principle of the CMS coding scheme is to include a common message in every subset of the descriptions, unlike the VKG scheme which sends a single common message in all the descriptions. In essence, we show that allowing for a common codeword in every subset of descriptions provides better freedom in coordinating the messages which can be exploited constructively to achieve points outside the VKG region.

This paper considers the problem of characterizing the optimal tradeoff between the total transmit versus receive rate in the Gray-Wyner network. This tradeoff plays a crucial role in many important practical applications including establishing fundamental limits in databases for correlated sources and in minimum cost routing for networks. We develop the insight into this tradeoff by defining two quantities C(X, Y; R' ) and K(X,Y;R"), which quantify the shared rate as a function of the total transmit and receive rates respectively. Closely tied up with this tradeoff is the notion of common information of two dependent random variables. The two most influential definitions are due to Wyner [2] and Gács-Körner [1]. Though it is well know that these definitions can be characterized as two extreme points in the Gray-Wyner region, no contour with operational significance is known which connects them. We will show that the tradeoff between transmit and receive rates leads to a contour of points on the boundary of Gray-Wyner region which passes through the operating points of Wyner and Gács-Körner. We use these properties to derive alternate characterizations for the two definitions of common information under a broader unified framework.

This paper focuses on optimal analog mappings for zero-delay, distributed source-channel coding. The objective is to obtain the optimal vector transformations that map between m-dimensional source spaces and k-dimensional channel spaces, subject to a prescribed power constraint and assuming the mean square error distortion measure. Closed-form necessary conditions for optimality of encoding and decoding mappings are derived. An iterative de- sign algorithm is proposed, which updates encoder and decoder mappings by sequentially enforcing the complementary optimality conditions at each iteration. The obtained encoding functions are shown to be a continuous relative of, and in fact subsume as a special case, the Wyner-Ziv mappings encountered in digital distributed source coding systems, by mapping multiple source intervals to the same channel interval. Example mappings and performance results are presented for Gaussian sources and channels.

This paper considers the problem of minimizing the communication cost for a general multi-hop network with correlated sources and multiple sinks. For the single sink scenario, it has been shown that this problem can be decoupled, without loss of optimality, into two separate subproblems of distributed source coding and finding the optimal routing (transmission structure). It has further been established that, under certain assumptions, such decoupling also applies in the general case of multiple sinks and arbitrary network demands. We show that these assumptions are significantly restrictive, and further provide examples to substantiate the loss, including settings where removing the assumptions yields unbounded performance gains. Finally, an approach to solving the unconstrained problem, where routing and coding cannot be decoupled, is derived based on Han and Kobayashi's achievability region for multi-terminal coding.

When is optimal estimation linear? It is well-known that, in the case of a Gaussian source contaminated with Gaussian noise, a linear estimator minimizes the mean square estimation error. This paper analyzes more generally the conditions for linearity of optimal estimators. Given a noise (or source) distribution, and a specified signal to noise ratio (SNR), we derive conditions for existence and uniqueness of a source (or noise) distribution that renders the Lpnorm optimal estimator linear. We then show that, if the noise and source variances are equal, then the matching source is distributed identically to the noise. Moreover, we prove that the Gaussian source-channel pair is unique in that it is the only source-channel pair for which the MSE optimal estimator is linear at more than one SNR values.

In this paper, we consider the problem of minimum cost joint compression and routing for networks with multiple-sinks and correlated sources. We introduce a routing paradigm, called dispersive information routing, wherein the intermediate nodes are allowed to forward a subset of the received bits on subsequent paths. This paradigm opens up a rich class of research problems which focus on the interplay between encoding and routing in a network. What makes it particularly interesting is the challenge in encoding sources such that, exactly the required information is routed to each sink, to reconstruct the sources they are interested in. We demonstrate using simple examples that our approach offers better asymptotic performance than conventional routing techniques. We also introduce a variant of the well known random binning technique, called `power binning', to encode and decode sources that are dispersively transmitted, and which asymptotically achieves the minimum communication cost within this routing paradigm.

This paper is concerned with optimal transform coding in conjunction with dithered quantization. While the optimal deterministic quantizer's error is uncorrelated with the reconstructed value, the dithered quantizer yields quantization errors that are correlated with the reconstruction but are white and independent of the source. These properties offer potential benefits, but also have implications on the optimization of the rest of the coder. We derive the optimal transform for consequent dithered quantization. For fixed rate coding, we show that the transform derived for dithered quantization is universally optimal (for all sources), unlike the conventional quantization case where optimality of the Karhunen-Loeve transform is guaranteed for Gaussian sources. Moreover, we establish variable rate coding optimality for Gaussian sources.

Summary form only given: Dithered quantization has useful properties such as producing quantization noise independent of the source and continous reconstruction at the decoder side. Dithered quantizers have traditionally been considered within their natural setting of uniform quantization framework. A uniformly distributed (with step size matched to the quantization interval) dither signal is added before quantization and the same dither signal is subtracted from the quantized value at the decoder side (only subtractive dithering is considered in this paper). The quantized values are entropy coded conditioned on the dither signal. This work proposes and analyzes optimal (non-uniform) dithered quantization. One immediate problem with nonuniform dithered quantization is how to apply dithering for unequal quantization intervals. This problem is circumvented by performing dithering in the companded domain. After appropriate companding, uniform dither can be applied. The quantization problem is defined as finding the optimal compander mapping that minimizes the mean square error. To solve the problem, some approximations of rate and distortion expressions and to the compander mapping are used. First, we only consider the piecewise linear compander which is also used in deterministic quantizers. Also, we assume the error in each half quantization interval (the interval between the decision boundary and the reconstruction) is constant and only a function of the intervals length, i.e., identical to the case where for each interval a uniform dithered quantizer is applied. We also assume that rate can be approximated by the rate of the deterministic quantizer which uses the same compander. We derive the necessary conditions for optimality and design the compander by iterating between the necessary conditions.

The objective of dynamic voltage scaling (DVS) is to adapt the frequency and voltage for configurable platforms to obtain energy savings. DVS is especially attractive for video decoding systems due to their time-varying and highly complex workload and because the utility of decoding a frame is solely depending on the frame being decoded before its display deadline. Several DVS algorithms have been proposed for multimedia applications. However, the prior work did not take into account the video compression algorithm specifics, such as considering the temporal dependencies among frames and the required display buffer. Moreover, the effect of the passive (leakage) power when performing DVS for multimedia systems was not explicitly considered. In this paper, we determine the optimal scheduling of the active and passive states to minimize the total energy for video decoding systems. We pose our problem as a buffer-constrained optimization problem with a novel, compression-aware definition of processing jobs. We propose low-complexity algorithms to solve the optimization problem and show through simulations that significant improvements can be achieved over state-of-the art DVS algorithms that aim to minimize only the active power.

A video compression standard incorporates many tools and technologies which must be licensed by systems that deploy the standard. The licensing determines the royalty costs that must be paid to the holders of intellectual property on the respective tools. With current abundance of well understood and effective video compression tools, one can imagine the formation of cross cutting tool libraries with tools drawn from different video compression standards. This allows dynamic selection from a large pool of tools, having potentially overlapping functionality, when encoding individual video sequences. In this paper we examine the royalty cost aspect of the scenario where video is encoded using a library of royalty bearing tools by considering encoding that jointly optimizes rate, distortion, and royalty cost. We provide a system that optimizes video delivery under various licensing conditions imposed on tool intellectual property. We present an example of royalty based encoding (using assumed royalty costs) to show the merit of the proposed framework.

A methodology for complexity scalable video encoding and complexity control within the framework of the H.264/AVC video encoder is presented. To yield good rate-distortion performance under strict complexity/time constraints for instance in real-time communication, a framework for optimal complexity allocation at the macroblock level is necessary. We developed a macroblock level fast motion estimation based complexity scalable motion/mode search algorithm where the complexity is adapted jointly by parameters that determine the aggressiveness of an early stop criteria, the number of ordered modes searched, and the accuracy of motion estimation steps for the INTER modes. Next, these complexity parameters are adapted per macroblock based on a control loop to approximately satisfy an encoding frame rate target. The optimal manner of adapting the parameters is derived from prior training. Results using the developed scalable complexity H.264/AVC encoder demonstrate the benefit of adaptive complexity allocation over uniform complexity scaling.

Significant power savings can be achieved on voltage/frequency configurable platforms by dynamically adapting the frequency and voltage according to the workload (complexity). Video decoding is one of the most complex tasks performed on such systems due to its computationally demanding operations like inverse filtering, interpolation, motion compensation and entropy decoding. Dynamically adapting the frequency and voltage for video decoding is attractive due to the time-varying workload and because the utility of decoding a frame is dependent only on decoding the frame before the display deadline. Our contribution in this paper is twofold. First, we adopt a complexity model that explicitly considers the video compression specifics to accurately predict execution times. Second, based on this complexity model, we propose a dynamic voltage scaling algorithm that changes effective deadlines of frame decoding jobs. We pose our problem as a buffer-constrained optimization and show that significant improvements can be achieved over the state-of-the-art dynamic voltage scaling techniques without any performance degradation.

Significant power savings can be achieved on voltage/ frequency configurable platforms by dynamically adapting the frequency and voltage according to the workload (complexity). Video decoding is one of the most complex tasks performed on such systems due to its computationally demanding operations like inverse filtering, interpolation, motion compensation and entropy decoding. Dynamically adapting the frequency and voltage for video decoding is attractive due to the time-varying workload and because the utility of decoding a frame is dependent only on decoding the frame before the display deadline. Our contribution in this paper is twofold. First, we adopt a complexity model thatexplicitlyconsiders the video compression and platform specifics to accurately predict execution times. Second, based on this complexity model, we propose a dynamic voltage scaling algorithm that changes effective deadlines of frame decoding jobs. We pose our problem as a buffer-constrained optimization and show that significant improvements can be achieved over the state-of-the-art dynamic voltage scaling techniques without any performance degradation.

Efficient peer-to-peer (P2P) video streaming is a challenging task due to time-varying nature of both the number of available peers and network/channel conditions. To this effect, we propose a receiver driven P2P streaming system which utilizes a flexible scalable multiple description coding method, where the number of base and enhancement descriptions, and the rate and redundancy level of each description can be adapted on the fly. The optimization of the parameters of the proposed MDC scheme according to network conditions is discussed within the context of the proposed adaptive P2P streaming framework, where the number and quality of available streaming peers/paths are a priori unknown and vary in time. Experimental results, by means of NS-2 network simulation of a P2P video streaming system, show that adaptation of the number, type, and rate of descriptions and the redundancy level of each description according to network conditions yields significantly superior performance when compared to MDC schemes using a fixed number of descriptions/layers with fixed rate and redundancy level.

Multiple description video coding mitigates the effects of packet losses introduced by congestion and/or bit errors. In this paper, we propose a novel multiple description video coding technique, based on fully scalable wavelet video coding, which allows post encoding adaptation of the number of descriptions, the redundancy level of each description, and bitrate of each description by manipulation of the encoded bitstream. We demonstrate that the proposed method provides excellent coding efficiency, outperforming most other multiple description methods proposed so far. We also provide experimental results to show that varying the number of descriptions according to network conditions is superior to using a fixed number of descriptions, by means of NS-2 network simulation of a peer-to-peer video streaming system.

We propose an adaptive motion-compensated temporal filtering (MCTF) structure to provide efficient temporal scalability within the H.264/AVC video compression standard. MCTF has traditionally been considered within fully scalable wavelet video coders. However, motion-compensated simple 5/3 lifted temporal wavelet filtering suffers at scene changes, as well as occlusion regions. We note that the bi-directional motion compensation mode in the H.264 standard is best equipped with the state of the art adaptive features such as adaptive block size, mode switching between forward, backward and bidirectional prediction and in-loop deblocking filter. Hence, we propose a GOP structure to implement block-based adaptive MCTF within the H.264 syntax using stored B-pictures, similar to the motion-compensated 5/3 wavelet filtering. We provide experimental results to compare the results of our proposed codec with those of other scalable wavelet video coders which use MCTF. It is also possible to employ the proposed adaptive MCTF structure within fully scalable wavelet video codecs.