Source author record

Charalambos D. Charalambous

Charalambos D. Charalambous appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

44works
8topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

44 published item(s)

preprint2022arXiv

Characterization of the Gray-Wyner Rate Region for Multivariate Gaussian Sources: Optimality of Gaussian Auxiliary RV

Examined in this paper, is the Gray and Wyner achievable lossy rate region for a tuple of correlated multivariate Gaussian random variables (RVs) $X_1 : Ω\rightarrow {\mathbb R}^{p_1}$ and $X_2 : Ω\rightarrow {\mathbb R}^{p_2}$ with respect to square-error distortions at the two decoders. It is shown that among all joint distributions induced by a triple of RVs $(X_1,X_2, W)$, such that $W : Ω\rightarrow {\mathbb W} $ is the auxiliary RV taking continuous, countable, or finite values, the Gray and Wyner achievable rate region is characterized by jointly Gaussian RVs $(X_1,X_2, W)$ such that $W $ is an $n$-dimensional Gaussian RV. It then follows that the achievable rate region is parametrized by the three conditional covariances $Q_{X_1,X_2|W}, Q_{X_1|W}, Q_{X_2|W}$ of the jointly Gaussian RVs. Furthermore, if the RV $W$ makes $X_1$ and $X_2$ conditionally independent, then the corresponding subset of the achievable rate region, is simpler, and parametrized by only the two conditional covariances $Q_{X_1|W}, Q_{X_2|W}$. The paper also includes the characterization of the Pangloss plane of the Gray-Wyner rate region along with the characterizations of the corresponding rate distortion functions, their test-channel distributions, and structural properties of the realizations which induce these distributions.

preprint2022arXiv

On the Capacity of Gaussian MIMO Channels with Memory

The operational capacity of Gaussian MIMO channels with memory was obtained by Brandenburg and Wyner in [9] under certain mild assumptions on the channel impulse response and its noise covariance matrix, which essentuially require channel memory to be not too strong. This channel was also considered by Tsybakov in [10] and its information capacity was obtained in some cases. It was further conjectured, based on numerical evidence, that these capacities are the same in all cases. This conjecture is proved here. An explicit closed-form expression for the optimal input power spectral density matrix is also given. The obtained result is further extended to the case of joint constraints, including per-antenna and interference power constraints as well as energy harvesting constraints. These results imply the information-theoretic optimality of OFDM-type transmission systems for such channels with memory.

preprint2021arXiv

A New Approach to Lossy Network Compression of a Tuple of Correlated Multivariate Gaussian RVs

The classical Gray and Wyner source coding for a simple network for sources that generate a tuple of multivariate, correlated Gaussian random variables $(Y_1,Y_2)$ is re-examined using the geometric approach of Gaussian random variables, and the weak stochastic realization of correlated Gaussian random variables. New results are: (1) The formulation, methods and algorithms to parametrize all random variables $W : Ω\rightarrow {\mathbb R}^n $ which make the two components of the tuple $(Y_1,Y_2)$ conditionally independent, according to the weak stochastic realization of $(Y_1, Y_2)$. (2) The transformation of random variables $(Y_1,Y_2)$ via non-singular transformations $(S_1,S_2)$, into their canonical variable form. (3) A formula for Wyner's lossy common information for joint decoding with mean-square error distortions. (4) The methods are shown to be of fundamental importance to the parametrization of the lossy rate region of the Gray and Wyner source coding problem, and the calculation of the smallest common message rate $R_0$ on the Gray and Wyner source problem, when the sum rate $R_0+R_1+R_2$ is arbitrary close to the joint rate distortion function $R_{Y_1, Y_2}(Δ_1, Δ_2)$ of joint decoding. The methods and algorithms may be applicable to other problems of multi-user communication, such as, the multiple access channel, etc. The discussion is largely self-contained and proceeds from first principles; basic concepts of weak stochastic realization theory of multivariate correlated Gaussian random variables are reviewed, while certain results are developed to meet the requirement of results (1)-(4).

preprint2020arXiv

Characterization of Conditional Independence and Weak Realizations of Multivariate Gaussian Random Variables: Applications to Networks

The Gray and Wyner lossy source coding for a simple network for sources that generate a tuple of jointly Gaussian random variables (RVs) $X_1 : Ω\rightarrow {\mathbb R}^{p_1}$ and $X_2 : Ω\rightarrow {\mathbb R}^{p_2}$, with respect to square-error distortion at the two decoders is re-examined using (1) Hotelling's geometric approach of Gaussian RVs-the canonical variable form, and (2) van Putten's and van Schuppen's parametrization of joint distributions ${\bf P}_{X_1, X_2, W}$ by Gaussian RVs $W : Ω\rightarrow {\mathbb R}^n $ which make $(X_1,X_2)$ conditionally independent, and the weak stochastic realization of $(X_1, X_2)$. Item (2) is used to parametrize the lossy rate region of the Gray and Wyner source coding problem for joint decoding with mean-square error distortions ${\bf E}\big\{||X_i-\hat{X}_i||_{{\mathbb R}^{p_i}}^2 \big\}\leq Δ_i \in [0,\infty], i=1,2$, by the covariance matrix of RV $W$. From this then follows Wyner's common information $C_W(X_1,X_2)$ (information definition) is achieved by $W$ with identity covariance matrix, while a formula for Wyner's lossy common information (operational definition) is derived, given by $C_{WL}(X_1,X_2)=C_W(X_1,X_2) = \frac{1}{2} \sum_{j=1}^n \ln \left( \frac{1+d_j}{1-d_j} \right),$ for the distortion region $ 0\leq Δ_1 \leq \sum_{j=1}^n(1-d_j)$, $0\leq Δ_2 \leq \sum_{j=1}^n(1-d_j)$, and where $1 > d_1 \geq d_2 \geq \ldots \geq d_n>0$ in $(0,1)$ are {\em the canonical correlation coefficients} computed from the canonical variable form of the tuple $(X_1, X_2)$. The methods are of fundamental importance to other problems of multi-user communication, where conditional independence is imposed as a constraint.

preprint2016arXiv

A General Formula for Compound Channel Capacity

A general formula for the capacity of arbitrary compound channels with the receiver channel state information is obtained using the information density approach. No assumptions of ergodicity, stationarity or information stability are made and the channel state set is arbitrary. A direct (constructive) proof is given. To prove achievability, we generalize Feinstein Lemma to the compound channel setting, and to prove converse, we generalize Verdu-Han Lemma to the same compound setting. A notion of a uniform compound channel is introduced and the general formula is shown to reduce to the familiar $\sup-\inf$ expression for such channels. As a by-product, the arbitrary varying channel capacity is established under maximum error probability and deterministic coding. Conditions are established under which the worst-case and compound channel capacities are equal so that the full channel state information at the transmitter brings in no advantage. The compound inf-information rate plays a prominent role in the general formula. Its properties are studied and a link between information-unstable and information-stable regimes of a compound channel is established. The results are extended to include $\varepsilon$-capacity of compound channels. Sufficient and necessary conditions for the strong converse to hold are given.

preprint2016arXiv

Capacity Achieving Distributions & Information Lossless Randomized Strategies for Feedback Channels with Memory: The LQG Theory of Directed Information-Part II

A methodology is developed to realized optimal channel input conditional distributions, which maximize the finite-time horizon directed information, for channels with memory and feedback, by information lossless randomized strategies. The methodology is applied to general Time-Varying Multiple Input Multiple Output (MIMO) Gaussian Linear Channel Models (G-LCMs) with memory, subject to average transmission cost constraints of quadratic form. The realizations of optimal distributions by randomized strategies are shown to exhibit a decomposion into a deterministic part and a random part. The decomposition reveals the dual role of randomized strategies, to control the channel output process and to transmit new information over the channels. Moreover, a separation principle is shown between the computation of the optimal deterministic part and the random part of the randomized strategies. The dual role of randomized strategies generalizes the Linear-Quadratic-Gaussian (LQG) stochastic optimal control theory to directed information pay-offs. The characterizations of feedback capacity are obtained from the per unit time limits of finite-time horizon directed information, without imposing á priori assumptions, such as, stability of channel models or ergodicity of channel input and output processes. For time-invariant MIMO G-LCMs with memory, it is shown that whether feedback increases capacity, is directly related to the channel parameters and the transmission cost function, through the solutions of Riccati matrix equations, and moreover for unstable channels, feedback capacity is non-zero, provided the power exceeds a critical level.

preprint2016arXiv

Feedback Does Not Increase the Capacity of Compound Channels with Additive Noise

A discrete compound channel with memory is considered, where no stationarity, ergodicity or information stability is required, and where the uncertainty set can be arbitrary. When the discrete noise is additive but otherwise arbitrary and there is no cost constraint on the input, it is shown that the causal feedback does not increase the capacity. This extends the earlier result obtained for general single-state channels with full transmitter (Tx) channel state information (CSI) to the compound setting. It is further shown that, for this compound setting and under a mild technical condition on the additive noise, the addition of the full Tx CSI does not increase the capacity either, so that the worst-case and compound channel capacities are the same. This can also be expressed as a saddle-point in the information-theoretic game between the transmitter (who selects the input distribution) and the nature (who selects the channel state), even though the objective function (the inf-information rate) is not convex/concave in the right way. Cases where the Tx CSI does increase the capacity are identified. Conditions under which the strong converse holds for this channel are studied. The ergodic behaviour of the worst-case noise in otherwise information-unstable channel is shown to be both sufficient and necessary for the strong converse to hold, including feedback and no feedback cases.

preprint2016arXiv

Information Structures for Feedback Capacity of Channels with Memory and Transmission Cost: Stochastic Optimal Control & Variational Equalities-Part I

The Finite Transmission Feedback Information (FTFI) capacity is characterized for any class of channel conditional distributions $\big\{{\bf P}_{B_i|B^{i-1}, A_i} :i=0, 1, \ldots, n\big\}$ and $\big\{ {\bf P}_{B_i|B_{i-M}^{i-1}, A_i} :i=0, 1, \ldots, n\big\}$, where $M$ is the memory of the channel, $B^n {\stackrel{\triangle}{=}} \{B_j: j=\ldots, 0,1, \ldots, n\}$ are the channel outputs and $A^n{\stackrel{\triangle}{=}} \{A_j: j=\ldots, 0,1, \ldots, n\}$ are the channel inputs. The characterizations of FTFI capacity, are obtained by first identifying the information structures of the optimal channel input conditional distributions ${\cal P}_{[0,n]} {\stackrel{\triangle}{=}} \big\{ {\bf P}_{A_i|A^{i-1}, B^{i-1}}: i=0, \ldots, n\big\}$, which maximize directed information. The main theorem states, for any channel with memory $M$, the optimal channel input conditional distributions occur in the subset satisfying conditional independence $\stackrel{\circ}{\cal P}_{[0,n]}{\stackrel{\triangle}{=}} \big\{ {\bf P}_{A_i|A^{i-1}, B^{i-1}}= {\bf P}_{A_i|B_{i-M}^{i-1}}: i=1, \ldots, n\big\}$, and the characterization of FTFI capacity is given by $C_{A^n \rightarrow B^n}^{FB, M} {\stackrel{\triangle}{=}} \sup_{ \stackrel{\circ}{\cal P}_{[0,n]} } \sum_{i=0}^n I(A_i; B_i|B_{i-M}^{i-1}) $. The methodology utilizes stochastic optimal control theory and a variational equality of directed information, to derive upper bounds on $I(A^n \rightarrow B^n)$, which are achievable over specific subsets of channel input conditional distributions ${\cal P}_{[0,n]}$, which are characterized by conditional independence. For any of the above classes of channel distributions and transmission cost functions, a direct analogy, in terms of conditional independence, of the characterizations of FTFI capacity and Shannon's capacity formulae of Memoryless Channels is identified.

preprint2016arXiv

Information Structures of Maximizing Distributions of Feedback Capacity for General Channels with Memory & Applications

For any class of channel conditional distributions, with finite memory dependence on channel input RVs $A^n {\stackrel{\triangle}{=}} \{A_i: i=0, \ldots, n\}$ or channel output RVs $B^n {\stackrel{\triangle}{=}} \{B_i: i=0, \ldots, n\}$ or both, we characterize the sets of channel input distributions, which maximize directed information defined by $ I(A^n \rightarrow B^n) {\stackrel{\triangle}{=}} \sum_{i=0}^n I(A^i;B_i|B^{i-1}) $ and we derive the corresponding expressions, called "characterizations of Finite Transmission Feedback Information (FTFI) capacity". The main theorems state that optimal channel input distributions occur in subsets ${\cal P}_{[0,n]}^{CI}\subseteq {\cal P}_{[0,n]} {\stackrel{\triangle}{=}}\big\{ {\bf P}_{A_i|A^{i-1}, B^{i-1}}: i=0, \ldots, n\big\}$, which satisfy conditional independence on past information. We derive similar characterizations, when general transmission cost constraints are imposed. Moreover, we also show that the structural properties apply to general nonlinear and linear autoregressive channel models defined by discrete-time recursions on general alphabet spaces, and driven by arbitrary distributed noise processes. We derive these structural properties by invoking stochastic optimal control theory and variational equalities of directed information, to identify tight upper bounds on $I(A^n \rightarrow B^n)$, which are achievable over subsets of conditional distributions ${\cal P}_{[0,n]}^{CI} \subseteq {\cal P}_{[0,n]}$, which satisfy conditional independence and they are specified by the dependence of channel distributions and transmission cost functions on inputs and output symbols. We apply the characterizations to recursive Multiple Input Multiple Output Gaussian Linear Channel Models with limited memory and we show a separation principle between the computation of the elements of the optimal strategies.

preprint2016arXiv

Optimal Signaling for Secure Communications over Gaussian MIMO Wiretap Channels

Optimal signalling over the Gaussian MIMO wire-tap channel is studied under the total transmit power constraint. A closed-form solution for an optimal transmit covariance matrix is obtained when the channel is strictly degraded. In combination with the rank-1 solution, this provides the complete characterization of the optimal covariance for the case of two transmit antennas. The cases of weak eavesdropper and high SNR are considered. It is shown that the optimal covariance does not converge to a scaled identity in the high-SNR regime. Necessary optimality conditions and a tight upper bound on the rank of an optimal covariance matrix are established for the general case, along with a lower bound to the secrecy capacity, which is tight in a number of scenarios.

preprint2016arXiv

Rank-Deficient Solutions for Optimal Signaling over Wiretap MIMO Channels

Capacity-achieving signaling strategies for the Gaussian wiretap MIMO channel are investigated without the degradedness assumption. In addition to known solutions, a number of new rank-deficient solutions for the optimal transmit covariance matrix are obtained. The case of a weak eavesdropper is considered in detail and the optimal covariance is established in an explicit, closed form with no extra assumptions. This provides lower and upper bounds to the secrecy capacity in the general case with a bounded gap, which are tight for a weak eavesdropper or/and low SNR. Closed form solutions are also obtained for isotropic and omnidirectional eavesdroppers, based on which lower and upper bounds to the secrecy capacity are established in the general case. Sufficient and necessary conditions for optimality of 3 popular transmission techniques, namely the zero-forcing (ZF), the standard water-filling (WF) over the channel eigenmodes and the isotropic signaling (IS), are established for the MIMO wiretap channel. These solutions are appealing due to their lower complexity. In particular, no wiretap codes are needed for the ZF transmission, and no precoding or feedback is needed for the isotropic signaling.

preprint2016arXiv

Sequential Necessary and Sufficient Conditions for Capacity Achieving Distributions of Channels with Memory and Feedback

We derive sequential necessary and sufficient conditions for any channel input conditional distribution ${\cal P}_{0,n}\triangleq\{P_{X_t|X^{t-1},Y^{t-1}}:~t=0,\ldots,n\}$ to maximize the finite-time horizon directed information defined by $$C^{FB}_{X^n \rightarrow Y^n} \triangleq \sup_{{\cal P}_{0,n}} I(X^n\rightarrow{Y^n}),~~~ I(X^n \rightarrow Y^n) =\sum_{t=0}^n{I}(X^t;Y_t|Y^{t-1})$$ for channel distributions $\{P_{Y_t|Y^{t-1},X_t}:~t=0,\ldots,n\}$ and $\{P_{Y_t|Y_{t-M}^{t-1},X_t}:~t=0,\ldots,n\}$, where $Y^t\triangleq\{Y_0,\ldots,Y_t\}$ and $X^t\triangleq\{X_0,\ldots,X_t\}$ are the channel input and output random processes, and $M$ is a finite nonnegative integer. \noi We apply the necessary and sufficient conditions to application examples of time-varying channels with memory and we derive recursive closed form expressions of the optimal distributions, which maximize the finite-time horizon directed information. Further, we derive the feedback capacity from the asymptotic properties of the optimal distributions by investigating the limit $$C_{X^\infty \rightarrow Y^\infty}^{FB} \triangleq \lim_{n \longrightarrow \infty} \frac{1}{n+1} C_{X^n \rightarrow Y^n}^{FB}$$ without any á priori assumptions, such as, stationarity, ergodicity or irreducibility of the channel distribution. The necessary and sufficient conditions can be easily extended to a variety of channels with memory, beyond the ones considered in this paper.

preprint2015arXiv

An Algorithm for Global Maximization of Secrecy Rates in Gaussian MIMO Wiretap Channels

Optimal signaling for secrecy rate maximization in Gaussian MIMO wiretap channels is considered. While this channel has attracted a significant attention recently and a number of results have been obtained, including the proof of the optimality of Gaussian signalling, an optimal transmit covariance matrix is known for some special cases only and the general case remains an open problem. An iterative custom-made algorithm to find a globally-optimal transmit covariance matrix in the general case is developed in this paper, with guaranteed convergence to a \textit{global} optimum. While the original optimization problem is not convex and hence difficult to solve, its minimax reformulation can be solved via the convex optimization tools, which is exploited here. The proposed algorithm is based on the barrier method extended to deal with a minimax problem at hand. Its convergence to a global optimum is proved for the general case (degraded or not) and a bound for the optimality gap is given for each step of the barrier method. The performance of the algorithm is demonstrated via numerical examples. In particular, 20 to 40 Newton steps are already sufficient to solve the sufficient optimality conditions with very high precision (up to the machine precision level), even for large systems. Even fewer steps are required if the secrecy capacity is the only quantity of interest. The algorithm can be significantly simplified for the degraded channel case and can also be adopted to include the per-antenna power constraints (instead or in addition to the total power constraint). It also solves the dual problem of minimizing the total power subject to the secrecy rate constraint.

preprint2015arXiv

Capacity of Binary State Symmetric Channel with and without Feedback and Transmission Cost

We consider a unit memory channel, called Binary State Symmetric Channel (BSSC), in which the channel state is the modulo2 addition of the current channel input and the previous channel output. We derive closed form expressions for the capacity and corresponding channel input distribution, of this BSSC with and without feedback and transmission cost. We also show that the capacity of the BSSC is not increased by feedback, and it is achieved by a first order symmetric Markov process.

preprint2015arXiv

Infinite Horizon Average Cost Dynamic Programming Subject to Total Variation Distance Ambiguity

We analyze the infinite horizon minimax average cost Markov Control Model (MCM), for a class of controlled process conditional distributions, which belong to a ball, with respect to total variation distance metric, centered at a known nominal controlled conditional distribution with radius $R\in [0,2]$, in which the minimization is over the control strategies and the maximization is over conditional distributions. Upon performing the maximization, a dynamic programming equation is obtained which includes, in addition to the standard terms, the oscillator semi-norm of the cost-to-go. First, the dynamic programming equation is analyzed for finite state and control spaces. We show that if the nominal controlled process distribution is irreducible, then for every stationary Markov control policy the maximizing conditional distribution of the controlled process is also irreducible for $R \in [0,R_{max}]$. Second, the generalized dynamic programming is analyzed for Borel spaces. We derive necessary and sufficient conditions for any control strategy to be optimal. Through our analysis, new dynamic programming equations and new policy iteration algorithms are derived. The main feature of the new policy iteration algorithms (which are applied for finite alphabet spaces) is that the policy evaluation and policy improvement steps are performed by using the maximizing conditional distribution, which is obtained via a water filling solution. Finally, the application of the new dynamic programming equations and the corresponding policy iteration algorithms are shown via illustrative examples.

preprint2014arXiv

Applications of Information Nonanticipative Rate Distortion Function

The objective of this paper is to further investigate various applications of information Nonanticipative Rate Distortion Function (NRDF) by discussing two working examples, the Binary Symmetric Markov Source with parameter $p$ (BSMS($p$)) with Hamming distance distortion, and the multidimensional partially observed Gaussian-Markov source. For the BSMS($p$), we give the solution to the NRDF, and we use it to compute the Rate Loss (RL) of causal codes with respect to noncausal codes. For the multidimensional Gaussian-Markov source, we give the solution to the NRDF, we show its operational meaning via joint source-channel matching over a vector of parallel Gaussian channels, and we compute the RL of causal and zero-delay codes with respect to noncausal codes.

preprint2014arXiv

Approximation of Markov Processes by Lower Dimensional Processes via Total Variation Metrics

The aim of this paper is to approximate a finite-state Markov process by another process with fewer states, called herein the approximating process. The approximation problem is formulated using two different methods. The first method, utilizes the total variation distance to discriminate the transition probabilities of a high dimensional Markov process and a reduced order Markov process. The approximation is obtained by optimizing a linear functional defined in terms of transition probabilities of the reduced order Markov process over a total variation distance constraint. The transition probabilities of the approximated Markov process are given by a water-filling solution. The second method, utilizes total variation distance to discriminate the invariant probability of a Markov process and that of the approximating process. The approximation is obtained via two alternative formulations: (a) maximizing a functional of the occupancy distribution of the Markov process, and (b) maximizing the entropy of the approximating process invariant probability. For both formulations, once the reduced invariant probability is obtained, which does not correspond to a Markov process, a further approximation by a Markov process is proposed which minimizes the Kullback-Leibler divergence. These approximations are given by water-filling solutions. Finally, the theoretical results of both methods are applied to specific examples to illustrate the methodology, and the water-filling behavior of the approximations.

preprint2014arXiv

Dynamic Programming Subject to Total Variation Distance Ambiguity

The aim of this paper is to address optimality of stochastic control strategies via dynamic programming subject to total variation distance ambiguity on the conditional distribution of the controlled process. We formulate the stochastic control problem using minimax theory, in which the control minimizes the pay-off while the conditional distribution, from the total variation distance set, maximizes it. First, we investigate the maximization of a linear functional on the space of probability measures on abstract spaces, among those probability measures which are within a total variation distance from a nominal probability measure, and then we give the maximizing probability measure in closed form. Second, we utilize the solution of the maximization to solve minimax stochastic control with deterministic control strategies, under a Markovian and a non-Markovian assumption, on the conditional distributions of the controlled process. The results of this part include: 1) Minimax optimization subject to total variation distance ambiguity constraint; 2) new dynamic programming recursions, which involve the oscillator seminorm of the value function, in addition to the standard terms; 3) new infinite horizon discounted dynamic programming equation, the associated contractive property, and a new policy iteration algorithm. Finally, we provide illustrative examples for both the finite and infinite horizon cases. For the infinite horizon case we invoke the new policy iteration algorithm to compute the optimal strategies.

preprint2014arXiv

Nonanticipative Rate Distortion Function and Filtering Theory: A weak Convergence Approach

In this paper the relation between nonanticipative rate distortion function (RDF) and Bayesian filtering theory is further investigated on general Polish spaces. The relation is established via an optimization on the space of conditional distributions of the so-called directed information subject to fidelity constraints. Existence of the optimal reproduction distribution of the nonanticipative RDF is shown using the topology of weak convergence of probability measures. Subsequently, we use the solution of the nonanticipative RDF to present the realization of a multidimensional partially observable source over a scalar Gaussian channel. We show that linear encoders are optimal, establishing joint source-channel coding in real-time.

preprint2014arXiv

Source-Channel Matching for Sources with Memory

In this paper we analyze the probabilistic matching of sources with memory to channels with memory so that symbol-by-symbol code with memory without anticipation are optimal, with respect to an average distortion and excess distortion probability. We show achievability of such a symbolby- symbol code with memory without anticipation, and we show matching for the Binary Symmetric Markov source (BSMS(p)) over a first-order symmetric channel with a cost constraint.

preprint2013arXiv

Centralized Versus Decentralized Team Games of Distributed Stochastic Differential Decision Systems with Noiseless Information Structures-Part I: General Theory

Decentralized optimization of distributed stochastic differential systems has been an active area of research for over half a century. Its formulation utilizing static team and person-by-person optimality criteria is well investigated. However, the results have not been generalized to nonlinear distributed stochastic differential systems possibly due to technical difficulties inherent with decentralized decision strategies. In this first part of the two-part paper, we derive team optimality and person-by-person optimality conditions for distributed stochastic differential systems with different information structures. The optimality conditions are given in terms of a Hamiltonian system of equations described by a system of coupled backward and forward stochastic differential equations and a conditional Hamiltonian, under both regular and relaxed strategies. Our methodology is based on the semi martingale representation theorem and variational methods. Throughout the presentation we discuss similarities to optimality conditions of centralized decision making.

preprint2013arXiv

Centralized Versus Decentralized Team Games of Distributed Stochastic Differential Decision Systems with Noiseless Information Structures-Part II: Applications

In this second part of our two-part paper, we invoke the stochastic maximum principle, conditional Hamiltonian and the coupled backward-forward stochastic differential equations of the first part [1] to derive team optimal decentralized strategies for distributed stochastic differential systems with noiseless information structures. We present examples of such team games of nonlinear as well as linear quadratic forms. In some cases we obtain closed form expressions of the optimal decentralized strategies. Through the examples, we illustrate the effect of information signaling among the decision makers in reducing the computational complexity of optimal decentralized decision strategies.

preprint2013arXiv

Dynamic Team Theory of Stochastic Differential Decision Systems with Decentralized Noiseless Feedback Information Structures via Girsanov's Measure Transformation

In this paper we generalized static team theory to dynamic team theory, in the context of stochastic differential decision system with decentralized noiseless feedback information structures. We apply Girsanov's theorem to transformed the initial stochastic dynamic team problem to an equivalent team problem, under a reference probability space, with state process and information structures independent of any of the team decisions. Subsequently, we show, under certain conditions, that continuous-time and discrete-time stochastic dynamic team problems, can be transformed to equivalent static team problems, although computing the optimal team strategies using this method might be computational intensive. Therefore, we propose an alternative method, by deriving team and Person-by-Person (PbP) optimality conditions, via the stochastic Pontryagin's maximum principle, consisting of forward and backward stochastic differential equations, and a set of conditional variational Hamiltonians with respect to the information structures of the team members. Finally, we relate the backward stochastic differential equation to the value process of the stochastic team problem.

preprint2013arXiv

Dynamic Team Theory of Stochastic Differential Decision Systems with Decentralized Noisy Information Structures via Girsanov's Measure Transformation

In this paper, we present two methods which generalize static team theory to dynamic team theory, in the context of continuous-time stochastic nonlinear differential decentralized decision systems, with relaxed strategies, which are measurable to different noisy information structures. For both methods we apply Girsanov's measure transformation to obtain an equivalent dynamic team problem under a reference probability measure, so that the observations and information structures available for decisions, are not affected by any of the team decisions. The first method is based on function space integration with respect to products of Wiener measures, and generalizes Witsenhausen's [1] definition of equivalence between discrete-time static and dynamic team problems. The second method is based on stochastic Pontryagin's maximum principle. The team optimality conditions are given by a "Hamiltonian System" consisting of forward and backward stochastic differential equations, and a conditional variational Hamiltonian with respect to the information structure of each team member, expressed under the initial and a reference probability space via Girsanov's measure transformation. Under global convexity conditions, we show that that PbP optimality implies team optimality. In addition, we also show existence of team and PbP optimal relaxed decentralized strategies (conditional distributions), in the weak$^*$ sense, without imposing convexity on the action spaces of the team members. Moreover, using the embedding of regular strategies into relaxed strategies, we also obtain team and PbP optimality conditions for regular team strategies, which are measurable functions of decentralized information structures, and we use the Krein-Millman theorem to show realizability of relaxed strategies by regular strategies.

preprint2013arXiv

Extremum Problems with Total Variation Distance and their Applications

The aim of this paper is to investigate extremum problems with pay-off being the total variational distance metric defined on the space of probability measures, subject to linear functional constraints on the space of probability measures, and vice-versa; that is, with the roles of total variational metric and linear functional interchanged. Utilizing concepts from signed measures, the extremum probability measures of such problems are obtained in closed form, by identifying the partition of the support set and the mass of these extremum measures on the partition. The results are derived for abstract spaces; specifically, complete separable metric spaces known as Polish spaces, while the high level ideas are also discussed for denumerable spaces endowed with the discrete topology. These extremum problems often arise in many areas, such as, approximating a family of probability distributions by a given probability distribution, maximizing or minimizing entropy subject to total variational distance metric constraints, quantifying uncertainty of probability distributions by total variational distance metric, stochastic minimax control, and in many problems of information, decision theory, and minimax theory.

preprint2013arXiv

Nonanticipative Rate Distortion Function and Relations to Filtering Theory

The relation between nonanticipative Rate Distortion Function (RDF) and filtering theory is discussed on abstract spaces. The relation is established by imposing a realizability constraint on the reconstruction conditional distribution of the classical RDF. Existence of the extremum solution of the nonanticipative RDF is shown using weak$^*$-convergence on appropriate topology. The extremum reconstruction conditional distribution is derived in closed form, for the case of stationary processes. The realization of the reconstruction conditional distribution which achieves the infimum of the nonanticipative RDF is described. Finally, an example is presented to illustrate the concepts.

preprint2013arXiv

Nonanticipative Rate Distortion Function for General Source-Channel Matching

In this paper we invoke a nonanticipative information Rate Distortion Function (RDF) for sources with memory, and we analyze its importance in probabilistic matching of the source to the channel so that transmission of a symbol-by-symbol code with memory without anticipation is optimal, with respect to an average distortion and excess distortion probability. We show achievability of the symbol-by-symbol code with memory without anticipation, and we evaluate the probabilistic performance of the code for a Markov source.

preprint2013arXiv

On the relation of nonanticipative rate distortion function and filtering theory

In this paper the relation between nonanticipative rate distortion function (RDF) and Bayesian filtering theory is investigated using the topology of weak convergence of probability measures on Polish spaces. The relation is established via an optimization on the space of conditional distributions of the so-called directed information subject to fidelity constraints. Existence of the optimal reproduction distribution of the nonanticipative RDF is shown, while the optimal nonanticipative reproduction conditional distribution for stationary processes is derived in closed form. The realization procedure of nonanticipative RDF which is equivalent to joint-source channel matching for symbol-by-symbol transmission is described, while an example is introduced to illustrate the concepts.

preprint2013arXiv

Optimal Nonstationary Reproduction Distribution for Nonanticipative RDF on Abstract Alphabets

In this paper we introduce a definition for nonanticipative Rate Distortion Function (RDF) on abstract alphabets, and we invoke weak convergence of probability measures to show various of its properties, such as, existence of the optimal reproduction conditional distribution, compactness of the fidelity set, lower semicontinuity of the RDF functional, etc. Further, we derive the closed form expression of the optimal nonstationary reproduction distribution. This expression is computed recursively backward in time. Throughout the paper we point out an operational meaning of the nonanticipative RDF by recalling the coding theorem derive in \cite{tatikonda2000}, and we state relations to Gorbunov-Pinsker's nonanticipatory $ε-$entropy \cite{gorbunov-pinsker}.

preprint2013arXiv

Rate Distortion Function for a Class of Relative Entropy Sources

This paper deals with rate distortion or source coding with fidelity criterion, in measure spaces, for a class of source distributions. The class of source distributions is described by a relative entropy constraint set between the true and a nominal distribution. The rate distortion problem for the class is thus formulated and solved using minimax strategies, which result in robust source coding with fidelity criterion. It is shown that minimax and maxmin strategies can be computed explicitly, and they are generalizations of the classical solution. Finally, for discrete memoryless uncertain sources, the rate distortion theorem is stated for the class omitting the derivations while the converse is derived.

preprint2013arXiv

Team and Person-by-Person Optimality Conditions of Differential Decision Systems

In this paper, we derive team and person-by-person optimality conditions for distributed differential decision systems with different or decentralized information structures. The necessary conditions of optimality are given in terms of Hamiltonian system of equations consisting of a coupled backward and forward differential equations and a Hamiltonian projected onto the subspace generated by the decentralized information structures. Under certain global convexity conditions it is shown that the optimality conitions are also sufficient.

preprint2013arXiv

Team Games Optimality Conditions of Distributed Stochastic Differential Decision Systems with Decentralized Noisy Information Structures

We consider a team game reward, and we derive a stochastic Pontryagin's maximum principle for distributed stochastic differential systems with decentralized noisy information structures. Our methodology utilizes the semi martingale representation theorem, variational methods, and backward stochastic differential equations. Furthermore, we derive necessary and sufficient optimality conditions that characterize team and person-by-person optimality of decentralized strategies. Finally, we apply the stochastic maximum principle to several examples from the application areas of communications, filtering and control.

preprint2013arXiv

Variable Length Lossless Coding for Variational Distance Class: An Optimal Merging Algorithm

In this paper we consider lossless source coding for a class of sources specified by the total variational distance ball centred at a fixed nominal probability distribution. The objective is to find a minimax average length source code, where the minimizers are the codeword lengths -- real numbers for arithmetic or Shannon codes -- while the maximizers are the source distributions from the total variational distance ball. Firstly, we examine the maximization of the average codeword length by converting it into an equivalent optimization problem, and we give the optimal codeword lenghts via a waterfilling solution. Secondly, we show that the equivalent optimization problem can be solved via an optimal partition of the source alphabet, and re-normalization and merging of the fixed nominal probabilities. For the computation of the optimal codeword lengths we also develop a fast algorithm with a computational complexity of order ${\cal O}(n)$.

preprint2013arXiv

Variational Equalities of Directed Information and Applications

In this paper we introduce two variational equalities of directed information, which are analogous to those of mutual information employed in the Blahut-Arimoto Algorithm (BAA). Subsequently, we introduce nonanticipative Rate Distortion Function (RDF) ${R}^{na}_{0,n}(D)$ defined via directed information introduced in [1], and we establish its equivalence to Gorbunov-Pinsker's nonanticipatory $ε$-entropy $R^{\varepsilon}_{0,n}(D)$. By invoking certain results we first establish existence of the infimizing reproduction distribution for ${R}^{na}_{0,n}(D)$, and then we give its implicit form for the stationary case. Finally, we utilize one of the variational equalities and the closed form expression of the optimal reproduction distribution to provide an algorithm for the computation of ${R}^{na}_{0,n}(D)$.

preprint2012arXiv

Causal Rate Distortion Function on Abstract Alphabets: Optimal Reconstruction and Properties

A causal rate distortion function with a general fidelity criterion is formulated on abstract alphabets and a coding theorem is derived. Existence of the minimizing kernel is shown using the topology of weak convergence of probability measures. The optimal reconstruction kernel is derived, which is causal, and certain properties of the causal rate distortion function are presented.

preprint2012arXiv

Directed Information on Abstract spaces: Properties and Extremum Problems

This paper describes a framework in which directed information is defined on abstract spaces. The framework is employed to derive properties of directed information such as convexity, concavity, lower semicontinuity, by using the topology of weak convergence of probability measures on Polish spaces. Two extremum problems of directed information related to capacity of channels with memory and feedback, and non-anticipative and sequential rate distortion are analyzed showing existence of maximizing and minimizing distributions, respectively.

preprint2012arXiv

Optimal Merging Algorithms for Lossless Codes with Generalized Criteria

This paper presents lossless prefix codes optimized with respect to a pay-off criterion consisting of a convex combination of maximum codeword length and average codeword length. The optimal codeword lengths obtained are based on a new coding algorithm which transforms the initial source probability vector into a new probability vector according to a merging rule. The coding algorithm is equivalent to a partition of the source alphabet into disjoint sets on which a new transformed probability vector is defined as a function of the initial source probability vector and a scalar parameter. The pay-off criterion considered encompasses a trade-off between maximum and average codeword length; it is related to a pay-off criterion consisting of a convex combination of average codeword length and average of an exponential function of the codeword length, and to an average codeword length pay-off criterion subject to a limited length constraint. A special case of the first related pay-off is connected to coding problems involving source probability uncertainty and codeword overflow probability, while the second related pay-off compliments limited length Huffman coding algorithms.

preprint2012arXiv

Realizable Rate Distortion Function and Bayesian FIltering Theory

The relation between rate distortion function (RDF) and Bayesian filtering theory is discussed. The relation is established by imposing a causal or realizability constraint on the reconstruction conditional distribution of the RDF, leading to the definition of a causal RDF. Existence of the optimal reconstruction distribution of the causal RDF is shown using the topology of weak convergence of probability measures. The optimal non-stationary causal reproduction conditional distribution of the causal RDF is derived in closed form; it is given by a set of recursive equations which are computed backward in time. The realization of causal RDF is described via the source-channel matching approach, while an example is briefly discussed to illustrate the concepts.

preprint2011arXiv

Causal Rate Distortion Function on Abstract Alphabets and Optimal Reconstruction Kernel

A Causal rate distortion function with a general fidelity criterion is formulated on abstract alphabets and the optimal reconstruction kernel is derived, which consists of a product of causal kernels. In the process, general abstract spaces are introduced to show existence of the minimizing kernel using weak*-convergence. Certain properties of the causal rate distortion function are presented.

preprint2011arXiv

Compound Outage Probability and Capacity of a Class of Fading MIMO Channels with Channel Distribution Uncertainty

Outage probability and capacity of a class of block-fading MIMO channels are considered with partial channel distribution information. Specifically, the channel or its distribution are not known but the latter is known to belong to a class of distributions where each member is within a certain distance (uncertainty) from a nominal distribution. Relative entropy is used as a measure of distance between distributions. Compound outage probability defined as min (over the transmit signal distribution) -max (over the channel distribution class) outage probability is introduced and investigated. This generalizes the standard outage probability to the case of partial channel distribution information. Compound outage probability characterization (via one-dimensional convex optimization), its properties and approximations are given. It is shown to have two-regime behavior: when the nominal outage probability decreases (e.g. by increasing the SNR), the compound outage first decreases linearly down to a certain threshold (related to relative entropy distance) and then only logarithmically (i.e. very slowly), so that no significant further decrease is possible. The compound outage depends on the relative entropy distance and the nominal outage only, all other details (nominal fading and noise distributions) being irrelevant. The transmit signal distribution optimized for the nominal channel distribution is shown to be also optimal for the whole class of distributions. The effect of swapping the distributions in relative entropy is investigated and an error floor effect is established. The compound outage probability under Lp distance constraint is also investigated. The obtained results hold for a generic channel model (arbitrary nominal fading and noise distributions).

preprint2011arXiv

Lossless Coding with Generalised Criteria

This paper presents prefix codes which minimize various criteria constructed as a convex combination of maximum codeword length and average codeword length or maximum redundancy and average redundancy, including a convex combination of the average of an exponential function of the codeword length and the average redundancy. This framework encompasses as a special case several criteria previously investigated in the literature, while relations to universal coding is discussed. The coding algorithm derived is parametric resulting in re-adjusting the initial source probabilities via a weighted probability vector according to a merging rule. The level of desirable merging has implication in applications where the maximum codeword length is bounded.

preprint2011arXiv

Minimum Redundancy Coding for Uncertain Sources

Consider the set of source distributions within a fixed maximum relative entropy with respect to a given nominal distribution. Lossless source coding over this relative entropy ball can be approached in more than one way. A problem previously considered is finding a minimax average length source code. The minimizing players are the codeword lengths --- real numbers for arithmetic codes, integers for prefix codes --- while the maximizing players are the uncertain source distributions. Another traditional minimizing objective is the first one considered here, maximum (average) redundancy. This problem reduces to an extension of an exponential Huffman objective treated in the literature but heretofore without direct practical application. In addition to these, this paper examines the related problem of maximal minimax pointwise redundancy and the problem considered by Gawrychowski and Gagie, which, for a sufficiently small relative entropy ball, is equivalent to minimax redundancy. One can consider both Shannon-like coding based on optimal real number ("ideal") codeword lengths and a Huffman-like optimal prefix coding.