The posterior matching scheme, for feedback encoding of a message point lying on the unit interval over memoryless channels, maximizes mutual information for an arbitrary number of channel uses. However, it in general does not always achieve any positive rate; so far, elaborate analyses have been required to show that it achieves any positive rate below capacity. More recent efforts have introduced a random "dither" shared by the encoder and decoder to the problem formulation, to simplify analyses and guarantee that the randomized scheme achieves any rate below capacity. Motivated by applications (e.g. human-computer interfaces) where (a) common randomness shared by the encoder and decoder may not be feasible and (b) the message point lies in a higher dimensional space, we focus here on the original formulation without common randomness, and use optimal transport theory to generalize the scheme for a message point in a higher dimensional space. By defining a stricter, almost sure, notion of message decoding, we use classical probabilistic techniques (e.g. change of measure and martingale convergence) to establish succinct necessary and sufficient conditions on when the message point can be recovered from infinite observations: Birkhoff ergodicity of a random process sequentially generated by the encoder. We also show a surprising "all or nothing" result: the same ergodicity condition is necessary and sufficient to achieve any rate below capacity. We provide applications of this message point framework in human-computer interfaces and multi-antenna communications.
Also, Shayevitz and Feder @cite_6 examined a randomized variant of the PM scheme with a random dither and were able to provide a much simpler proof of optimality over general memoryless channels when @math . That is, as compared to the proofs above which are restricted to non-sequential variants with a fixed number of messages and only apply to DMCs, Shayevitz and Feder @cite_6 used a random dither to provide a proof of optimality of the sequential, horizon-free, posterior matching scheme over general memoryless channels. These settings where the encoder and decoder share a common source of randomness by way of a dither, however, may be undesirable in some situations (e.g. when considering human involvement as described above).
@cite_6
2509220592 2964122424 2163608699 2074430484
Shayevitz and Feder proposed a capacity-achieving sequential transmission scheme for memoryless channels called posterior matching (PM). The proof of capacity achievability of PM is involved and requires invertibility of the PM kernel (also referred to as one-step invertibility). Recent work by the same authors provided a simpler proof but still requires PM kernel invertibility. Posterior matching (PM) is a sequential horizon-free feedback communication scheme introduced by the authors, who also provided a rather involved optimality proof, showing that it achieves capacity for a large class of memoryless channels. considered a non-sequential variation of PM with a fixed number of messages and a random decision-time, and gave a simpler proof establishing its optimality via a novel extrinsic Jensen–Shannon divergence argument. Another simpler optimality proof was given by Li and El Gamal, who considered a fixed-rate fixed block-length variation of PM with an additional randomization. Both these works also provided error exponent bounds. However, their simpler achievability proofs apply only to discrete memoryless channels, and are restricted to a non-sequential setup with a fixed number of messages. In this paper, we provide a short and transparent proof for the optimality of the fully sequential randomized horizon-free PM scheme over general memoryless channels. Borrowing the key randomization idea of Li and El Gamal, our proof is based on analyzing the random walk behavior of the shrinking posterior intervals induced by a reversed iterated function system decoder. For a memoryless channel, although feedback cannot increase capacity, it can reduce the complexity and or improve the error performance of a communication system. Recently, Shayevitz and Feder proposed the posterior matching scheme (PMS) which is a simple recursive transmission scheme that achieves the capacity of memoryless channels with feedback. Furthermore, Coleman provided a Lyapunov function approach to prove capacity achievability of the PMS. In this paper, we investigate a capacity-achieving PMS for the case of finite-state channels (FSCs). We first derive a single-letter expression for the capacity of the FSC with delayed output and state feedback by formulating the problem in a stochastic control framework. The resulting capacity expression can be evaluated using dynamic programming. We then propose a simple recursive PMS-like transmission scheme. To prove capacity achievability of the proposed PMS, we identify an appropriate Markov chain induced by the PMS. This paper re-visits Shayevitz & Feder's recent ‘Posterior Matching Scheme’, an explicit, dynamical system encoder for communication with feedback that treats the message as a point on the [0,1] line and achieves capacity on memo-ryless channels. It has two key properties that ensure that it maximizes mutual information at each step: (a) the encoder sequentially hands the decoder what is missing; and (b) the next input has the desired statistics. Motivated by brain-machine interface applications and multi-antenna communications, we consider developing dynamical system feedback encoders for scenarios when the message point lies in higher dimensions. We develop a necessary and sufficient condition — the Jacobian equation — for any dynamical system encoder that maximizes mutual information. In general, there are many solutions to this equation. We connect this to the Monge-Kantorovich Optimal Transportation Problem, which provides a framework to identify a unique solution suiting a specific purpose. We provide two examplar capacity-achieving solutions — for different purposes — for the multi-antenna Gaussian channel with feedback. This insight further elucidates an interesting relationship between interactive decision theory problems and the theory of optimal transportation.