Search

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(\frac{1}{T})$. This gives an explicit rate of convergence that quantifies the near-optimality of finite window (finite-memory) codes among all optimal zero-delay codes., Comment: 15 pages

In this paper, we study the problem of achieving average consensus over a random time-varying sequence of directed graphs by extending the class of so-called push-sum algorithms to such random scenarios. Provided that an ergodicity notion, which we term the directed infinite flow property, holds and the auxiliary states of agents are uniformly bounded away from zero infinitely often, we prove the almost sure convergence of the evolutions of this class of algorithms to the average of initial states. Moreover, for a random sequence of graphs generated using a so-called time-varying $B$ -irreducible probability matrix, we establish convergence rates for the proposed push-sum algorithm.

We consider finite model approximations of discrete-time partially observed Markov decision processes (POMDPs) under the discounted cost criterion. After converting the original partially observed stochastic control problem to a fully observed one on the belief space, the finite models are obtained through the uniform quantization of the state and action spaces of the belief space Markov decision process (MDP). Under mild assumptions on the components of the original model, it is established that the policies obtained from these finite models are nearly optimal for the belief space MDP, and so, for the original partially observed problem. The assumptions essentially require that the belief space MDP satisfies a mild weak continuity condition. We provide an example and introduce explicit approximation procedures for the quantization of the set of probability measures on the state space of POMDP (i.e., belief space).

The Rényi cross-entropy measure between two distributions, a generalization of the Shannon cross-entropy, was recently used as a loss function for the improved design of deep learning generative adversarial networks. In this work, we examine the properties of this measure and derive closed-form expressions for it when one of the distributions is fixed and when both distributions belong to the exponential family. We also analytically determine a formula for the cross-entropy rate for stationary Gaussian processes and for finite-alphabet Markov sources., Appeared in the Proceedings of CWIT'22 (updated version)

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., Comment: 27 pages and 1 figure. arXiv admin note: text overlap with arXiv:1901.06738

This paper considers an information bottleneck problem with the objective of obtaining a most informative representation of a hidden feature subject to a Renyi entropy complexity constraint. The optimal bottleneck trade-off between relevance (measured via Shannon's mutual information) and Renyi 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 Renyi 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.

In this paper, we make use of channel symmetry properties to determine the capacity region of three types of two-way networks: (a) two-user memoryless two-way channels (TWCs), (b) two-user TWCs with memory, and (c) 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., Comment: 56 pages, 8 figures, a missing condition in Corollary 4 and Theorem 9 added

We consider a distributed online optimization problem where, at each time, a group of agents choose their individual states, after which an individual cost function is revealed to each of them. The whole network then faces a regret according to the cumulative sum of costs incurred by the agents’ chosen states, and each agent faces an individual regret according to the cumulative sum of costs incurred by the agent's state estimation, perceived as the whole network's chosen state. In order to tackle the minimization of the individual regret using only local information, we assume that the group of agents communicate over a fixed undirected connected graph. We then propose an online version of the alternating direction method of multipliers algorithm, distributed over the communication graph, which allows each agent to drive its individual average regret over time to zero.

Optimal zero-delay coding (fixed-rate quantization) of ℝd-valued linear Markov sources is studied. The structure and existence of deterministic and stationary coding policies for the infinite horizon average cost problem is established. Prior results in the literature studying optimality results for Markov sources under infinite horizons either considered finite alphabet sources or, for ℝd-valued case, only established the existence of deterministic and non-stationary Markov coding policies or those which are randomized. In addition to existence results, the finite blocklength (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 ).

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., a spelling error corrected

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., Comment: 44 pages, 6 figures

We consider the distributed optimization problem for the sum of convex functions where the underlying communications network connecting agents at each time is drawn at random from a collection of directed graphs. We propose a modified version of the subgradient-push algorithm that is provably almost surely convergent to an optimizer on any such sequence of random directed graphs, establishing the first of this kind.

We provide a set of counterexamples for the monotonicity of the Newton–Hewer method (Hewer, 1971) for solving the discrete-time algebraic Riccati equation in dynamic settings, drawing a contrast with the Riccati difference equation (Caines and Mayne, 1970).

Calculating optimal policies is known to be computationally difficult for Markov decision processes (MDPs) with Borel state and action spaces. This paper studies finite-state approximations of discrete time Markov decision processes with Borel state and action spaces, for both discounted and average costs criteria. The stationary policies thus obtained are shown to approximate the optimal stationary policy with arbitrary precision under quite general conditions for discounted cost and more restrictive conditions for average cost. For compact-state MDPs, we obtain explicit rate of convergence bounds quantifying how the approximation improves as the size of the approximating finite state space increases. Using information theoretic arguments, the order optimality of the obtained convergence rates is established for a large class of problems. We also show that as a pre-processing step, the action space can also be finitely approximated with sufficiently large number points; thereby, well known algorithms, such as value or policy iteration, Q-learning, etc., can be used to calculate near optimal policies.

This paper introduces a class of discrete-time distributed online optimization algorithms, with a group of agents whose communication topology is given by a uniformly strongly connected sequence of time-varying networks. At each time, a private locally Lipschitz strongly convex objective function is revealed to each agent. In the next time step, each agent updates its state using its own objective function and the information gathered from its immediate in-neighbors at that time. Under the assumption that the sequence of communication topologies is uniformly strongly connected, we design an algorithm, distributed over the sequence of time-varying topologies, which guarantees that the individual regret, the difference between the network cost incurred by the agent's states estimation and the cost incurred by the best fixed choice, grows only sublinearly. This algorithm consists of a subgradient flow along with a push-sum step to adjust for the directed nature of the network topologies. We implement the proposed algorithm in a collaborative localization problem, and the results show the proper performance of the algorithm.

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., a spelling error corrected

In this report, we generalize Shannon's push-to-talk two-way channel (PTT-TWC) by allowing reliable full-duplex transmission as well as noisy reception in the half-duplex (PTT) mode. Viewing a PTT-TWC as two state-dependent one-way channels, we introduce a channel symmetry property pertaining to the one-way channels. Shannon's TWC capacity inner bound is shown to be tight for the generalized model under this symmetry property. We also analytically derive the capacity region, which is shown to be the convex hull of (at most) 4 rate pairs. Examples that illustrate different shapes of the capacity region are given, and efficient transmission schemes are discussed via the examples., 10 pages, 5 figures, 5 tables, a typo corrected, presented at CWIT'19

This paper studies the approximation of optimal control policies by quantized (discretized) policies for a very general class of Markov decision processes (MDPs). The problem is motivated by applications in networked control systems, computational methods for MDPs, and learning algorithms for MDPs. We consider the finite-action approximation of stationary policies for a discrete-time Markov decision process with discounted and average costs under a weak continuity assumption on the transition probability, which is a significant relaxation of conditions required in earlier literature. The discretization is constructive, and quantized policies are shown to approximate optimal deterministic stationary policies with arbitrary precision. The results are applied to the fully observed reduction of a partially observed Markov decision process, where weak continuity is a much more reasonable assumption than more stringent conditions such as strong continuity or continuity in total variation., Comment: 19 pages

Many applications in networked control require intermittent access of a controller to a system, as in event-triggered systems or information constrained control applications. Motivated by such applications and extending previous work on Lyapunov-theoretic drift criteria, we establish both subgeometric and geometric rates of convergence for Markov chains under state dependent random time drift criteria. We quantify how the rate of ergodicity, nature of Lyapunov functions, their drift properties, and the distributions of stopping times are related. We finally study an application in networked control.

We consider push-sum algorithms for average consensus over a random time-varying sequence of directed graphs. Motivated by the notion of infinite flow property used in the consensus literature, we introduce the notion of directed infinite flow property, which allows us to establish the ergodicity of matrices corresponding to the push-sum protocol. Using this result and the assumption that the auxiliary states of agents are uniformly bounded away from zero infinitely often, we prove the almost sure convergence of the evolutions of this class of algorithms to the average of initial states. We demonstrate that many interesting time-varying sequences of random directed graphs satisfy our condition. In particular, for a random sequence of directed graphs, we obtain uniform convergence rates for the push-sum algorithm.

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.

Due to copyright restrictions, the access to the full text of this article is only available via subscription. This chapter studies the finite-model approximation of discrete-time partially observed Markov decision process. We will find that by performing the standard reduction method, where one transforms a partially observed model to a belief-based fully observed model, we can apply and properly generalize the results in the preceding chapters to obtain approximation results. The versatility of approximation results under weak continuity conditions become particularly evident while investigating the applicability of these results to the partially observed case. We also provide systematic procedures for the quantization of the set of probability measures on the state space of POMDPs which is the state space of belief-MDPs.

Due to copyright restrictions, the access to the full text of this article is only available via subscription. This chapter studies the finite-state approximation of a discrete-time constrained Markov decision process with compact state space, under the discounted and average cost criteria. Using the linear programming formulation of the constrained discounted problem, we prove the convergence of the optimal value function of the finite-state model to the optimal value function of the original model. Under further continuity conditions on the transition probability of the original discounted model, we also establish a method to compute approximately optimal policies. For the average cost criterion, instead of using the finite-state linear programming approximation method, we use a direct method to establish analogous results under drift and minorization conditions which guarantee the geometric ergodicity of Markov chains induced by stationary policies.

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., Comment: 5 pages, 2 figures, a mis-inserted figure corrected, to be presented at IEEE ISIT 2018

In this chapter we study the finite-state approximation problem for computing near optimal policies for discrete-time MDPs with Borel state and action spaces, under discounted and average costs criteria. Even though existence and structural properties of optimal policies of MDPs have been studied extensively in the literature, computing such policies is generally a challenging problem for systems with uncountable state spaces. This situation also arises in the fully observed reduction of a partially observed Markov decision process even when the original system has finite state and action spaces. Here we show that one way to compute approximately optimal solutions for such MDPs is to construct a reduced model with a new transition probability and one-stage cost function by quantizing the state space, i.e., by discretizing it on a finite grid. It is reasonable to expect that when the one-stage cost function and the transition probability of the original model has certain continuity properties, the cost of the optimal policy for the approximating finite model converges to the optimal cost of the original model as the discretization becomes finer. Moreover, under additional continuity conditions on the transition probability and the one stage cost function we also obtain bounds on the accuracy of the approximation in terms of the number of points used to discretize the state space, thereby providing a tradeoff between the computation cost and the performance loss in the system. In particular, we study the following two problems.

Due to copyright restrictions, the access to the full text of this article is only available via subscription. In this chapter, we study the approximation of Witsenhausen’s counterexample and the Gaussian relay channel problem by using the results of the previous chapter. In particular, our goal is to establish that finite models obtained through the uniform quantization of the observation and action spaces result in a sequence of policies whose costs converge to the value function. We note that the operation of quantization has typically been the method to show that a non-linear policy can perform better than an optimal linear policy, both for Witsenhausen’s counterexample [10, 86] and the Gaussian relay channel problem [88, 152]. Our findings show that for a large class of problems, quantized policies not only may perform better than linear policies, but that they are actually almost optimal.

Due to copyright restrictions, the access to the full text of this article is only available via subscription. In this chapter, we study the approximation of static and dynamic team problems using finite models which are obtained through the uniform discretization, on a finite grid, of the observation and action spaces of agents. In particular, we are interested in the asymptotic optimality of quantized policies.

Due to copyright restrictions, the access to the full text of this article is only available via subscription. In Part II, we focus on decentralized stochastic control problems and their applications. In Chapter 8, we present our results on the finite model approximation of multi-agent stochastic control problems (team decision problems). We show that optimal strategies obtained from finite models approximate the optimal cost with arbitrary precision under mild technical assumptions. In particular, we show that quantized team policies are asymptotically optimal. In Chapter 9, the results are applied to Witsenhausen’s counterexample and the Gaussian relay channel problem.

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., Comment: 5 pages, 3 figures, a minor typo fixed, presented at IEEE ITW 2017

The optimal energy allocations for minimizing the joint symbol error rate for binary signaling of two correlated sources over the orthogonal multiple-access Gaussian channel under joint maximum a priori (MAP) detection are determined. An exact expression for the system's probability of joint symbol error, as well as its union bound, is derived. Analytic minimization of the union bound reveals that the optimal energy allocation coincides with that of nonuniform binary signaling over the single-user additive white Gaussian noise channel. It is also shown numerically that the optimal energies that minimize the union bound also minimize the exact probability of error. Finally, it is shown via simulations for strongly biased sources that the use of joint MAP detection over two independent single-user systems leads to significant gains.

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., 15 pages

We consider the discrete approximation of stationary policies for a discrete-time Markov decision process with Polish state and action spaces under total, discounted, and average cost criteria. Deterministic stationary quantizer policies are introduced and shown to be able to approximate optimal deterministic stationary policies with arbitrary precision under mild technical conditions, thus demonstrating that one can search for $\varepsilon$ -optimal policies within the class of quantized control policies. We also derive explicit bounds on the approximation error in terms of the quantization rate.

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 block-lengths., Comment: To appear in the IEEE Transactions on Information Theory

We investigate the problem of estimating a random variable $Y\in \mathcal{Y}$ under a privacy constraint dictated by another random variable $X\in \mathcal{X}$, where estimation efficiency and privacy are assessed in terms of two different loss functions. In the discrete case, we use the Hamming loss function and express the corresponding utility-privacy tradeoff in terms of the privacy-constrained guessing probability $h(P_{XY}, \epsilon)$, the maximum probability $\mathsf{P}_\mathsf{c}(Y|Z)$ of correctly guessing $Y$ given an auxiliary random variable $Z\in \mathcal{Z}$, where the maximization is taken over all $P_{Z|Y}$ ensuring that $\mathsf{P}_\mathsf{c}(X|Z)\leq \epsilon$ for a given privacy threshold $\epsilon \geq 0$. We prove that $h(P_{XY}, \cdot)$ is concave and piecewise linear, which allows us to derive its expression in closed form for any $\epsilon$ when $X$ and $Y$ are binary. In the non-binary case, we derive $h(P_{XY}, \epsilon)$ in the high utility regime (i.e., for sufficiently large values of $\epsilon$) under the assumption that $Z$ takes values in $\mathcal{Y}$. We also analyze the privacy-constrained guessing probability for two binary vector scenarios. When $X$ and $Y$ are continuous random variables, we use the squared-error loss function and express the corresponding utility-privacy tradeoff in terms of $\mathsf{sENSR}(P_{XY}, \epsilon)$, which is the smallest normalized minimum mean squared-error (mmse) incurred in estimating $Y$ from its Gaussian perturbation $Z$, such that the mmse of $f(X)$ given $Z$ is within $\epsilon$ of the variance of $f(X)$ for any non-constant real-valued function $f$. We derive tight upper and lower bounds for $\mathsf{sENSR}$ when $Y$ is Gaussian. We also obtain a tight lower bound for $\mathsf{sENSR}(P_{XY}, \epsilon)$ for general absolutely continuous random variables when $\epsilon$ is sufficiently small., Comment: To appear in IEEE Transaction on Information Theory

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(P_{XY}, \epsilon)$ as the maximum probability of correctly guessing $Y$ given an auxiliary random variable $Z$, where the maximization is taken over all $P_{Z|Y}$ ensuring that the probability of correctly guessing $X$ given $Z$ does not exceed $\epsilon$. We show that the map $\epsilon\mapsto h(P_{XY}, \epsilon)$ is strictly increasing, concave, and piecewise linear, which allows us to derive a closed form expression for $h(P_{XY}, \epsilon)$ when $X$ and $Y$ are connected via a binary-input binary-output channel. For $(X^n, Y^n)$ being pairs of independent and identically distributed binary random vectors, we similarly define $\underline{h}_n(P_{X^nY^n}, \epsilon)$ under the assumption that $Z^n$ is also a binary vector. Then we obtain a closed form expression for $\underline{h}_n(P_{X^nY^n}, \epsilon)$ for sufficiently large, but nontrivial values of $\epsilon$., Comment: ISIT 2017

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.

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 feedback does not increase capacity and generalizing prior related results. The capacity-cost function of the channel with and without feedback is also 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., Parts of this work will be presented at the 2017 IEEE International Symposium on Information Theory

Subspace constrained mean shift (SCMS) is a non-parametric, iterative algorithm that has recently been proposed to find principal curves and surfaces based on a new definition involving the gradient and Hessian of a kernel probability density estimate. Although simulation results using synthetic and real data have demonstrated the usefulness of the SCMS algorithm, a rigorous study of its convergence is still missing. This paper aims to take initial steps in this direction by showing that the SCMS algorithm inherits some important convergence properties of the mean shift (MS) algorithm. In particular, the monotonicity and convergence of the density estimate values along the sequence of output values of the algorithm is shown. Also, it is shown that the distance between consecutive points of the output sequence converges to zero, as does the projection of the gradient vector onto the subspace spanned by the D − d eigenvectors corresponding to the D-d largest eigenvalues of the local inverse covariance matrix. These last two properties provide theoretical guarantees for stopping criteria. By modifying the projection step, three variations of the SCMS algorithm are proposed and the running times and performance of the resulting algorithms are compared.

Probabilistic ‘distances’ (also called divergences), which in some sense assess how ‘close’ two probability distributions are from one another, have been widely employed in probability, statistics, information theory, and related fields. Of particular importance due to their generality and applicability are the Renyi divergence measures. This paper presents closed-form expressions for the Renyi and Kullback–Leibler divergences for nineteen commonly used univariate continuous distributions as well as those for multivariate Gaussian and Dirichlet distributions. In addition, a table summarizing four of the most important information measure rates for zero-mean stationary Gaussian processes, namely Renyi entropy, differential Shannon entropy, Renyi divergence, and Kullback–Leibler divergence, is presented. Lastly, a connection between the Renyi divergence and the variance of the log-likelihood ratio of two distributions is established, thereby extending a previous result by Song [J. Stat. Plan. Infer. 93 (2001)] on the relation between Renyi entropy and the log-likelihood function. A table with the corresponding variance expressions for the univariate distributions considered here is also included.

The joint source-channel coding (JSCC) problem for soft-decision-demodulated time-correlated fading channels is investigated without the use of channel coding and interleaving. For the purpose of system design, the recently introduced nonbinary noise discrete channel with queue-based (QB) noise (NBNDC-QB) is adopted. This analytically tractable Markovian model has been shown to represent effectively correlated fading channels that are hard to handle analytically. Optimal sequence maximum a posteriori (MAP) detection of a discrete Markov source sent over the NBNDC-QB is first studied. When the Markov source is binary and symmetric, a necessary and sufficient condition under which the MAP decoder is reduced to a simple instantaneous symbol-by-symbol decoder is established. Two robust lossy source coding schemes with a low encoding delay are next proposed for the NBNDC-QB. The first scheme consists of a scalar quantizer (SQ), a proper index assignment, and a sequence MAP decoder designed to harness the redundancy left in the indexes of the quantizer and the soft-decision output and the noise correlation of the channel. The second scheme is a classical noise-resilient vector quantizer known as the channel-optimized vector quantizer (COVQ). It is demonstrated that both systems can successfully exploit the memory and soft-decision information of the channel. Signal-to-distortion-ratio (SDR) gains of more than 1.7 dB are obtained over hard-decision demodulation by using only two bits for soft decision. Furthermore, gains as high as 4.4 dB can be achieved for a strongly correlated channel, in comparison with systems designed for the ideally interleaved (memoryless) channel. Finally, it is numerically observed that, for low coding rates, the NBNDC-QB model can accurately approximate discrete fading channels (DFCs) in terms of SDR performance.

In this paper, we consider finite model approximations of a large class of static and dynamic team problems where these models are constructed through uniform quantization of the observation and action spaces of the agents. The strategies obtained from these finite models are shown to approximate the optimal cost with arbitrary precision under mild technical assumptions. In particular, quantized team policies are asymptotically optimal. This result is then applied to Witsenhausen's celebrated counterexample and the Gaussian relay channel problem. For the Witsenhausen's counterexample, our approximation approach provides, to our knowledge, the first rigorously established result that one can construct an $\varepsilon$-optimal strategy for any $\varepsilon > 0$ through a solution of a simpler problem., 13 pages, double column

In this paper, we consider finite model approximations of team problems where the finite models are constructed through uniform quantization of the observations of the agents. Strategies obtained from finite models are shown to approximate the optimal cost with arbitrary precision under mild technical assumptions. An analogous result is separately proved for the Witsenhausen's celebrated counterexample. For this counterexample, our approximation approach provides the first rigorously established result, to our knowledge, that for any e > 0, one can construct an e-optimal strategy through an explicit solution of a simpler problem.

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 \emph{optimal} random mapping $P_{Z|Y}$ such that the MMSE of $Y$ given $Z$ is minimized while the MMSE of $X$ given $Z$ is greater than $(1-\epsilon)\mathsf{var}(X)$ for a given $\epsilon\geq 0$. We also consider the case where $(X,Y)$ are continuous and $P_{Z|Y}$ is restricted to be an additive noise channel., Comment: 9 pages, 3 figures

We study the maximal mutual information about a random variable Y (representing non-private information) displayed through an additive Gaussian channel when guaranteeing that only \(\varepsilon \) bits of information is leaked about a random variable X (representing private information) that is correlated with Y. Denoting this quantity by \(g_\varepsilon (X,Y)\), we show that for perfect privacy, i.e., \(\varepsilon =0\), one has \(g_0(X,Y)=0\) for any pair of absolutely continuous random variables (X, Y) and then derive a second-order approximation for \(g_\varepsilon (X,Y)\) for small \(\varepsilon \). This approximation is shown to be related to the strong data processing inequality for mutual information under suitable conditions on the joint distribution \(P_{XY}\). Next, motivated by an operational interpretation of data privacy, we formulate the privacy-utility tradeoff in the same setup using estimation-theoretic quantities and obtain explicit bounds for this tradeoff when \(\varepsilon \) is sufficiently small using the approximation formula derived for \(g_\varepsilon (X,Y)\).

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., Comment: 6 pages, 2 figures

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 algorithm $\A$ that 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 of $\A$ in the sense that it can be implemented with time and space complexity only $O(n^{\gamma} \ln n)$ times larger than that of $\A$, where $n$ is the time horizon and $\gamma \ge 0$ is a parameter of the algorithm. With $\A$ properly chosen, our algorithm achieves a regret bound of optimal order for $\gamma>0$, and only $O(\ln n)$ times larger than the optimal order for $\gamma=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 optimal $O(\ln n)$ regret rate with time complexity $O(n^{1+\gamma}\ln n)$ for any $\gamma\in (0,1)$., Comment: 17 pages, to appear in the IEEE Transactions on Information Theory