We study the problem of exact sampling under an exponential communication cost, specifically Campbell’s average codeword lengthL(t)of ordert[1], and Rényi’s entropy. We provide a lower bound on the Campbell cost of exact sampling that grows approximately asD1/α(P||Q), the Rényi divergence of order 1/α, with α = 1/1 +t. Using the Poisson functional representation of Li and El Gamal [2], we prove an upper bound onL(t)whose leading Rényi divergence term has order within ϵ of that of the lower bound. Our results reduce to the bounds of Harsha et al. [3] as α→1. We also provide numerical examples comparing the bounds in the cases of normal and Laplacian distributions, demonstrating that the upper and lower bounds are typically within 5-10 bits of each other. Our results characterize exactly the optimal asymptotic Campbell costL(t)per sample as the number of independent and identically distributed (i.i.d.) samples grows to infinity. We show that under the exponential cost, any causal sampler performs strictly worse asymptotically than noncausal samplers. This contrasts with the case of expected message length, where both causal and noncausal samplers have the same optimal asymptotic cost.

In the classical lossy source coding problem, one encodes long blocks of source symbols that enables the distortion to approach the ultimate Shannon limit. This approach is undesirable in many delay-sensitive applications. We consider the zero-delay case, where the goal is to encode and decode a finite-alphabet Markov source without any delay. It has been shown that this problem lends itself to stochastic control techniques, which lead to existence, structural, and approximation results. However, these techniques have only resulted in computationally prohibitive algorithms for code design. We present a practical reinforcement learning design algorithm and rigorously prove its asymptotic optimality. In particular, we show that a quantized Q-learning algorithm can be used to obtain a near-optimal coding policy for this problem. The proof builds on recent results on quantized Q-Iearning for weak Feller controlled Markov chains whose application necessitates the development of supporting technical results on regularity and stability properties, and relating the solutions for discounted and average cost criteria problems. These theoretical results are supported by simulations.

Given finite dimensional random vectors$\boldsymbol{Y,X}$and$\boldsymbol{Z}$that form a Markov chain in that order$(\boldsymbol{Y}\rightarrow \boldsymbol{X}\rightarrow \boldsymbol{Z})$, we derive Rényi divergence based upper bounds for excess minimum risk, where$\boldsymbol{Y}$is a (target) vector that is to be estimated from an observed (feature) vector$\boldsymbol{X}$or its (stochastically) degraded version$\boldsymbol{Z}$. We define the excess minimum risk as the difference between the minimum expected loss in estimating$\boldsymbol{Y}$from$\boldsymbol{X}$and the minimum expected loss in estimating$\boldsymbol{Y}$from$\boldsymbol{Z}$. We obtain a family of bounds which generalize the bounds developed by Györfi et al. (2023) expressed in terms of Shannon's mutual information. Our bounds are similar to the bounds by Modak et al. (2021) obtained in the context of the generalization error of learning algorithms, but unlike the latter they do not involve fixed sub-Gaussian parameters and therefore hold for more general joint distributions of$\boldsymbol{Y,X}$, and$\boldsymbol{Z}$. We also provide an example with Bernoulli random variables where Rényi's divergence based upper bound are tighter than mutual information bounds.

In the classical lossy source coding problem, one encodes long blocks of source symbols that enables the distortion to approach the ultimate Shannon limit. Such a block-coding approach introduces large delays, which is undesirable in many delay-sensitive applications. We consider the zero-delay case, where the goal is to encode and decode a finite-alphabet Markov source without any delay. It has been shown that this problem lends itself to stochastic control techniques, which lead to existence, structural, and general structural approximation results. However, these techniques so far have only resulted in computationally prohibitive algorithmic implementations for code design. To address this problem, we present a practically implementable reinforcement learning design algorithm and rigorously prove its asymptotic optimality. In particular, we show that a quantized Q-learning algorithm can be used to obtain a near-optimal coding policy for this problem. The proof builds on recent results on quantized Q-learning for weakly Feller controlled Markov chains whose application necessitates the development of supporting technical results on regularity and stability properties, and relating the optimal solutions for discounted and average cost infinite horizon criteria problems. These theoretical results are supported by simulations.

This paper addresses the capacity problem for a class of finite-state two-way channels (FS-TWCs). Specifically, inner and outer bounds for the channel capacity of FS-TWCs are derived, and they are combined to characterize the capacity region in a limiting expression for some special FS-TWCs. Although such an expression is often incomputable, it is illustrated via an example that a reduction to single-letter form is possible as long as the system variables exhibit stationarity and the associated "average channel" satisfies certain symmetry properties.

It is known that under fixed-rate information constraints, adaptive quantizers can be used to stabilize an open-loop-unstable linear system on$\mathbb {R}^{n}$driven by unbounded noise. These adaptive schemes can be designed so that they have near-optimal rate, and the resulting system will be stable in the sense of having an invariant probability measure, or ergodicity, as well as boundedness of the state second moment. Although structural results and information theoretic bounds of encoders have been studied, the performance of such adaptive fixed-rate quantizers beyond stabilization has not been addressed. In this paper, we propose a two-part adaptive (fixed-rate) coding scheme that achieves state second moment convergence to the classical optimum (i.e., for the fully observed setting) under mild moment conditions on the noise process. The first part, as in prior work, leads to ergodicity (via positive Harris recurrence) and the second part ensures that the state second moment converges to the classical optimum at high rates. These results are established using an intricate analysis which uses random-time state-dependent Lyapunov stochastic drift criteria as a core tool.

It is known that fixed rate adaptive quantizers can be used to stabilize an open-loop-unstable linear system driven by unbounded noise. These quantizers can be designed so that they have near-optimal rate, and the resulting system will be stable in the sense of having an invariant probability measure, or ergodicity, as well as the boundedness of the state second moment. However, results on the minimization of the state second moment for such quantizers, an important goal in practice, do not seem to be available. In this paper, we construct a two-part adaptive coding scheme that is asymptotically optimal in terms of the second moments as the data rate grows large. The first part, as in prior work, leads to ergodicity (via positive Harris recurrence) and the second part attains order optimality of the invariant second moment, resulting in near optimal performance at high rates.

Optimal zero-delay coding (quantization) of$\mathbb {R}^{d}$-valued linearly generated Markov sources is studied under quadratic distortion. The structure and existence of deterministic and stationary coding policies that are optimal for the infinite horizon average cost (distortion) problem are established. Prior results studying the optimality of zero-delay codes for Markov sources for infinite horizons either considered finite alphabet sources or, for the$\mathbb {R}^{d}$-valued case, only showed the existence of deterministic and non-stationary Markov coding policies or those which are randomized. In addition to existence results, for finite blocklength (horizon)$T$the performance of an optimal coding policy is shown to approach the infinite time horizon optimum at a rate$O\left({\frac {1}{T}}\right)$. This gives an explicit rate of convergence that quantifies the near-optimality of finite window (finite-memory) codes among all optimal zero-delay codes.

We investigate the equilibrium behavior for the decentralized cheap talk problem for real random variables and quadratic cost criteria in which an encoder and a decoder have misaligned objective functions. In prior work, it has been shown that the number of bins in any equilibrium has to be countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we first refine this result in the context of log-concave sources. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. In contrast, for sources with semi-unbounded support, there may be a finite upper bound on the number of bins in equilibrium depending on certain conditions stated explicitly. Moreover, we prove that for log-concave sources, the expected costs of the encoder and the decoder in equilibrium decrease as the number of bins increases. Furthermore, for strictly log-concave sources with two-sided unbounded support, we prove convergence to the unique equilibrium under best response dynamics which starts with a given number of bins, making a connection with the classical theory of optimal quantization and convergence results of Lloyd’s method. In addition, we consider more general sources which satisfy certain assumptions on the tail(s) of the distribution and we show that there exist equilibria with infinitely many bins for sources with two-sided unbounded support. Further explicit characterizations are provided for sources with exponential, Gaussian, and compactly-supported probability distributions.

This paper considers an information bottleneck problem with the objective of obtaining a most informative representation of a hidden feature subject to a Rényi entropy complexity constraint. The optimal bottleneck trade-off between relevance (measured via Shannon's mutual information) and Rényi entropy cost is defined and an iterative algorithm for finding approximate solutions is provided. We also derive an operational characterization for the optimal trade-off by demonstrating that the optimal Rényi entropy-relevance trade-off is achievable by a simple time-sharing scalar coding scheme and that no coding scheme can provide better performance. Two examples where the optimal Shannon entropy-relevance tradeoff can be exactly determined are further given.

We propose an adaptive lossy joint source-channel coding (JSCC) scheme for sending correlated sources over two-terminal discrete-memoryless two-way channels (DM-TWCs). The main idea is to couple the independent operations of the terminals via an adaptive coding mechanism, which can mitigate cross-interference resulting from simultaneous channel transmissions and concurrently exploit the sources' correlation to reduce the end-to-end reconstruction distortions. Our adaptive JSCC scheme not only subsumes existing lossy coding methods for two-way simultaneous communication but also improves their performance. Furthermore, we derive outer bounds for our two-way lossy transmission problem and establish complete JSCC theorems in some special settings. In these special cases, a non-adaptive separate source-channel coding (SSCC) scheme achieves the optimal performance, thus simplifying the design of the source-channel communication system.

An adaptive joint source-channel coding (JSCC) scheme is presented for transmitting correlated sources over discrete-memoryless two-way channels subject to distortion constraints. The proposed JSCC scheme makes use of the previously transmitted and received channel signals as well as the sources' correlation to facilitate coordination between terminals. It is shown that the adaptive scheme strictly subsumes prior lossy coding methods for two-way simultaneous transmission and yields a new adaptive separate source-channel coding result. Two examples are given to show the scheme's advantages.

We investigate the equilibrium behavior for the decentralized quadratic cheap talk problem in which an encoder and a decoder, viewed as two decision makers, have misaligned objective functions. In prior work, we have shown that the number of bins under any equilibrium has to be at most countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we refine this result in the context of exponential and Gaussian sources. For exponential sources, a relation between the upper bound on the number of bins and the misalignment in the objective functions is derived, the equilibrium costs are compared, and it is shown that there also exist equilibria with infinitely many bins under certain parametric assumptions. For Gaussian sources, it is shown that there exist equilibria with infinitely many bins.

A joint source-channel coding (JSCC) scheme based on hybrid digital/analog coding is proposed for the transmission of correlated sources over discrete-memoryless two-way channels (DM-TWCs). The scheme utilizes the correlation between the sources in generating channel inputs, thus enabling the users to coordinate their transmission to combat channel noise. The hybrid scheme also subsumes prior coding methods such as rate-one separate source-channel coding and uncoded schemes for two-way lossy transmission, as well as the correlation-preserving coding scheme for (almost) lossless transmission. Moreover, we derive a distortion outer bound for the source-channel system using a genie-aided argument. A complete JSSC theorem for a class of correlated sources and DM-TWCs whose capacity region cannot be enlarged via interactive adaptive coding is also established. Examples that illustrate the theorem are given.

We investigate the problem of estimating a random variable Y under a privacy constraint dictated by another correlated random variable X. When X and Y are discrete, we express the underlying privacy-utility tradeoff in terms of the privacy-constrained guessing probability (PXY, ε), and the maximum probability Pc(Y|Z) of correctly guessing Y given an auxiliary random variable Z, where the maximization is taken over all PZ|Yensuring that Pc(X|Z) ≤ ε for a given privacy threshold ε ≥ 0. We prove that ħ (PXY, ·) is concave and piecewise linear, which allows us to derive its expression in closed form for any ε when X and Y are binary. In the non-binary case, we derive (PXY, ε) in the high-utility regime (i.e., for sufficiently large, but nontrivial, values of ε) under the assumption that Y and Z have the same alphabets. We also analyze the privacy-constrained guessing probability for two scenarios in which X, Y, and Z are binary vectors. When X and Y are continuous random variables, we formulate the corresponding privacy-utility tradeoff in terms of sENSR(PXY, ε), the smallest normalized minimum mean squared-error (mmse) incurred in estimating Y from a Gaussian perturbation Z. Here, the minimization is taken over a family of Gaussian perturbations Z for which the mmse of f (X) given Z is within a factor 1-ε from the variance of f (X) for any non-constant real-valued function f . We derive tight upper and lower bounds for sENSR when Y is Gaussian. For general absolutely continuous random variables, we obtain a tight lower bound for sENSR(PXY, ε) in the high privacy regime, i.e., for small ε.

A class of burst noise-erasure channels which incorporate both errors and erasures during transmission is studied. The channel, whose output is explicitly expressed in terms of its input and a stationary ergodic noise-erasure process, is shown to have a so-called “quasi-symmetry” property under certain invertibility conditions. As a result, it is proved that a uniformly distributed input process maximizes the channel's block mutual information, resulting in a closed-form formula for its non-feedback capacity in terms of the noise-erasure entropy rate and the entropy rate of an auxiliary erasure process. The feedback channel capacity is also characterized, showing that the feedback does not increase capacity and generalizing prior related results. The capacity-cost function of the channel with and without feedback is next investigated. A sequence of finite-letter upper bounds for the capacity-cost function without feedback is derived. Finite-letter lower bonds for the capacity-cost function with feedback are obtained using a specific encoding rule. Based on these bounds, it is demonstrated both numerically and analytically that feedback can increase the capacity-cost function for a class of channels with Markov noise-erasure processes.

In this paper, we make use of channel symmetry properties to determine the capacity region of three types of two-way networks: 1) two-user memoryless two-way channels (TWCs); 2) two-user TWCs with memory; and 3) three-user multiaccess/degraded broadcast (MA/DB) TWCs. For each network, symmetry conditions under which a Shannon-type random coding inner bound (under independent non-adaptive inputs) is tight are given. For two-user memoryless TWCs, prior results are substantially generalized by viewing a TWC as two interacting state-dependent one-way channels. The capacity of symmetric TWCs with memory, whose outputs are functions of the inputs and independent stationary and ergodic noise processes, is also obtained. Moreover, various channel symmetry properties under which the Shannon-type inner bound is tight are identified for three-user MA/DB TWCs. The results not only enlarge the class of symmetric TWCs whose capacity region can be exactly determined but also imply that interactive adaptive coding, not improving capacity, is unnecessary for such channels.

New sufficient conditions for determining in closed form the capacity region of point-to-point memoryless two-way channels (TWCs) are derived. The proposed conditions not only relax Shannon's condition which can identify only TWCs with a certain symmetry property but also generalize other existing results. Examples are given to demonstrate the advantages of the proposed conditions.

This work focuses on the construction of optimized binary signaling schemes for two-sender uncoded transmission of correlated non-uniform sources over non-orthogonal Gaussian multiple access channels. Based on an error-rate analysis under joint maximum-a-posteriori decoding, optimized binary-pulsed-amplitude modulation constellations for two senders are derived to minimize the system's error rate. The joint probability distribution of the two-senders' source is observed to induce a special layout of optimized constellations which can effectively control the interference due to non-orthogonal transmission. Numerical results further confirm that significant gains are achievable by the proposed design.

We investigate the problem of guessing a discrete random variable Y under a privacy constraint dictated by another correlated discrete random variable X, where both guessing efficiency and privacy are assessed in terms of the probability of correct guessing. We define h(PXY,ε) as the maximum probability of correctly guessing Y given an auxiliary random variable Z, where the maximization is taken over all PZ|Yensuring that the probability of correctly guessing X given Z does not exceed ε. We show that the map ε → h(PXY,ε) is strictly increasing, concave, and piecewise linear, which allows us to derive a closed form expression for h(PxY,ε) when X and Y are connected via a binary-input binary-output channel. For {(Xi, Yi)}ni=1being pairs of independent and identically distributed binary random vectors, we similarly define h_n(PX n Y n, ε) under the assumption that Znis also a binary vector. Then we obtain a closed form expression for h_n(PX n Y n, ε) for sufficiently large, but nontrivial values of ε.

A class of burst noise-erasure channels which incorporate both errors and erasures during transmission is studied. The channel, whose output is explicitly expressed in terms of its input and a stationary ergodic noise-erasure process, is shown to satisfy a so-called “quasi-symmetry” condition under certain invertibility conditions. As a result, it is proved that a uniformly distributed input process maximizes the channel's block mutual information, resulting in a closed-form formula for its nonfeedback capacity in terms of the noise-erasure entropy rate and the entropy rate of an auxiliary erasure process. The feedback channel capacity is also characterized, showing that feedback does not increase capacity and generalizing prior related results.

Achievability and converse results for the lossy transmission of correlated sources over Shannon's two-way channels (TWCs) are presented. A joint source-channel coding theorem for independent sources and TWCs for which adaptation cannot enlarge the capacity region is also established. We further investigate the optimality of scalar coding for TWCs with discrete modulo additive noise as well as additive white Gaussian noise. Comparing the distortion of scalar coding with the derived bounds, we observe that scalar coding achieves the minimum distortion over both families of TWCs for independent and uniformly distributed sources and independent Gaussian sources.

The optimal zero delay coding of a finite-state Markov source is considered. The existence and structure of optimal codes are studied using a stochastic control formulation. Prior results in the literature established the optimality of deterministic Markov (Walrand–Varaiya-type) coding policies for the finite time horizon problem, and the optimality of both deterministic nonstationary and randomized stationary policies for the infinite time horizon problem. Our main result here shows that for any irreducible and aperiodic Markov source with a finite alphabet,deterministic and stationaryMarkov coding policies are optimal for the infinite horizon problem. In addition, the finite block length (time horizon) performance of an optimal (stationary and Markov) coding policy is shown to approach the infinite time horizon optimum at a rate$O(1/T)$. The results are extended to systems, where zero delay communication takes place across a noisy channel with noiseless feedback.

We investigate the problem of the predictability of random variable Y under a privacy constraint dictated by random variable X, correlated with Y , where both predictability and privacy are assessed in terms of the minimum mean-squared error (MMSE). Given that X and Y are connected via a binary-input symmetric-output (BISO) channel, we derive the optimal random mapping PZ|Ysuch that the MMSE of Y given Z is minimized while the MMSE of X given Z is greater than (1-ε)var(X) for a given ε ≥ 0. We also consider the case where (X, Y ) are continuous and PZ|Yis restricted to be an additive-noise channel.

In two-way channels, each user transmits and receives at the same time. This allows each encoder to interactively adapt the current input to its own message and all previously received signals. Such coding approach can introduce correlation between inputs of different users, since all the users' outputs are correlated by the nature of the channel. However, for some channels, such adaptation in the coding scheme and its induced correlation among users are useless in the sense that they do not help enlarge the capacity region with respect to the standard coding method (where each user encodes only based on its own message). In this paper, it is shown that adaptation is not helpful for enlarging the capacity region of two classes of two-way discrete channels: the modulo additive-noise channel with memory and the multiple access/degraded broadcast channel.

Optimal zero-delay coding (quantization) of a finite-state Markov source is considered. Building on our earlier work and previous literature, using a stochastic control problem formulation, the existence and structure of optimal quantization policies are studied. Our main result establishes, for infinite horizon problems, the optimality of deterministic and stationary (Walrand-Varaiya type) Markov coding policies. In addition, the ε-optimality of finite-memory quantizers is established and the dependence between the memory length and ε is quantified. Numerical results are also presented.

This paper studies fixed-rate randomized vector quantization under the constraint that the quantizer's output has a given fixed probability distribution. A general representation of randomized quantizers that includes the common models in the literature is introduced via appropriate mixtures of joint probability measures on the product of the source and reproduction alphabets. Using this representation and results from optimal transport theory, the existence of an optimal (minimum distortion) randomized quantizer having a given output distribution is shown under various conditions. For sources with densities and the mean square distortion measure, it is shown that this optimum can be attained by randomizing quantizers having convex codecells. For stationary and memoryless source and output distributions, a rate-distortion theorem is proved, providing a single-letter expression for the optimum distortion in the limit of large blocklengths.

This paper studies a Shannon-theoretic version of the generalized distribution preserving quantization problem where a stationary and memoryless source is encoded subject to a distortion constraint and the additional requirement that the reproduction also be stationary and memoryless with a given distribution. The encoder and decoder are stochastic and assumed to have access to independent common randomness. Recent work has characterized the minimum achievable coding rate at a given distortion level when unlimited common randomness is available. Here, we consider the general case where the available common randomness may be rate limited. Our main result completely characterizes the set of achievable coding and common randomness rate pairs at any distortion level, thereby providing the optimal tradeoff between these two rate quantities. We also consider two variations of this problem where we investigate the effect of relaxing the strict output distribution constraint and the role of private randomness used by the decoder on the rate region. Our results have strong connections with Cuff's recent work on distributed channel synthesis. In particular, our achievability proof combines a coupling argument with the approach developed by Cuff, where instead of explicitly constructing the encoder-decoder pair, a joint distribution is constructed from which a desired encoder-decoder pair is established. We show, however, that for our problem, the separated solution of first finding an optimal channel and then synthesizing this channel results in a suboptimal rate region.

We consider the joint source-channel coding (JSCC) problem where the real valued outputs of two correlated memoryless Gaussian sources are scalar quantized, bit assigned, and transmitted, without applying any error correcting code, over a multiple access channel (MAC) which consists of two orthogonal point-to- point time-correlated Rayleigh fading sub-channels with soft- decision demodulation. At the receiver side, a joint sequence maximum a posteriori (MAP) detector is used to exploit the correlation between the two sources as well as the redundancy left in the quantizer's indices, the channel's soft-decision outputs, and noise memory. The MAC's sub-channels are modeled via non-binary Markov noise discrete channels recently shown to effectively represent point-to-point fading channels. For the simple case of quantizing the sources with two levels, we establish a necessary and sufficient condition under which the joint sequence MAP decoder can be reduced to a simple instantaneous symbol-by-symbol decoder. Then, using numerical results obtained by system simulation, it is observed that when the sources are highly correlated and soft-decision quantization is used, JSCC can profit from a high correlation in the channel noise process and provide significant signal-to-distortion ratio improvements of up to 6.3 dB over a fully interleaved channel.

Optimal zero-delay coding (quantization) of a vector-valued Markov source driven by a noise process is considered. Using a stochastic control problem formulation, the existence and structure of optimal quantization policies are studied. For a finite-horizon problem with bounded per-stage distortion measure, the existence of an optimal zero-delay quantization policy is shown provided that the quantizers allowed are ones with convex codecells. The bounded distortion assumption is relaxed to cover cases that include the linear quadratic Gaussian problem. For the infinite horizon problem and a stationary Markov source, the optimality of deterministic Markov coding policies is shown. The existence of optimal stationary Markov quantization policies is also shown provided randomization that is shared by the encoder and the decoder is allowed.

We consider the problem of optimal randomized vector quantization under a constraint on the output's distribution. The problem is formalized by introducing a general representation of randomized quantization via probability measures over the space of joint distributions on the source and reproduction alphabets. Using this representation and results from optimal transport theory, we show the existence of an optimal (minimum distortion) randomized quantizer having a fixed output distribution under various conditions. For sources with densities and the mean square distortion measure, we show that this optimum can be attained by randomizing quantizers having convex code cells. We also consider a relaxed version of the problem where the output marginal must belong to some neighborhood (in the weak topology) of a fixed probability measure. We demonstrate that finitely randomized quantizers form an optimal class for the relaxed problem.

We study a joint source-channel decoding scheme that exploits the channel's statistical memory and soft-decision information in fading channels. The channel considered is a recently introduced binary input 2q-ary output channel with Markovian ergodic noise based on a finite queue (called NBNDC-QB). This model has been shown to effectively represent soft-decision demodulated correlated Rayleigh fading channels. The coding scheme consists of a scalar quantizer, a proper index assignment, and a sequence maximum a posteriori (MAP) decoder designed to harness the redundancy left in the quantizer's indices, the channel's soft-decision output, and correlation in the channel noise process. We first consider the simple case where the quantized indices form a binary symmetric Markov source and establish a necessary and sufficient condition under which the sequence MAP decoder is reduced to a simple instantaneous symbol-by-symbol decoder. We next assess the signal-to-distortion ratio (SDR) performance of our general system. Our numerical results confirm that this system can successfully take advantage of the channel memory and outperforms systems that use channel interleaving by as much as 2.6 dB in SDR. In addition, SDR gains of up to 2.8 dB are achieved using as few as 2 bits for soft-decision quantization over hard quantized output schemes. Finally, the NBNDC-QB channel model is validated in terms of SDR performance by fitting the NBNDC-QB model to a discrete correlated Rayleigh fading channel, designing a system for this matched NBNDC-QB model, and comparing this system's performance over both the NBNDC-QB and the Rayleigh fading channels.

In the framework of prediction with expert advice we consider prediction algorithms that compete against a class of switching strategies that can segment a given sequence into several blocks and follow the advice of a different “base” expert in each block. The performance is measured by the regret defined as the excess loss relative to the best switching strategy selected in hindsight. Our goal is to construct low-complexity prediction algorithms for the case where the set of base experts is large. In particular, starting with an arbitrary prediction algorithm A designed for the base expert class, we derive a family of efficient tracking algorithms that can be implemented with time and space complexity only O(ηγIn n) times larger than that of A, where n is the time horizon and γ ≥ 0 is a parameter of the algorithm. With A properly chosen, our algorithm achieves a regret bound of optimal order for γ >; 0, and only O(ln n) times larger than the optimal order for γ = 0 for all typical regret bound types we examined. For example, for predicting binary sequences with switching parameters, our method achieves the optimal O(ln n) regret rate with time complexity O(n1+γIn n) for any γ ϵ (0,1).

In the framework of prediction of individual sequences, sequential prediction methods are to be constructed that perform nearly as well as the best expert from a given class. We consider prediction strategies that compete with the class of switching strategies that can segment a given sequence into several blocks, and follow the advice of a different “base” expert in each block. As usual, the performance of the algorithm is measured by the regret defined as the excess loss relative to the best switching strategy selected in hindsight for the particular sequence to be predicted. In this paper, we construct prediction strategies of low computational cost for the case where the set of base experts is large. In particular, we provide a method that can transform any prediction algorithmAthat is designed for the base class into a tracking algorithm. The resulting tracking algorithm can take advantage of the prediction performance and potential computational efficiency ofAin the sense that it can be implemented with time and space complexity onlyO(nγlnn) times larger than that ofA, wherenis the time horizon and γ ≥ 0 is a parameter of the algorithm. WithAproperly chosen, our algorithm achieves a regret bound of optimal order for γ >; 0, and onlyO(lnn) times larger than the optimal order for γ = 0 for all typical regret bound types we examined. For example, for predicting binary sequences with switching parameters under the logarithmic loss, our method achieves the optimalO(lnn) regret rate with time complexityO(n1+γlnn) for any γ ∈ (0,1).

Properties of scalar quantization with th power distortion and constrained Rényi entropy of order are investigated. For an asymptotically (high-rate) optimal sequence of quantizers, the contribution to the Rényi entropy due to source values in a fixed interval is identified in terms of the “entropy density” of the quantizer sequence. This extends results related to the well-known point density concept in optimal fixed-rate quantization. A dual of the entropy density result quantifies the distortion contribution of a given interval to the overall distortion. The distortion loss resulting from a mismatch of source densities in the design of an asymptotically optimal sequence of quantizers is also determined. This extends Bucklew's fixed-rate and Gray et al.'s variable-rate mismatch results to general values of the entropy order parameter .

A vector extension of a necessary condition for asymptotically optimal stationary (sliding-block) source codes is presented. The condition implies the intuitive result that the reproduction process for an IID input must be approximately uncorrelated if the code is approximately optimal, a property previously demonstrated empirically for common examples. One-bit coding of a Gaussian IID process is used to illustrate the goodness of fit of the empirical distribution of the reproduction to the Shannon optimal distribution.

We consider optimal scalar quantization with rth power distortion and constrained Rényi entropy of order α. For sources with absolutely continuous distributions the high rate asymptotics of the quantizer distortion has long been known for α = 0 (fixed-rate quantization) and α = 1 (entropy-constrained quantization). For a large class of absolutely continuous source distributions we determine the sharp asymptotics of the optimal quantization distortion for Rényi entropy constraints of order α ∈ [-∈, 0) ∪ (0; 1). The proof of achievability is based on companding quantization and is thus constructive.

We consider the problem of sending a bivariate Gaussian source S=(S1,S2) across a power-limited two-user Gaussian broadcast channel. User i (i=1,2) observes the transmitted signal corrupted by Gaussian noise with power σi2and desires to estimate Si. We study hybrid digital-analog (HDA) joint source-channel coding schemes and analyze the region of (squared-error) distortion pairs that are simultaneously achievable. Two cases are considered: 1) broadcasting with bandwidth compression, and 2) broadcasting with bandwidth expansion. We modify and adapt HDA schemes of Wilson et al. and Prabhakaran et al. , originally proposed for broadcasting a single common Gaussian source, in order to provide achievable distortion regions for broadcasting correlated Gaussian sources. For comparison, we also extend the outer bound of Soundararajan et al. from the matched source-channel bandwidth case to the bandwidth mismatch case.

We consider optimal scalar quantization with rth power distortion and constrained Rényi entropy of order α. For sources with absolutely continuous distributions the high rate asymptotics of the quantizer distortion has long been known for α = 0 (fixed-rate quantization) and α = 1 (entropy-constrained quantization). These results have recently been extended to quantization with Rényi entropy constraint of order α ≥r+1. Here we consider the more challenging case α ∈ [-∞,0)∪(0,1) and for a large class of absolutely continuous source distributions we determine the sharp asymptotics of the optimal quantization distortion. The achievability proof is based on finding (asymptotically) optimal quantizers via the companding approach, and is thus constructive.

Necessary conditions for asymptotically optimal sliding-block or stationary codes for source coding and rate-constrained simulation of memoryless sources are presented and used to motivate a design technique for trellis-encoded source coding and rate-constrained simulation. The code structure has intuitive similarities to classic random coding arguments as well as to “fake process” methods and alphabet-constrained methods. Experimental evidence shows that the approach provides comparable or superior performance in comparison with previously published methods on common examples, sometimes by significant margins.

A formal result is stated and proved showing that the bit stream produced by the encoder of a nearly optimal sliding-block source coding of a stationary and ergodic source is close to an equiprobable i.i.d. binary process.

We consider the transmission of a bivariate Gaussian source S = (S1, S2) across a power-limited two-user Gaussian broadcast channel. User i (i = 1, 2) observes the transmitted signal corrupted by Gaussian noise with power sigmai2and wants to estimate Si. We study hybrid digital-analog (HDA) joint source-channel coding schemes and analyze these schemes to obtain achievable (squared-error) distortion regions. Two cases are considered: 1) source and channel bandwidths are equal, 2) broadcasting with bandwidth compression. We adapt HDA schemes of Wilson et al. and Prabhakaran et al. to provide various achievable distortion regions for both cases. Using numerical examples, we demonstrate that for bandwidth compression, a three-layered coding scheme consisting of analog, superposition, and Costa coding performs well compared to the other provided HDA schemes. In the case of matched bandwidth, a three-layered coding scheme with an analog layer and two layers, each consisting of a Wyner-Ziv coder followed by a Costa coder, performs best.

We study the maximum a posteriori (MAP) decoding of memoryless non-uniform sources over multiple-antenna channels. Our model is general enough to include space-time coding, BLAST architectures, and single-transmit multi-receive antenna systems which employ any type of channel coding. We derive a closed-form expression for the codeword pairwise error probability (PEP) of general multi-antenna codes using moment generating function and Laplace transform arguments. We then consider space-time orthogonal block (STOB) coding and prove that, similar to the maximum likelihood (ML) decoding case, detection of symbols is decoupled in MAP decoding. We also derive the symbol PEP in closed-form for STOB codes. We apply these results in several scenarios. First, we design a binary antipodal signaling scheme which minimizes the system bit error rate (BER) under STOB coding. At a BER of 10-6, this constellation has a channel signal-to-noise ratio (CSNR) gain of 4.7 dB over conventional BPSK signaling for a binary nonuniform source with p0Delta=P(0) = 0.9. We next design space-time linear dispersion (LD) codes which are optimized for the source distribution under the criterion of minimizing the union upper bound on the frame error rate (FER). Two codes are given here: one outperforms V-BLAST by 3.5 dB and Alamouti's code by 12.3 dB at an FER of 10-2for a binary source with p0= 0.9, and the other outperforms V-BLAST by 4.2 dB at an FER of 10-3for a uniform source. These codes also outperform the LD codes of constructed under a different criteria. Finally, the problem of bit-to-signal mapping is studied. It is shown that for a binary source with p0= 0.9, 64-QAM signaling, and SER = 10-3, a gain of 3.7 dB can be achieved using a better-than-Gray mapping. For a system with one transmit and two receive antennas that uses trellis coding with 16-QAM signaling, a 1.8 dB gain over quasi-Gray mapping and ML decoding is observed when MAP decoding is used for binary sources with p0= 0.9.

Three hybrid digital-analog (HDA) systems, denoted by HDA-I, HDA* and HDA-II, for the coding of a memoryless discrete-time Gaussian source over a discrete-time additive memoryless Gaussian channel under bandwidth compression are studied. The systems employ simple linear coding in their analog component and superimpose their analog and digital signals before channel transmission. Information-theoretic upper bounds on the asymptotically optimal mean squared error distortion of the systems are obtained under both matched and mismatched channel conditions. Allocation schemes for distributing the channel input power between the analog and the digital signals are also examined. It is shown that systems HDA* and HDA-II can asymptotically achieve the optimal Shannon-limit performance under matched channel conditions. Low-complexity and low-delay versions of systems HDA-I and HDA-II are next designed and implemented without the use of error correcting codes. The parameters of these HDA systems, which employ vector quantization in conjunction with binary phase-shift keying modulation in their digital part, are optimized via an iterative algorithm similar to the design algorithm for channel-optimized vector quantizers. Both systems have low complexity and low delay, and guarantee graceful performance improvements for high CSNRs. For memoryless Gaussian sources the designed HDA-II system is shown to be superior to the HDA-I designed system. When applied to a Gauss-Markov source under Karhunen-Loeve processing, the HDA-I system is shown to provide considerably better performance.

We establish random-coding lower bounds to the error exponent of discrete and Gaussian joint quantization and private watermarking systems. In the discrete system, both the covertext and the attack channel are memoryless and have finite alphabets. In the Gaussian system, the covertext is memoryless Gaussian and the attack channel has additive memoryless Gaussian noise. In both cases, our bounds on the error exponent are positive in the interior of the achievable quantization and watermarking rate region.

We propose a simple multiple description (MD) video coding technique motivated by human visual perception. This method employs two simple parameters to characterize the smoothness and edge features of DCT blocks and measure their perceptual tolerance against visual distortion. We duplicate the key components of compressed video and split the remaining according to the calculated perceptual tolerance parameter. Simulation results reveal that our simple MD video coding method achieves superior performance compared to other similar techniques which lack to consider the perceptual distortion in the design problem.

We consider the estimation of a Gaussian source by a Gaussian sensor network where L distributed sensors transmit noisy observations of the source through a fading Gaussian multiple access channel (MAC) to a fusion center (FC). Since sensor power is usually limited, our goal is to characterize the optimal tradeoff between the transmission cost, i.e., the power vector P = (P1, P2, ..., PL), and the average estimation distortion, D. We focus on asymmetric fading sensor networks in which the sensors have differing signal to noise ratios and transmission powers. We present necessary and sufficient conditions for the achievability of (L + 1)-tuples (P1, P2, ..., PL, D). For a symmetric Gaussian sensor network with deterministic and equal-magnitude fading, we derive the optimal power-distortion tradeoff. We also provide an achievable power-distortion region for the asymmetric sensor network with deterministic fading by analyzing the transmission of scaled versions of vector-quantized observations. We show that some of the power-distortion tuples achievable by this scheme are not achievable via an uncoded system.

We consider a public multi-user information embedding (watermarking) system in which two messages (watermarks) are independently embedded into two correlated covertexts and are transmitted through a multiple-access attack channel. The tradeoff between the achievable embedding rates and the average distortions for the two embedders is studied. For given distortion levels, inner and outer bounds for the embedding capacity region are obtained in single-letter form. Tighter bounds are also given for independent covertexts.

In this paper, the Lagrangian formulation of variable-rate vector quantization is extended to quantization with simultaneous constraints on entropy and codebook size, including variable- and fixed-rate quantization as special cases. The formulation leads to a Lloyd quantizer design algorithm and generalizations of Gersho's approximations characterizing optimal performance for asymptotically large rate. A variation of Gersho's approach is shown to yield rigorous results partially characterizing the asymptotically optimal performance.

An algorithm is presented for online prediction that allows to track the best expert efficiently even when the number of experts is exponentially large, provided that the set of experts has a certain additive structure. As an example, we work out the case where each expert is represented by a path in a directed graph and the loss of each expert is the sum of the weights over the edges in the path. These results are then used to construct universal limited-delay schemes for lossy coding of individual sequences. In particular, we consider the problem of tracking the best scalar quantizer that is adaptively matched to the source sequence with piecewise different behavior. A randomized algorithm is presented which can perform, on any source sequence, asymptotically as well as the best scalar quantization algorithm that is matched to the sequence and is allowed to change the employed quantizer for a given number of times. The complexity of the algorithm is quadratic in the sequence length, but at the price of some deterioration in performance, the complexity can be made linear. Analogous results are obtained for sequential multiresolution and multiple description scalar quantization of individual sequences.

Consider a multi-user private information-hiding scenario in which two information hiders separately embed correlated sources (S1, S2) into a common host source U (covertext). The i-th information hider embeds the secret source Siinto the covertext U subject to a distortion constraint Di(i = 1, 2). The outputs (stegotexts) are corrupted by a multiple access channel attack WY|X1X2. A sufficient condition (in single-letter form) under which (S1, S2) can be successfully embedded into U under WY|X1X2is established.

We present an efficient algorithmic lower bound for the block error rate of linear binary block codes under soft maximum-likelihood decoding over binary phase-shift keying modulated additive white Gaussian noise channels. We cast the problem of finding a lower bound on the probability of a union as an optimization problem that seeks to find the subset that maximizes a recent lower bound - due to Kuai, Alajaji, and Takahara - that we will refer to as the KAT bound. The improved bound, which is denoted by LB-s, is asymptotically tight [as the signal-to-noise ratio (SNR) grows to infinity] and depends only on the code's weight enumeration function for its calculation. The use of a subset of the codebook to evaluate the LB-s lower bound not only significantly reduces computational complexity, but also tightens the bound specially at low SNRs. Numerical results for binary block codes indicate that at high SNRs, the LB-s bound is tighter than other recent lower bounds in the literature, which comprise the lower bound due to Seguin, the KAT bound (evaluated on the entire codebook), and the dot-product and norm bounds due to Cohen and Merhav.

The on-line shortest path problem is considered in the bandit setting. Given a weighted directed acyclic graph whose edge weights can change in an arbitrary way, a decision maker has to pick in each round a path between two distinguished vertices, such that the weight of this path, given as the sum of the weights of its composing edges, be as small as possible. The decision maker has only limited information on how the weights of the edges are generated. In particular, the edge weights in the current round are unknown to the decision maker when it chooses a path, and after choosing a path, it learns only the weights of those edges that belong to the chosen path. An algorithm is given whose average cumulative loss in n rounds exceeds that of the best path, matched off-line to the entire sequence of the edge weights, by a quantity that is proportional to 1/√n and depends only polynomially on the number of edges of the graph. The algorithm can be implemented with linear complexity in the number of rounds n and in the number of edges. This result improves earlier algorithms which have performance bounds that either depend exponentially on the number of edges or converge to zero at a slower rate than O(1/√n).

In a causal source coding system, the reconstruction of the present source sample is restricted to be a function of the present and past source samples, while the code stream itself may be noncausal and have variable rate. Neuhoff and Gilbert showed that for memoryless sources, optimum performance among all causal source codes is achieved by time-sharing at most two memoryless codes (quantizers) followed by entropy coding. In this work, we extend Neuhoff and Gilbert's result in the limit of small distortion (high resolution) to two new settings. First, we show that at high resolution, an optimal causal code for a stationary source with finite differential entropy rate consists of a uniform quantizer followed by a (sequence) entropy coder. This implies that the price of causality at high resolution is approximately 0.254 bit, i.e., the space-filling loss of the uniform quantizer. Then, we consider individual sequences and introduce a deterministic analogue of differential entropy, which we call "Lempel-Ziv differential entropy." We show that for any bounded individual sequence with finite Lempel-Ziv differential entropy, optimum high-resolution performance among all finite-memory variable-rate causal codes is achieved by dithered scalar uniform quantization followed by Lempel-Ziv coding. As a by-product, we also prove an individual-sequence version of the Shannon lower bound.

Industry-standard lossless compression algorithms (such as LZW) are usually implemented so that they work on bytes as symbols. Experiments indicate that data for which bytes are not the natural choice of symbols compress poorly using these implementations, while algorithms working on a bit level perform reasonably on byte-based data in addition to having computational advantages resulting from operating on a small alphabet. In this correspondence, we offer an information-theoretic explanation to these experimental results by assessing the redundancy (which is approximated by the divergence rate of two source distributions) of a bit-based model when applied to a byte-based source. More specifically, we study the problem of approximating a block Markov source (our model for byte-based data) with higher order Markov sources (which model bit-based Markov encoders), and show that the divergence rate between a block Markov source and the best matching higher order Markov model for that source converges to zero exponentially fast as the memory of the model increases. This result is applied to obtain bounds on the redundancy of certain symbol-based universal codes when they are used for byte-aligned sources

A joint source-channel coding system for image communication over an additive white Gaussian noise channel is presented. It employs vector quantization based hybrid digital-analog modulation techniques with bandwidth compression and expansion for transmitting and reconstructing the wavelet coefficients of an image. The main advantage of the proposed system is that it achieves good performance at the design channel signal-to-noise ratio (CSNR), while still maintaining a "graceful improvement" characteristic at higher CSNR. Comparisons are made with two purely digital systems and two purely analog systems. Simulation shows that the proposed system is superior to the other investigated systems for a wide range of CSNR.

In this paper we consider zero delay lossy coding schemes for individual sequences, and address the problem of tracking the best scalar quantizer which is adaptively matched to the sequence. The problem is an individual-sequence version of the problem of scalar quantization of piecewise stationary sources. A randomized algorithm is presented which can perform, on any source sequence, asymptotically as well as the best scalar quantization algorithm matched to the sequence which is allowed to change the employed quantizer from time to time. The complexity of the algorithm is quadratic in the sequence length. At the price of a slight deterioration of performance, the complexity can be made linear in the sequence length

The performance of space-time orthogonal block (STOB) codes over slow Rayleigh fading channels and maximum-likelihood (ML) decoding is investigated. Two Bonferroni-type bounds (one upper bound and one lower bound) for the symbol error rate (SER) and bit error rate (BER) of the system are obtained. The bounds are expressed in terms of the pairwise error probabilities (PEPs) and the two-dimensional pairwise error probabilities (2-D PEPs) of the transmitted symbols. Furthermore, the bounds can be efficiently evaluated and they hold for arbitrary (nonstandard) signaling schemes and mappings. Numerical results demonstrate that the bounds are very accurate in estimating the performance of STOB codes. In particular, the upper and lower bounds often coincide even at low channel signal-to-noise ratios, large constellation sizes, and large diversity orders.

Channel-optimized vector quantization (COVQ) has proven to be an effective joint source-channel coding technique that makes the underlying quantizer robust to channel noise. Unfortunately, COVQ retains the high encoding complexity of the standard vector quantizer (VQ) for medium-to-high quantization dimensions and moderate-to-good channel conditions. A technique called sample adaptive product quantization (SAPQ) was recently introduced by Kim and Shroff to reduce the complexity of the VQ while achieving comparable distortions. In this letter, we generalize the design of SAPQ for the case of memoryless noisy channels by optimizing the quantizer with respect to both source and channel statistics. Numerical results demonstrate that the channel-optimized SAPQ (COSAPQ) achieves comparable performance to the COVQ (within 0.2 dB), while maintaining considerably lower encoding complexity (up to half of that of COVQ) and storage requirements. Robustness of the COSAPQ system against channel mismatch is also examined.

Recent results and conjectures are presented regarding the behavior of asymptotically optimal vector quantizers. The principal new results are four lemmas and a corollary relating the distortion and entropy of quantizers and asymptotically optimal quantizers. Several related conjectures (some of which are based on simulations) are made regarding the behavior of asymptotically optimal quantizers.

Zero-delay sequential lossy source coding schemes are considered for both individual sequences and random sources. Performance is measured by the distortion redundancy, defined as the difference between the normalized cumulative distortion of the scheme and that of the best scalar quantizer matched to the entire sequence to be encoded. Weiss-man and Merhav [2001] constructed a randomized scheme which, for any bounded individual sequence of length n, achieves a distortion redundancy O(n/sup -1/3/ logn). However, this scheme has prohibitive complexity. Here we present an algorithm with encoding complexity O(n/sup 4/3/ logn) and distortion redundancy O(n/sup -1/3/ logn). The complexity can be made linear in the sequence length n at the price of increasing the distortion redundancy to O(n/sup -1/4/logn/sup 1/2/). We also show that for the class of bounded memoryless sources, the minimax expected distortion redundancy in zero-delay lossy coding is upper and lower bounded by (constant multiples of) n/sup -1/2/.

In causal source coding, the reconstruction is restricted to be a function of the present and past source samples, while the variable-length code stream may be noncausal. Neuhoff and Gilbert [1982] showed that for memoryless sources, optimum performance among all causal lossy source codes is achieved by time-sharing at most two memoryless codes (scalar quantizers) followed by entropy coding. We extend this result to causal coding of individual sequences in the limit of small distortion. The optimum performance of finite-memory variable-rate causal codes in this setting is characterized by a deterministic analogue of differential entropy, which we call "Lempel-Ziv differential entropy." As a by-product, we also provide an individual-sequence version of the Shannon lower bound to the rate-distortion function.

It is shown that if an asymptotically optimal sequence of variable rate codes is designed for a k-dimensional probability density function (pdf) g and then applied to another pdf f for which f/g is bounded, then the resulting mismatch or loss of performance from the optimal possible is given by the relative entropy or Kullback-Leibler divergence I(f/spl par/g). It is also shown that under the same assumptions an asymptotically optimal code sequence for g can be converted to an asymptotically optimal code sequence for a mismatched source f by modifying only the lossless component of the code. The development does not require Gersho's conjecture.

Summary form only given. An experiment was conducted to evaluate a block-sorting compression scheme that operates at the bit level. The experiment demonstrated that even such a simple technique, which ignores byte boundaries and uses a very simple modeling scheme for the output of the block-sorting transform, outperforms some of the best industry standard compressors for sources that are not byte-aligned, while providing reasonable compression ratios for byte-aligned sources. Although the scheme can be substantially improved using more sophisticated modeling and coding techniques, preliminary experimental results point out the potential advantages of this approach.

We derive a closed-form expression for the exact pairwise error probability (PEP) of a non-uniform memoryless binary source transmitted over a Rayleigh fading channel using space-time orthogonal block codes and maximum a posteriori (MAP) detection. The expression is easy to evaluate and holds for any signaling scheme. We then use this result to minimize the bit error rate of the binary antipodal signaling scheme. Numerical results for the case of binary antipodal signaling (BPSK and optimal) verify the accuracy of our formula and quantify substantial gains of MAP decoding over maximum likelihood (ML) decoding for sources with strong non-uniformity.

Bucklew's (1984) high-rate vector quantizer mismatch result is extended from fixed-rate coding to variable-rate coding using a Lagrangian formulation. It is shown that if an asymptotically (high-rate) optimal sequence of variable rate codes is designed for a k-dimensional probability density function (PDF) g and then applied to another PDF f for which f/g is bounded, then the resulting mismatch or loss of performance from the optimal possible is given by the relative entropy or Kullback-Leibler (1968) divergence I(f/spl par/g). It is also shown that under the same assumptions, an asymptotically optimal code sequence for g can be converted to an asymptotically optimal code sequence for a mismatched source f by modifying only the lossless component of the code. Applications to quantizer design using uniform and Gaussian densities are described, including a high-rate analog to the Shannon rate-distortion result of Sakrison (1975) and Lapidoth (1997) showing that the Gaussian is the "worst case" for lossy compression of a source with known covariance. By coupling the mismatch result with composite quantizers, the worst case properties of uniform and Gaussian densities are extended to conditionally uniform and Gaussian densities, which provides a Lloyd clustering algorithm for fitting mixtures to general densities.

Properties of optimal entropy-constrained vector quantizers (ECVQs) are studied for the squared-error distortion measure. It is known that restricting an ECVQ to have convex codecells may preclude its optimality for some sources with discrete distribution. We show that for sources with continuous distribution, any finite-level ECVQ can be replaced by another finite-level ECVQ with convex codecells that has equal or better performance. We generalize this result to infinite-level quantizers, and also consider the problem of existence of optimal ECVQs for continuous source distributions. In particular, we show that given any entropy constraint, there exists an ECVQ with (possibly infinitely many) convex codecells that has minimum distortion among all ECVQs satisfying the constraint. These results extend analogous statements in entropy-constrained scalar quantization. They also generalize results in entropy-constrained vector quantization that were obtained via the Lagrangian formulation and, therefore, are valid only for certain values of the entropy constraint.

An entropy-constrained quantizer Q is optimal if it minimizes the expected distortion D(Q) subject to a constraint on the output entropy H(Q). We use the Lagrangian formulation to show the existence and study the structure of optimal entropy-constrained quantizers that achieve a point on the lower convex hull of the operational distortion-rate function D/sub h/(R) = inf/sub Q/{D(Q) : H(Q) /spl les/ R}. In general, an optimal entropy-constrained quantizer may have a countably infinite number of codewords. Our main results show that if the tail of the source distribution is sufficiently light (resp., heavy) with respect to the distortion measure, the Lagrangian-optimal entropy-constrained quantizer has a finite (resp., infinite) number of codewords. In particular, for the squared error distortion measure, if the tail of the source distribution is lighter than the tail of a Gaussian distribution, then the Lagrangian-optimal quantizer has only a finite number of codewords, while if the tail is heavier than that of the Gaussian, the Lagrangian-optimal quantizer has an infinite number of codewords.

A progressive method for transmission of images over a bursty noise channel is presented. It is based on discrete wavelet transform (DWT) coding and channel-optimized scalar quantization. The main advantage of the proposed system is that it exploits the channel memory and hence has superior performance over a similar scheme designed for the equivalent memoryless channel through the use of channel interleaving. In fact, the performance of the proposed system improves as the noise becomes more correlated, at a fixed bit error rate. Comparisons are made with other alternatives which employ independent source and channel coding over the fully interleaved channel at various bit rates and bit error rates. It is shown that the proposed method outperforms these substantially more complex systems for the whole range of considered bit rates and for a wide range of channel conditions.

Zador's (1963, 1966) classic result for the asymptotic high-rate behavior of entropy-constrained vector quantization is recast in a Lagrangian form which better matches the Lloyd algorithm used to optimize such quantizers. The equivalence of the two formulations is shown and the result is proved for source distributions that are absolutely continuous with respect to the Lebesgue measure which satisfy an entropy condition, thereby generalizing the conditions stated by Zador under which the result holds.

The nearest neighbor condition implies that when searching for a mean-square optimal fixed-rate quantizer it is enough to consider the class of regular quantizers, i.e., quantizers having convex cells and codepoints which lie inside the associated cells. In contrast, quantizer regularity can preclude optimality in entropy-constrained quantization. This can be seen by exhibiting a simple discrete scalar source for which the mean-square optimal entropy-constrained scalar quantizer (ECSQ) has disconnected (and hence nonconvex) cells at certain rates. In this work, new results concerning the structure and existence of optimal ECSQs are presented. One main result shows that for continuous sources and distortion measures of the form d(x,y)=/spl rho/(|x-y|), where /spl rho/ is a nondecreasing convex function, any finite-level ECSQ can be "regularized" so that the resulting regular quantizer has the same entropy and equal or less distortion. Regarding the existence of optimal ECSQs, we prove that under rather general conditions there exists an "almost regular" optimal ECSQ for any entropy constraint. For the squared error distortion measure and sources with piecewise-monotone and continuous densities, the existence of a regular optimal ECSQ is shown.

The Lagrangian formulation of variable-rate vector quantization is known to yield useful necessary conditions for quantizer optimality and generalized Lloyd algorithms for quantizer design. The Lagrangian formulation is demonstrated to provide a convenient framework for analyzing the empirical design of variable-rate vector quantizers. In particular, the consistency of empirical design based on minimizing the Lagrangian performance over a stationary and ergodic training sequence is shown for sources with finite second moment. The finite sample performance is also studied for independent training data and sources with bounded support.

We consider adaptive sequential lossy coding of bounded individual sequences when the performance is measured by the sequentially accumulated mean-squared distortion. The encoder and the decoder are connected via a noiseless channel of capacity R and both are assumed to have zero delay. No probabilistic assumptions are made on how the sequence to be encoded is generated. For any bounded sequence of length n, the distortion redundancy is defined as the normalized cumulative distortion of the sequential scheme minus the normalized cumulative distortion of the best scalar quantizer of rate R which is matched to this particular sequence. We demonstrate the existence of a zero-delay sequential scheme which uses common randomization in the encoder and the decoder such that the normalized maximum distortion redundancy converges to zero at a rate n/sup -1/5/ log n as the length of the encoded sequence n increases without bound.

Principal curves have been defined as "self-consistent" smooth curves which pass through the "middle" of a d-dimensional probability distribution or data cloud. They give a summary of the data and also serve as an efficient feature extraction tool. We take a new approach by defining principal curves as continuous curves of a given length which minimize the expected squared distance between the curve and points of the space randomly chosen according to a given distribution. The new definition makes it possible to theoretically analyze principal curve learning from training data and it also leads to a new practical construction. Our theoretical learning scheme chooses a curve from a class of polygonal lines with k segments and with a given total length to minimize the average squared distance over n training points drawn independently. Convergence properties of this learning scheme are analyzed and a practical version of this theoretical algorithm is implemented. In each iteration of the algorithm, a new vertex is added to the polygonal line and the positions of the vertices are updated so that they minimize a penalized squared distance criterion. Simulation results demonstrate that the new algorithm compares favorably with previous methods, both in terms of performance and computational complexity, and is more robust to varying data models.

Optimal scalar quantization subject to an entropy constraint is studied for a wide class of difference distortion measures including rth-power distortions with r>0. It is proved that if the source is uniformly distributed over an interval, then for any entropy constraint R (in nats), an optimal quantizer has N=[e/sup R/] interval cells such that N-1 cells have equal length d and one cell has length c/spl les/d. The cell lengths are uniquely determined by the requirement that the entropy constraint is satisfied with equality. Based on this result, a parametric representation of the minimum achievable distortion D/sub h/(R) as a function of the entropy constraint R is obtained for a uniform source. The D/sub h/(R) curve turns out to be nonconvex in general. Moreover, for the squared-error distortion it is shown that D/sub h/(R) is a piecewise-concave function, and that a scalar quantizer achieving the lower convex hull of D/sub h/(R) exists only at rates R=log N, where N is a positive integer.

The in-training-set performance of a vector quantizer as a function of its training set size is investigated. For squared error distortion and independent training data, worst case type upper bounds are derived on the minimum training distortion achieved by an empirically optimal quantizer. These bounds show that the training distortion can underestimate the minimum distortion of a truly optimal quantizer by as much as a constant times n/sup -1/2/, where n is the size of the training data. Earlier results provide lower bounds of the same order.

High-resolution bounds in lossy coding of a real memoryless source are considered when side information is present. Let X be a "smooth" source and let Y be the side information. First we treat the case when both the encoder and the decoder have access to Y and we establish an asymptotically tight (high-resolution) formula for the conditional rate-distortion function R/sub X|Y/(D) for a class of locally quadratic distortion measures which may be functions of the side information. We then consider the case when only the decoder has access to the side information (i.e., the "Wyner-Ziv problem"). For side-information-dependent distortion measures, we give an explicit formula which tightly approximates the Wyner-Ziv rate-distortion function R/sup WZ/(D) for small D under some assumptions on the joint distribution of X and Y. These results demonstrate that for side-information-dependent distortion measures the rate loss R/sup WZ/(D)-R/sub X|Y/(D) can be bounded away from zero in the limit of small D. This contrasts the case of distortion measures which do not depend on the side information where the rate loss vanishes as D/spl rarr/0.

The asymptotic (small distortion) behavior of the rate-distortion function of an n-dimensional source vector with mixed distribution is derived. The source distribution is a finite mixture of components such that under each component distribution a certain subset of the coordinates have a discrete distribution while the remaining coordinates have a joint density. The expected number of coordinates with a joint density is shown to equal the rate-distortion dimension of the source vector. Also, the exact small distortion asymptotic behavior of the rate-distortion function of a special but interesting class of stationary information sources is determined.

The problem of asymptotic (i,e., low-distortion) behavior of the rate-distortion function of a random vector is investigated for a class of non-difference distortion measures. The main result is an asymptotically tight expression which parallels the Shannon lower bound for difference distortion measures. For example, for an input-weighted squared error distortion measure d(x,y)=/spl par/W(x)(y-x)/spl par//sup 2/,y,x/spl isin/R/sup n/, the asymptotic expression for the rate-distortion function of X/spl isin/R/sup n/ at distortion level D equals h(X)-/sub 2///sup n/log(2/spl pi/eD/n)+Elog|detW(X)| where h(X) is the differential entropy of X. Extensions to stationary sources and to high-resolution remote ("noisy") source coding are also given.

Entropy-coded vector quantization is studied using high-resolution multidimensional companding over a class of nondifference distortion measures. For distortion measures which are "locally quadratic" a rigorous derivation of the asymptotic distortion and entropy-coded rate of multidimensional companders is given along with conditions for the optimal choice of the compressor function. This optimum compressor, when it exists, depends on the distortion measure but not on the source distribution. The rate-distortion performance of the companding scheme is studied using an asymptotic expression for the rate-distortion function which parallels the Shannon lower bound for difference distortion measures. It is proved that the high-resolution performance of the scheme is arbitrarily close to the rate-distortion limit for large quantizer dimensions if the compressor function and the lattice quantizer used in the companding scheme are optimal, extending an analogous statement for entropy-coded lattice quantization and MSE distortion. The companding approach is applied to obtain a high-resolution quantizing scheme for noisy sources.

Consider encoding a memoryless source using two descriptions, the first at rate R/sub 1/ and distortion d/sub 1/, the second at rate R/sub 2/ and distortion d/sub 2/. Combining the two descriptions the source can be reconstructed with distortion d/sub 0/. For a Gaussian source of variance /spl sigma//sup 2/, Ozarow (1980) found an explicit characterization of the region R*(/spl sigma//sup 2/; d/sub 1/,d/sub 2/,d/sub 0/)/spl sub/R/sup 2/ of achievable rate pairs (R/sub 1/, R/sub 2/) with given mean squared distortions d/sub 1/, d/sub 2/, and d/sub 0/. This is the only case for which the multiple description rate-distortion region is completely known. We show that for a general real valued source X and a locally quadratic distortion measure of the form /spl rho/(x,x/spl circ/)=w(x)/sup 2/(x-x/spl circ/)/sup 2/+o((x-x/spl circ/)/sup 2/), the region of admissible rate pairs is arbitrary well approximated in the limit of small distortions by the region R*(P/sub X/2/sup 2E{log m(X)}/; d/sub 1/,d/sub 2/,d/sub 0/) where R*(/spl sigma//sup 2/; d/sub 1/,/sub 2/, d/sub 0/) denotes the multiple description rate region of a Gaussian source with variance /spl sigma//sup 2/, and where P/sub X/ is the entropy-power of the source. Applications to companding quantization are also considered.

We obtain minimax lower and upper bounds for the expected distortion redundancy of empirically designed vector quantizers. We show that the mean-squared distortion of a vector quantizer designed from n independent and identically distributed (i.i.d.) data points using any design algorithm is at least /spl Omega/(n/sup -1/2/) away from the optimal distortion for some distribution on a bounded subset of /spl Rscr//sup d/. Together with existing upper bounds this result shows that the minimax distortion redundancy for empirical quantizer design, as a function of the size of the training data, is asymptotically on the order of n/sup -1/2/. We also derive a new upper bound for the performance of the empirically optimal quantizer.

In this paper we apply the method of complexity regularization to derive estimation bounds for nonlinear function estimation using a single hidden layer radial basis function network. Our approach differs from previous complexity regularization neural-network function learning schemes in that we operate with random covering numbers and l(1) metric entropy, making it possible to consider much broader families of activation functions, namely functions of bounded variation. Some constraints previously imposed on the network parameters are also eliminated this way. The network is trained by means of complexity regularization involving empirical risk minimization. Bounds on the expected risk in terms of the sample size are obtained for a large class of loss functions. Rates of convergence to the optimal loss are also derived.

The problem of vector quantizer empirical design for noisy channels or for noisy sources is studied. It is shown that the average squared distortion of a vector quantizer designed optimally from observing clean independent and identically distributed (i.i.d.) training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the clean source and transmitting across a discrete memoryless noisy channel. Similarly, it is shown that if the source is corrupted by additive noise, then the average squared distortion of a vector quantizer designed optimally from observing i.i.d. noisy training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the noisy source and transmitting across a noiseless channel. Rates of convergence are also provided.

It is proven that for every random variable with a countably infinite set of outcomes and finite entropy there exists an optimal prefix code which can be constructed from Huffman codes for truncated versions of the random variable, and that the average lengths of any sequence of Huffman codes for the truncated versions converge to that of the optimal code. Also, it is shown that every optimal infinite code achieves Kraft's inequality with equality.

The problem of vector quantizer empirical design for noisy channels or for noisy sources is studied. It is shown that the average squared distortion of a vector quantizer designed optimally from observing clean i.i.d. training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the clean source and transmitting across a discrete memoryless noisy channel. Similarly, it is shown that if the source is corrupted by additive noise, then the average squared distortion of a vector quantizer designed optimally from observing i.i.d. noisy training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the noisy source and transmitting across a noiseless channel. Rates of convergence are also provided.

The method of complexity regularization is applied to one hidden-layer radial basis function networks to derive regression estimation bounds and convergence rates for classification. Bounds on the expected risk in terms of the training sample size are obtained for a large class of activation functions, namely functions of bounded variation. Rates of convergence to the optimal loss are also derived.

The problem of fixed-rate block quantization of an unbounded real memoryless source is studied. It is proved that if the source has a finite sixth moment, then there exists a sequence of quantizers Q/sub n/ of increasing dimension n and fixed rate R such that the mean squared distortion /spl Delta/(Q/sub n/) is bounded as /spl Delta/(Q/sub n/)/spl les/D(R)+O(/spl radic/(log n/n)), where D(R) is the distortion-rate function of the source. Applications of this result include the evaluation of the distortion redundancy of fixed-rate universal quantizers, and the generalization to the non-Gaussian case of a result of Wyner on the transmission of a quantized Gaussian source over a memoryless channel.

Studies convergence properties of radial basis function (RBF) networks for a large class of basis functions, and reviews the methods and results related to this topic. The authors obtain the network parameters through empirical risk minimization. The authors show the optimal nets to be consistent in the problem of nonlinear function approximation and in nonparametric classification. For the classification problem the authors consider two approaches: the selection of the RBF classifier via nonlinear function estimation and the direct method of minimizing the empirical error probability. The tools used in the analysis include distribution-free nonasymptotic probability inequalities and covering numbers for classes of functions.

A fixed-rate universal lossy coding scheme is introduced for independent and identically distributed (i.i.d.) sources. It is shown for finite alphabet sources and arbitrary single letter distortion measures that as the sample size n grows the expected distortion obtained using this universal scheme converges to Shannon's distortion rate function D(R) at a rate O(log n/n). The scheme can be extended to universal quantization of real i.i.d sources subject to a squared error criterion. It is shown in this case that the per-letter distortion converges to D(R) at a rate O(/spl radic/(log n/n)) both in expectation and almost surely for any real-valued bounded i.i.d. source.>

In the paper convergence properties of radial basis function (RBF) networks are studied for a large class of basis functions. The universal approximation property of the nets is shown. Parameters of RBF nets are learned through empirical risk minimization. The optimal nets are shown to be consistent in nonparametric classification. The tools used in the analysis include Vapnik-Chervonenkis (VC) dimension and the covering numbers.

A universal source coding system with vector quantizer codebook transmissions is studied using high resolution quantization theory. Conditions are derived for the optimal tradeoff between quantizer resolution and the information rate used to transmit codebooks. A formula that tightly bounds the mean squared error of the universal coding system as a function of the time between codebook transmissions is experimentally verified and found to be tight, and a new and simpler derivation is given. Other research in the literature has proposed vector quantizing the transmitted codebooks; one conclusion we prove here is that under some reasonable conditions uniform scalar quantization of the transmitted codebooks performs as well as vector quantizing them. Experimental results are given that support the analytic derivations.>

Rate of convergence results are established for vector quantization. Convergence rates are given for an increasing vector dimension and/or an increasing training set size. In particular, the following results are shown for memoryless real-valued sources with bounded support at transmission rate R. (1) If a vector quantizer with fixed dimension k is designed to minimize the empirical mean-square error (MSE) with respect to m training vectors, then its MSE for the true source converges in expectation and almost surely to the minimum possible MSE as O(/spl radic/(log m/m)). (2) The MSE of an optimal k-dimensional vector quantizer for the true source converges, as the dimension grows, to the distortion-rate function D(R) as O(/spl radic/(log k/k)). (3) There exists a fixed-rate universal lossy source coding scheme whose per-letter MSE on a real-valued source samples converges in expectation and almost surely to the distortion-rate function D(R) as O((/spl radic/(loglog n/log n)). (4) Consider a training set of n real-valued source samples blocked into vectors of dimension k, and a k-dimension vector quantizer designed to minimize the empirical MSE with respect to the m=[n/k] training vectors. Then the per-letter MSE of this quantizer for the true source converges in expectation and almost surely to the distortion-rate function D(R) as O(/spl radic/(log log n/log n))), if one chooses k=[(1/R)(1-/spl epsiv/)log n] for any /spl epsiv//spl isin/(0.1).>

Two results are given. First, using a result of Csiszar (1973) the asymptotic (i.e., high-resolution/low distortion) performance for entropy-constrained tessellating vector quantization, heuristically derived by Gersho (1979), is proven for all sources with finite differential entropy. This implies, using Gersho's conjecture and Zador's formula, that tessellating vector quantizers are asymptotically optimal for this broad class of sources, and generalizes a rigorous result of Gish and Pierce (1968) from the scalar to the vector case. Second, the asymptotic performance is established for Zamir and Feder's (1992) randomized lattice quantization. With the only assumption that the source has finite differential entropy, it is proven that the low-distortion performance of the Zamir-Feder universal vector quantizer is asympotically the same as that of the deterministic lattice quantizer.>

New results are proved on the convergence of the Shannon (1959) lower bound to the rate distortion function as the distortion decreases to zero. The key convergence result is proved using a fundamental property of informational divergence. As a corollary, it is shown that the Shannon lower bound is asymptotically tight for norm-based distortions, when the source vector has a finite differential entropy and a finite /spl alpha/ th moment for some /spl alpha/>0, with respect to the given norm. Moreover, we derive a theorem of Linkov (1965) on the asymptotic tightness of the Shannon lower bound for general difference distortion measures with more relaxed conditions on the source density. We also show that the Shannon lower bound relative to a stationary source and single-letter difference distortion is asymptotically tight under very weak assumptions on the source distribution.>

The authors show that without knowing anything about the statistics of a bounded real-valued memoryless source, it is possible to construct a sequence of codes, of rate not exceeding a fixed number R>0, such that the per-letter sample distortion converges to the distortion-rate function D(R) with probability one as the length of the message approaches infinity. It is proven that the distortion converges to D(R) as square root log log n/log n almost surely, where n is the length of the data to be transmitted.>

A fast nearest-neighbor algorithm is presented. It works in general spaces in which the known cell techniques cannot be implemented for various reasons, such as the absence of coordinate structure or high dimensionality. The central idea has already appeared several times in the literature with extensive computer simulation results. An exact probabilistic analysis of this family of algorithms that proves its O(1) asymptotic average complexity measured in the number of dissimilarity calculations is presented.>