Journals:
C.D. Charalambous and C. Kourtellaris and S. Loyka, “Capacity Achieving Distributions and Separation Principle for Feedback Channels with Memory: The LQG Theory of Directed Information,” IEEE Transactions on Information Theory, vol.64, no.9, pages 6384-6418, September 2018
Abstract
A method is developed to realize optimal channel input conditional distributions, which maximize the finite transmission feedback information (FTFI) capacity, often called n -block length feedback capacity, by information lossless randomized strategies. The method is applied to compute closed form expressions for the FTFI capacity and feedback capacity, of nonstationary, nonergodic, unstable, multiple input multiple output Gaussian channels with memory on past channel outputs, subject to average transmission cost constraints of quadratic form in the channel inputs and outputs. It is shown that randomized strategies decompose into two orthogonal parts-an deterministic part, which controls the channel output process, and an innovation part, which transmits new information over the channel. Then a separation principle is shown between the computation of the optimal deterministic part and the random part of the optimal randomized strategies. Finally, the ergodic theory of linear-quadratic-Gaussian stochastic optimal control theory, is applied to identify sufficient conditions, expressed in terms of solutions to matrix difference and algebraic Riccati equations, so that the optimal control part of randomized strategies induces asymptotic stationarity and ergodicity, and feedback capacity is characterized by the per unit time limit of the FTFI capacity. The method reveals an interaction of the control and the information transmission parts of the optimal randomized strategies, and that whether feedback increases capacity, is directly related to the channel parameters and the transmission cost function, through the solutions of the matrix Riccati equations. For unstable channels, it is shown that feedback capacity exists and it is strictly positive, provided the power exceeds a critical threshold.
C. Kourtellaris and C.D. Charalambous, “Information Structures of Capacity Achieving Distributions for Feedback Channels with Memory and Transmission Cost: Stochastic Optimal Control & Variational Equalities,” IEEE Transactions on Information Theory, Vol.64, No.7, pp.4962-4992, July, 2018
Abstract
The information structures of the optimal channel input distributions P [0,n] = Δ {P Ai|Ai-1, Bi-1 : i = 0,1,..., n}, which correspond to the extremum problem of feedback capacity C An→Bn FB = Δ sup P [0,n] Σ i=0 n I(A i ;B i |B i-1 ) are identified, for any class of channel distributions {P Bi|Bi-1,Ai : i = 0,1,...,n} and {P Bi|B i-M i-1 ,Ai : i = 0,1,...,n}, where B n = Δ {B j : j = 0,1,...,n} are the channel output RVs, A n = Δ {A j : j = 0,1,...,n} are the channel inputs RVs, and M is a finite nonnegative integer. The methodology utilizes stochastic optimal control theory, to identify the control process, the controlled process, and a variational equality of directed information, to derive upper bounds on I(A n → B n )= Δ Σ i=0 n I(A i ;B i |B i-1 ), which are achievable over specific subsets of P [0,n] , which satisfy conditional independence. The main theorem states, that for any channel with memory M, the optimal channel input conditional distribution occur in the subset P [0,n] = Δ {P Ai|B i-M i-1 : i = 1,...,n} ⊂ P [0,n] , and the corresponding extremum problem simplifies to the following characterization C An→Bn FB,M = Δ sup P [0,n] Σ i=0 n I(A i ;B i |B i-M i-1 ).
Photios Stavrou and C.D. Charalambous and C. Kourtellaris, “Sequential Necessary and Sufficient Conditions for Capacity Achieving Distributions of Channels with Memory and Feedback,” IEEE Transactions on Information Theory, vol.63, no.11, pp.7095-7115, July 2017
Abstract
We derive sequential necessary and sufficient conditions for any channel input conditional distribution P 0,n =Δ {P Xt|Xt-1,Yt-1 : t = 0, ..., n} to maximize the finite-time horizon directed information defined by C Xn→Yn FB =Δ sup P0,n I(X n → Y n ), where I(X n → Y n ) = Σ t=0 n I(X t ; Y t |Y t-1 ), for channel distributions {P Yt |Y t-1 ,Xt: t = 0, ..., n} and {P Yt |Y t-M t-1 ,X t : t = 0, ..., n}, where Y t =Δ {Y -1 , Y 0 , ..., Y t } and X t =Δ {X 0 , ..., X t } are the channel input and output random processes, and M is a finite non-negative integer. We apply the necessary and sufficient conditions to application examples of time-varying channels with memory to derive recursive closed form expressions of the optimal distributions, which maximize the finite-time horizon directed information. Furthermore, we derive the feedback capacity from the asymptotic properties of the optimal distributions by investigating the limit C X∞→Y∞ FB =Δ lim n→∞ (1/(n + 1))C Xn→Yn FB without any á priori assumptions, such as stationarity, ergodicity, or irreducibility of the channel distribution. The framework based on sequential necessary and sufficient conditions can be easily applied to a variety of channels with memory, beyond the ones considered in this paper.
C.D. Charalambous and C. Kourtellaris and I. Tzortzis, “Information Transfer of Control Strategies: Dualities of Stochastic Optimal Control Theory and Feedback Capacity of Information Theory,” IEEE Transactions on Automatic Control, vol.62, no.10, pp.5010-5025, November 2017
Abstract
The control-coding capacity of stochastic control systems is introduced, and its operational meaning is established using randomized control strategies, which simultaneously control output processes encode information, and communicate information from control processes to output processes. The control-coding capacity is the analog Shannon's coding-capacity of noisy channels. Furthermore, duality relations to stochastic optimal control problems with deterministic and randomized control strategies are identified including the following. First, extremum problems of stochastic optimal control with directed information payoff are equivalent to feedback capacity problems of information theory, in which the control system act as a communication channel. Second, for Gaussian linear decision models with average quadratic constraints, it is shown that optimal randomized strategies are Gaussian, and decompose into a deterministic part and a random part. The deterministic part is precisely the optimal strategy of the linear quadratic Gaussian stochastic optimal control problem, whereas the random part is the solution of an water-filling information transmission problem that encodes information, which is estimated by a decoder.
Conferences:
C. Kourtellaris and C.D. Charalambous and S. Loyka, “New Formulas for Ergodic Feedback Capacity of AGN Channels Driven by Stable and Unstable Autoregressive Noise,” in Proceedings of the 2020 IEEE International Symposium on Information Theory, pages-6, Los Angeles, USA, July 21-26, 2020
Abstract
In this paper we characterize the feedback capacity of Additive Gaussian Noise (AGN) channels driven by stable and unstable autoregressive noise, for time-invariant feedback codes (channel input distributions). For stable (resp. unstable) channel noise we identify necessary and sufficient conditions for the optimal input process to induce asymptotic stationarity and ergodicity of the channel output (resp. innovations) process. We call this the {\emph{ergodic feedback capacity}}. From our characterization follows the surprising result: for a time-invariant unit memory Gaussian autoregressive noise AR($c$), $c\in (-\infty,\infty)$, (i) feedback does not increase capacity for the region with $c\in (-1,1)$ and certain unstable $c$, and total transmit power $\kappa \in [0,\infty)$, and (ii) feedback increases capacity for the compliment of the region of values of $(c, \kappa)$, not covered in (i).
C. Kourtellaris and C.D. Charalambous and S. Loyka, “From Feedback Capacity to Tight Achievable Bounds without Feedback for AGN Channels with Stable and Unstable Autoregressive Noise,” in Proceedings of the 2020 IEEE International Symposium on Information Theory, pages-6, Los Angeles, USA, July 21-26, 2020
Abstract
In this paper we employ the information structures of optimal channel inputs of feedback capacity of additive Gaussian noise (AGN) channels, driven by stable and unstable autoregressive noise, to derive achievable rates for nofeedback capacity, and the corresponding channel input processes. The expressions of rates are derived using time-domain methods, they hold for stable and unstable noise, for all values of transmit power. The method avoids power spectral techniques and their limitations. The lower bounds are evaluated against the classical nonfeedback capacity obtained via water-filling frequency-domain techniques.
C.D. Charalambous, C. Kourtellaris and S. Loyka, “Control-Coding Capacity of Decision Models Driven by Correlated Noise and Gaussian Application Examples” in Proceedings of the 57th IEEE Conference on Decision Control, Miami, FL, USA, December, 2018
Abstract
We characterize the n -finite time feedback information (FTFI) control-coding capacity of decision models (DMs) driven by correlated noise. Under information stability the per unit limit, called control-coding (CC) capacity of the DM is operational, and analogous to Shannon's coding capacity of noisy communication channels, with the encoder replaced by a controller-encoder. We also analyze application examples of recursive linear DMs driven by correlated Gaussian noise, subject to an average cost constraint of quadratic form, called linear-quadratic Gaussian DMs (LQG-DMs). In one of the main theorems we show that the optimal randomized control strategies that achieve the n -FTFI CC capacity of the LQG-DMs, consist of multiple parts, that include control, estimation, and information transmission/signalling strategies, and that these strategies are determined using decentralized optimization techniques.
C.D. Charalambous and C. Kourtellaris and I. Tzortzis and S. Loyka, “The Decentralized Structures of Capacity Achieving Distributions of Channels with Memory and Feedback,” in 2018 International Zurich Seminar on Information and Communication, Zurich, Switzerland, February 21-23, 2018
Abstract
We consider extremum problems of feedback capacity for models with memory, subject to average cost constraints. We show the optimal input process that maximizes directed information consists of two parts, one responsible to control the output process, and one responsible to transmit new information that interact. Unlike [1], the decentralized structure of the optimal input process is demonstrated for Gaussian models with memory on past inputs and outputs. A semi-separation principle is shown that states, the optimal input process is generated from multiple strategies of a decentralized optimization problem, of control and information transmission. Further, it is shown that the derivation of directed information stability is semi-separable, in the sense that it separates into a statement about the ergodic properties of the stochastic optimal control problem with partial information, and a statement related to an information transmission problem.
C.D. Charalambous, C. Kourtellaris and T. Charalambous, “A General Coding Scheme of Signalling Gaussian Processes over Gaussian Decision Models” in Proceedings of the 19th IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), Kalamata, Greece, June 25-28, 2018
Abstract
In this paper, we transform the n-finite transmission feedback information (FTFI) capacity of unstable Gaussian decision models with memory on past outputs, subject to an average cost constraint of quadratic form derived in [1], into controllers-encoders-decoders that control the output process, encode a Gaussian process, reconstruct the Gaussian process via a mean-square error (MSE) decoder, and achieve the n-FTFI capacity. For a Gaussian RV message X N(0,σ 2 X) it is shown that the MSE decays according to E X-X' n n 2 = -2C 0, n (k)σ X 2 , K ∈ (k min ,∞), where C 0, n (k) is the n-FTFI capacity, and k min is the threshold on the power to ensure convergence.
C. Kourtellaris, C.D. Charalambous, “Two-Letter Capacity Formula for Channels with Memory and Feedback,” in Proceedings of the 2017 IEEE Information Theory Workshop, pages-6, November 6-10, Kaohsiung, Taiwan, 2017
Abstract
For a class of channels with unit memory on previous channels outputs, we identify necessary and sufficient conditions, to test whether the capacity achieving channel input distributions with feedback are time-invariant, and whether feedback capacity is characterized by a two-letter expression, similar to that of memoryless channels. The method is based on showing that a certain dynamic programming equation, which in general, is a nested optimization problem over the sequence of channel input distributions, reduces to a non-nested optimization problem. We then apply these conditions to derive a two-letter expression for the feedback capacity of the Binary State Symmetric Channel, which is evaluated explicitly. Further, we derive computationally efficient upper bounds on the probability of maximum likelihood decoding error in the finite-blocklength regime.
C.D. Charalambous, C. Kourtellaris, I. Tzortzis, S. Loyka, “The Capacity of Unstable Dynamical Systems-Interaction of Control and Information Transmission,” in Proceedings of the 2017 IEEE International Symposium on Information Theory, pages-6, June 25-30, Aachen, Germany, 2017
Abstract
Feedback capacity is extended beyond classical communication channels, to stochastic dynamical systems, which may correspond to unstable control systems or unstable communication channels, subject to average cost constraints of total power κ ∈ [0, ∞). It is shown that optimal conditional distributions or randomized strategies, have a dual role, to simultaneously control the output process and to encode information. The dual role is due to the interaction of control and information transmission; it states that encoders in communication channels operate as encoders-controllers, while controllers in control systems operate as controllers-encoders. The concepts are illustrated through the analysis of Gaussian control systems with randomized strategies, which are equivalent to Additive Gaussian Noise channels, Stable or Unstable, with arbitrary memory on past outputs, with an average constraint of quadratic form. It is shown that such unstable dynamical systems have Control-Coding Capacity which is operational, precisely as in Shannon's operational definition. However, the control-coding capacity is zero, unless the power κ allocated to the system, exceeds a threshold K min , where K min is the minimum cost of ensuring asymptotic stability and ergodicity. The excess power κ - K min is turned into an achievable rate of information transmission over the dynamical system.
Photios Stavrou and C.D. Charalambous and C. Kourtellaris, “Sequential Necessary and Sufficient Conditions for Optimal Channel Input Distributions of Channels with Memory and Feedback,” in Proceedings of the 2016 IEEE International Symposium on Information Theory, pages-6, July 2016
Abstract
We derive Sequential Necessary and Sufficient Conditions (SNSC) for any channel input distribution P 0,n =̑{P((X t )|X t-1 ,Y t-1 ):t=0,1,...,n} to maximize directed information for channel distributions of the form {P(Y t |Y t-M t-1 ,x t ): t=0,1,...,n} where X n =̑{X 0 ...,X n } , and Y n =̑{Y 0 ,...,Y n } are the channel input and output random variables, and M is nonnegative and finite. The results are obtained using the information structures of the optimal channel input distributions and the corresponding Finite Transmission Feedback Information (FTFI) capacity, convexity properties of directed information, and dynamic programming recursions. The conditions are applied to a finite alphabet channel with M = 1 to derive recursive closed form expressions for the optimal (nonstationary) distributions, which achieve the FTFI capacity. Further, ergodic feedback capacity is obtained in closed form, using the asymptotic properties of the optimal distributions. A numerical example is presented to illustrate the convergence properties of the per unit time limiting version of the FTFI capacity.
C. Kourtellaris and C.D. Charalambous, “Information Structures of Capacity Capacity Achieving Distributions for Channels with Memory and Feedback,” in Proceedings of the 2016 IEEE International Symposium on Information Theory, pages-6, July 2016
Abstract
The information structures of the optimal channel input distributions P [0,n] = Δ {P Ai|Ai-1, Bi-1 : i = 0,1,..., n}, which correspond to the extremum problem of feedback capacity C An→Bn FB = Δ sup P [0,n] Σ i=0 n I(A i ;B i |B i-1 ) are identified, for any class of channel distributions {P Bi|Bi-1,Ai : i = 0,1,...,n} and {P Bi|B i-M i-1 ,Ai : i = 0,1,...,n}, where B n = Δ {B j : j = 0,1,...,n} are the channel output RVs, A n = Δ {A j : j = 0,1,...,n} are the channel inputs RVs, and M is a finite nonnegative integer. The methodology utilizes stochastic optimal control theory, to identify the control process, the controlled process, and a variational equality of directed information, to derive upper bounds on I(A n → B n )= Δ Σ i=0 n I(A i ;B i |B i-1 ), which are achievable over specific subsets of P [0,n] , which satisfy conditional independence. The main theorem states, that for any channel with memory M, the optimal channel input conditional distribution occur in the subset P [0,n] = Δ {P Ai|B i-M i-1 : i = 1,...,n} ⊂ P [0,n] , and the corresponding extremum problem simplifies to the following characterization C An→Bn FB,M = Δ sup P [0,n] Σ i=0 n I(A i ;B i |B i-M i-1 ).
C. Kourtellaris, and C.D. Charalambous, “Capacity of Binary State Symmetric Channel with and without Feedback and Transmission Cost,” in Proceedings of the 2015 IEEE Information Theory Workshop, Jerusalem, Israel, April 26-May 1, 2015
Abstract
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 for the BSSC with and without feedback and transmission cost. We also show that the capacity of the BSSC, with or without feedback, is achieved by a first order symmetric Markov process.
X. Ma, C.D. Charalambous, S.M. Djouadi, S. Denic, “Encoder, Controller and Decoder Design of Jump Linear Systems over Jump Communication Systems,” in Proceedings of the 2013 American Control Conference, Washington, DC., USA, June 27-29, 2013
Abstract
In this work, we focus on the encoder, decoder, and controller design for jump linear systems over jump communication channels. The plant state information (PSI) and the channel state information (CSI) are assumed to be known at the both transmitter and the receiver ends. Both the PSI and the CSI are governed by a finite state Markov chain. The control and communication system is designed for the general vector observations over two different channels. One is assumed to be a vector channel, and the other one is a scalar channel. We design the optimal encoder, controller and decoder for both channels and the design scheme achieves the desired distortion. The rate distortions for both cases are also computed.
C.D. Charalambous, C. Kourtellaris, C. Hadjicostis, “Optimal Encoders Maximizing Directed Information of Channels with Memory and Feedback: Control and Dynamic Programming,” in Proceeding of the 18th World Congress of the International Federation of Automatic Control, Milano, Italy, August 28-September 2, 2011 (Invited Session)
Abstract
This paper is concerned with the stochastic control formulation of the capacity of channel with memory and feedback. The pay-off is the directed information from the source sequence to the channel output sequence, while the objective is to find the optimal encoder which maximizes this quantity. By invoking a change of measure technique this problem is reformulated in terms of controlling the a posteriori probability via the choice of the encoder strategies to maximize the directed information. A principle of optimality is derived and a dynamic programming equation is obtained which describe how the optimal encoder strategy should be selected. Further, a generalization of posterior matching scheme is presented.
C.D. Charalambous and C. Kourtellaris and C. Hadjicostis “Capacity of Channels with Memory and Feedback: Encoder Properties and Dynamic Programming,” in Proceeding of the 48th Allerton Conference on Communication, Control, Computing, Urbana Champaign, Illinois, September 29-October 1, 2010
Abstract
This paper is concerned with capacity formulae for channels with memory and feedback, properties of the capacity achieving encoder, and dynamic programming for designing optimal encoders. The source is general and the techniques discussed include outputs of dynamic systems whose conditional probability distribution depends causally on the channel output and encoder law. First, encoder strategies are identified to maximize directed information, between the source and the channel output. Second, various definitions of information capacity are introduced via directed information, and converse coding theorems are derived. Encoder properties which lead to a tight upper bound on achievable rates are identified. Specifically, it is shown that channel inputs need to be independent of past channel outputs. Third, the form of the capacity achieving encoder is described. The encoder law is a functional of the a posteriori distribution of the source output given a sequence of observable channel outputs. Here a generalization of the Posterior Matching Scheme to channels with memory and feedback is shown to hold. Finally, dynamic programming is discussed, identifying analogies with optimal stochastic control under partial information.
